본문 바로가기
728x90

동적계획법4

[PG/Python] 광고 삽입 📌 문제 https://programmers.co.kr/learn/courses/30/lessons/72414?language=python3 코딩테스트 연습 - 광고 삽입 시간을 나타내는 HH, H1, H2의 범위는 00~99, 분을 나타내는 MM, M1, M2의 범위는 00~59, 초를 나타내는 SS, S1, S2의 범위는 00~59까지 사용됩니다. 잘못된 시각은 입력으로 주어지지 않습니다. (예: 04:60:24, 11 programmers.co.kr 📌 문제 접근 방법 아이디어를 참고한 풀이 : https://dev-note-97.tistory.com/156 시간을 모두 초로 바꾸어서 Memoization을 사용한다. 로그의 시간을 all_time 리스트에 저장할 때, 반복문을 사용해서 start부.. 2022. 6. 24.
[PG/Python] 2 x n 타일링 📌 문제 https://programmers.co.kr/learn/courses/30/lessons/12900 코딩테스트 연습 - 2 x n 타일링 가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 programmers.co.kr 📌 문제 접근 방법 n이 1일 때부터 경우의 수를 모두 계산해보니 점화식이 f(n) = f(n-1) + f(n-2)가 나왔다. 위의 식을 피보나치 수열이라고 하는데, 이를 재귀로 구현할 경우 시간이 오래걸리기 때문에 메모이제이션을 사용해서 풀이했다. 하지만 시간초과가 나서 질문하기를 살펴보니, 나는 매번 연산을 하는게 시간이 오래걸릴거라고 .. 2022. 1. 24.
[PG/Python] N으로 표현 📌 문제 https://programmers.co.kr/learn/courses/30/lessons/42895 코딩테스트 연습 - N으로 표현 programmers.co.kr 📌 문제 접근 방법 N으로 표현할 수 있는 숫자의 경우의 수를 생각해줬다. 우선 N은 1~8번만 사용하면 되고 그 외의 경우에는 -1을 리턴해주기 때문에 answer는 -1로 초기화한다. 인덱스를 N 사용횟수와 맞춰주기 위해 all_cases의 0번째에 빈 set을 넣어줬다. temp라는 set에 N을 i번 사용하여 나온 숫자를 저장할 것이다. set을 사용한 이유는 연산의 결과로 똑같은 숫자가 여러 번 나올 수 있기 때문에 중복을 제거해주기 위해서이다. N이 5라고 했을 때, 1번만 사용하는 경우는 5 하나밖에 없다. 2번 사용하.. 2021. 12. 22.
[Algorithm] DP (Dynamic Programming) 동적 계획 (DP; Dynamic Programming) 그리디 알고리즘과 같이 최적화 문제를 해결하는 알고리즘 입력 크기가 작은 부분 문제들을 모두 해결한 후에 그 해들을 이용하여 보다 큰 크기의 부분 문제들을 해결 Memoization 피보나치 수열을 재귀함수로 구현하는 경우 '엄청난 중복 호출이 존재한다'는 문제점이 있음 def fibo(n): if n < 2: return 2 else: return fibo(n-1) + fibo(n-2) 메모이제이션 (Memoization) 컴퓨터 프로그램을 실행할 때 이전에 계산한 값을 메모리에 저장해서 매번 다시 계산하지 않도록 하여 전체적인 실행 속도를 빠르게 하는 기술 동적 계획법의 핵심이 되는 기술 앞의 예에서 fibo(n)의 값을 계산하자마자 저장하면(.. 2021. 10. 3.
728x90

티스토리툴바