본문 바로가기

CS/알고리즘5

[알고리즘] 이분탐색 헷갈리지 않기 저는 이분탐색 문제를 풀 때마다 헷갈립니다. . 탈출 조건 중 어느 걸 선택해야 할지, while 문도 범위를 매번 정확히 하지 않은채 문제를 풀곤 했는데요. 오늘 헷갈리지 않게 구현하는 방법을 정리하려고 합니다 ! 이분탐색 결정 문제의 답이 이분적일 때 사용할 수 있는 탐색 기법입니다. 이 때, 결정 문제란 답이 Yes or No인 문제를 말합니다. 예를 들어, 1 ~ 50까지의 오름차순 정렬된 카드 더미(v[])에서 val번 카드를 찾는 문제를 예시로 들게요. 이 경우, 결정 문제를 "v[i] >= val인가 ?"로 잡으면 결정 문제는 i가 증가함에 따라 F, F, ... F, T, T, ... 와 같이 분포하게 됩니다. 이 때, 찾고자 하는 값은 처음으로 v[i] >= val인 지점, 즉 처음 결정.. 2022. 11. 25.
[알고리즘] 다익스트라 + 플로이드 워샬 구현 (Swift) 합승 택시 요금 문제를 풀다가 다익스트라랑 플로이드 워샬에 대해 정리하고 가려고 합니다 . . 문제는 가중치 있는 그래프가 주어지고, 시작점[s]으로부터 특정 한 지점[i]을 거쳐 결국 다른 두 개의 도착지[a, b]에 도착하는 최단거리를 구하면 되는 문제입니다. 다익스트라 가장 먼저 다익스트라 풀이를 생각했습니다. 다익스트라는 최단거리를 갱신해나가는 알고리즘으로 일종의 dp 방식입니다. 코드로 구현하는 게 오늘 포스팅의 목적이기 때문에 알고리즘은 간단하게 설명할게요 . . ! 1. 최단 거리 저장하는 배열 dist[]를 INF로 초기화 2. 시작점부터 인접한 노드들 돌면서 최단 거리 갱신 - priorityQueue 사용하여 cost 가장 낮은 노드순으로 pop하기 - dist[다음노드] > 현재 거리.. 2022. 11. 24.
[알고리즘] 분할정복(divide and conquer) 분할정복이란 ? 분할정복 알고리즘은 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법입니다. 대표적인 예로는 정렬 알고리즘 중 퀵 정렬이나 합병 정렬과 이진 탐색, 선택 문제, 고리 푸리의 변환(FTT) 문제들이 대표적입니다. 정렬 알고리즘 선택 정렬과 삽입 정렬의 최대 실행시간은 O(n^2)로 입력하는 배열의 크기가 크다면 정렬하는데 시간이 오래 걸릴 수 있습니다. 반면 분할정복 알고리즘을 사용하는 합병정렬의 실행시간은 O(nlogn)으로 퀵 정렬은 최대 O(n^2)지만 최선이나 평균의 경우 O(nlogn)으로 비교적 빠른 시간을 갖는 것을 볼 수 있습니다. 정렬 알고리즘 최대 실행 시간 최소 실행 시간 평균 실행 시간 선택 정렬 O(n^2) O(n^2) O(n^2) 삽입 정렬 .. 2022. 9. 21.
[알고리즘] 백트래킹 (Backtracking) 백트래킹(Backtracking)이란 ? 해를 찾는 도중 해가 아니어서 막히면 되돌아가서 다시 해를 찾아가는 기법을 말합니다. 최적화 문제와 결정 문제를 푸는 방법이 됩니다. 깊이 우선 탐색 (DFS) vs. 백트래킹 (Backtracking) DFS DFS는 가능한 모든 경로를 탐색합니다. 그러므로 불필요한 경로를 사전에 차단하는 등의 행동이 없으므로 경우의 수를 줄일 수 없습니다. 따라서 N! 가지의 경우의 수를 가진 문제는 DFS로 처리가 불가능합니다. 백트래킹 해를 찾아가는 도중 지금의 경로가 해가 될 것 같지 않다면 그 경로를 더 이상 가지 않고 되돌아갑니다. 이를 가지치기라고 하는데 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 의미입니다. 하지만 만약 N! 의 경우의 수를 가진 문제에서.. 2022. 9. 14.
[알고리즘] 이분탐색 (Binary Search) 이분 탐색이란 ? 정렬된 배열에서 원하는 값의 존재 여부 및 위치를 찾는 알고리즘으로 탐색할 때마다 검사 범위가 절반으로 줄어듭니다. 시간 복잡도 : O(log N) 이분 탐색 과정 1. 검사 범위에서 중간 값(mid)를 선택해 찾고자 하는 값(target)이 같은지 확인 2. 찾고자 하는 값이라면 해당 값 반환 3. 찾고자 하는 값보다 작다면 (mid target), high = mid - 1 5. 1 ~ 4번을 (low = M) {// 집에 가져가려하는 길이 M보다 큰 경우 ans = mid; low = mid + 1;// 덜 가져가야하므로 더 크게 } else {// 반대의 경우 high = mid - 1;// .. 2022. 9. 7.

티스토리툴바