mondegreen

동적계획법의 개념 그리지 알고리즘과 같이 최적화 문제를 해결하는 방법으로서 먼저 작은 부분의 문제들의 해를 구하고 이들을 이용하여 보다 큰 부분 문제를 해결한다. 이러한 방식으로 최종적으로 원래 주어진 문제를 해결하는 방법 동적계획법의 특징 1) 상향식 방법으로 접근한다. 2) (중복 부분문제 구조) 부분 문제 간 연관이 있어야만 적용 가능하다. 3) (중복 부분문제 구조) 모든 부분 문제는 한번만 계산한 뒤 결과를 저장하여 그 결과값만 재사용한다. (재계산 아님) 4) (최적화의 원칙) 전체 문제의 해가 최적이려면 그 해를 구성하는 작은 문제들의 해 역시 최적이어야 한다. 5) 수행 속도가 빠름 => 재귀와 달리 중복 계산이 없고, 반복문 사용으로 함수 호출없다. => 이 '중복 부분문제 구조 Over..

위상정렬의 개념 위상정렬이란 순서가 있는(즉, 방향이 있는) 작업을 차례로 진행해야 할 때 순서를 결정해주기 위해 사용하는 알고리즘이다. 사이클이 없는 방향 그래프(Directed Acyclic Graph)의 모든 노드를 주어진 "선행순서를 위반하지 않으면서" 나열하는 것이다. 예시: 대학교 선수과목, 공장의 작업 순서, 요리 순서... 특정 정점을 진행하기 위해 거쳐야 하는 정점의 수(간선으로 연결된)를 진입차수라 하고 특정 정점에서 넘어가야 할 다음 정점의 수를 진출차수라고 한다. 그 중 선행 조건이 되는 진입차수가 중요하다. 위상정렬의 특징 1) 하나의 방향그래프에서는 여러 위상 정렬이 가능하다. 2) 위상 정렬의 과정에서 선택되는 정점의 순서를 위상 순서라 한다. 3) 위상 정렬의 과정에서 그래프..

최단 경로의 개념 간선의 가중치가 있는 그래프에서 "두 정점 사이의 경로들 중"에 간선의 가중치의 합이 최소인 경로 1) 다익스트라(음의 가중치 허용하지 않음) 2) 벨만-포드(음의 가중치 허용함) 다익스트라의 개념 시작 정점에서 끝 정점까지 거리가 최소인 정점을 선택해가며 최단 경로를 구하는 방식 프림과 유사하나 당장의 가중치 한 개의 값이 아닌 "가중치의 합"을 고려해야 하는 알고리즘이다. 그래프에서 한 정점(노드)에서 다른 정점까지의 최단 경로를 구하는 알고리즘 중 하나이다. 이 과정에서 도착 정점 뿐만 아니라 모든 다른 정점까지 최단 경로로 방문하며 각 정점까지의 최단 경로를 모두 찾게 된다. 매번 최단 경로의 정점을 선택해 탐색을 반복하는 것이다. 다익스트라 동작 과정 1) 시작 정점 선택 2)..

최소 신장 트리의 개념 신장 트리 중에서 사용된 간선의 가중치의 합이 최소인 트리' 최소 신장 트리의 특징 1) 무방향 가중치 그래프 2) 그래프 가중치의 합이 최소 3) N개의 정점이 있는 그래프에 대해 반드시 N-1개의 간선을 사용해야 함 4) 사이클을 포함하면 안 된다 => 사이클 포함 = 불필요한 간선 존재 최소 신장 트리의 실 사용 비용이 최소가 되어야 하는 도로망, 통신망과 같은 다양한 분야 최소 신장 트리 구현 1) 크루스칼(Kruskal); 그리디 알고리즘의 한 종류 => 희소 그래프 인 경우 적합 간선을 하나씩 선택하며 MST를 찾는 알고리즘 (1) 모든 간선을 가중치에 따라 오름차순 정렬 (2) 가중치가 낮은 간선부터 선택하며 트리 증가 => 사이클이 존재*하면 그 다음 가중치를 가진 ..

서로소 집합의 개념 서로 중복 포함된 원소가 없는 집합들로서 즉, 교집합이 없는 집합이다. 집합에 속한 하나의 특정 멤버를 통해(→ 대표자; 대표자는 딱 하나 존재한다) 각 집합들을 구분한다. 특정 원소의 대표자를 가져왔을 때 동일하면 같은 집합에 속해있다고 판단할 수 있다. Union-Find의 개념 서로소 집합을 표편할 때 사용하는 알고리즘으로서 트리를 이용해 구현 가능 ; 그밖에 비트 벡터, 배열, 연결리스트를 이용해서도 구현 가능 Union-Find의 연산 연산1) Make-Set(x): 집합 생성 역할(x라는 원소를 대표자로 만든다) 연산2) Find-Set (x): x의 대표자를 가져오는 역할 (부모가 아님) 연산3) Union(x, y): x와 y 두개의 원소를 하나의 그룹으로 만드는 역할 ..

