NAN-NOO

동적 계획법은 복잡한 문제를 여러 개의 간단한 문제로 분리하여 부분의 문제를 해결함으로써 최종적으로 복잡한 문제의 답을 구하는 방법을 말한다. 🔰특징 큰 문제를 작은 문제로 나눌 수 있어야 한다. 작은 문제들이 반복적으로 나타나고 사용되며, 작은 문제의 결과값은 변하지 않아야 한다. 모든 작은 문제를 한 번만 계산해 dp 테이블에 저장하여 재사용한다. 이를 memoization이라 한다. 탑-다운 방식과 바텀-업 방식으로 구현할 수 있다. 🔰접근 방법 피보나치 수열에서 6번째 수를 구하는 문제가 있다고 가정하자. 동적 계획법으로 풀 수 있는지 확인한다. 6번째 수는 5번째 피보나치 수와 4번째 피보나치 수의 합이다. 따라서 5번째 수를 구하는 문제와, 4번째 수를 구하는 작은 문제로 나눌 수 있고, 그 ..

조합은 nCr로 표현하고, n개의 숫자에서 r개를 뽑는 경우의 수를 말한다. 비슷한 개념으로 순열은 nPr로 표현하고, n개의 숫자 중 순서를 고려하여 r개를 뽑는 경우의 수를 말한다. 조합은 순서를 고려하지 않는다. nPr = n! / (n - r)! nCr = n! / (n - r)!r! 조합은 동적 계획법의 시작이라 볼 수 있다. 알고리즘에서 조합을 구현할 때는 위의 수학 공식을 코드화하지 않고, 점화식을 사용해서 표현한다. 🔰접근 방법 특정 문제를 가정하기 예를 들어, 5개 중 3개를 선택하는 조합의 경우의 수를 푸는 문제로 가정하자. 모든 부분 문제가 해결된 상황이라고 가정하고 현재의 문제를 생각하기 먼저 5개 데이터 중 4개를 이미 선택 여부를 결정했다고 가정하자. 그리고 마지막 1개의 데이터..

최소 공통 조상(LCA; Lowest Common Ancestor) 알고리즘이란, 트리에서 임의의 두 노드를 선택해서 각각의 부모 노드를 탐색할 때 처음으로 만나는 공통 부모 노드를 찾는 알고리즘이다. 일반적인 방법과 빠르게 찾는 방법이 있다. 시간 복잡도는 트리의 height와 관련있다. 🔰구현 일반적인 최소 공통 조상 구하기 트리의 height가 크지 않을 때 사용한다. 루트 노드부터 탐색을 시작해 각 노드의 부모 노드의 인덱스와 depth를 저장한다. 탐색은 DFS나 BFS를 이용한다. 트리의 특징때문에 바로 직전에 탐색한 노드가 부모 노드가 되고, depth를 저장할 수 있다. 선택된 두 노드의 깊이가 다른 경우, 더 깊은 깊이를 가진 노드를 부모 노드로 대체하면서 같은 깊이로 맞춘다. 이때 두 ..

주어진 데이터의 구간 합과 데이터 업데이트를 빠르게 수행하기 위해 고안한 자료구조다. 큰 범위에선 인덱스 트리라고 불린다. 구간 합은 합 배열을 이용해서 쉽게 구할 수 있다. 그런데도 세그먼트 트리를 사용하게 된 이유는, 데이터의 업데이트때문이다. 합 배열을 사용할 경우, 일부 데이터가 수정되었을 때 합 배열을 수정하는 시간이 오래 걸린다. 데이터의 업데이트가 빈번하게 이뤄질 경우, 합배열보단 세그먼트 트리를 사용한다. 최대 log_2(N)만큼만 업데이트가 일어난다. 🔰구현 세그먼트 트리 종류는 구간 합, 최대 및 최소 구하기로 나눌 수 있다. 트리 초기화: 리프 노드가 원본 데이터인 이진 트리(1차원 배열)로 초기화한다. 리프 노드의 개수가 데이터의 개수(N) 이상이 되도록 트리 배열을 만든다. 트리 ..

이진 트리란, 각 노드의 자식 노드 개수가 2 이하로 구성된 트리를 말한다. 트리 분야에서 가장 많이 사용되는 형태다. 트리를 일차원 배열로 표현하려면, 이진 트리여야 한다. -> 인덱스 트리와 LCA에 적용할 수 있다. 🔰이진 트리 종류 편향 이진 트리 노드들이 한쪽으로 편향되어 생성된 이진 트리다. 이 형태인 경우, 탐색 속도가 저하되고 공간 효율이 낮다. 링크드 리스트와 같은 구조! 포화 이진 트리 트리의 높이가 모두 일정하며, 리프 노드가 모두 차 있는 이진 트리를 말한다 완전 이진 트리 마지막 레벨을 제외한 나머지 레벨에 노드들이 모두 채워져 있고, 마지막 레벨은 왼쪽부터 채워진 이진 트리다. 일반적으로 코딩 테스트에서는 완전 이진 트리 형태를 사용한다. 🔰이진 트리 표현 가장 직관적이면서 편리..

