L.O.K

[알고리즘] 다익스트라 알고리즘(Dijkstra)이란? 다익스트라 알고리즘(Dijkstra) 다익스트라 알고리즘은 특정지점에서 다른지점으로 가는 최단경로를 구하는 알고리즘이다. 다익스트라 알고리즘은 그리디(Greedy) 알고리즘 기반으로 한다. 그리디( lordofkangs.tistory.com 이전에는 다익스트라 알고리즘이 무엇인지 알아보았고 이번에는 다익스트라 알고리즘을 개선해보겠다. 다익스트라 알고리즘은 그리디(Greedy) 알고리즘을 기반으로 한다. 현재 상황에서 최적의 해를 구하는 것이다. 차가 A에서 각 노드로 가는 최단거리를 구한다고 가정해보자. A에서 출발한 차가 B일때, C일때, D일때... 각 노드별 최단거리를 구해야 한다. 이는 두 과정이 필요하다. 1) 모든 노드를 탐색해야 한다. ..

다익스트라 알고리즘(Dijkstra) 다익스트라 알고리즘은 특정지점에서 다른지점으로 가는 최단경로를 구하는 알고리즘이다. 다익스트라 알고리즘은 그리디(Greedy) 알고리즘 기반으로 한다. 그리디(Greedy) 알고리즘은 '현재'를 기준으로 최적해를 구하는 알고리즘이다. 네비게이션을 떠올리면 이해가 쉽다. 네비게이션은 차가 위치한 '현재'를 기점으로 최단경로를 탐색한다. A와 B는 5L의 기름으로 연결된다. A와 B는 '노드'이고 5L의 기름은 '간선'이다. 그럼 차가 A에서 출발하여 E로 간다고 가정해보자. 네비게이션이 A -> B -> D -> E 경로가 최적이라 알려주어도 운전자가 C로 이동하면 네비게이션은 C에서의 최단경로를 파악해야 한다. '현재'를 기준으로 최적해를 구해야 한다는 의미다. 또한..

그래프란 노드(Node)가 있고 노드를 연결한 간선(Edge)이 있는 자료구조이다. 그래프를 완전탐색하는 기본적인 알고리즘은 DFS와 BFS이다. 탐색을 하려면 우선 자료구조가 정의되어야 한다. 그래프(Graph)는 두 가지 방식으로 표현된다. 1. 인접행렬( 2차원 배열 ) 2. 인접리스트 ( 리스트 ) 행렬은 '인덱스'가 있다. 인덱스는 랜덤엑세스를 가능하게 하여, 특정노드에 접근하는 속도가 빠르다. 하지만 배열구조로 쓰레기값이 들어있는 공간도 유지를 해야하기에 메모리낭비가 심하다. 인접리스트방식은 리스트 자료구조를 이용한다. '연결' 방식의 자료구조인 만큼, 특정 노드를 시작으로 인접노드를 순회하는 경우 유리하다. '인덱스'가 아닌 '주소'로 인접노드에 접근하니 메모리 낭비도 적다. 그러나 랜덤엑세..

그래프란 노드(Node)가 있고 노드를 연결한 간선(Edge)이 있는 자료구조이다. 그래프를 완전탐색하는 기본적인 알고리즘은 DFS와 BFS이다. 탐색을 하려면 우선 자료구조가 정의되어야 한다. 그래프(Graph)는 두 가지 방식으로 표현된다. 1. 인접행렬( 2차원 배열 ) 2. 인접리스트 ( 리스트 ) 행렬은 '인덱스'가 있다. 인덱스는 랜덤엑세스를 가능하게 하여, 특정노드에 접근하는 속도가 빠르다. 하지만 배열구조로 쓰레기값이 들어있는 공간도 유지를 해야하기에 메모리낭비가 심하다. 인접리스트방식은 리스트 자료구조를 이용한다. '연결' 방식의 자료구조인 만큼, 특정 노드를 시작으로 인접노드를 순회하는 경우 유리하다. '인덱스'가 아닌 '주소'로 인접노드에 접근하니 메모리 낭비도 적다. 그러나 랜덤엑세..

분할정복(Divide&Conquer)이란? 재귀호출 방식의 완전탐색의 단점을 보완하는 방식으로 전체를 부분으로 분할(Divide) 한 뒤 다시 부분을 전체로 병합(Merge)하는 과정을 거쳐 문제를 해결하는 방식이다. [알고리즘] 재귀호출(recursive call)이란? '재귀호출(recursive call)'은 완전탐색을 구현할때 용이하다. 완전 탐색은 선형적 방식과 재귀적 방식(계층적) 으로 접근할 수 있다. 선형적 방식은 반복문을 돌려 하나씩 탐색하는 방식이다. 재귀 lordofkangs.tistory.com 재귀호출(Recursive Call)은 발생 가능한 모든 조합을 완전탐색하는 방식으로 n부터 1까지 모든 함수가 호출된다. 하지만 이런 재귀호출 방식은 특정한 규칙이 있는 문제라면 비효율이다..

