반응형 알고리즘91 위상 정렬(Topological Sort) 위상 정렬(Topological Sort) 위상 정렬이란? - 정점의 순서가 주어졌을 때 역행하지 않고 정상적으로 정렬하는 방법. - 방향이 존재하는 간선들이 주어졌을 때 역행하지 않고 정렬 하는 방법. - 시간 복잡도 : O(V+E) 위상 정렬 방법 - 0. indegree[i] : i번째 정점으로 들어오는 간선의 개수 result : 위상 정렬의 결과 값 - 1. 가장 먼저 올 수 있는 정점들을 먼저 선택하여 queue에 넣는다. 위상 정렬에서 가장 먼저 올 수 있는 정점은 들어오는 간선이 없는 정점이다. - 2. queue에 있는 정점들을 탐색하면서 해당 정점들과 연결된 정점들의 indegree값을 하나씩 감소시킨 후 위상 정렬 결과 값인 result에 넣어준다. - 3. queue에 값이 존재하면.. 2021. 6. 30. Java 코테용 정리 자바는 원시 타입을 제외하면 모두 참조 타입이다. [ 입출력 ] 테스트 케이스 이용 System.setIn(new FileInputSteam("input.txt")) 테스트 케이스 하나하나 입력하지 않고, 파일로 실행하기 문자열 입력 받을 때 Scanner가 아니라 BufferedReader를 사용하자. import java.io.*; Scanner가 공백, 개행 시 나눠주는 것이 편하지만 느리다. BufferedReader는 하나 하나 사용자가 나누어주어야 한다. // split 보다 BufferedReader가 더 빠르다. StringTokenizer를 이용한다. 예시 BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); .. 2021. 4. 3. 최소 공통 조상 찾기(Lowest Common Ancestor) 최소 공통 조상 찾기(LCA) LCA란? - 트리에서 두 노드 u, v가 가지는 최소 공통 조상을 찾는 알고리즘 - 최소 공통 조상을 이용하여 해당 정점들 간의 최단 거리를 빠르게 계산할 수 있다. LCA 동작 방식 - 0. 각 정점마다 부모의 정보를 가진 배열, 정점의 높이를 저장한 배열을 만든다. - 1. 두 정점 u, v의 높이 Hu, Hv를 구한다. - 2. 두 정점의 높이가 다르다면 더 큰 높이의 정점은 현재 정점을 부모의 정점으로 변경하여 높이를 낮춘다. 이 과정을 높이가 같아질 때 까지 반복한다. - 3. 정점들의 높이가 같아지면, 하나씩 부모로 이동하며 같은 원소가 나오는지 판단한다. 이 과정을 같은 정점이 될 때 까지 반복한다. - 4. 3번까지의 과정을 통해 얻은 정점이 두 정점 u, .. 2021. 3. 26. 최장 증가 부분 수열(Longest Increasing Subsequence) 최장 증가 부분 수열(LIS) LIS란? - 임의의 수열이 주어졌을 때 이 수열의 부분 수열 중 원소가 증가하는 부분 수열을 만든다. 이 부분 수열 중 길이가 최장인 수열을 의미한다. - 부분 수열이란, 원래의 수열 중 임의의 원소를 삭제한 수열을 말한다. - Ex) 원래 수열 : 1 9 8 7 5 2 부분 수열 : 1 8 7 2 / 9 5 2 / 1 5 등 증가 부분 수열 : 1 9 / 1 8 / 1 7 등 LIS 알고리즘1 - 완전 탐색 - 수열의 원소를 하나씩 탐색하며, 해당 원소가 포함이 될 지 안될 지를 선택하며 탐색한다. - 원소가 N개인 경우 시간 복잡도는 O($2^N$)가 되기 때문에 매우 비효율적이다. LIS 알고리즘2 - DP - 수열의 원소를 하나씩 탐색하며, 해당 수열이 마지막으로 .. 2021. 3. 25. 이전 1 ··· 11 12 13 14 15 16 17 ··· 23 다음 반응형
