목록전체 글 (24)
free from
들어가기 11404. 플로이드는 모든 노드간의 최단 거리을 구하는 문제입니다 시작과 도착이 같은 노드의 입력 값은 없으므로 Loop는 없습니다. 비용의 입력값이 자연수이므로 음수의 비용도 없습니다. 그러므로 제목 그대로 플로이드 와샬 알고리즘으로 푸는 문제입니다. 플로이드-와샬 알고리즘 플로이드 와샬 알고리즘은 3중 for을 바탕으로 동작합니다. 노드 간의 최소 비용을 기록합니다. 최소 비용을 기록하여 재사용하기 때문에 DP입니다. 3중 for을 바탕으로 계산하기 때문에 복잡도는 O(n3)입니다. 아래는 기본이 되는 플로이드 - 와샬 코드입니다. 동일한 노드(i -> i)를 방문하는 경우, 노드 사이 간선이 없을 경우(여기서는 MAX_COST로 나타냈습니다)를 제외하면 i -> j의 노드 사이에 k 노드..
문제소개 벽 부수고 이동하기는 BFS 최단 거리 문제입니다. 상하좌우를 이동하면서 벽이 없으면 이동할 수 있으며 벽이 있을 때 망치( K > 0 )이면 벽을 부수고 이동할 수 있습니다. 벽을 부술 수 있는 망치가 있기 때문에 망치 사용 여부만 잘 확인해주시면 크게 어려운 문제는 아닙니다. 문제풀이 BFS 최단거리를 풀 때 활용되는 Priority Queue를 통해서 cost가 최소가 되는 Item을 우선적으로 처리합니다. BFS와 Priority Queue를 통해서 풀기 때문에 특정 x , y에 도달하게 되면 cost가 최소입니다. 한 가지 주의해야할 것은 망치의 사용 여부입니다. 'START'에서 '여기까지'로 갈 때 비용은 1번, 2번 경로 모두 3(START 포함)입니다. 하지만 바로 망치 사용 여..
문제소개 5021왕위 계승 문제는 dfs로 tree형태의 그래프를 형성하는 문제입니다. tree형태를 만든 다음 주어진 계승자를 계산하면 풀수 있는 문제입니다. 문제풀이 먼저 노드 구조체를 만들겠습니다. 트리의 노드 형태는 다음과 같습니다. struct node { string _name; vector _child; node(){} node(string name) { this->_name = name; } }; 각 트리의 노드를 정의했으니 트리를 만들겠습니다. 트리는 dfs로 구성할 것이며 제일 먼저 주어진 유토피아의 왕부터 시작합니다. void dfs(node& parent) { int j = 0; for (int i = 0; i < N; i++) { if (lines[i][1] == parent._n..
문제 소개 1756피자굽기 문제는 구현문제입니다. (DP로 풀수도 있습니다.) 반죽을 완료한 순서대로 오븐에 넣습니다. 이때, 반죽의 지름이 오븐의 지름보다 작거나 같을 때만 오븐에 넣을 수 있으며 가능한 가장 깊은 오븐에 반죽을 넣고 싶습니다. 피자반죽 입력 300,000 = 10^5 오븐 입력 300,00 = 10^5 이므로 이중 for문은 10^10의 크기를 가지므로 시간초과가 날 것입니다. 또한, 피자 반죽 지름과 오븐의 지름의 순서가 중요하기 때문에 정렬을 할 수 없습니다. 문제 풀이 7 3 5 6 4 3 6 2 3 //오븐 지름 3 2 5 // 피자 반죽 지름 위 예제를 가지고 예시를 들겠습니다. 먼저, 지름이 3인 첫번째 피자 반죽을 오븐의 가장 깊은 곳까지 넣을 수 있는 위치는 5번째 오븐..
문제소개 1348주차장은 이분매칭 + 이분탐색 문제입니다. 차 한대씩 주차 공간 1곳에 주차하는 것이기 때문에 직관적으로 이분매칭을 생각할 수 있습니다. 저는 이 문제를 MCMF 그러니깐 SPFA로 해결하려고 시도했다가 "아 그러면 안되는 구나"를 깨달았고 SPFA와 이분매칭을 조금더 생각할 수 있었습니다. 문제풀이 3 13 .C.....P.X... XX.......X..P XX.....C..... 문제는 다음과 같은 입력값을 받습니다. 그러므로 각각의 차들에서 각각의 주차공간까지 최단거리를 계산해야 합니다. 이때 계산은 BFS로 진행합니다. 그리고 계산한 최단경로 값을 노드와 엣지로 정리합니다. 왼쪽이 차량이며 오른쪽이 주차공간입니다. 다음 그래프에서는 2가지 경우의 이분매칭을 만들 수 있습니다. 1 ..
문제소개 1637날카로운 눈은 이분 탐색 문제입니다. 문제 분류가 DFS로 분류되어 있어서 어떻게 하면 DFS로 풀 수 있을까를 생각하느라 조금 오래 걸렸습니다. (DFS로 풀진 못했습니다.) 문제의 입력값이 20억 이므로 O(N)이 아닌 O(logN)의 알고리즘을 생각해야 하며 O(logN)에 어울리는 탐색 방법으로 이분 탐색을 생각할 수 있습니다. log2(2,000,000,000) ≒ 602,059,991 그러면 어떻게 생각해야 '1637날카로운 눈' 문제에 이분 탐색을 적용할 수 있을까요? 그 해답의 포인트는 홀수 개수를 가진 특정 정수는 하나라는 점입니다. 문제풀이 4 1 10 1 4 4 1 1 5 1 6 10 1 다음과 같은 입력값을 아래와 같이 표로 정리했습니다. 1 2 3 4 5 6 7 8..
문제소개 1253좋다 문제는 투 포인터 알고리즘 문제입니다. 배열에서 다른 두 개의 숫자를 더하여 배열 내의 다른 숫자를 만드는 문제입니다. 예를 들어 (idx:숫자) 아래와 같이 숫자 배열이 있습니다. idx 1 2 3 4 5 숫자 0 -10 -2 4 2 3: -2와 4: 4를 합하여 5: 2를 만들 수 있습니다. 이렇게 만들 수 있는 숫자의 개수를 구하는 문제입니다. 숫자는 정수인 점을 유의하세요. 문제 풀이 이 문제를 러프(rough)하게 풀면 O(N^3)으로 풀 수 있습니다. 그런데 2000개의 입력값을 가지므로 1초 내에 풀기는 어렵기 때문에 O(N^2)로 풀 수있는 투 포인터 알고리즘으로 풀어야 합니다. 그러니깐 배열을 먼저 정렬해야 합니다. idx 1 2 3 4 5 숫자 -10 -2 0 2 ..