본문 바로가기
728x90

DP7

[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.
[BOJ/Python] 2096. 내려가기 📌 문제 https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 📌 문제 접근 방법 처음엔 dfs를 사용해서 최소값, 최대값을 갱신시켰는데 숫자가 많아질수록 모든 숫자를 저장하는 자체에서 메모리 초과가 발생하는 것 같았다. 따라서 입력 숫자를 저장하지 않고 입력받자마자 바로 사용할 수 있도록 dp를 사용해서 구현했다. 아래줄의 입장에서 0번째 숫자는 윗줄의 0, 1번째 숫자를 더할 수 있고, 1번째 숫자는 윗줄의 모든 숫자, 2번째 숫자는 윗줄의 1, 2번째 숫자를.. 2021. 12. 8.
728x90

티스토리툴바