4Legs_Archives

문제 링크 : www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 문제를 봤을 때 BFS로 풀어야 하는 문제이구나! 하는 느낌은 바로 받을 수 있지만, 막상 문제를 해결하려고 하면 생각이 복잡해지는 문제이다. 출구를 향해 일단 가다가 잠긴 문을 만나면 목적지를 열쇠로 바꿔가면서 가는 방법을 제일 처음 생각해 볼 수 있다. 이 방법은 각 출구마다의 최단경로 path를 기억해 놓고, 통과해야 하는 문이 어떤 문들인지를 파악한 후에 가장..

문제 링크 : www.acmicpc.net/problem/1726 1726번: 로봇 많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 �� www.acmicpc.net 다소 전형적인 2차원 배열에서의 BFS 응용 문제이다. 2차원 배열의 판(Board)에 로봇(말)이 있고, 목표 지점까지의 최소 거리 등을 구하는 유형의 문제이다. [BFS에 대해] BFS (Breadth-First Search, 너비 우선 탐색) [서론] BFS는 DFS와 더불어 그래프 탐색의 기본적인 알고리즘이다. DFS로 풀 수 있는 문제의 대부분은 BFS로 풀 수 있다. 갈 수 있는 모든 노드를..

문제 링크 : https://www.acmicpc.net/problem/16437 16437번: 양 구출 작전 2, 3, 5번에 사는 모든 양들은 1번 섬으로 갈 수 있지만 7번 섬에 사는 양들은 1번 섬으로 가기 위하여 6번 섬을 거쳐야 하는데 6번 섬에 사는 늑대들의 수가 7번 섬에 사는 양들의 수보다 많으므로 www.acmicpc.net DFS를 재귀 형태로 구현하면 쉽게 풀 수 있는 문제이다. 문제의 그래프를 인접 리스트 형내로 변환한 뒤, 한 노드에 들어올 수 있는 양의 수 = 모든 자식 노드들에 들어올 수 있는 양의 수 합 이라는 점을 이용하여 루트 노드(1번)의 최종 값을 구하면 된다. 양의 수가 음수가 될 수 없다는 것과 각 값 자료형에만 유의하면 쉽게 해결할 수 있다. [코드] 1 2 3..

문제 링크 : https://www.acmicpc.net/problem/1176 1176번: 섞기 첫 줄에는 학생의 수 N(1 ≤ N ≤ 16)과 최소 넘어야할 키의 차이 값 K(1 ≤ K ≤ 3,400)가 주어진다. 다음 N개의 줄에는 학생들의 키가 순서대로 들어온다. 키는 25,000 이하인 자연수만 들어온다. www.acmicpc.net 분할 정복을 이용한 아이디어 캐치가 중요한 문제이다. 문제의 상황은 N명을 줄세울 때, 줄을 서는 각 학생들의 양 옆 학생들과의 키 차이를 K 초과로 만들고 싶은 상황이다. 가능한 모든 경우를 보려면 최대 경우의 수가 16!로, 무려 조 단위의 수이므로 불가능하다. N명을 줄 세우는 과정을 생각해보자. 지금까지 내가 몇 명을 세웠던 관계없이, 학생 한 명을 지금 세..

문제 링크 : www.acmicpc.net/problem/2600 2600번: 구슬게임 첫 줄에는 한번에 꺼낼 수 있는 구슬의 개수를 나타내는 세 개 의 정수 b1 , b2, b3 가 나타난다. 그 다음 5개의 각 줄에는 두 통속에 처음 담겨있는 구슬의 개수 k1, k2가 각각 표시되어 있다. www.acmicpc.net 개인적으로는 DP문제가 어려운 이유를 느낄 수 있었던 문제이다. 이 문제는 복잡하게 생각할수록 풀기 어렵고, DP의 개념 중 하나인 분할 정복을 잘 생각한다면 쉽게 풀 수 있는 문제이다. 양쪽 통에 구슬이 각각 x개, y개 들어있을 때, 현재 구슬을 꺼내야 하는 플레이어가 이기는 경우를 생각해 보자. 플레이어는 여러 가지 수를 둘 수 있다. 문제에서 제시된 예제의 경우만 해도 최대 6가..

문제 링크 : www.acmicpc.net/problem/1102 1102번: 발전소 은진이는 발전소에서 근무한다. 은진이가 회사에서 잠깐 잘 때마다, 몇몇 발전소가 고장이난다. 게다가, 지금 은진이의 보스 형택이가 은진이의 사무실로 걸어오고 있다. 만약 은진이가 형택이� www.acmicpc.net DP와 Bitmask를 활용해 해결할 수 있는 문제이다. Bitmask에 대해서는 다음 링크에 설명해 두었다. 4legs-study.tistory.com/5 Bitmask 에 대해 [서론] 스위치 4개가 있다고 생각해 보자. 이 스위치가 각각 켜져 있거나, 꺼져 있는 경우를 나타내려면 어떻게 해야 할까? 단순하게 생각해 보면 각 스위치마다 켜져 있는지, 꺼져 있는지에 �� 4legs-study.tistory..

문제 링크 : www.acmicpc.net/problem/1082 1082번: 방 번호 문방구에서 파는 숫자의 개수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 문방구에서 파는 숫자는 0보다 크거나 같고, N-1보다 작거나 같은 자연수이다. 예를 들어, N=4이면, 문방구에서 파� www.acmicpc.net DP의 대표적 유형인 거스름돈 문제와 유사한 문제이다. 숫자를 구매하여 높은 숫자를 만드는 방법은 두 가지가 있다. 1. 자릿수가 높은 숫자를 만든다. (ex. 11111 > 9999) 2. 자릿수가 같다면, 값이 높은 숫자를 만든다. 따라서, "숫자를 많이 사는 것"을 1순위로, "높은 숫자를 사는 것"을 2순위로 두고 구매한다. 아래 코드에서 vector dp[n] 은 금액 n으로 구..