반응형 Computer Science/알고리즘21 투포인터 알고리즘(Two Pointers Algorithm) 이번에 배워볼 알고리즘은 투포인터 알고리즘이다. 요즘 코딩 테스트에서 투포인터 알고리즘이 자주 나와서 한번 짚고 넘어가려고 한다. C언어를 배웠다면 포인터라는 개념은 어느 정도 알고 있을 것이다. 투포인터 알고리즘은 C언어의 포인터는 아니지만 비슷한 개념으로 어떤 위치?를 가리키는 2개의 포인터를 적절히 활용하여 원하는 값을 얻어내는 방법이다. 투포인터 알고리즘 또한 알고리즘이기보단 기법에 가깝기 때문에 예시를 통해 직접 겪어보는 것이 좋다. 투포인터 알고리즘을 이해하기 위한 대표적인 예시로 부분합이라는 문제가 있다. 우리도 이 문제를 통해 투포인터 알고리즘을 이해해 보자. 부분합이라는 문제는 리스트에 1부터 N까지 수열이 주어지면 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 .. 2021. 7. 4. 탐욕(그리디) 알고리즘(Greedy Algorithm) 이번에 배워볼 알고리즘은 탐욕(그리디) 알고리즘(Greedy Algorithm)이다. 탐욕 알고리즘도 다이나믹 프로그래밍처럼 알고리즘이라기보다는 문제를 해결하기 위한 기법이다. 탐욕이란 뜻은 다들 알고 있을 것이다. 탐욕 알고리즘은 말 그대로 미래는 생각하지 않고 현재 주어진 상황에서 최선의 선택을 하는 것을 의미한다. 탐욕 알고리즘은 다이나믹 프로그래밍보다 빠른 시간 내에 정답에 가까운 근삿값을 구할 수는 있지만 구해낸 답이 다이나믹 프로그래밍처럼 항상 최적해를 보장해 주지 않는다. 왜냐하면 매 순간 최선의 선택이 최종적으로 최선의 선택이 된다고 보장할 수 없기 때문이다. 간단하게 지금 당장 100원을 주는 것과 1분 후 1억을 주는 상황이 있다고 생각해 보자. 만약 탐욕 알고리즘으로 접근한다면 우리.. 2021. 7. 4. 다이나믹 프로그래밍(Dynamic Programming) : 동적계획법 이번에 배워볼 알고리즘은 다이나믹 프로그래밍(Dynamic Programming)이다. 다이나믹 프로그래밍은 알고리즘이라기보다는 문제 해결 패러다임에 가깝다고 할 수 있다. 이게 무슨 말이 나면 이전에 배운 다익스트라를 생각해 보자. 다익스트라는 한 정점에서 다른 정점으로 가는 최단 경로를 구하는 알고리즘이었다. 다익스트라에서 최단 경로를 어떤 식으로 갱신했는지 기억해보자. 우리는 다익스트라에서 이미 저장된 현재의 최소 비용과 간선을 통한 새로운 비용을 비교해서 최소 비용을 갱신하였다. 이미 구한 값과 비교하는 방법이 바로 다이나믹 프로그래밍이다. 다이나믹 프로그래밍이란 어떤 문제에서 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 구하는 알고리즘 설계 기법이다. 간.. 2021. 7. 4. 위상 정렬(Topological Sort) 이번에 배워볼 알고리즘은 위상 정렬(Topological Sort) 알고리즘이다. 위상 정렬은 순서가 정해져 있는 작업들을 차례대로 수행해야 할 때, 그 순서를 결정해 주는 알고리즘이다. 간단한 예시를 들어본다면 라면을 끓이기 위해서는 물이 먼저 끓어야 한다. 이처럼 작업의 순서가 정해져 있는 그래프에서 작업의 순서를 정렬해 주는 알고리즘이다. 단, 위상 정렬은 DAG에서만 적용이 가능하다. DAG는 Directed Acyclic Graph의 줄임말로써 방향 사이클이 없는 방향 그래프를 뜻한다. 왜냐하면 방향 사이클이 존재한다면 시작 지점을 정할 수 없기 때문이다. 위와 같은 그래프는 DAG가 아니다. 1-2-3-1로 이루어지는 방향 사이클이 존재하기 때문이다. 1번 작업을 수행하기 위해선 3번 작업이.. 2021. 7. 4. 프림 알고리즘(Prim Algorithm) 이번에 배워볼 알고리즘은 크루스칼 알고리즘(Kruskal Algorithm)과 같이 최소 비용 신장 트리(MST)를 구하는 프림 알고리즘(Prim Algorithm)이다. 크루스칼 알고리즘은 간선 선택을 기반으로 하는 알고리즘이었다면, 프림 알고리즘은 정점 선택을 기반으로 하는 알고리즘이다. 또한, 크루스칼 알고리즘은 이전 단계에서 만들어진 신장 트리와는 상관없이 무조건 최소 간선만을 선택하는 방법이라면, 프림 알고리즘은 이전 단계에서 만들어진 신장 트리를 확장하는 방식이다. 프림 알고리즘은 그리디 알고리즘에 속한다. 그 이유는 추가할 새로운 정점을 선택할 때 최소 비용을 가지는 간선을 선택하기 때문이다. 프림 알고리즘의 동작 원리는 다음과 같다. 시작 정점을 선택한다. 현재 구성된 신장 트리에 속.. 2021. 7. 4. 크루스칼 알고리즘(Kruskal Algorithm) 최소 비용 신장 트리(MST)를 구하는 알고리즘은 크루스칼 알고리즘(Kruskal Algorithm)과 프림 알고리즘(Prim Algorithm)이 존재한다. 이번에 배워볼 알고리즘은 이전에 배운 합집합 찾기(Union Find)에서 언급한 크루스칼 알고리즘(Kruskal Algorithm)이다. 크루스칼 알고리즘은 그리디 알고리즘이라고 불린다. 그 이유는 추가할 새로운 간선을 선택할 때 최소 비용을 가지는 간선을 선택하기 때문이다. 우선 크루스칼 알고리즘을 배우기 전에 신장 트리가 무엇인지에 대해서 알고 넘어가자. 신장 트리란 그래프 내의 모든 정점을 포함하는 트리를 뜻한다. 신장 트리는 트리의 특수한 형태이므로 모든 정점들이 연결되어 있어야 하고 사이클을 포함해서는 안 된다. 따라서 신장 트리는 .. 2021. 7. 4. 합집합 찾기(Union Find) 이번에 배워볼 알고리즘은 합집합 찾기(Union Find) 알고리즘이다. 서로소 집합(Disjoint Set) 알고리즘이라고도 불리는 이 알고리즘은 그래프 상의 두 개의 노드가 같은 그래프에 속하는지를 판별하기 위해 사용되는 알고리즘이다. 다음에 배울 최소 비용 신장 트리(MST)를 구성하는 알고리즘 중 하나인 크루스칼(Kruskal) 알고리즘이 합집합 찾기 알고리즘을 응용한 알고리즘이다. 합집합 찾기 알고리즘의 원리는 다음과 같다. 자신의 부모 노드를 저장하는 1차원 배열을 선언 후 각 정점의 부모를 자신을 가리키도록 초기화한다. 두 개의 노드를 선택하여 Union 연산을 수행하면 두 개의 노드의 부모를 하나의 노드로 통일한다. 이때 더 작은 번호를 가리키도록 부모를 통일한다. 두 개의 노드를 선택.. 2021. 7. 3. 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm) 이번에 배워볼 알고리즘은 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)이다. 이전에 배운 다익스트라, 벨만-포드 알고리즘은 한 정점에서 다른 정점으로 가는 최단 경로를 구하는 알고리즘이었다면, 플로이드-워셜은 모든 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘이다. 플로이드 워셜 알고리즘은 벨만-포드 알고리즘처럼 음의 간선이 존재하여도 모든 최단 경로를 구할 수 있다. 물론 음의 사이클이 존재하면 불가능하다. 또한, 이전에 저장해놓은 최단 경로를 이용해서 새로운 최단 경로로 갱신하는 과정에서 플로이드 워셜 알고리즘 역시 다이나믹 프로그래밍이라고 할 수 있다. 플로이드 워셜 알고리즘의 핵심은 간단하다. 이전에 다익스트라나 벨만 포드 알고리즘에서 정점 A에서 정점 C까지 가.. 2021. 7. 3. 벨만-포드 알고리즘(Bellman-Ford Algorithm) 이번에 배워볼 알고리즘은 벨만 포드 알고리즘(Bellman-Ford Algorithm)이다. 이 알고리즘 또한 이전에 배운 다익스트라 알고리즘처럼 그래프에서 한 정점에서 다른 모든 정점으로 가는 최단 경로를 구할 수 있는 알고리즘이다. 벨만 포드 알고리즘은 다익스트라 알고리즘보다 시간이 더 걸리지만 음의 간선이 존재해도 최단 경로를 찾을 수 있는 알고리즘이다. 벨만 포드 알고리즘은 다이나믹 프로그래밍이라고 할 수 있다. 그 이유는 매번 저장해놓은 최소 비용을 이용해서 새로운 최소 비용으로 갱신하기 때문이다. 벨만 포드 알고리즘이 다익스트라 알고리즘보다 시간이 오래 걸리는 이유는 다익스트라는 최소 비용을 가지는 간선만 우선적으로 뽑으면서 경우의 수를 줄여가며 비용을 갱신하였다. 하지만 벨만 포드 알고리즘.. 2021. 7. 3. 이전 1 2 3 다음 반응형
