다익스트라 알고리즘 다익스트라 알고리즘은 음의 가중치가 없는 그래프의 한 정점에서 모든 정점까지의 최단거리를 각각 구하는 알고리즘이다. 다익스트라 알고리즘을 구현하는 과정은 다음과 같다. 방문하지 않은 정점 중 가장 가중치 값이 작은 정점을 방문한다. (처음에는 시작 정점을 방문한다.) 해당 정점을 거쳐서 갈 수 있는 정점의 거리가 이전에 기록한 값보다 작다면 그 거리를 갱신한다. 프로그래머스의 배달 문제의 그래프를 예시로 다익스트라 알고리즘을 설명해보겠다. 1번 정점을 시작 정점으로 잡고 1번 정점에서 방문할 수 있는 각 정점까지의 거리를 표시한다. 1번 정점에서 방문할 수 없는 정점은 INF(무한대)로 표시해둔다. 방문하지 않은 정점 중 가장 거리가 짧은 2번 정점을 방문한다. 1번 정점에서 2번 정..

분할 정복(Divide and Conquer) 문제를 나눌 수 없을 때 까지 나눠 각각을 풀면서 다시 합병하여 문제를 해결하는 알고리즘이다. 상위의 해답을 구하기 위해 아래로 내려가며 하위의 해를 구하는 하향식 접근법을 사용하여 일반적으로 재귀함수로 구현된다. 분할정복의 대표적인 알고리즘은 퀵 정렬과 병합 정렬이 있다. DP와 분할 정복이 비슷한 느낌이어서 공통점과 차이점을 찾아보았다. 공통점 문제를 가장 작은 단위가 될 때까지 나눠서 분할함 차이점 동적 계획법 중복된 문제의 답은 저장되어 상위 문제 해결 시 재활용 됨 (메모이제이션 기법) 분할 정복 부분 문제는 서로 중복되지 않음(메모이제이션 기법 사용 안함) 분할 정복을 설계하는 방법 1) Divide : 문제가 분할이 가능할 경우, 2개 이상의 문..

그래프 탐색 그래프 탐색 알고리즘 중 대표적으로 사용되는 DFS에 대해 알아보자. 그래프 탐색이란 그래프 내 임의의 한 정점에서 시작해서 모든 정점들을 탐색하는 것을 말한다. DFS는 현재 정점에서 갈 수 있는 정점까지 들어가면서 탐색하는 것이고, 또 다른 대표적인 그래프 탐색 기법인 BFS는 현재 정점에 연결되어 있는 가까운 정점들부터 차례대로 탐색한다. DFS (Depth-First Search) DFS는 깊이 우선 탐색 이라고도 부르는 방법으로 선택한 정점에서 가장 깊게 들어갈 수 있는 부분까지 들어가며 탐색하는 방법이다. DFS 구현 방법 스택 재귀함수 DFS의 장점과 단점 장점 현 경로상의 노드들만을 기억하므로 저장공간을 적게 사용한다. 목표노드가 깊은 단계에 있는 경우 해를 빠르게 구할 수 있..

문제 김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 영어 소문자로만 이루어지며, 그 길이는 20 이하이다. N, M은 500,000 이하의 자연수이다. 듣도 못한 사람의 명단에는 중복되는 이름이 없으며, 보도 못한 사람의 명단도 마찬가지이다. 출력 듣보잡의 수와 그 명단을 사전순으로 출력한다. 풀이 STL의 set 라이브러리와 algorithm의 set_intersection 함수를 사용하여 교..

문제 이다솜이라는 친구가 포켓몬 마스터가 되기 위해 떠나는 여정에 대한 이야기인데 엄청 길고 없어도 문제 푸는 데 지장이 없기 때문에 생략. 입력 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 물어봐도 괜찮아. 나는 언제든지 질문에 답해줄 준비가 되어있어. 둘째 줄부터 N개의 줄에 포켓몬의 번호가 1번인 포켓몬부터 N번에 해당하는 포켓몬까지 한 줄에 하나씩 입력으로 들어와. 포켓몬의 이름은 모두 영어로만 이루어져있고, 또, 음... 첫 글자만 대문자이고, 나머지 문자는 소문자로만 이루어져 있어. 포켓몬 이름의 최대 길이는 20이야. 그 다음 줄부터..

문제 N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다. 출력 M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다. 알고리즘 분류 이분 탐색 문제 - 1 페이지 www.acmicpc.net 코드 #include #include #include using n..

bool binarySearch(vector &list, int findNum) { int start = 0; int end = list.size() - 1; while (start