최소 신장 트리 신장 트리란 그래프 $G$의 부분 그래프 중 트리의 조건을 만족하는 것이다. 다시 말해서, 그래프 $G$의 모든 정점을 하나 이상의 간선을 사용해 트리 형태로 연결한 것이다. 최소 신장 트리란 무방향 가중치 그래프의 신장 트리 중 간선의 가중치의 합이 최소인 신장 트리이다. 최소 신장 트리를 구현하는 알고리즘에는 크루스칼 알고리즘과...

분리 집합 분리 집합은 공통 원소가 없는 집합(서로소 집합)들에 대한 정보를 저장하고 조작하는 자료 구조이다. 두 원소가 같은 집합에 속해있는지 확인하거나, 최소 신장 트리를 구현하는 등 여러 상황에서 사용할 수 있다. 분리 집합은 유니온 파인드라고도 하는데, 분리 집합이 Union과 Find 두 가지 연산을 지원하기 때문이다. 연산 Union...

투 포인터 알고리즘 투 포인터 알고리즘은 배열에서 각 원소를 가리키는 두 개의 포인터를 조작하여 $O(N)$에 문제를 해결하는 알고리즘이다. 일반적으로 투 포인터는 두 가지 종류가 있다. 두 포인터가 양 끝에서 시작하는 경우와 한 점(일반적으로 시작점)에서 시작하는 경우다. 한 점에서 시작하는 경우 2003번: 수들의 합2는 배열에서 연속된 원...

플로이드-워셜 알고리즘 앞선 다익스트라와 벨만-포드 알고리즘은 한 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘이었다. 그렇다면 모든 정점에 대하여 다른 모든 정점까지의 최단 경로를 구하려면 어떻게 해야할까? 음수 간선의 존재 여부에 따라 모든 정점에 대해서 다익스트라 혹은 벨만-포드 알고리즘을 사용할 수도 있겠지만, 플로이드 워셜 알고...

벨만-포드 알고리즘 벨만-포드 알고리즘은 다익스트라 알고리즘과 마찬가지로 한 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘이다. 다익스트라 알고리즘은 음수 간선이 포함된 경우 제대로 동작하지 않지만, 벨만-포드 알고리즘은 음수 간선이 포함된 경우에도 정확한 최단 거리를 구할 수 있고, 음수 사이클의 존재 여부까지 판별할 수 있다. ...