그래프의 특수한 형태 cycle이 없고, 1개의 루트 노드가 있다. 루트 노드를 제외한 노드는 1개의 부모 노드를 갖는다. 트리의 부분(subtree) 역시 트리의 모든 특징을 따른다. 트리에서 임의의 두 노드를 이어주는 경로는 유일하다. 🔰구성 요소 구성 요소 설명 노드 데이터의 index와 value를 표현하는 요소 엣지 노드와 노드의 연결 관계를 나타내는 선 루트 노드 트리에서 가장 상위에 존재하는 노드 부모 노드 두 노드 사이의 관계에서 상위 노드에 해당하는 노드 자식 노드 두 노드 사이의 관계에서 하위 노드에 해당하는 노드 리프 노드 트리에서 가장 하위에 존재하는 노드(자식 노드가 없음) 서브 트리 전체 트리에 속한 작은 트리 🍎 코딩 테스트에서 트리 1. 그래프로 푸는 트리: 인접 리스트로 표..

최소 신장 트리는 그래프에서 모든 노드를 연결할 때 사용된 엣지들의 가중치 합을 최소로 하는 트리다. 대표적인 알고리즘으로 크루스칼 알고리즘, 프림 알고리즘이 있다. 두 알고리즘은 구현 방식만 약간 다르고 목적이 같다. 🔰최소 신장 트리의 특징 사이클이 포함되면 가중치 합이 최소가 될 수 없으므로 사이클을 포함하지 않는다. n개의 노드가 있으면 최소 신장 트리를 구성하는 엣지의 개수는 항상 n - 1 개다. 🔰구현(Kruskal algorithm) 엣지 리스트로 그래프를 구현하고, 동시에 유니온 파인드 리스트를 초기화한다. 유니온 파인드 알고리즘은 사이클 판별을 위해 사용한다. 유니온 파인드 리스트는 초기에 자기 자신이 대표 노드이므로 각 인덱스를 자기 자신으로 초기화한다. 그래프를 가중치 기준으로 오름..

그래프에서 최단 거리를 구하는 알고리즘이다. 단, 특정 노드가 아닌 모든 노드 간에 최단 경로를 탐색한다. 음수 가중치가 있어도 가능하다. 동적 계획법의 원리를 이용해 알고리즘에 접근한다. 시간 복잡도는 O(V^3)이다. -> 시간 초과때문에 규모가 작은 경우에 활용한다(N = 200 정도?). 🔰구현 삼중 for문으로 되어 있고, 구현이 쉽다. a 노드에서 b 노드까지 최단 경로를 구했다고 가정했을 때, 그 경로를 이루는 부분 경로 역시 최단 경로다. 즉, 전체 경로의 최단 경로는 부분 경로의 최단 경로 조합으로 이뤄진다. D[S][E] = min(D[S][E], D[S][K] + D[K][E]), K는 S 노드와 E 노드까지의 경로에 존재하는 모든 노드를 의미한다. 최단 거리 인접 행렬을 선언하고 초..

그래프에서 특정 출발 노드에서 다른 모든 노드까지의 최단 거리를 구하는 알고리즘이다. 음수 가중치가 있어도 수행할 수 있다. 전체 그래프에서 음수 사이클이 존재하는 지 여부를 판단할 수 있다. 시간복잡도는 O(VE)다. 🔰구현 엣지 리스트로 그래프를 구현하고, 최단 경로 리스트를 초기화한다. 최단 경로 리스트의 출발 노드는 0, 나머지 노드는 무한대로 초기화한다. 모든 엣지를 확인해 최단 거리 리스트를 갱신한다. 이 갱신 반복 횟수는 (그래프의 노드 개수 - 1)번이다. 사이클이 없는 그래프에서 특정 두 노드의 최단 거리를 구성하는 엣지의 최대 개수는 (전체 노드 개수 - 1)이기 때문이다. 엣지 리스트에서 선택한 엣지의 출발 노드의 최단 거리 배열의 값이 무한대가 아닐 때, 도착 노드의 최단 거리 배열..

출발 노드와 다른 모든 노드간의 최단 거리를 구하는 알고리즘이다. 엣지는 모두 양수의 가중치를 가진다. 시간 복잡도는 O(E * logV)다. 🔰구현 인접 리스트로 그래프를 구현한다. 최단 거리 배열을 초기화한다. 출발 노드의 값은 0, 이외의 노드는 무한(실제로는 적당히 큰 값)으로 초기화한다. 최단 거리 배열에서 값이 가장 작은 노드를 고른다. 처음에는 값이 0인 출발 노드를 고르면 된다. 이미 선택했던 노드인 경우 다시 선택되지 않도록 방문 배열을 만들어 처리한다. 선택된 노드에 연결된 엣지의 값을 바탕으로 다른 노드의 최단 거리 배열 값을 갱신한다. 인접 리스트를 이용하면 된다. 연결된 노드의 최단 거리 배열의 값은 min(선택 노드의 최단 거리 배열의 값 + 엣지의 가중치, 연결된 노드의 최단 ..