Coding Diary

1. 개념 복잡한 문제를 여러 개의 간단한 문제로 분리하여 부분의 문제들을 해결함으로써 최종적으로 복잡한 문제의 답을 구하는 방법 2. 특징 큰 문제를 작은 문제로 나눌 수 있어야 한다 작은 문제들이 반복되고, 작은 문제들의 결과값은 항상 같아야 한다. 작은 문제들은 한 번만 계산해 DP 테이블에 저장한다. 이후에 재사용할 때는 DP 테이블에 있는 것을 사용한다. 이는 메모이제이션 기법이다. 톱 다운 방식과 바텀 업 방식으로 구현 가능하다 3. 원리 피보나치 수열을 통해 원리를 알아보자. 피보나치 수열 공식: D[N] = D[N-1] + D[N-2] 1) 동적 계획법으로 풀 수 있는지 확인하기 피보나치 수열의 3번째 값은 1번째 값과 2번째 값의 합이다. 그리고 이는 수열이 진행되면서 반복된다. 즉 큰 ..

1. 개념 n개 중 r개를 선택하는 경우의 수를 뜻한다. 이때, 선택한 것들의 순서가 달라도 같은 것이라고 처리한다. 예를 들어 1 2 3 4 5 중 2개를 뽑았을 때 1 2 를 뽑은 것과 2 1 을 뽑은 것을 같은 것이라고 보는 것이다. 2. 공식 3. 점화식 1) 조합 공식보다 점화식을 사용하면 좋은 이유 조합 공식의 경우 팩토리얼 연산을 사용해야 하는데 큰 수의 경우 계산 비용이 높다. 팩토리얼 연산을 재귀로 구현할 경우 스택 오버 플로우 문제가 발생할 수 있다. 점화식을 사용하면 반복 계산을 피할 수 있다. 이전에 계산된 것을 동적 계획법의 방식으로 사용하기 때문에 계산 비용을 줄일 수 있고 더 효율적으로 접근할 수 있다. 2) 점화식 개념 점화식을 세울 때는 모든 부분 문제가 해결된 상황이라고 ..

1. 개념 트리 그래프에서 임의의 두 노드를 선택했을 때 두 노드가 각각 자신을 포함해 거슬러 올라가면서 부모 노드를 탐색할 때 처음 공통으로 만나게 되는 부모 노드를 최소 공통 조상이라고 한다. 2. 원리 1) 일반적인 최소 공통 조상 구하기 4번과 15번 노드의 최소 공통 조상을 구한다고 가정. 루트 노드에서 탐색을 시작해 4번의 부모 노드와 깊이를 저장, 루트 노드에서 탐색을 시작해 15번의 부모 노드와 깊이를 저장 선택된 두 노드의 깊이가 같은 경우 동시에 부모 노드로 올라가면서 두 노드가 같은 노드가 될 때까지 반복 - 1 선택된 두 노드의 깊이가 다른 경우 더 깊은 노드의 노드를 부모 노드로 올려서 같은 깊이로 맞추기 그리고 1을 진행 트리의 높이가 커질 경우 시간 제약 문제에 직면할 수 있다..

1. 개념 그래프에서 모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 트리이다. 2. 특징 사이클은 없어야 한다. 사이클이 있으면 가중치의 합이 최소가 될 수 없기 때문이다. N개의 노드가 있으면 최소 신장 트리를 구성하는 에지의 개수는 항상 N-1개다. 에지 리스트의 형태로 구현하는 것이 간단하다. 3. 종류 1) 크루스칼 모든 에지를 가중치 기준으로 오름차순으로 정렬한 후, 가중치가 작은 간선부터 선택하면서 사이클을 형성하지 않도록 하여 최소 신장 트리를 만든다. 2) 프림 시작 노드부터 출발하여 가장 가까운 노드를 선택하며, 해당 노드와 연결된 에지 중 가장 가중치가 작은 간선을 선택하는 방식으로 최소 신장 트리를 만든다. 4. 크루스칼 1) 원리 에지 리스트를 생성한다. 에지 리..

1. 개념 그래프 상에 있는 모든 경로의 최단 경로를 구할 수 있는 알고리즘이다. 즉, 노드 1 2 3 4 5 가 있을 때, 노드 1과 노드 2사이의 최단 경로, 노드 1과 노드 3 사이의 최단 경로....노드 4와 노드 5 사이의 최다 경로를 모두 구할 수 있다. 출발 노드로부터 각 노드까지의 최단 경로를 구하는 다익스트라나 벨만포드 알고리즘과는 살짝 다르다. 2. 특징 모든 노드 간의 최단 경로를 탐색할 수 있다. 음수 가중치 에지가 있어도 수행할 수 있다. 동적 계획법의 원리를 이용해 알고리즘에 접근한다. 시간 복잡도가 O(V3)이다. V는 노드의 수. 인접 행렬을 이용하면 구현이 간단하다. 3. 원리 동적 계획법의 원리 시작 노드부터 도착 노드까지의 최단 경로는 시작 노드부터 중간 노드까지의 최단..

