기록

동적 계획법 (Dynamic Programming) 하나의 문제는 단 한 번만 풀도록 하는 알고리즘이다. 한 번 푼 것을 여러 번 다시 푸는 비효율적인 알고리즘을 개선시키는 방법이기도 하다. 상당수 분할 정복 기법은 동일한 문제를 다시 푼다는 단점을 가지고 있다. (다만 분할 정복 기법을 '정렬'과 같은 몇몇 요소에 대해서는 동일한 문제를 다시 풀게 되는 단점이 없다.) 대표적인 예시로는 피보나치 수열이 있다. 피보나치 수열은 특정한 숫자를 구하기 위해 그 앞에 있는 숫자와 두 칸 앞에 있는 숫자의 합을 구해야 한다. 만약 재귀함수만으로 프로그래밍을 한다면, 15번째 피보나치 수열의 값을 구하기 위해서는12번째 피보나치 수열값을 3번이나 계산하게 된다. 우리는 이런 불필요한 계산을 DP를 이용하여 없앨 ..

정렬 알고리즘 1. 선택 정렬 (Selection Sort) ​ 1 10 5 8 7 6 4 3 2 9 이걸 오름차순으로 정렬할 때, 가장 작은 걸 골라(select) 맨 앞으로 가져오는 알고리즘이다. Source Code #include int main(void){ int i, j, min, index, temp; int array[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9}; for(i = 0; i array[j]){ //min값을 i번째 부터 마지막 원소까지 검사한다. min = array[j]; index = j; } temp = array[i]; //원래..

이진 트리의 구현과 순회 방식 기본적으로 가장 많이 사용되는 비선형 자료구조는 이진 트리이다. 이진 트리는 트리 자료구조를 활용한 대표적인 예시로 데이터의 탐색 속도를 빠르게 하기 위해 사용하는 구조이다. 힙정렬에서는 완전 이진 트리를 사용했기 때문에 트리를 배열로 구현할 수 있었지만, 실제로 불규칙한 트리를 제대로 구현하기 위해서는 포인터를 사용해야한다. 포인터를 이용해 특정한 루트에서 자식노드로 접근할 수 있기 때문이다. 포인터를 사용하는 이유는 자원 낭비를 막기 위함이다. 이진 트리에서 데이터를 순회하는 방법은 크게 세가지가 있다. 전위 순회 : 자기 자신 -> 왼쪽 자식 -> 오른쪽 자식 중위 순회 : 왼쪽 자식 -> 자기 자신 -> 오른쪽 자식 후위 순회 (컴퓨터가 이해하기 좋은 방식) : 왼쪽..

Searching 1. 너비 우선 탐색 (Breath First Search) 너비 우선 탐색은 '최단 경로'를 찾아준다는 점에서 최단 길이를 보장해야 할 때 많이 사용된다. 준비물: 큐(Queue), 탐색할 그래프 큐에서 하나의 노드를 꺼낸다. 해당 노드에 연결된 노드 중 방문하지 않은 노드를 방문하고, 차례대로 큐에 삽입한다. 위 두 과정을 계속 반복한다. #include #include #include using namespace std; int number = 7; int c[7]; vector a[8]; void bfs(int start) { queue q; q.push(start); c[start] = true; while(!q.empty()) { int x = q.front(); q.pop(..

동적 계획법 (Dynamic Programming) 하나의 문제는 단 한 번만 풀도록 하는 알고리즘이다. 한 번 푼 것을 여러 번 다시 푸는 비효율적인 알고리즘을 개선시키는 방법이기도 하다. 상당수 분할 정복 기법은 동일한 문제를 다시 푼다는 단점을 가지고 있다. (다만 분할 정복 기법을 '정렬'과 같은 몇몇 요소에 대해서는 동일한 문제를 다시 풀게 되는 단점이 없다.) 대표적인 예시로는 피보나치 수열이 있다. 피보나치 수열은 특정한 숫자를 구하기 위해 그 앞에 있는 숫자와 두 칸 앞에 있는 숫자의 합을 구해야 한다. 만약 재귀함수만으로 프로그래밍을 한다면, 15번째 피보나치 수열의 값을 구하기 위해서는12번째 피보나치 수열값을 3번이나 계산하게 된다. 우리는 이런 불필요한 계산을 DP를 이용하여 없앨 ..

정렬 알고리즘 1. 선택 정렬 (Selection Sort) 1 10 5 8 7 6 4 3 2 9 이걸 오름차순으로 정렬할 때, 가장 작은 걸 골라(select) 맨 앞으로 가져오는 알고리즘이다. Source Code #include int main(void){ int i, j, min, index, temp; int array[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9}; for(i = 0; i array[j]){ //min값을 i번째 부터 마지막 원소까지 검사한다. min = array[j]; index = j; } temp = array[i]; //원래 i..

1. DFS, Death-First Search (깊이 우선) * 그래프 탐색의 경우 어떤 노드를 방문했었는지 반드시 검사해야한다 : 백트래킹 너비 우선 탐색과 마찬가지로 각 노드를 탐색할 때 사용된다. 너비 우선 탐색과 달리 스택을 사용한다. 사실 스택을 사용하지 않아도 구현이 가능 (재귀함수) 준비물: 스택, 그래프 스택의 최상단 노드를 확인한다. 최상단 노드에게 방문하지 않은 인접 노드가 있으면 그 노드를 스택에 넣고 방문 처리한다. 모든 인접노드에 방문한 후에는 스택의 최상단 노드를 뺀다. 위 세 과정을 반복하는 원리이다. 근데 대회에서는 빠르게 구현하고, 동작하게 하기 위해 재귀함수를 많이 쓴다. 아래 소스코드는 DFS를 재귀함수로 구현한 것이다. #include #include using na..

그리디 알고리즘이란? 문제를 해결하는 과정에서 매번 최적이라고 생각하는 방법으로 결정하는 태도라고 할 수 있을 것같다. 특별한 공식같은 건 없는 거같다. 그래서 이름이 Greedy인 것이 아닐까? Greedy 알고리즘은 1. Greedy choice property 2. Optimal Substructure 위의 두 조건이 성립될 때 적용 가능하다. : 이 조건을 만족함은 앞의 선택이 이후의 선택에 영향을 주지 않는다는 것이다. : 전체 문제의 최적해가 부분 문제의 최적해들로써 구성된다는 것이다.