반응형 알고리즘36 [알고리즘/백준] 1309번 동물원 Python 파이썬 저번 문제는 혼자 힘으로 못 풀어서 글을 못 썼는데 이번 문제는 나름 풀고 성찰할 부분이 있어서 글을 적게 되었습니다. 이번 문제도 DP 문제입니다. 이번 문제는 2 X N 사자 우리가 주어지고 사자들을 배치할 때의 경우의 수를 9901로 나눈 나머지를 출력하는 문제입니다. 저번에 2133번 문제를 풀었는데 나름 방식이 유사한 문제인거 같습니다. 혹시 해당 문제를 푸셨다면 다음은 2133번을 풀어보는 것을 추천드립니다. 일단 풀이 과정으로는 몇가지의 경우의 수를 직접 그려보았습니다. 각 경우의 답에서 규칙성을 찾아보았을 때 DP[i] = DP[i-2] + (DP[i-1]*2) 식을 정의할 수 있습니다. 이를 적용해서 코드를 구현하였습니다.. 다음과 같은 코드로 통과하였습니다.. import sys inp.. 2023. 4. 24. [알고리즘/백준] 11048번 이동하기 Python 파이썬 갈수록 DP에 대한 감을 잡아가고 있는 것 같습니다. 이번에도 DP 관련 문제입니다. 준규가 (1,1) 위치에서 (N, M) 위치까지 갈 때 최대로 얻을 수 있는 사탕의 갯수를 구하는 문제로 지도가 나오길래 BFS 문제인가 흠칫했습니다. DFS든 BFS든 여러 방법으로 풀 수 있는 문제같긴 했습니다. (궁금해서 찾아보니 BFS 로는 가능하고 DFS 경우 메모이제이션을 했다면 전에 값을 구한 적이 있을 때 바로 리턴하는 부분이 있어야 하는데 이 코드에서는 끝에 도달했을 때만 리턴을 할 뿐 메모한 부분을 활용하고 있어 의미가 없다고 하네요. 시간초과 날 경우도 높고) 일단 DP 문제로 들어온거라 DP 방식을 사용해서 풀어볼려고 시도해보았습니다. (BFS와 DP 문제 구분법 : BFS는 그래프에서 간선의 가중.. 2023. 4. 21. [알고리즘/백준] 2193번 이친수 Python 파이썬 요즘도 여전히 다이나믹 프로그래밍 문제를 풀고 있습니다. 이번 문제는 위 조건에서 요구하는 이친수를 찾는 문제입니다. 그러면 무엇을 해야하는가? 전번 풀이에도 이야기했듯이 다이나믹 프로그래밍 문제를 풀 때는 규칙성을 찾는 것이 매우 중요하며 이를 찾기 위해 직접 몇가지의 경우의 수를 적어보면서 어떻게 결과가 도출되는지 과정을 살펴보는 것이었습니다. 그렇기 때문에 초반에 어떻게 결과가 도출되는지 아래와 같이 적어보았습니다. 위 풀이를 보면서 규칙성을 찾을 수 있게 되었습니다. 바로 전 2단계의 답 합이 다음 답이라는 것이었습니다. 즉 dp[i] = dp[i-1] + dp[i-2] 로 정의할 수 있습니다. 다음과 같은 코드로 통과하였습니다. import sys input = sys.stdin.readline.. 2023. 4. 19. [알고리즘/백준] 11057번 오르막 수 Python 파이썬 아쉽게도 골드 문제는 아니였지만 드디어 DP 문제를 풀이 안보고 풀 수 있게 되었습니다. 수의 길이 N이 주어졌을 때 오름차순을 이루는 수%10007 을 구하는 문제였습니다. DP 문제를 풀면서 느낀 점은 규칙성을 찾는 것이 매우 중요하다고 느꼈고 이를 적용시키기 위해서는 직접 몇가지의 경우의 수를 적어보면서 어떻게 결과가 도출되는지 과정을 살펴보는 것이었습니다. 먼저 다음과 같은 코드로 통과하였습니다. import sys input = sys.stdin.readline n = int(input()) dp = [ 1 for _ in range(10) ] for i in range(2, n+1): for j in range(10): if i == 2: dp[j] = 10 - j else: for k in .. 2023. 4. 18. 이전 1 2 3 4 ··· 9 다음 반응형
