거창한 시작

www.acmicpc.net/problem/17244 17244번: 아맞다우산 경재씨는 저녁 약속을 가기 전 챙기지 않은 물건들이 있는 지 확인하고 있다. 필요한 물건은 전부 챙긴 것 같았고 외출 후 돌아오는 길에 경재씨는 외쳤다. "아 맞다 우산!!!" 경재 씨는 매번 외출 www.acmicpc.net 알고리즘 종류 - 구현 - BFS 사고 과정 - 이 문제에서 중요한 조건은 재방문 처리이다. 특히 아래와 같은 상황이다. 시작점 S에서 빨간색 선으로 이동하고, 초록색선으로 이동한다. 이 때 초록색 화살표 끝의 X에서는 어떻게 재방문을 처리해야 할까? - 일단, X를 구별할 수 없으니 번호를 붙여주기로 했다. - 이제 비교해볼 상황이 있다. 1. 0을 방문했고 다시 0으로 오는 경우 2. 0을 방문했고 ..

www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 알고리즘 종류 - 우선순위 큐 - 위상정렬 사고 과정 - 순서가 있는 일을 순서대로 나열하는 문제이므로 위상정렬으로 풀 수 있다. - 가능하면 쉬운 문제부터 풀어야 하므로 우선순위 큐를 이용해서 작은 번호 문제를 먼저 오게 할 수 있다. - 문제의 예시로 과정을 설명해 보겠다. * 3번 보다 1번을 먼저 풀고, 4번 보다 2번을 먼저 풀어야 합니다. * 초기에 진입차수가 0인 번호..

www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 알고리즘 종류 - 우선순위 큐 사고 과정 - 카드의 합이 작은 것부터 합치면 된다. * 10 20 40의 카드를 합칠 때에 큰 카드부터 합치기 시작하면 큰 카드의 숫자를 중복해서 합치게 된다. 예시) (20 + 40) + (60 + 10) = 150이 나온다. 여기서 60은 40과 20의 합이다. 따라서 작은 수부터 더하면 된다. 구현(C++) 1 2 3 4 5 6 7 8 9 10 11 12 13..

www.acmicpc.net/problem/1400 1400번: 화물차 입력은 여러 개의 테스트 케이스로 구성된다. 각 테스트 케이스의 첫째 줄에는 두 개의 정수 m과 n이 주어진다, 여기서 m은 지도를 나타내는 행렬의 행의 크기이고 n은 열의 크기이다(2 ≤ m, n ≤ 2 www.acmicpc.net 알고리즘 종류 - 구현 - BFS 사고 과정 - 이동 조건 * 차량은 이동하거나 제자리에 머물기 가능 * 교차로에 진입할 때, 이동가능한 방향일 때만 이동 가능 - 신호등 * 남북 또는 서동 방향으로 주기적으로 신호등이 변함 - 위 조건을 보고 생각한 내용 * Queue의 사이즈로 while문을 돌려서 시간을 더해가자 * Queue에는 위치 y, x만 넣자 * 신호등을 만났을 때 처리할 배열은 state..

www.acmicpc.net/problem/14950 14950번: 정복자 서강 나라는 N개의 도시와 M개의 도로로 이루어졌다. 모든 도시의 쌍에는 그 도시를 연결하는 도로로 구성된 경로가 있다. 각 도로는 양방향 도로이며, 각 도로는 사용하는데 필요한 비용이 존재 www.acmicpc.net 알고리즘 종류 - MST - Prim 사고 과정 - 모든 노드를 최소 비용으로 연결하는 MST 문제이다. 그런데 간선 기준이 아닌 노드 기준으로 탐색되고 있다. 따라서 Prim 알고리즘을 사용한다. 구현(C++) 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657#include ..

www.acmicpc.net/problem/2307 2307번: 도로검문 그림 1은 어떤 도시의 주요 지점과 그 지점들 간의 이동시간을 나타낸 그래프이다. 그래프의 노드는 주요 지점을 나타내고 두 지점을 연결한 도로(에지)에 표시된 수는 그 도로로 이동할 때 걸 www.acmicpc.net 알고리즘 종류 - 다익스트라 사고 과정 1. 검문을 하지 않을 때, 최단경로를 구한다. 1-1. 최단 경로를 저장한다. 저장하는 방법은 parents 배열을 이용해서 부모 노드를 기록한다. 2. 최단 경로에 있는 노드를 막고, 다익스트라를 수행한다. 2-1. 구해진 최단 경로 비용이 무한대이면, -1 출력 2-2. 구해진 최단 경로 비용 - 검문하지 않은 최단 경로 비용 출력 구현(C++) 1 2 3 4 5 6 7 8..

www.acmicpc.net/problem/16137 16137번: 견우와 직녀 견우와 직녀는 여러 섬과 절벽으로 이루어진 지역에서 살고 있다. 이 지역은 격자로 나타낼 수 있으며, 상하좌우로 인접한 칸으로 가는 데 1분이 걸린다. 7월 7일은 견우와 직녀가 오작교를 건너 www.acmicpc.net 알고리즘 종류 - 구현 - BFS 사고 과정 - 조건을 다음과 같다. * 오작교 조건 1. 1분 동안 유지 2. 주기대로 생성 3. 교차 절벽에 생성 금지 4. 이미 생성된 절벽에 오작교 겹쳐서 생성 금지 * 다리 건너는 조건 1. 오작교가 M주기로 생성될 때, 견우는 오작교 주변에서 M-1시간이어야 한다. (본인은 이 조건이 이해가 안되서 고생했다. 마치, 건너기 전에 다리가 생성되었는지 모르고 있다가 건..

www.acmicpc.net/problem/16954 16954번: 움직이는 미로 탈출 욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 www.acmicpc.net 알고리즘 종류 사고 과정 1. 욱제를 9방향으로 움직인다. 2. 벽을 내린다. - 고려해야할 상황은, 욱제가 벽을 피하기 위해서 이전 시간대에 갔던 위치를 다시 갈 수 있다. 따라서 방문을 체크하는 배열을 시간대에 따라 초기화해야 한다. 구현(C++) 123456789101112131415161718192021222324252627282930313233343536373839404142434445464..

www.acmicpc.net/problem/16929 16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문 www.acmicpc.net 알고리즘 종류 - 구현 - BFS 사고 과정 - 사이클을 형성하기 위하기 위한 조건 * 시작점으로 돌아온다. * 최소 변의 개수가 4개이다. - 주변을 탐색하는 것이 아닌 깊이 우선 탐색하기 때문에 DFS를 사용한다. - 방문했던 곳을 확인하는 배열(isVisited)로 재방문을 하지 못하면 시작점에 도달할 수 없다. 그렇다고, 재방문을 허락하면, 무한히 순환한다. 그러면 시작점을 어떻게 방문할 수 있..

www.acmicpc.net/problem/2234 2234번: 성곽 첫째 줄에 두 정수 n, m이 주어진다. 다음 m개의 줄에는 n개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, www.acmicpc.net 알고리즘 종류 - BFS - 구현 사고 과정 - 구해야 하는 항목은 3가지이다. * 방의 개수, 가장 넓은 방의 크기, 하나의 벽을 허물었을 때 가장 큰 방의 크기 - 문제에서 제시해 주고 있듯이 비트 연산을 사용하면 쉽게 풀 수 있다. * 간단하게 하는 방법을 알아보자. + 1은 0001, 2는 0010, 4는 0100, 8은 1000 이다. + 12는 1100이다. 위에서 1000과 0100의 합으로 ..