체계적인 알고리즘 학습 공략

1. 문제를 읽고 이해한다. 2. 문제를 익숙한 용어로 재정의한다. 3. 어떻게 해결할 지 계획을 새운다. 4. 계획을 검증한다. 5. 프로그램으로 구현한다. 6. 회고한다.

// 값의 구분자 없이 입력을 받는 경우 1. 0123456789 // 공백을 값의 구분자로 입력을 받는 경우 2. 0 1 2 3 4 5 6 7 8 9 // 줄바꿈으로 값의 구분자를 입력 받는 경우 3. 0 1 2 3 ... 9

// 코드로 작성하면 아래와 같다. bool isPrime(int n) { int r = 2; while (n > r) // 2부터 시작하여 자기 자신 바로 전까지 { if (n % r == 0) return false; r++; // 하나씩 증가하며 나누어 떨어지는 수가 있는지 계속 확인한다. } return true; // 나누어 떨어지는 것이 하나도 없다면 이는 소수이다. }

for(int i=0; i<10만; i++) { for(int j=0; j<10만; j++) { } }

for(int i=0; i<10만; i++) { } for(int j=0; j<10만; j++) { }

1,000,000 * (1,000,000 + 1) / 2 = 500,000,500,000

bool* checkPrime(int n) // n까지의 소수인지 아닌지를 판단하는 배열을 리턴한다. { bool* PrimeArray = new bool[n + 1]; // n 즉 1,000,000 까지 소수인지 아닌지를 담을 배열 for (int i = 2; i <= n; i++) PrimeArray[i] = true; // 일단 모두 참으로 초기화 한다. for (int i = 2; i * i <= n; i++) // 루트 n만큼 조사한다. { if (PrimeArray[i]) // 소수인 경우에는 for (int j = i * i; j <= n; j += i) { // 소수를 약수로 둔 수들을 PrimeArray[j] = false; // 약수를 두고 있으므로 거짓으로 변환한다. } } return PrimeArray; }

