LIS(최장 증가 부분 수열)

Longest Increasing Subsequence 수열 수열(數列)은 수 또는 다른 대상의 순서 있는 나열이다. 나열 순서를 생각해야 하고 중복이 허용된다는 점에서 집합과 구분된다. 부분 수열 부분 수열이란, 나열 순서가 변하지 않은 채로 일부 항을 제거해 얻는 새로운 수열을 의미한다. 최장 증가 부분 수열 부분 수열 중 오름 차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열이라고 한다. 정의 최장 증가 부분 수열 문제는 동적 계획법으로 풀 수 있는 유명한 알고리즘 문제이다. 예를 들어 다음과 같은 수열이 주어졌다고 하자. 5 3 7 8 6 2 9 4위 수열에서 특정 위치에 있는 몇개의 수를 제거해 부분 수열을 만들 수 있는데, 그 중에서 최장 증가 부분 수열을 구해보자. ✔ 첫 번째 조건은 나..

조합(Combination)

조합(Combination) 이번 시간에는 DFS 로 조합을 구현하는 방법을 배워보자. N 명 중 R 명을 뽑는 경우의 수 nCr 은 n 개의 원소를 갖는 집합에서 r 개의 부분 집합을 고르는 경우의 수를 의미하므로 부분 집합과도 관련이 있다. 구현 // 조합(Combination) : nCr = n-1Cr-1 + n-1Cr // n 명 중에서 r 명을 뽑는 경우 // 5C3 = 4C2 + 4C3 public class Main { static int[][] store = new int[35][35]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); System.out.println(combinationByDfsW..

부분 집합 구하기(DFS)

부분 집합 구하기(DFS) 이번 시간에는 DFS 를 이용한 부분 집합을 구하는 방법에 대해서 배워보자. 문제 자연수 N 이 주어지면 1 ~ N 까지의 원소를 갖는 집합의 부분집합을 모두 출력하는 프로그램을 작성하세요. 단, 공집합은 출력 하지 않습니다. 입력 3 출력 1 2 3 1 2 1 3 1 2 3 2 3$$원소의 개수가 N 인 부분집합의 개수 : 2^n$$ $$공집합을 제외한 부분집합의 개수 : 2^n-1$$ 루트 노드부터 보면, 1을 포함하는 경우 하지 않는 경우로 나누고, 2 depth 에서는 원소 2를 포함하는 경우 하지 않는 경우로 나눌 수 있다. 따라서, N 만큼의 반복을 돌고 depth 가 N + 1 이 되는 경우 종료된다. 구현 public class Main { private stat..

깊이 우선 탐색(DFS)

깊이 우선 탐색(DFS) DFS(Depth-First Search) 는 깊이 우선 탐색이라고 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. DFS 는 Stack 자료구조를 사용하며 Stack 을 이용하기 때문에 재귀 함수를 이용하면 쉽게 DFS 구현을 할 수 있다. 재귀와 Stack 에 대해서 잘 모르겠으면 해당 링크를 통해서 배우고 오자. 동작 과정 Step1 Step1. 시작 노드를 스택에 넣고 방문 처리한다. Step2 Step2. 방문하지 않은 인접 노드 중에서 번호가 가장 낮은 곳을 방문하고 해당 노드를 스택에 넣어 방문 처리 한다. Step3 Step3. 위 과정을 반복한다. 구현 public class Main { public static boolean[] visited ..

위상 정렬

위상 정렬(Topology Sort) 위상 정렬(Topology Sort)은 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘이다. 즉, 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열 하는 것이다. 사용 예시 선수과목을 고려한 학습 순서 설정 A 과목을 수행하고 B 과목을 수강하는 것을 권장할 때, A, B 를 각각 노드로 표현하고 A -> B 로 가는 방향을 갖는 간선을 그린다. 즉, 그래프 상에서 선, 후 관계가 존재하면 위상 정렬을 수행하여 모든 선후 관계를 지키는 전체 순서를 계산할 수 있다. 진입 차수(Indegree) 진입 차수(Indegree)란 특정한 노드로 들어오는 간선의 개수를 의미한다. A -> B, B -> C, D -> B 의 ..

신장 트리와 크루스칼 알고리즘

신장 트리(Spanning Tree)와 크루스칼 알고리즘(Kruskal Algorithm) 신장 트리(Spanning Tree)와 크루스칼 알고리즘(Kruskal Algorithm)에 대해서 배워보자. 신장 트리 신장 트리(Spanning Tree)란 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다. 크루스칼 알고리즘 크루스칼 알고리즘은 최소 신장 트리(Minimum Spanning Tree, MST)를 구하기 위해서 사용되는 알고리즘 이다. 크루스칼 알고리즘은 그리디(Greedy) 알고리즘으로 분류된다. 크루스칼 알고리즘을 사용하면 가장 적은 비용으로 모든 노드를 연결할 수 있다. 크루스칼 알고리즘을 구현할 때에는 Union-Find 알고리즘을 사용하므로,..

서로소 집합

서로소 집합(Disjoint Sets) 서로소 집합(Disjoint Sets)은 공통 원소가 없는 두 집합을 의미한다. 예를 들면 {1, 2}와 {3, 4} 가 서로소 집합에 해당된다. 서로소 집합 자료구조란 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조라고 할 수 있다. 서로소 집합 자료구조는 union 과 find 이 2개의 연산으로 조작할 수 있다. union(합집합) 연산 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산 find(찾기) 연산 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산 서로소 집합 자료구조는 합집합과 찾기 연산으로 이루어져 있다. 따라서 union-find 자료구조라고도 한다. 서로소 집합 자료구조 서로소 집합 자료구조를 구현할 때는 트..

플로이드 워셜 알고리즘

플로이드 워셜(Floyd Warshall) 플로이드 워셜 알고리즘(Floyd-Warshall Algorithm)은 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야하는 경우에 사용할 수 있는 경우이다. 다익스트라 알고리즘에서는 한 지점에서 다른 모든 지점까지의 최단거리인 반면, 플로이드 워셜은 모든 지점 to 모드 지점인 것이다. 플로이드 워셜 알고리즘은 2차원 리스트에 최단 거리 정보를 저장한다. 노드의 개수가 N 개일 때 알고리즘상으로 N 번의 단계를 수행하며, 단계마다 O(N^2)의 연산을 통해 현재 노드를 거쳐가는 모든 경로를 고려한다. 따라서 총 시간 복잡도는 O(N^3)이다. 플로이드 워셜 알고리즘을 사용해야 하는지에 대한 판단 기준 가중치 방향 그래프가 주어진다. A -> K ->..