깊이우선탐색의 개념 1) 루트 노드(또는 임의의 노드)에서 시작해 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 2) 직전의 갈림선이 있는 정점을 되돌아가야 하기 때문에 재귀적으로 구현하거나, 후입선출 구조의 스택을 활용 ; 시작 정점의 한 방향으로 갈 수 있는 가장 깊은 경로까지 탐색하다가 끝을 만나면 직전의 갈림선이 있는 정점으로 돌아와 다른 방향의 정점으로 탐색을 계속 반복하여 모든 정점을 탐색하는 방법 깊이우선탐색의 특징 1) 자기 자신을 호출하는 순환 알고리즘의 형태이다. 2) 위와 같은 이유로 방문한 노드는 그 여부를 반드시 검사해야 무한 루프에 빠지지 않는다. 3) 전위 순회, 중위 순회, 후위 순회 모든 형태의 트리 순회는 모두 DFS의 한 종류이다. 4) 인접 행렬 또는 ..

너비우선탐색 개념 탐색 시작점의 인접한 정점들을 먼저 모두 차례로 방문한 후, 방문했던 정점을 시작점으로 하여 그 시작점과 인접한 정점을 다시 차례로 방문하는 방식을 말한다. 이 때 방문했던 인접 정점도 순서대로 다시 인접 정점을 탐색해야 하므로 선입선출 형태의 자료구조인 Queue(큐)를 활용한다. 방문 여부 검사를 통해 무한루프에 빠지지 말아야 한다. 너비우선탐색 특징 1) 시작 노드로부터 단계적으로 거리에 따라 탐색한다. 2) 재귀적으로 작동하지 않는다. 3) 프림 및 다익스트라 알고리즘과 유사하다. 구현 방식1) 인접행렬 두 정점이 연결되어 있는 여부를 한 눈에 확인 가능하나, 시간도 많이 사용하고 메모리 낭비가 심하다. 들어오고 나가는 간선이 한 눈에 보이기 때문에 간선이 많을 때(밀집 그래프)..

그래프의 개념 - 아이템들과 이들 사이의 연결관계를 표현하는 정점들의 집합과 이들을 연결하는 간선들의 집합으로 구성된 자료 구조 - 선형 자료구조나 트리 자료구조로 표현하기 어려운 N:N 관계를 가진 원소들을 표현하기에 편리함 - 정점: 그래프의 구성요소로서 하나의 연결점 - 간선: 두 정점을 연결하는 선 - 차수: 정점에 연결된 간선의 수 그래프의 종류 무향 그래프 유향 그래프 가중치 그래프 사이클 없는 방향 그래프(Directed Acyclic Graph) 완전 그래프: 정점들에 대해 가능한 모든 간선을 가진 그래프 부분 그래프: 원래 그래프에서 일부의 정점이나 간선을 제외한 그래프 그래프의 표현 1) 인접행렬: 2차원 배열 이용하여 간선 정보 저장 희소 그래프인 경우, 즉 정점 수 대비 간선 수가 ..

백트래킹의 개념 해를 찾는 도중 해가 아니면, 되돌아가서 다시 해를 찾아가는 방법 => 모든 가능한 경우의 수 중 특정한 조건을 만족하는 경우만 살펴보는 방법 => 만족하지 않는 것이 확인되면 부모 노드로 돌아가 다음 자식 노드를 확인한다. => 가지치기라고 말하는데 불필요한 부분을 굳이 연산하지 않아 효율적이다. => 최악의 경우에는 여전히 지수함수 시간을 요할 수 있어 반드시 답을 얻는 것은 아님 깊이우선탐색(DFS) + 가지치기(Pruning) DFS만으로는 답이 될 수 없는 경우도 모두 리프까지 탐색하므로 이 때 특정 조건문을 작성하여 조건에 해당하지 않으면 해당 경로를 가지는 않는 가지치기 방식을 적용해 백트래킹을 구현할 수 있다. 백준 9663 import java.util.Scanner; p..

분할정복의 개념 1) 분할: 해결할 문제를 여러 개의 작은 부분으로 나누기 2) 정복: 나눈 작은 문제를 각각 해결하기 => 이 때 나눈 작은 문제가 더 나눠질 수 있다면 다시 나눈다. 3) 통합: 해결한 해답을 모으기 분할정복의 응용 1) 병합 정렬(top-down 방식) - 안정 정렬 (1) 데이터 집합의 크기가 0 또는 1인지 확인 => true면 정렬 (2) 데이터 집합을 반으로 분할 (3) 나눈 집합을 하나의 집합으로 병합 (4) 최소 크기가 될 때까지 분할 (5) 조각난 데이터 집합을 정렬하며 병합(재귀 호출 이용) 시간 복잡도 공간 복잡도 O(nlogn) O(n) 2) 퀵정렬 - 불안정 정렬 (1) 데이터 집합의 크기가 0 또는 1인지 확인 => true면 정렬 (2) 데이터 집합을 반으로 ..