4. All possible subset 문제

임의의 정수 N에 대해 {0,1,2,...,N-1}의 가능한 모든 부분 집합을 출력하라 recursive 전략과 container 자료를 쓰면 편하게 되는 것 같다. recursive에서 분기를 2개로 나눠서 call하면 된다. 이런 문제의 경우 2^n의 시간 복잡도는 피할 수 없는 것 같다. #include #include using namespace std; int S=0; void PrintAllPosSet(int* arr, int size, int depth,vector set) { if (depth == size) { //도달 : basis case cout
기초 알고리즘 문제 풀이 2020. 2. 18. 15:37
3. 임의의 정수 sequence에 대해 중복제거 정렬 sequence출력

#include #include #include using namespace std; //주어진 임의의 정수 n개에 대하여 이들 중 서로 다른 정수를 정렬된 순서로 출력하라. int main() { vector v; //simple test case int num_seq[] = { 10,40,10,20,30,50,10,60,30,70,80,44,20,40 }; int N = 14; for (int i = 0; i < N; i++) v.push_back(num_seq[i]); //sol code sort(v.begin(), v.end()); cout
기초 알고리즘 문제 풀이 2020. 2. 18. 15:15
2. 주어진 날짜에 대한 요일 출력

기준요일 2020.1.1 수요일에 대한 상대적 날짜 계산을 통해 요일을 구한다. 년들의 날짜를 더할 때는 사실 윤년일 때 366, 아닐 때 365를 더하는 알고리즘으로 해도 되는데 조금 더 일반적인 달력계산 체계를 위해 모든 월을 더하는 알고리즘으로 작성했다. 실제로 쓸 때는 365,366으로만 작성하면 n time을 몇 개 줄일 수 있다. /* 3/19에 수정함 */ 생각해보니까 365는 7로 나누면 1임 그러므로 윤년이 아닌 해는 걍 동일 일에 대해서 한 요일만이 늦어질 뿐임. 이걸 생각하면 더 쉽게 짤 수 있음. 물론 아래 코드는 각 달의 일을 수정해서 계산할 수 있게 해서 조금 무식한 풀이임 하지만 다시 똑똑한 코드를 짜는게 너무 귀찮으니까 두겠음. 실제로 빠른 계산을 해야하는 사람은 밑의 코드를..
기초 알고리즘 문제 풀이 2020. 2. 18. 15:07
1. 순열 출력 문제

//순열생성알고리즘 #include #include using namespace std; void swap(int& a, int& b) { int temp = a; a = b; b = temp; } void printSoon(int*arr,int N,int depth) { //basis case에 출력하게 만들자. if (depth == N) { for (int i = 0; i < N; i++) cout
기초 알고리즘 문제 풀이 2020. 2. 17. 14:25
1 ··· 3 4 5 6