반응형 분류 전체보기110 파라메트릭 서치(Parametric Search) 파라메트릭 서치(Parametric Search) 파라메트릭 서치란? - 문제를 최적화 하는 방법 중 하나. - 특정 값을 구하라는 문제(최대 값, 최소 값을 구하라)를 결정 문제로 바꿔서 생각하는 방법이다. - 특정 조건에 맞는 최대 값을 구하라 => 값 X가 특정 조건에 맞는가? - 이분 탐색을 이용하여 알맞는 X값을 찾는다. 탐색 알고리즘 - 이분 탐색(Binary Search) 이분 탐색(Binary Search) 이분 탐색이란? - 정렬되어 있는 데이터에서 원하는 값을 찾을 때 효율적으로 사용할 수 있는 알고리즘이다. - 순차 탐색 보다 훨씬 좋은 성능을 보인다. - n개의 데이터 9327144.tistory.com - 시간 복잡도 : O(MlogN) M : 값 X가 주어졌을 때 조건에 맞는지 .. 2021. 6. 30. 위상 정렬(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. 이전 1 ··· 12 13 14 15 16 17 18 ··· 28 다음 반응형
