쿠쿠의 개발일지

다익스트라 알고리즘 이란? 그래프에서 여러 개의 노드가 있을 때, 특정한 한 정점(=노드)에서 출발하여 다른 모든 정점으로 가는 최단 경로를 구하는 알고리즘입니다. 다익스트라 최단 경로 알고리즘은 '음의 간선' 즉, 가중치가 0보다 작은 값이 아닌 경우에 때 정상 동작합니다. 현실 세계에서의 길(간선) 음의 간선으로 표현되지 않아 다익스트라 알고리즘은 실제로 인공위성 GPS 소프트웨어 등에서 가장 많이 사용됩니다. 다익스트라 최단 경로 알고리즘은 기본적으로 그리디 알고리즘으로 분류됩니다. 왜냐하면 매번 '가장 비용이 적은 노드'를 선택해서 임의의 과정을 반복합니다. 동작과정 출발 노드를 설정 최단 거리 테이블 초기화 방문하지 않은 노드 중에서 최단 거리(가중치)가 가장 짧은 노드 선택 해당 노드를 거쳐 ..

[문제] 출처 - https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net [문제풀이 전] 이코테책의 Q29번 문제이기도 합니다. 해당 문제를 풀 때는 단순 이분 탐색을 사용해서 푸는 줄 알고 있었는데, 이것을 응용해서 푸는 것을 Parametric Search라는 기법이 있는 것을 알게 되었습니다. Parametric Search 정의 - 조합 최적화를 위한 알고리즘의 설계 및 분석에서 파라매트릭서치..

그리디 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법으로, 매 선택에서 그 순간에 가장 최적이라 생각되는것을 선택하여 결과에 도달하는 방법입니다. 매 순간 가장 최적을 선택하기 때문에 현재 상황의 선택이 나중에 미칠 영향은 고려하지 않습니다. 그래서 결과를 만들었다고 해서 그것이 최적이라는 보장이 없습니다. 하지만 이 알고리즘을 적용할 수 있는 문제들은 지역적으로, 전역적으로 최적인 문제입니다. 지역적으로 전역적으로 무슨말인지 헷갈리시다면 위 그림을 보시면 바로 이해가 가능합니다. 왼쪽 그림은 최소값을 찾는다고 가정했을때 지역적으로, 전역적으로 최적인 답을 만족하는 그래프의 형태이고 오른쪽 그림은 지역적으로는 최적인 답을 찾을 수 있지만, 전역적으로는 최적인 답이 아닙니다. 그래서 문제를 접하면..

[문제] 출처 - https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net [문제풀이] BFS와 구현으로 푸는 문제이다. 구현 문제만 오면 많이 버벅여서 더 많은 연습이 필요 할 것 같다. https://moonsbeen.tistory.com/231 를 참고하여 문제를 풀었다. 맨 처음 상어의 위치를 Queue에 넣어주고 해당 위치를 빈칸으로 만든다. 1. BFS탐색을 하여 상어가 먹을 수 있는 물고기 후보들을 List에 담는다. 2. 만약 물고..

퇴각검색(영어: backtracking, 한국어: 백트래킹)은 한정 조건을 가진 문제를 풀려는 전략이다. "퇴각검색(backtrack)"이란 용어는 1950년대의 미국 수학자 D. H. 레머가 지었다. -출처 위키백과 백트래킹(Backtracking) 해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더 이상 가지 않고 되돌아갑니다. 이를 가지치기라고 하는데, 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 의미 입니다. 가지치기를 얼마나 잘하느냐에 따라 효율성이 결정되게 됩니다. 즉 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴보는 것 입니다. 주로 문제 풀이에서는 재귀로 모든 경우의 수를 탐색하는 과정에서 답이 절대로 될 수 없는 상황을 정의하고 그 경우 ..

[문제] 출처 - https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net [문제 풀이 전] N = Target) Left++; (2) 부분 배열의 합이 Target 값보다 작으면 Right = Right + 1 해줍니다. (부분 배열의 길이를 늘려 합을 더한다.) if(sum < Target) Right++; (3) 부분 배열의 합이 Target 값과 같다면 결과 값을 +1 해줍니다. if( sum == Tar..

[문제] 출처 - https://www.acmicpc.net/problem/10972 10972번: 다음 순열 첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다. www.acmicpc.net [문제 풀이 전] 순열의 정의 : 순서가 부여된 임의의 집합을 다른 순서로 뒤섞는 연산이다 (위키백과) 크기가 N인 수열이 서로 다른 순열은 총 N! 개가 있다. 모든 순열을 사전순으로 나열했을 때 A = { 1 , 2, 3 } 인 경우 사전 순은 다음과 같다. 1 2 3 = i 이면서 A[j] > A [i-1]을 만족하는 가장 큰 j를 찾는다. A[i-1] 보다 큰 수 중 가장 작은 수 A [j] = 4 ---> 7 2 3 6 5 4 1..