Code Review/BaekJoon (10) 썸네일형 리스트형 [ 백준 1520번 내리막 길 ] Python 코드 (메모이제이션 a.k.a. DP) 1. 문제 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 2. 리뷰 어떻게 DP문제는 풀 때마다 새롭다. 이것도 DP로 풀 수 있다고?라는 충격의 연속이다. 특히 이 문제는 Top-Down 방식의 메모이제이션만이 DP에 비해 차별화된 강점을 보여주었다. 지금까지 푼 문제들은 DP와 메모이제이션이 상호변환이 가능했는데, 이 문제는 DP로는 풀기 어려웠다. (솔직히 불가능하다고 생각하지만 혹시 모르니까....ㅎㅎㅎ) 문제를 보면 가장 먼저 DF.. [ 백준 17144번 미세먼지 안녕! ] Python 코드 (Simulation) 1. 문제 https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 2. 풀이 문제가 어려운 것은 아니었지만 Python3로 돌리면 시간초과가 발생했다. PyPy3로는 통과되었지만 뭔가 만족스럽지 않아서 Python3로 통과될 때까지 코드를 최적화했다. 그래서 어떻게 겨우겨우 Python3로도 통과를 했다!! 상위코드를 몇 개를 살펴 보았는데, 내가 제출한 코드와 비슷한데도 2배 정도 시간차이가 났다. 어째서인지 잘 모르겠다. 내가 적용한 최적화 방법.. [ 백준 1726번 로봇 ] Python 코드 (BFS) 1. 문제 https://www.acmicpc.net/problem/1726 1726번: 로봇 많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 www.acmicpc.net 2. BFS 풀이 (3차원 visited 배열) 나는 처음에 다른 방식으로 풀었다. BFS에서 visited배열의 활용 방식을 살짝 변경해서 최단거리를 찾는 알고리즘으로 사용했는데 혼자 풀고 뿌듯함에 차있을 때, 다른 분들의 3차원 visited 배열을 보고 무릎을 탁 쳤다. 메모리 사용량과 처리시간도 더 적었을 뿐더러, 무엇보다 기본적인 BFS 알고리즘 동작방식을 그대로 따랐다. 3차원 visi.. [ 백준 11265번 끝나지 않는 파티 ] Python 코드 (다익스트라, 벨만포드) 1. 문제 https://www.acmicpc.net/problem/11265 11265번: 끝나지 않는 파티 입력의 첫 번째 줄에는 파티장의 크기 N(5 ≤ N ≤ 500)과 서비스를 요청한 손님의 수 M(1 ≤ M ≤ 10,000) 이 주어진다. 각각의 파티장은 1번부터 N번까지 번호가 붙여져 있다. 다음에는 N개의 줄에 걸 www.acmicpc.net 2. 풀이 2.1. Bellman-Ford 입력이 2차원 배열인데다가, 출발지도 여러개여서 Bellman-Ford 알고리즘을 쓰고 싶은 충동에 휩싸인다. 실제로 Bellman-Ford를 써서 풀 수 있기는 하다! 그런데 파이썬의 비애로 자잘한 최적화를 해줘야 한다. 관련 내용은 이 블로그를 참조했다. 아주 자세하고 친절하게 써주셨다. 무조건 min으로.. [ 백준 1922번 네트워크 연결 ] Python 코드 (MST) 1. 문제 https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 2. 풀이 물구나무 서서 봐도 MST(최소 스패닝 트리) 문제이다. 특별하게 꼰 부분도 없어서 MST 알고리즘 연습하기 딱 좋다. 대표적인 MST 알고리즘으로는 Prim과 Kruskal이 있다. 주어진 그래프의 노드가 V개, 간선이 E개라고할 때 시간복잡도는 다음과 같다. 알고리즘의 반복문 부분을 보면 어렵지 않게 확인할 수 있다. Prim Prim with heap Kruskal 시간복잡도 O(V**2) O(E*logV) O(E*logV) 특징 자료구조 heap을 사용해야 .. [ 백준 21610번 마법사 상어와 비바라기 ] Python 코드 (Simulation) 1. 문제 https://www.acmicpc.net/problem/21610 21610번: 마법사 상어와 비바라기 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기 www.acmicpc.net 2. 아이디어 코드 짜기가 어려운 문제는 아닌데, 시간초과가 나버렸다. 두손 모아 기도하며 PyPy로도 돌려보았지만 여전히 시간초과였다. 주저리주저리 설명할 것 없이, 내가 개선한 방법만 말하면 다음 3가지다. 리스트 복사는 하지 않는다. 시간복잡도 O(n) 리스트의 모든 요소를 복사해야하기 때문에 시간복잡도가 O(n)이다. 가능하면 리스트 대신 집합에서 in 구문을 쓰자. 시간.. [ 백준 2156번 포도주 시식 ] Python 코드 (DP) 1. 문제 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 2. 아이디어 다이나믹 프로그래밍의 핵심은 DP배열이 가지는 의미 & DP배열을 계산하는 방법이다. 2.1. DP배열이 가지는 의미 지금까지 풀어본 문제들을 보면, DP[n]은 대부분 다음 두 가지 중 하나의 의미를 가졌다. n번째를 선택했을 때의 최적값 n번째까지 고려했을 때의 최적값 (n번째를 선택하지 않는 경우까지 고려) 이 문제는 두번째 경우에 해당한다. 왜냐하면 최댓값을 만드는데.. [ 백준 9465번 스티커 ] Python 코드 (DP) 1. 문제 https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 2. 아이디어 다이나믹 프로그래밍의 핵심은 DP배열이 가지는 의미 & DP배열을 계산하는 방법이다. 2.1. DP배열이 가지는 의미 지금까지 풀어본 문제들을 보면, DP[n]은 대부분 다음 두 가지 중 하나의 의미를 가졌다. n번째를 선택했을 때의 최적값 n번째까지 고려했을 때의 최적값 (n번째를 선택하지 않는 경우까지 고려) 이 문제는 첫번째 경우에 해당한다. 왜냐하면 총 .. [ 백준 12865번 평범한 배낭 ] Python 코드 (DP) 1. 문제 백준 12865번 평범한 배낭 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 2. 풀이 Dynamic Programming의 대표적인 문제이다. 원래라면 모든 부분집합을 다 확인해야 하기에 O(2**N)의 시간 복자도를 가지지만, DP를 활용함으로써 시간복잡도를 O(NM)으로 개선시켰다. 다만 여기서 M은 N에 대해 독립적인 값이기 때문에, M이 매우 커진다면 시간복잡도 또한 매우 커진다. DP문제의 쟁점은 늘 그렇듯 어떻게 prob.. [ 백준 1890번 점프 ] Python 코드 (DP) 1. 문제 백준 1890번 점프 2. 풀이 백트래킹, 메모이제이션, DP을 모두 적용시킬 수 있는 아주 흥미로운 문제이다. (아물론 제약조건 때문에 DP를 적용한 코드만 통과했다.) 3가지 풀이방법 모두 완전탐색을 기반으로 한다. 다만 그 효율성을 어떻게 높였는지에 따라 알고리즘이 분류된 것일 뿐이다. 백드래킹은 가지치기 코드를 통해 유효하지 않은 상태트리(경우의 수)를 더이상 탐색하지 않는다. 메모이제이션은 탑다운 방식으로 탐색을 이어나가는 중, 중복되는 상태트리를 만나는 경우 저장된 값을 불러온다. DP는 바텀업 방식으로 탐색을 하되, 이전 탐색의 값을 기억해두었다가 적절하게 재활용하여 완전탐색을 만족시킨다. 개인적으로 백트래킹과 메모이제이션은 어느 정도 코드의 정형화가 가능하기에 상대적으로 쉬운 반.. 이전 1 다음