다익스트라 알고리즘 다익스트라 알고리즘은 한 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘이다. 그래프 뿐만 아니라 그래프로 변환할 수 있는(2차원 배열 등) 자료구조에서 전부 사용할 수 있다. 최단 경로라고 표현했지만, 문제에 따라 최소 가중치, 최소 비용등으로도 표현 가능하다. 진행 방식 방문하지 않은(거리가 확...

다이나믹 프로그래밍

그리디 그리디 알고리즘은 현재 상황에서 가장 좋은(최적의) 선택을 하는 알고리즘 기법이다. 부분 문제들의 최적해의 집합이 전체 문제의 최적해와 일치할 때만 사용할 수 있다. 부분 문제들의 최적해의 집합이 전체 문제의 최적해와 일치 노드에 적힌 숫자의 합을 최대로 해서 S에서 E까지 가는 문제가 있다고 해보자. 위 그래프에서는 2개의 부분 문제...

백트래킹 백트래킹은 promising한 상태(state)만 탐색하는 탐색 알고리즘이다. 여기서 promising이란 유망한이라는 의미로, 현재 상태에서 해를 찾을 수 있는 가능성이 있다는 의미이다. 쉽게 말해서 현재 상태가 문제의 제약 조건을 전부 만족할 경우 promising하다고 말한다. 백트래킹은 기본적으로 완전 탐색이다. 하지만 둘의 결정적인...

너비 우선 탐색(BFS: Breadth First Search) BFS는 너비를 우선적으로 탐색하는 알고리즘으로 그래프 뿐만 아니라 트리, 배열 등에서도 사용할 수 있다. 진행 방식은 아래와 같다. 그래프와 트리에서는 정점으로, 배열에서는 칸으로 생각하면 된다. 시작 정점을 방문한다. 시작 정점과 연결된 정점을 전부 방문한다. 2번에...

깊이 우선 탐색(DFS: Depth First Search) DFS는 깊이를 우선적으로 탐색하는 알고리즘으로 그래프 뿐만 아니라 트리, 배열 등에서도 사용할 수 있다. 진행 방식은 아래와 같다. 그래프와 트리에서는 정점으로, 배열에서는 칸으로 생각하면 된다. 시작 정점을 방문한다. 시작 정점과 연결된 정점 중 하나를 방문한다. 방문할 수...

부분 합 부분 합 알고리즘은 배열의 각 index에 대해 배열의 시작부터 현재 index까지의 원소의 합을 구하는 것이다. 1차원 구간 합 배열 arr에 대한 구간 합 sum은 위 사진과 같고, 아래와 같이 정의할 수 있다. $sum[i] = \displaystyle\sum_{j=0}^{i} arr[j]$ 구현하는 방법은 다음과 같다. ...

최적화 문제를 결정 문제로 변환 파라메트릭 서치는 “최적화 문제”를 “결정 문제”로 바꾸고, 이분 탐색을 이용해서 푸는 알고리즘이다. 종만북의 “최적화 문제 결정 문제로 바꿔 풀기” 파트에서 파라메트릭 서치를 설명하면서 딱히 이름이 붙어 있지 않다고 하는 걸 보니 꽤 최근에 네이밍이 된 듯 하다. 최적화 문제와 결정 문제의 정의는 다음과 같다. ...

JUnit JUnit이란 자바용 단위 테스트(유닛 테스트) 프레임워크이다. 여기서 단위 테스트란 애플리케이션 코드 블록(일반적으로 함수 또는 메서드)가 개발자의 이론적 논리에 따라 예상대로 실행되는지 확인하는 코드 블록이다. JUnit을 사용하면 System.out.println()을 사용하여 콘솔로 확인하지 않아도 메소드가 의도대로 실행되는지 테스트...

문제 1167번: 트리의 지름 트리의 지름 트리의 지름이란 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 의미한다. 아이디어 트리의 지름을 구하는 알고리즘은 잘 알려진 웰노운 테크닉이다. 굉장히 간단한 알고리즘으로, 정리하면 다음과 같다. 임의의 한 정점 u에서 dfs를 통해 가장 멀리 있는 정점을 찾는다. 이 ...

이분 탐색 이분 탐색은 $O(logN)$의 시간복잡도를 가지는 탐색 알고리즘으로, 원소들이 정렬된 상태에서만 사용할 수 있다는 특징이 있다. 알고리즘 진행 방식은 다음과 같다. 첫 번째 원소를 low, 마지막 원소를 high로 설정한다. mid = (low + high) / 2 mid가 key보다 작은 경우, low = m...

웰노운 테크닉 웰노운(진짜 웰노운)이지만, 따로 작성하기엔 양이 적은 테크닉들 모음. 상하좌우 탐색 (x, y)를 기준으로 상하좌우 좌표를 생각해보자. x의 변화량은 {-1, 1, 0, 0}이고, y의 변화량은 {0, 0, -1, 1}이다. 이것을 dx, dy배열로 만들어서 상하좌우 좌표를 계산하는 테크닉이다. 2차원의 4방향뿐만 아니라, N차...

번외: FastIO #define FastIO ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); vector // 생성 vector<int> v; // int type vector 생성 vector<int> v(N); // N개의 크기를 가지는 vector 생성 ...

문제 백준 2505번: 두 번 뒤집기 아이디어 보드를 뒤집는 구간을 [L1, R1], [L2, R2]라고 했을 때, 구간의 관계에 따라 3가지 경우가 존재한다. 두 구간이 독립적인 경우 두 구간이 서로 독립적인 경우이다. 이 경우는 브루트포스로 [L1, R1], [L2, R2]을 전부 구할 수 있으므로 문제가 되지 않는다. 한 구간이 ...

문제 24896번: 르블랑의 트리 순회 아이디어 순회가 불가능한 조건 1번 노드를 루트 노드로 트리를 순회한다고 가정했을 때, 한 번에 체크포인트가 3개 이상 필요하면 순회가 불가능하다. 위와 같은 트리는 순회가 가능하지만 위와 같은 트리는 순회가 불가능하다. 1번 노드의 오른쪽 서브 트리를 탐색한 후 왼쪽 서브 트리를 탐색하기 위해서...

그래프 그래프는 정점과 간선으로 이루어진 객체 사이의 연결성을 표시하는 비선형 자료구조이다. 그래프 G는 G=(V, E)로 정의하는데, V는 정점의 집합, E는 간선의 집합을 의미한다. 그래프 용어 정점(Vertex) 객체를 의미한다. V(G)는 그래프의 정점의 집합을 의미한다. 간선(Edge) 객체를 연결하는 선이다. E(G)는 그래프의 ...

힙 힙은 중복된 키 값을 가질 수 있는 완전 이진 트리의 한 종류로, 원소들 중 가장 큰 값이나 가장 작은 값을 $O(logN)$에 찾기 위해 사용된다. 모든 노드에 대해 부모의 키 값 $\geq$ 자식의 키 값을 만족하는 힙을 최대 힙, 자식의 키 값 $\geq$ 부모의 키 값을 만족하는 힙을 최소 힙이라고 한다. 최대 힙에서의 최댓값과 최소...

레드-블랙 트리 레드-블랙 트리는 높이를 $Klog_2(N)$으로 유지하는 자가 균형 이진 트리이다. 모든 노드가 red 혹은 black 색깔을 가지고 있으며, 다른 트리들과 다르게 NIL(NULL)노드를 표시한다. 레드-블랙 트리의 성질 모든 노드는 red or black node이다. 루트 노드는 항상 black node이다. ...

AVL 트리 AVL트리는 좌우 서브 트리의 높이의 차이가 1 이하인 트리로, 자가 균형 이진 탐색 트리이다. AVL 트리는 왜 등장하게 됐을까? 트리의 좌우 균형이 잘 맞을수록 트리의 높이는 낮아진다. 이진 탐색 트리에서 트리의 높이가 최소일 때 탐색 연산의 시간 복잡도는 $O(logN)$이고, 최고일 때의 시간 복잡도는 $O(N)$이다. 완전 이진...

이진 탐색 트리 이진 탐색 트리(BST: Binary Search Tree)는 탐색을 위한 이진 트리 형식의 자료구조이다. 임의의 노드를 루트 노드로 하는 서브 트리에서 왼쪽 자식 노드는 루트 노드보다 작은 값이, 오른쪽 자식 노드는 루트 노드보다 큰 값이 들어간다. 이진 탐색 트리의 노드는 유일한 값을 가진다. 이진 탐색 트리 탐색연산 찾으...

이진 트리 이진 트리는 모든 노드가 2개 이하의 자식 노드를 가지고 있는 트리를 말한다. 즉, 모든 노드의 차수가 2이하이다. 이진 트리의 종류 Full Binary Tree 모든 노드의 차수가 0 혹은 2인 트리 Degenerate Binary Tree 모든 내부 노드의 차수가 1인 트리 Skewed ...

트리 트리의 정의 트리란 노드와 간선으로 이루어진 계층형 자료구조이다. 트리의 특징 트리는 N개의 노드와 N-1개의 간선으로 이루어져 있다. 사이클이 존재하지 않는다. 모든 노드는 서로 유일한 경로로 연결되어 있다. 모든 트리는 1개의 루트 노드를 갖는다. 루트 노드를 제외한 모든 노드는 1개의 부모 노드를 갖는다. ...

덱 덱(deque: double-ended queue)은 front, rear에서 삽입과 삭제가 전부 가능한 자료구조이다. 덱 ADT 데이터 element E 메소드 내용 add...

큐 큐는 먼저 추가된 데이터가 먼저 삭제되는 선입선출(FIFO: First Input FIrst Out)구조를 가지고 있는 자료구조이다. 큐의 종류에는 선형 큐와 원형 큐가 있다. 큐에서 삭제가 일어나는, 즉 가장 앞에 있는 곳을 front, 삽입이 일어나는 가장 뒤에 있는 곳을 rear이라고 한다. 큐 ADT 데...

스택 스택은 나중에 삽입한 데이터가 먼저 나오는 후입선출(LIFO: Last In First Out)의 구조를 가지고 있는 자료구조이다. 스택에서 삽입과 삭제가 일어나는 가장 위에 있는 곳을 top이라고 한다. 스택 ADT 데이터 element E ...

리스트 리스트란 순서를 가진 데이터들을 일자로 나열한 자료구조이다. 리스트의 종류에는 선형 리스트와 연결 리스트가 있다. 리스트 ADT 데이터 element E 메소드 내용 add(...

다중 상속 다중 상속이란 2개 이상의 클래스로부터 동시에 상속받는 것을 말한다. 자바에서는 다중 상속을 허용하지 않는다. C++에서는 다중 상속을 허용했었던 기억이 있는데, 왜 자바에서는 다중 상속을 허용하지 않을까? 자바는 왜 다중 상속을 허용하지 않을까? One reason why the Java programming language d...