거창한 시작

www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 알고리즘 종류 구현 완전탐색 사고 과정 최대 5번 이동이라고 하니 5번 이동해서 최대값을 찾습니다. 1. 이동방향은 순열조합으로 찾습니다. 2. 네 방향에 따라 이중 for문을 다르게 하여 블록을 이동시킵니다. 이동시키는 방법은 아래와 같습니다. 2-1) 범위 끝 또는 숫자가 있는 블록을 마주하면 한 칸 전으로 이동합니다. 2-2) 현재 한 칸 이전에 있는 상태입니다. 한 칸 앞에 ..

www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 알고리즘 종류 구현 BFS 사고 과정 BFS를 이용해서 각 구슬의 위치를 저장하여 해결했습니다. 동일한 위치로 갈 수 있기 때문에 4차원 배열 isVisited를 생성하여 재방문을 체크했습니다. 1. 파란 구슬과 빨간 구슬을 움직입니다. 움직이는 도중에 구멍을 지나면 체크해 줍니다. 2. 파란 구슬이 빠졌으면 continue 합니다. 빨간 구슬만 빠졌으면 종료합..

www.acmicpc.net/problem/1445 1445번: 일요일 아침의 데이트 첫째 줄에 숲의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 3보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 숲의 지도가 주어진다. 숲의 지도는 S, F, g, . 만으로 이루어져 있 www.acmicpc.net 알고리즘 종류 다익스트라 우선순위 큐 사고 과정 다익스트라를 2차원 배열에 사용하여 해결했습니다. 값을 저장할 dp 2차원 배열을 만들어 줍니다. 시작점에서 출발하여, 아래 2가지 조건으로 비교합니다. 1. 쓰레기를 지나는 경우 비교 2. 쓰레기를 지나는 경우가 같으면, 쓰레기 주변을 지나는 경우 비교 목표 지점에 도착하면, 종료합니다. 구현(C++) 1 2 3 4 5 6 7 8 9..

www.acmicpc.net/problem/17780 17780번: 새로운 게임 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하 www.acmicpc.net 알고리즘 종류 구현 사고 과정 1. 말의 상태를 담을 수 있는 배열이 필요할 것 같았습니다. 그래서 Piece라는 구조체를 만들고, 이 구조체로 ps라는 배열을 만들었습니다. 구조체에는 말의 위치(y, x)와 방향(d) 그리고 맨 밑인지(isButtom)를 확인하는 변수들이 있습니다. 2. 말을 쌓을 수 있어야 합니다. 그래서 3차원 벡터를 만들기로 했습니다. state라는 명을 붙였습니다. 3. 이제 턴 1회..

www.acmicpc.net/problem/14464 14464번: 소가 길을 건너간 이유 4 첫 줄에 C와 N이 주어진다. 다음 C줄에는 T1…TC가 주어지고, 그 다음 N줄에는 Aj와 Bj(Aj ≤ Bj)가 주어진다. A, B, T는 모두 최대 1,000,000,000인 음이 아닌 정수이고, 같을 수도 있다. www.acmicpc.net 알고리즘 종류 우선순위 큐 정렬 사고 과정 1. 닭의 시간을 오름차순으로 정렬하여 저장합니다. 2. 소의 끝나는 시간을 기준으로 오름차순 정렬합니다. 저는 우선순위 큐를 이용해서 저장했습니다. 3. 소를 하나씩 꺼내서 Ai ~ Bi에 속하는 닭이 있는지 확인합니다. 닭을 확인했으면, 체크합니다. 구현(C++) 12345678910111213141516171819202..

