전체 글 (19) 썸네일형 리스트형 [ 백준 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.. [LeetCode 433. Minimum Genetic Mutation] Python 코드 (Bactracking, BFS) 1. 문제 https://leetcode.com/problems/minimum-genetic-mutation/ Minimum Genetic Mutation - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 2. 리뷰 아주 재밌는 문제다. 처음에는 백트래킹으로 풀었고, 최적화를 통해 꽤 괜찮은 결과를 냈다. 그런데 문제가 요구하는 바를 잘 살펴보면, BFS가 더 적합하고 효율적임을 알 수 있었다. 백트래킹, BFS, DFS 등은 모두 완전탐색 기반의 알고리즘이다... [ 백준 17144번 미세먼지 안녕! ] Python 코드 (Simulation) 1. 문제 https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 2. 풀이 문제가 어려운 것은 아니었지만 Python3로 돌리면 시간초과가 발생했다. PyPy3로는 통과되었지만 뭔가 만족스럽지 않아서 Python3로 통과될 때까지 코드를 최적화했다. 그래서 어떻게 겨우겨우 Python3로도 통과를 했다!! 상위코드를 몇 개를 살펴 보았는데, 내가 제출한 코드와 비슷한데도 2배 정도 시간차이가 났다. 어째서인지 잘 모르겠다. 내가 적용한 최적화 방법.. 이전 1 2 3 4 ··· 7 다음
