Algorithm (8) 썸네일형 리스트형 플로이드-워셜 (Floyd-Warshall) 1. 플로이드-워셜 알고리즘 다익스트라 알고리즘은 '한 특정 지점에서 다른 특정 지점까지의 최단경로를 구할때' 쓰는 알고리즘이다. 이와는 다르게 플로이드-워셜 알고리즘은 '모든 지점에서 다른 모든지점까지의 최단경로를 모두 구할때' 쓰는 알고리즘이다. 2. 플로이드-워셜 알고리즘의 시간복잡도 생각보다 단순하게도 O(N^3) 의 시간 복잡도를 가진다. 다만 N^3 이라는 것 자체가 N이 커질수록 기하 급수적으로 커지기 때문에 노드의 개수가 N개일때, 이 N의 제한이 조금 작을때만 사용이 가능하다. 플로이드-워셜 알고리즘은 다익스트라 알고리즘과는 다르게 다이나믹 프로그래밍의 일부로 볼 수 있다. 노드의 개수가 N개 라고 할때, N번 만큼의 단계를 반복하며 '점화식에 맞게' 2차원 리스트(배열) 을 갱신하기 때.. Dijkstra (다익스트라) 2 이 글에서는 개선된 다익스트라 알고리즘을 알아 보겠다. 간단히 구현했던 다익스트라 알고리즘의 시간복잡도는 노드의 개수가 V개 일때 O(V^2) 로 표현된다고 했다. 이는 노드의 개수가 많아질 수록 굉장히 오래걸리므로 개선시켜야 한다. 간단한 다익스트라 알고리즘은 최단거리가 가장 짧은 노드를 찾기 위해 매번 최단거리 테이블을 선형적으로 탐색했다. 그러니까 처음부터 하나씩 다 계산해서 최단거리를 찾았다는 것이다. 이것은 특정 자료구조를 활용하면 개선시킬 수 있다. 개선된 다익스트라 알고리즘에서는 힙(heap) 을 사용한다. 이를 사용하면 선형적으로 탐색했던 이 부분을 개선시켜 로그의 시간으로 사용할 수 있다. O(N) 에서 O(logN)이 되는 것이다. 1. 힙 (Heap) 힙은 우선순위 큐(Priority.. Dijkstra (다익스트라) 1. 최단 경로 알고리즘 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. 최단 경로 알고리즘에는 크게 3가지가 있다. 다익스트라(Dijkstra) 알고리즘, 플로이드-워셜(Floyd-Warshall), 벨만 포드(Bellman Ford) 알고리즘이 있다. 이 중 다익스트라 알고리즘을 알아보자. 2. 다익스트라 알고리즘 다익스트라 알고리즘은 그래프에서 여러개의 노드가 있을 때, 특정 노드에서 출발하여 다른 노드로 가는 각각의 최단경로를 구해주는 알고리즘이다. 다익스트라 알고리즘은 '음의간선' 이 없을 때 정상적으로 작동한다. 다익스트라 알고리즘은 기본적으로 그리디 알고리즘으로 분류되기도 하는데 그이유는, 매번 '가장 비용이 적은 노드' 를 선택해서 임의의 과정을 반복하기 때문이다. - 출발 노드를 설정한다.. 정렬(Sorting) 정렬(Sorting)이란 데이터를 특정 기준에 따라서 순서대로 나열하는 것이다. 예를들어 오름차순, 내림차순 등이 있다. 정렬 알고리즘 중에 유명한 것은 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬등이 있다. 1. 선택 정렬 7 5 9 0 3 1 6 2 4 8 위와 같은 상태의 데이터가 있다고 가정해보자. 선택정렬은 데이터들 중 가장 작은 데이터를 선택해 맨앞의 데이터와 바꾸고, 그다음 작은 데이터는 두번째 데이터와 바꾸고... 의 과정을 반복하는 것이다. 일단 가장 작은 데이터를 찾는다. 그리고 맨앞의 7과 바꾼다. 0 5 9 7 3 1 6 2 4 8 이제 0은 정렬이 된 상태이다. 이제 두번째로 작은 값인 1을 두번째 값과 바꾼다. 0 1 9 7 3 5 6 2 4 8 0과 1은 정렬이 된 상태이다... Greedy (탐욕법) 그리디 알고리즘은 어렵지 않으면서도 가장 많이 코테에 출제된다고 한다. 그만큼 중요하기도 하고, 많이 풀어봐야하는 문제 유형이다. 그리디 알고리즘의 핵심은 '현재 상황에서 지금 당장 좋은 것만 고르는 방법' 이다. 이 알고리즘은 현재 가장 좋아보이는 방법만을 선택하며, 현재의 선택이 나중에 미칠 영향은 고려하지 않는다. 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로, 문제에서 '가장 큰 순서대로', '가장 작은 순서대로' 와 같이 은연중에 기준을 제시해준다. 이런것을 보고 그리디 알고리즘 사용 문제구나! 눈치 챌 수 있으면 된다. ++그리디 알고리즘은 주로 정렬 알고리즘과 자주 같이 출제 된다. 예시로 거스름돈 문제를 들겠다. 문제: 카운터에는 500원,100원,50원,10원 짜리 동전.. DP (Dynamic Programming) 오늘 쓸 주제는 DP, 즉 동적 계획법 이다. 공부하기전에 여러 글을 읽었었는데, 초보자가 제일 감을 잡기 어렵다고 했고, 감을 잡는데 시간도 오래걸린다고 했다. 실제로 이 글을 쓰는 지금 현재 나도 아직 감을 잡는중이고 그만큼 어려운 알고리즘인것 같다. 하지만 코딩테스트에 자주 출제되고 피해갈 수 없는 부분이다보니, 열심히 해야겠다! DP 동적 계획법은 두가지 조건을 만족해야 풀 수 있다. 1. Overlapping Subproblem : 겹치는 작은 부분 문제 큰문제와 작은 문제를 같은 방법으로 풀 수 있다. && 문제를 작은 문제로 쪼갤 수 있다. 2. Optimal Substructure : 최적의 부분구조 문제의 정답을 작은 문제의 정답에서 구할 수 있다. 예로 피보나치 수를 들어보겠다. 0,1.. BFS의 특성 (최단경로) 그래프 상에서 길을 찾는 두가지 방법인 DFS와 BFS는 접근 우선순위에서 차이가 있다. 이 중 BFS는 방법의 특성상 최단 경로를 찾을 때 사용할 수 있다. 1. BFS의 특성 BFS는 방문한 정점을 queue에 push하고 queue내부에 가장 앞에 있는 원소를 기준삼아 다음 단계를 진행 한다. 이러한 특성상 BFS는 한곳만 집중해서 파고 돌아오는게(DFS의 방식) 아니라 여러군데를 한꺼번에 방문하며 나아가게 된다. 2. 최단경로? 위와 같은 BFS의 특성 덕분에, 지나가는 길에 여태껏 지나온 정점의 개수라던가 길의 길이를 기록한다면 이는 그 자체로 최단 경로가 된다. 최단경로 관련 문제는 DFS방식으로는 풀 수 없다! 3. 결론 최단경로 관련 문제는 BFS를 사용하자! DFS & BFS 1. 그래프 -그래프는 자료구조의 일종으로 정점(Vertex)과 간선(Edge)로 이루어져있다. 1.1 그래프의 표현 -그래프는 크게 두가지 방법으로 저장한다. -인접행렬 (adjacency matrix) : 정점의 개수가 V개인 그래프에서 V x V 크기의 2차원 배열을 사용하여, A[i][j]=1 이 면 간선이 있다고 표시한다. + 방향이 있는 간선에서는 정점 1과 2가 연결되어있을때, A[1][2]와 A[2][1] 둘 중 하나에만 1을 대입 하지만, 방향이 없다면 A[1][2] = 1; A[2][1] = 1; 으로 해줘야 한다. ++ 가중치가 있는 문제라면 1대신 가중치를 대입한다. +++ 한 정점과 연결된 모든 간선을 찾는 시간은 O(V)로 표현된다. -인접 리스트(adjacency list) :.. 이전 1 다음
