NAN-NOO

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

https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 2023.04.14 - [코딩 테스트/개념] - Tree # 2 ≤ N ≤ 100,000 from collections import deque import sys readline = sys.stdin.readline N = int(readline()) tree = [[] for _ in range(N + 1)] for _ in range(N - 1): v1, v2 = map(int, readline().split()) tree[v1].append(v2) tre..

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

https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 2023.04.12 - [코딩 테스트/개념] - MST # 1

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

https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 2023.04.11 - [코딩 테스트] - Floyd-Warshall algorithm # 2

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