1. 개념 그래프에서 출발 노드와 다른 노드들 간의 최단 거리를 구하는 알고리즘이다. 즉 노드 1, 2, 3, 4, 5가 있고 출발 노드가 1이라고 했을 때, 1부터 2까지 가는 최단 거리, 1부터 3까지가는 최단거리, 1부터 4까지가는 최단 거리, 1부터 5까지 가는 최단 거리를 구할 수 있는 알고리즘이다. 2. 특징 음수 가중치 에지가 있어도 수행할 수 있다 전체 그래프에서 음수 사이클의 존재 여부를 판단할 수 있다 시간 복잡도가 O(VE)이다. V는 노드수, E는 에지수. 에지 리스트를 사용하는 것이 간단하다. 3. 원리 에지 리스트를 만든다 최단 거리 배열을 만든다 출발 노드는 0으로 설정하고, 이외의 노드는 적당히 큰 값으로 설정한다. 에지 리스트를 순회하면서 [출발 노드로부터 해당 에지의 출발..

1. 개념 그래프에서 출발 노드와 다른 노드들 간의 최단 거리를 구하는 알고리즘이다. 즉 노드 1, 2, 3, 4, 5가 있고 출발 노드가 1이라고 했을 때, 1부터 2까지 가는 최단 거리, 1부터 3까지가는 최단거리, 1부터 4까지가는 최단 거리, 1부터 5까지 가는 최단 거리를 구할 수 있는 알고리즘이다. 2. 특징 간선의 가중치가 양수다. 시간 복잡도가 O(에지수log노드수) 이다. 우선순위 큐를 사용하여 시간복잡도를 시간 복잡도를 줄인다 우선순위 큐를 사용하면 현재 위치로부터 최소 비용으로 갈 수 있는 다음 노드를 먼저 탐색하여서 불필요한 경로를 탐색하지 않아도 된다. 즉, 모든 노드를 탐색해보지 않아도 된다. 인접 리스트를 사용하는 것이 간단하다. 3. 원리 인접 리스트를 만든다 최단 거리 배열..

1. 개념 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘이다. 이렇게 구한 노드 순서는 해당 순서의 노드가 처리되기 위해서는 그 노드보다 앞에 있는 노드가 처리되어야 함을 의미한다. 즉, 반약 위상 정렬의 결과가 1 2 3 4 5 일 때, 2가 처리되기 위해서는 무조건 1이 처리되어야 하는 것이고, 5가 처리되기 위해서는 무조건 1234가 처리 되어 있어야 하는 것이다. 2. 특징 항상 유일한 값으로 정렬되지 않는다. 시간 복잡도는 O(노드 수 + 에지 수) 이다. 3. 원리 진입 차수를 이용한다 진입 차수는 자기 자신을 가리키는 에지의 개수를 의미한다. 진입 차수가 0이라는 것은 해당 노드는 아무 것에도 의지하지 않는다는 것을 의미한다. 그래서 진입 차수가 0인 것을 먼저 정렬한다. -- 1..

1. 개념 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과, 특정 원소가 속한 집합의 대표 원소를 반환하는 find 연산. 2. 연산 1) union 원소 a가 집합 A에 속해있고, 원소 b가 집합 B에 속해 있을 때 a와 b를 union한다는 것은 A와 B의 합집합을 구하는 것과 같다. 2) find 집합 A에는 다양한 원소들이 있고, 그 중에 a도 있다. find(a)는 a가 속한 집합에 있는 다양한 원소 중 대표 원소를 구하는 연산이다. 3. 원리 1차원 배열을 선언한다. 그 배열의 인덱스는 원소를 의미하고, 인덱스에 있는 값은 해당 원소가 속한 집합을 의미한다. 1) find 1 2 3 4 5 6 1 2 3 4 5 6 find(1)은 1이 속한 집합의 대표 ..

1. 개념 방정식의 해를 구하기 위해 사용하는 알고리즘이다. 2. 원리 ax+by=c(a,b,c,x,y는 정수) 와 같은 방정식이 있을 때, c가 a와 b의 최대 공약수의 배수인 경우에만 정수해를 가진다. ax+by=c가 정수해를 갖게 하는 c의 최솟값이 gcd(a,b)이다. 3. 방법 5x + 9y = 2 일때, 이 식을 만족하는 정수 x와 y를 찾아보자. 식이 정수해를 갖게 하는 c의 최솟값이 gcd(5,9)라는 것을 적용하여 식을 다시 놓는다. 5x + 9y = 1 5와 9로 유클리드 호제법을 반복 실행하며 몫과 나머지를 저장한다. 나머지가 0이 되면 반복을 중단한다. 유클리드 호제법 실행 나머지 몫 5%9 5 0 9%5 4 1 5%4 1 1 4%1 0 4 위에서 구한 나머지와 몫을 이용하여 x와 ..