void Recursive(int n){ if(n == 4) return; for(int i = 0; i < n; i++){ // 별 그리기 printf("*"); } printf("\n"); Recursive(n + 1); // Recursive(재귀) } Recursive(1); // 결과 // * // ** // ***

const a = (v) => { if(v > 10000000) return; a(v + 1); }

void FunctionA() {} void FunctionB() {} void FunctionC() { FunctionB(); // B가 실행되는 동안 C는 여전히 실행중이다. // C함수 종료 } void FunctionD() { FunctionA(); // A가 실행되는 동안 D는 여전히 실행 중(스택에 담겨있는 중)이다. FunctionC(); // C가 실행되는 동안 D는 여전히 실행 중이다. // D함수 종료 }

void Recursive(int n){ if(n == 4) return; for(int i = 0; i < n; i++){ printf("*"); } printf("\n"); Recursive(n + 1); } Recursive(1); // 결과 // * // ** // ***

void Recursive(int n){ if(n == 4) return; Recursive(n + 1); for(int i = 0; i < n; i++){ printf("*"); } printf("\n"); } Recursive(1); // Recursive(1) 실행 stack [] // Recursive(2) 실행 stack [Recursive(1)] // Recursive(3) 실행 stack [Recursive(1), Recursive(2)] // *** for문으로 별 그리기 stack [Recursive(1), Recursive(2)] // ** stack [Recursive(1)] // * stack []

for(int i=1; i<=4; i++) { for(int j=1; j<=4; j++) { printf("%d %d", i, j); } }

int n, m; int arr[8]; // 뽑은 카드를 임시로 보관하는 배열 // repeatPermutation는 1부터 n까지의 카드를 뽑는 함수이다. // 카드를 모두 뽑으면 뽑은 카드들을 출력한다. // x는 뽑은 카드의 수 즉, arr에 저장할 인덱스의 위치이다. // 예를 들어 arr[0] = 1 이라면 첫번째 뽑은 카드는 1이다. 총 m장 뽑으면 종료한다. void repeatPermutation(int x) { // 카드를 모두 뽑으면 종료한다. if(x == m) { for(int i=0; i<m; i++) { printf("%d ", arr[i]); } printf("\n"); return; } // 1부터 n사이의 카드를 뽑고, 다음 장을 뽑을 함수를 실행한다. for(int i=1; i<=n; i++) { arr[x] = i; repeatPermutation(x + 1); } } repeatPermutation(0); // n = 3, m = 2 일때, // 1 1 // 1 2 // 1 3 // 2 1 // 2 2 // 2 3 // 3 1 // 3 2 // 3 3

int n, m; int arr[8]; bool visited[8]; // 방문한 인덱스를 체크하기 위한 배열 // x는 현재 방문할 인덱스 (뽑아야 할 카드 번 째) void Permutation(int x) { if(x == m) { for(int i=0; i<m; i++) { printf("%d ", arr[i]); } printf("\n"); return; } for(int i=1; i<=n; i++) { if(visited[i]) continue; // 방문한 인덱스에 대해선 재방문 하지 않는다. visited[i] = true; arr[x] = i; Permutation(x + 1); // 다음 카드를 뽑는다. visited[i] = false; // 스택을 정리하는 과정에서 방문 여부를 초기화 한다. } } Permutation(0);

int n, m; int arr[8]; bool visited[8]; // x는 현재 방문할 "인덱스", start는 오름차순으로 출력하기 위한 "이전 값보다 큰 값" void Combination(int x, int start) { if(x == m) { for(int i=0; i<m; i++) { printf("%d ", arr[i]); } printf("\n"); return; } for(int i=start; i<=n; i++) { // 다음에 뽑을 카드들은 start부터 n까지의 수를 뽑는다. if(visited[i]) continue; visited[i] = true; arr[x] = i; Combination(x + 1, i + 1); // 다음에 뽑을 수를 호출한다. // 이 때, 내가 뽑은 수보다 큰 수부터 뽑게 start를 지정. visited[i] = false; } } Combination(0, 1);

void repeatPermutation(int x) { if(x == m) { for(int i=0; i<m; i++) { printf("%d ", arr[i]); } printf("\n"); return; } for(int i=1; i<=n; i++) { arr[x] = i; repeatPermutation(x + 1); } } repeatPermutation(0);

int m; int cnt = 0; void repeatPermutation(int sum) { if(sum == m) { // 수열의 합을 통해 m을 만들었으면 cnt를 증가시킨다. cnt++; return; } for(int i=1; i<=3; i++) { // 1부터 3까지의 수를 사용한다. if(sum + i > m) continue; // 만약 m이상이면 수열을 더 이상 진행하지 않는다. repeatPermutation(sum + i); // 현재 수열에 i를 더한다. } } repeatPermutation(0, 0);

int n, m; int arr[8]; bool visited[8]; void Permutation(int x) { if(x == m) { for(int i=0; i<m; i++) { printf("%d ", arr[i]); } printf("\n"); return; } for(int i=1; i<=n; i++) { if(visited[i]) continue; visited[i] = true; arr[x] = i; Permutation(x + 1); visited[i] = false; } } Permutation(0);

const int PLUS = 0, MINUS = 1, MULTI = 2, DIVIDE = 3; int n, arr[15], operatorArr[15]; bool visited[15]; int max = -1000000000, min = 1000000000; // x는 연산자의 인덱스, sum은 결과 void Permutation(int x, int sum) { if(x == n - 1) { int result = sum; if(max < result) max = result; if(result < min) min = result; return; } for(int i=0; i<n-1; i++) { // 연산자의 총 개수는 수에 하나 모자란 값. if(visited[i]) continue; visited[i] = true; switch(operatorArr[i]) { case PLUS: { // "수 연산자 수" 형식이기 때문에 연산을 할 수의 인덱스는 x+1 Permutation(x + 1, sum + arr[x+1]); break; } case MINUS: { Permutation(x + 1, sum - arr[x+1]); break; } case MULTI: { Permutation(x + 1, sum * arr[x+1]); break; } case DIVIDE: { Permutation(x + 1, sum / arr[x+1]); break; } } visited[i] = false; } } Permutation(0, arr[0]); // 첫번째 sum은 연산 값의 맨 앞 숫자이다.

void merge(int s1, int e1, int s2, int e2) { int temp[100005]; int cursor= 0; int start = s1, end = e2; while(s1 <= e1 && s2 <= e2) { // 왼쪽 인덱스 혹은 오른쪽 인덱스가 남을 때까지 if(arr[s1] < arr[s2]) { // 더 작은 값을 임시 배열에 담는다. temp[cursor++] = arr[s1++]; } else { temp[cursor++] = arr[s2++];; } } // 담기지 않은 남은 배열 처리 while(s1 <= e1) { temp[cursor++] = arr[s1++]; } while(s2 <= e2) { temp[cursor++] = arr[s2++]; } // 기존 배열에 병합 for(int i=start; i<=end; i++) { arr[i] = temp[i-start]; } } void mergeSort(int start, int end) { if(start == end) return; // 종료 조건 int middle = (start + end) / 2; // 절반씩 나눈다. mergeSort(start, middle); mergeSort(middle + 1, end); merge(start, middle, middle+1, end); // mergeSort가 종료 되었을 때 자식 호출부터 처리한다. }

int N, Q; int int arr[MAX] = {3,7,9,13,16,19,23,44,45}; bool binarySearch(int x) { int s=0, e = N + 1; while(s + 1 < e) { int mid = (s + e) / 2; if(arr[mid] == x) return true; else if(arr[mid] < x) s = mid; else e = mid; } if(arr[s] == x) return true; return false; } binarySearch(9)

// C++ #include <stack>; stack<char> s; s.push(1); s.top(); // 1 s.pop(); s.top(); // empty;

// javascript const s = [] s.push(1); s[s.length-1]; // 1 s.pop(); // 1 s[s.length-1]; // undefined

// 객체(구조체)를 활용하는 방법 Node tree[10]; struct Node { char name; char leftNode; char rightNode; } Node.name = 'A'; Node.leftNode = 'B'; Node.rightNode = 'C'; tree[0] = Node; // 배열을 이용하는 방법 char tree[10][2] tree['A'-'A'][0] = 'B' // 0번 인덱스는 leftNode tree['A'-'A'][1] = 'C' // 1번 인덱스는 rightNode

const int NO_EDGE = -1; void preorder(int x) { printf("%d ", x); // 만나는 족족 (루트 노드) 처리 for(int i=0; i<2; i++) { if(Tree[x][i] != NO_EDGE) preorder(Tree[x][i]); } } void inorder(int x) { if(Tree[x][0] != NO_EDGE) inorder(Tree[x][0]); printf("%d ", x); // 왼쪽 노드부터 처리 if(Tree[x][1] != NO_EDGE) inorder(Tree[x][1]); } void postorder(int x) { for(int i=0; i<2; i++) { if(Tree[x][i] != NO_EDGE) postorder(Tree[x][i]); } printf("%d ", x); // 마지막 까지 스택에 담은 후(오른쪽 노드에 다다를때 까지) 처리 }

int Parent[100010]; int idx_x = 0; x = 타겟 while(x != root){ Parent[idx_x++] = x; x = tree[x]; } // 이와 같은 느낌으로 저장 가능하다.

int i = Parent_X.length - 1; int j = Parent_Y.length - 1; while(i >= 0 && j >= 0 && Parent_X[i] == Parent_Y[j]){ i--; j--; } // Parent_X[i + 1] 와 Parent_Y[j + 1] 이 두 트리의 LCA

vector<int> Graph[1005]; // const Grahp = []; 스크립트 언어에서는 2차원 배열을 선언하면 된다. for(int i=0; i<M; i++) { int a,b; scanf("%d %d", &a, &b); // 입력값 a, b v[a].push_back(b); // 양방향일 때는 서로에게 연결한다. v[b].push_back(a); // 단방향일 때는, 해당 라인처럼 역방향 연결은 하지 않는다. }

// DFS bool visited[GRAPH_SIZE]; void DFS(int x) { if(visited[x]) return; visited[x] = true; printf("%d ", x); for(int i=0; i<v[x].size(); i++) DFS(v[x][i]); }

// BFS bool visited[GRAPH_SIZE]; void BFS(int x) { queue<int> q; q.push(x); // 처음 방문할 노드를 큐에 담는다. visited[x] = true; while(!q.empty()) { // 더 이상 다음에 방문할 노드가 없을 때까지 int next = q.front(); // 가장 먼저 방문한 노드를 소비하여, 해당 노드의 인접노드를 찾는다. q.pop(); printf("%d ", next); for(int i=0; i<v[next].size(); i++) { // 해당 노드의 인접노드들을 반복하면서 int value = v[next][i]; if(visited[value]) continue; // 이미 방문한 노드라면 생략하고 q.push(value); // 그렇지 않다면 방문한다. visited[value] = true; } } }

const int INF = 9999999; int cost[GRAPH_SIZE]; void dijkstra() { for(int i=0; i<N; i++) cost[i] = INF; cost[S] = 0;

// for(int i=0; i<N; i++) cost[i] = INF; // cost[S] = 0; for(int i=0; i<N; i++) { // 모든 노드에 대해서 반복한다. int min = 9999999, minIndex = -1; // 현재 상태에서 방문하지 않은 노드 중 최소 비용을 가진 노드를 찾는다. for(int j =0; j<N; j++) { if(!visited[j] && cost[j] < min) { min = cost[j]; minIndex = j; } } // 방문하여, 인접노드의 최소 비용 값을 갱신한다. visited[minIndex] = true; for(int j=0; j<v[minIndex].size(); j++) { if(cost[minIndex] + weight[minIndex][j] < cost[v[minIndex][j]]) // 인접노드의 비용보다, 현재 노드와 그 가중치의 합이 더 작은 경우에 갱신한다. cost[v[minIndex][j]] = cost[minIndex] + weight[minIndex][j] ; } }

priority_queue<pair<int,int, ascending>>pq; // 큐에 가중치와 인덱스를 페어로 저장한다. pq.push({0, 0}); // 가중치 : 0 시작 노드 : 0으로 시작한다. cost[start]=0; while(!pq.empty()) { int dist = pq.top().first; // 가중치가 최소인 가중치를 가져온다. int curr = pq.top().second; // 가중치가 최소인 인덱스를 가져온다. pq.pop(); if(visited[curr]) continue; visited[curr] = true; for(int i=0; i<v[curr].size(); i++) // 반복한다. { if(dist + weight[curr][i] < cost[v[now][i]]) { cost[v[now][i]]= dist + weight[curr][i]; pq.push(make_pair(cost, v[now][i])); } } }

int Fibonacci(i) { if(i == 0 || i == 1) return 1; return Fibonacci(i-1) + Fibonacci(i-2); } Fibonacci(5); // Fibonacci(3) 과 Fibonacci(4) 를 더한 어떤 값.

int Fibonacci[6]; Fibonacci[0] = 1; // 초기 기저 조건 설정 Fibonacci[1] = 2; for(int i=2; i<=5; i++) { Fibonacci[i] = Fibonacci[i-1] + Fibonacci[i-2]; // 점화식 구현 }

int arr[301]; int F[301]; for(int i=1; i<=n; i++) { scanf("%d", &arr[i]); } F[0] = 0; F[1] = arr[1]; F[2] = arr[1]; for(int i=3; i<=n; i++) { F[i] = arr[i] + std::max(arr[i-1] + F[i-3], F[i-2]); } for(int i=0; i<=n; i++) { printf("%d\n", F[i]); }