www.acmicpc.net/problem/1826 1826번: 연료 채우기 첫째 줄에 주유소의 개수 N(1 ≤ N ≤ 10,000)가 주어지고 두 번째 줄부터 N+1번째 줄 까지 주유소의 정보가 주어진다. 주유소의 정보는 두개의 정수 a,b로 이루어 져 있는데 a(1 ≤ a ≤ 1,000,000)는 성경 www.acmicpc.net 알고리즘 종류 우선순위 큐 사고 과정 우선순위 큐 2개를 이용해서 해결했습니다. 현재 가진 연료로 갈 수 있는 거리까지 이동하고, 이 후에 나타난 주유소까지 도달하기 위한 연료를 지나친 주유소에서 가장 연료를 많이 주는 주유소를 선택하는 방법으로 해결했습니다. 1. 우선순위 큐(pq1)에 주유소 위치와 연료를 저장합니다. 주유소의 주유소의 위치를 기준으로 최소 힙을 만듭니다..

www.acmicpc.net/problem/2406 2406번: 안정적인 네트워크 첫째 줄에 두 정수 n(1≤n≤1,000), m이 주어진다. n은 컴퓨터의 개수이며, m은 연결되어 있는 지사 컴퓨터들의 쌍의 개수이다. 다음 m개의 줄에는 두 정수 x, y가 주어진다. 이는 서로 다른 두 컴퓨터, www.acmicpc.net 알고리즘 종류 MST 사고 과정 1번 본사는 모든 지사와 연결되어 있기 때문에 제외합니다. 그러면 나머지 노드들을 가지고 MST를 진행하면 됩니다. 입력에서 이미 연결된 노드들이 주어지므로 union_find으로 두 노드의 부모 노드를 합쳐주는 것이 편합니다. 구현(C++) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 2..

www.acmicpc.net/problem/16434 16434번: 드래곤 앤 던전 첫 번째 줄에 방의 개수 N (1 ≤ N ≤ 123,456) 과 용사의 초기 공격력 HATK (1 ≤ HATK ≤ 1,000,000) 가 주어집니다. i+1번째 줄엔 i번째 방의 정보를 나타내는 세개의 정수 ti, ai, hi (ti ∈ {1, 2}, 1 www.acmicpc.net 알고리즘 종류 구현 사고 과정 던전을 지나 N번 방에 몬스터를 쓰러트리고 아름다운 공주를 구하기 위한 최소 MaxHP를 구하는 문제이다. 간단하게 이분탐색을 이용해서 해결할 수 있다. 구현(C++) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 ..

www.acmicpc.net/problem/16118 16118번: 달빛 여우 첫 줄에 나무 그루터기의 개수와 오솔길의 개수를 의미하는 정수 N, M(2 ≤ N ≤ 4,000, 1 ≤ M ≤ 100,000)이 주어진다. 두 번째 줄부터 M개의 줄에 걸쳐 각 줄에 세 개의 정수 a, b, d(1 ≤ a, b ≤ N, a ≠ b www.acmicpc.net 알고리즘 종류 다익스트라 사고 과정 늑대가 움직이는 것이 주목해야 할 부분입니다. '속력 = 거리 / 시간' 공식이 있습니다. 속력이 2배 빠르다는 것은 거리가 같을 때 시간이 1/2배 된다는 것이고, 속력이 1/2배 빠르다는 것은 거리가 같을 때 시간이 2배 된다는 것입니다. 따라서, 늑대가 빠르게 달릴 때는 거리 가중치에 1/2배를 해주고, 늑대가 느..

www.acmicpc.net/problem/13911 13911번: 집 구하기 첫줄에는 정점의 개수 V(3 ≤ V ≤ 10,000)와 도로의 개수 E(0 ≤ E ≤ 300,000)가 주어진다. 그 다음 E줄에 걸쳐 각 도로를 나타내는 세 개의 정수 (u,v,w)가 순서대로 주어진다. 이는 u와 v(1 ≤ u,v ≤ V)사 www.acmicpc.net 알고리즘 종류 다익스트라 사고 과정 다익스트라는 한 정점에서 모든 정점으로 가는 최단거리를 구하는 알고리즘입니다. 이 문제에서는 많은 맥도날드에서 모든 집으로 가는 최다거리와 많은 스타벅스에서 모든 집으로 가는 최단거리의 합을 구하는 문제이다. 많은 맥도날드와 많은 스타벅스를 어떻게 하나의 정점으로 처리할 수 있을까요? 비용이 없는 가상의 맥도날드 노드 한 ..