'재귀호출(recursive call)'은 완전탐색을 구현할때 용이하다. 완전 탐색은 선형적 방식과 재귀적 방식(계층적) 으로 접근할 수 있다. 선형적 방식은 반복문을 돌려 하나씩 탐색하는 방식이다. 재귀적 방식(계층적)은 Top에서 Bottom으로 Down하며 모든 경우의 수를 탐색하는 방식이다. 그렇다면 어떤 경우에 어떤 방식을 사용해야 할까? 반복문을 사용하는 경우 완전탐색은 반복문을 사용하여 구현할 수 있다. 1 ~ 10개의 원소가 있다. 이중 특정 조건에 부합하는 4가지 원소를 찾으려 한다. 그럼 1부터 10까지 탐색을 해야하는데 '반복문'을 사용한다고 가정해보자. 4가지 원소로 구성된 한 조합을 찾아야 하므로 for문의 변수는 네 개가 필요하다. 반복문을 사용하는 경우 10개의 원소 중 조건에..

예제) 어떤 퀴즈대회에서 숫자게임이 진행되었다. 숫자게임의 규칙은 주어진 범위 안의 숫자들을 더해 목표하는 수를 만드는 것이다. 중복된 숫자를 사용하는 것은 가능하지만 숫자들의 조합은 두 사람 이상 똑같이 사용할 수 없다. 사용 가능한 숫자 범위와 목표하는 수가 주어졌을 때, 목표하는 수를 만들 수 있는 최대 경우의 수를 구하시오. 숫자 범위 [ 1 , 2 , 3 ] 목표 : 8 ( 답지에 답은 10이라 나온다. 근데 문제 조건이 너무 헷갈리고 'SSAFY 5일완성' 책이 오류가 상당히 많다. 조건이 애매하니 어떻게 해석하느냐에 따라 결과가 달라진다고 생각한다. 그래서 그냥 내가 해석한 방식대로 풀었고 답은 31은 나왔다. ) 1, 2, 3을 더해 8을 만드는 경우의 수를 구하는 문제이다. 동적계획법의 ..

예제) 남자 m명과 여자 n명이 있다. 남자는 여자보다 많고 커플은 여자의 수만큼 생성된다. 여자는 키가 큰 순서로 선택할 수 있다. 남자는 키 순서대로 서있다. 한 여자가 한 남자를 선택했을 때, 다음 여자는 선택된 남자보다 키 큰 남자를 선택할 수 없다. 남성의 키가 모두 다를 때, 커플이 탄생할 수 있는 경우의 수를 구하라. ( 개인적으로 이게 뭔 문제인지 감도 잘 안 잡혔다. 동적계획법에 억지로 문제를 끼어맞추다보니 이상한 문제가 탄생한거 같다. 그래도 한 번 풀어보자. ) 결국 커플은 n개 탄생한다. 동적계획법을 발상하려면 두 가지를 고려하면 된다. 1) 큰 단위와 작은 단위에 공통으로 적용되는 원리를 발견한다. 2) 큰 단위와 작은 단위를 분리한다. 첫 번째 여자는 3명의 남자를 선택할 수 있..

예제 ) 하노이탑 원반의 개수가 주어질 때 원반을 이동시킬 최소 횟수를 구하시오. 규칙 1. 1회에 한 개의 원판만 옮길 수 있다. 2. 반드시 큰 원판 위에 작은 원판이 있어야 한다. . 1번에 쌓여있는 원판들을 규칙을 지키며 3번까지 옮겨야 한다. 동적계획법의 TopDown 방식에 따라 결과부터 생각해보자. n개의 원판을 3번 막대로 옮기려면 우선, n-1개 원판을 2번 막대로 옮겨야 한다. 그래야 가장 큰 원판을 3번으로 옮길 수 있다. 그 다음, 2번 막대의 n-1개 원판을 다시 3번 막대로 옮긴다. 공식으로 나타내보자. n : 원판 갯수 F(n) : n개의 원판을 한 막대에서 다른 막대로 옮기는 경우의 최소 횟수 과정 1) n-1개 원판을 1번에서 3번으로 이동 : F(n-1) 2) 가장 큰 원..

예제) 철수는 매일 점심마다 짜장면이나 짬뽕을 먹는다. 시험기간이 n일 남았을 때, 철수가 짜장, 짬뽕을 먹는 경우의 수를 구하라. ( 단, 짜장면은 2일, 4일, 6일... 같이 짝수날을 연속으로 먹어야 한다. 또한 짜장면을 먹고 짬뽕을 먹은 뒤 다시 짜장면을 먹을 수 없다. ) 조건이 까다롭다. 조건1) 짜장면은 2, 4, 6... 연속으로 먹을 수 있다. 조건2) 짜 → 짬 → 짜 순으로 먹을 수 없다. 경우의 수를 따질 때, 동적계획법으로 접근하면 효율적이다. 시험기간 n일을 작은 단위로 분류해야한다. 조건1)은 분류에 적합하다. 예를들어, 시험기간이 8일이 남았다고 해보자. 1) 짜장면을 8일 먹은 날 2) 짜장면을 6일 먹은 날 3) 짜장면을 4일 먹은 날 4) 짜장면을 2일 먹은 날 5) 짜..