문제 https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 개요 어제 블로그에 다익스트라(Dijkstra) 알고리즘을 정리한 글을 작성했다. 그리고, 오늘 실제로 다익스트라를 활용한 문제를 풀어보고자 이 문제를 풀어보았다. 예전에는 다익스트라 코드를 무식하게 다 외우기만 해서 시간이 지나면 금방 휘발되었는데, 확실히 알고리즘 동작 과정을 세세하게 이해하면서 코드를 직접 작성하니까 실수 없이 다익스트라 코드..
백준 문제 리뷰
문제 https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 개요 이 문제는 구현 문제이다. 위의 5가지 종류의 테트로미노가 주어지는데, 회전과 대칭이 가능하기 때문에 가능한 모양은 5개가 아니라 사실상 총 19개가 나온다. 19가지 경우를 모두 하나하나 구현해야하는 것인가 하고 굉장히 막막했다. 그러던 중에 DFS + 백트래킹을 이용하면 더욱 쉽게 풀 수 있음을 알게 되었다. 문제 풀이 위에서 언급했던 총 19가지 모양에 대해 각각 if문을 구현하여..
문제 https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$ 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽 www.acmicpc.net 개요 처음 풀어본 시뮬레이션 문제이다. 일단 직접 그림을 그려보지 않고 머릿속으로만 생각하다보니까 문제 설명을 이해하는 데 굉장히 오래 걸렸다. 그리고, 시뮬레이션 문제라는 사실에 미리 겁을 먹은 것도 있다. 시뮬레이션 문제는 뭔가 특별한 방식을 사용하는 줄 알고 DFS, BFS를 사용하면 안 될 것 같다는 착각에 빠졌다. 그래서 굉장히 이상..
문제 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 개요 문제를 처음 봤을 때 백트래킹 문제임을 바로 파악하지는 못했다. 이차원 배열이 주어져서 당연하게 DFS 혹은 BFS로 접근해야겠다고 생각했다. 백트래킹을 고려하지 않고 있었기 때문에, 여러 개의 치킨집 중에서 M개를 어떻게 선택해야 할지 고민하는 데에 시간을 굉장히 많이 썼다. 이 문제 또한 결국 구글링의 힘을 빌렸다...! (언제쯤 혼자 풀어낼 거냐..나 자신아...
문제 https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 개요 문제를 읽자마자 백트래킹을 이용해겠다고 생각했다. 바로 이전에 백트래킹 문제를 한 번 풀어봤기 때문에 감을 살려서 도전했다. 그러나, 백트래킹 함수를 구현할수록 코드가 너무 과하게 복잡해지는 느낌이 들었고, 테스트케이스 실행 시 자꾸 다른 답이 도출되었다. 결구 이 문제 또한 구글링을 시도했다...! 구글링한 후 코드를 참고하고 이해한 후에, 다시 내 식대로 코드를 작성했는데 테스트케이스 3가지는 모두 통과..
문제 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱 www.acmicpc.net 개요 문제를 읽자마자 백트래킹을 사용해야하겠다고 생각했다. 그러나, 백트래킹 문제를 안 풀어본지 너무 오래 되어서 함수를 어떻게 짜야 할지 뇌정지가 왔다. 그래서 결국 뇌정지를 이겨내지 못하고 구글링을 했다. (이 때 좀 현타가 세게 왔다.) 문제 풀이 전형적인 백트래킹 문제이다. 먼저, 수열과 연산자를 각각 배열에 저장한다. 그리고..
문제 https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 개요 문제를 다 읽자마자 DP로 접근해야겠다는 생각이 들었다. 그래서 dp[i]를 'i번째 날까지의 최대 금액'으로 정한 후에, 점화식을 계속 생각해보았는데, 20분 넘게 떠올리지 못했다. 이차원 dp 배열을 이용한 접근도 시도했는데, 파고들수록 더 복잡해질 것 같았다. 그래서 결국 구글링한 후에 블로그 글을 참고하여 풀었다. 문제 풀이 이 문제의 핵심은 앞에서부터 생각하는 것이 아니라, 뒤에서부터 생각하는 것이다. 1일 2일 3일 4일 5일 6일 7일 t[i] 3 5 1 1 2 4 2 p[i] 10 20 10 20 15 40 ..
문제 https://www.acmicpc.net/problem/1183 1183번: 약속 마법사 N명이 머글 문화를 이해하기 위해 머글과 약속을 잡았다. 각 마법사는 한 명의 머글을 만날 예정이다. 하지만, 마법사는 약속 시간보다 빨리 또는 늦게 도착할 수 있기 때문에 고민에 빠 www.acmicpc.net 개요 실버 랜덤 디펜스를 처음 시작했다. PS가 습관이 되지 않아 뭔가 새로운 자극이 필요했고, DP, 그리디 등의 알고리즘 분류를 모르는 채로 문제를 맞닥뜨린 채로 문제를 풀 수 있는 랜덤 디펜스를 습관 들이기로 했다. 실버 랜덤 디펜스가 정상적으로 습관화되고, 실버 문제를 빠른 시간 내에 정확히 푸는 실력이 갖추어지면 그 때 골드 랜덤 디펜스로 넘어가야겠다고 생각했다. 실랜디를 시작하고 맞이한 첫..
