free from

문제소개 벽 부수고 이동하기는 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 ..

문제소개 7344나무막대 문제는 LIS 문제이며 해당 문제는 2001년 ACM-ICPC 대전 기출 문제입니다. 나무 막대기 가공 순서를 비교하는 문제로 비교 값은 길이와 무게 2개 입니다. 길이를 I, 무게를 W라고 하면 I 2:(3,5) -> 3(4:9) 순서로 한 번의 준비 작업으로 처리할 수 있습니다. 그리디한 해결방법이네요. 소스보기

문제소개 8979올림픽 문제는 올림픽에 참가하는 국가 간의 순위를 정하는 문제입니다. 특정 국가를 입력 받고 그 국가의 순위를 출력하는 문제로 금,은,동 개수를 비교하여 순위를 정해야합니다. 금 > 은 > 동를 획득한 개수가 많은 순으로 순위가 결정 됩니다. 문제 해결 비교를 조금더 쉽게 하기 위해서 금 은 동을 점수화 했습니다. 금 : 100,000점 은 : 1 점 동 : 0.000,001점 점수화 후 우선순위 큐에 넣어 순서대로 순위를 정해줬습니다. 소스보기