반응형 알고리즘/알고리즘 이론23 파라메트릭 서치(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. 최소 공통 조상 찾기(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 2 3 4 ··· 6 다음 반응형
