초보개발자

트리 순회에는 세 가지 방법이 있다. 전위순회(preorder), 중위순회(inorder), 후위순회(postorder) 어떻게 분류하는 거냐면 언제 부모의 Value를 방문하는 순간으로 분류한다. 즉, 아래와 같다. 전위순회: 부모 - left - right 중위순회: left - 부모 - right 후위순회: left - right - 부모 만약 value를 출력하거나 임의의 함수를 호출한다면 저 순서대로 출력하면 된다. 예를 들면 노드에 문자를 저장해놓고 중위순회하는 코드는 아래와 같다. void inorder(int node, const int n) { if (node > n) return; inorder(node * 2, n); printf("%c", tree[node]); inorder(nod..

[알고리즘] Floyd-Warshall 이 알고리즘은 Transitive closure나 다대다 최단 거리를 구할 때 사용하는 알고리즘이다. 동적계획법(Dynamic Programming) 기법이 포함되어 있다. Transitive closure란 간접적으로 연결되어 있는 간선을 직접갈 수 있는 간선을 추가한 그래프이다.즉, 이 그래프는 원하는 정점이 서로 직접 혹은 간접적으로 연결되어 있냐를 확인할 수 있다. pseudo code는 아래와 같다. D: 주어진 인접행렬 for k from 1 to |V| for i from 1 to |V| for j from 1 to |V| D[i][j] := D[i][j] | (D[i][k] & D[k][j]) return D D[i][j] := D[i][j] | (D..

[알고리즘] 위상정렬(topological sorting) 위상정렬은 그래프를 자료구조로 가지는 알고리즘으로 유향 그래프의 정점들을 한 방향으로 나열하는 것을 말한다. 예를 들어 김치찌개를 만드는 방법을 입력받았을 때 그것을 하나의 순서로 만드는 것이다. 여러 가지 순서를 가질 수 있으며, 특정 조건에 따라 우선순위 큐(priority queue)를 사용할 수 있다. 위상 정렬이 성립하기 위해서는 반드시 그래프의 순환이 존재하지 않아야 하며 이러한 그래프를 비순환 유향 그래프라고 한다. 위상정렬을 구현하는데 여러 방법을 쓰일 수 있는데, 나는 여기서 큐와 진입 차수(indegree)를 이용한 방법을 설명하려고 한다. 알고리즘 순서는 다음과 같다.1. 간선 정보를 초기화한다. 이 때, 문제에 따라 인접행렬..

[알고리즘] 최소 스패닝 트리 - kruskal 알고리즘최소 스패닝 트리정의: 가중치 그래프의 스패닝 트리 중 가중치의 합이 가장 작은 트리를 찾는 문제종류: kruskal 알고리즘, prime 알고리즘이 존재한다.kruskal 알고리즘정의: 최소 스패닝 트리를 구현하는 하나의 방법으로 가중치가 가장 작은 간선이 최소 스패닝 트리에 포함될 가능성이 높다는 생각에 착안되어서 만들어진 알고리즘 구현 방법: 그래프의 모든 간선을 가중치의 오름차순으로 정렬한 뒤, 스패닝 트리에 하나씩 추가를 한다. 단, 추가를 했을 경우 사이클이 발생하면 안되기 때문에 이 간선은 제외해야 한다.참고 문제: [LAN] 근거리 네트워크 http://yejin0730.tistory.com/10출처: 알고리즘 문제 해결 전략2

[알고리즘] 정수론유클리드 알고리즘(Euclidean algorithm)정의: 두 수의 최대공약수를 구하는 방법구현 방법: 파라미터로 a와 b를 받고, b=0이면 a를 반환한다. 아닐 경우, b와 a를 b로 나눈 나머지(a % b)를 인수로 재귀함수를 호출한다. a = b * R1 + 2, b = R1 * R2 + R3, ... , R(n-2) = R(n-1) * Rn + 0 일 때, Rn이 최대공약수이다.구현:int gcd(int a, int b){ if(b == 0) return a; else return gcd(b, a % b); }모듈라 연산정의: 모듈로(modulus) M에 도달하면 다시 0으로 돌가는 정수들을 가지고 하는 연산. 덧셈, 뺄셈, 곱셈(a + b)%M = ((a%M) + (b%M)..

[알고리즘] 동적계획법 동적 계획법은 큰 의미에서 분할 정복과 같은 접근방식을 의미한다.메모이제이션(memoization): 함수의 결과를 저장하는 장소를 마련해 두고, 한 번 계산한 값을 저장해 뒀다 재활용하는 최적화 기법대표적인 사용 방법:항상 기저 사례를 제일 먼저 처리. 접근을 벗어나는 등의 오류가 발생.cache(이미 계산한 값을 저장해 두는 메모리의 장소)를 -1로 초기화. -1이 아닌 경우에는 계산이 된 경우가 아님을 의미.ret는 cache[idx]의 참조형(reference)으로, 해당 값이 수정되면 ret 값도 수정되어 계산되었음을 의미.초기화하는 방법은 memset() 혹은 vector를 사용하여 초기화할 수 있음.가장 유명한 예: 이항 계수(binomial co-efficient)참..