[백준] 11722번 - 가장 긴 감소하는 부분 수열 (한줄평) LIS 알고리즘을 알면 쉽게 풀 수 있었던 문제! 유사 문제: 11053, 11054 https://hseungyeon.tistory.com/304 [다이나믹 프로그래밍] ▲ 11053번 - 가장 긴 증가하는 부분 수열 [백준] 11053번 - 가장 긴 증가하는 부분 수열 (한줄평) 풀었던 문제지만 다시 풀려니 기억이 잘 안나서 어려웠던 문제.. 꼭 복습이 필요하다!!! 풀이 시간: 30분 이내 유사 문제: https://hseungyeon.ti hseungyeon.tistory.com https://hseungyeon.tistory.com/305 [다이나믹 프로그래밍] 11054번 - 가장 긴 바이토닉 부분 수열 [백준] 11054번 - ..
[백준] 10844번 - 쉬운 계단 수 (한줄평) 생각보다 빨리 아이디어가 떠올라 쉽게 풀 수 있었던 문제! 2차원으로 접근해야한다는 것을 깨달으면 쉽게 풀 수 있다. 한번쯤 복습해보면 좋을 것 같은 문제 풀이 시간: 20분 이내 1) 문제 해결 아이디어 인접한 모든 자리의 차이가 1인 수를 계단수라고 한다. (단, 0으로 시작하는 수는 계단수가 아니다) 1이상 100이하의 자연수 n이 주어질 때, 길이가 n인 계단 수의 총 개수를 구하는 문제다. 길이가 n인 계단 수의 마지막 숫자는 0 ~ 9 사이의 수로 10가지 경우가 있다. 길이가 n, 마지막 숫자가 j인 계단 수의 개수 = 길이가 (n - 1)인 계단수 중 j - 1, j + 1 로 끝나는 계단수의 개수의 합이다. 그러므로 길이가 n인 계단수의 ..
[백준] 1932번 - 정수 삼각형https://www.acmicpc.net/problem/1932 (한줄평) 익숙한 dp 문제라 쉽게 풀 수 있었던 문제! 풀이 시간: 10분 이내 유사 문제: 1149 https://hseungyeon.tistory.com/298 [다이나믹 프로그래밍] 1149번 - RGB거리 [백준] 1149번 - RGB거리 (한줄평) 아이디어를 쉽게 떠올릴 수 있었던 문제! 효율적인 코드를 짤 수 있게 고민해볼 수 있는 문제였다 이 문제는 집의 수 n(2
t = int(input()) # 테스트 케이스 수 for _ in range(t): n = int(input()) # 정수 d = [0] * 11 # 11보다 작은 양수 d[1], d[2], d[3] = 1, 2, 4 for i in range(4, n + 1): d[i] = d[i - 3] + d[i - 2] + d[i - 1] print(d[n]) [백준] 9095번 - 1, 2, 3 더하기 (한줄평) 아이디어만 떠올린다면 쉽게 풀 수 있는 문제! 풀이 시간: 20분 이내 1) 문제 해결 아이디어 11보다 작은 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제다. DP문제는 보통 아이디어만 잘 떠올리고 점화식을 세운다면 코드 자체는 간결하게 해결할 수 있는 문제..
[백준] 9184번 - 신나는 함수 실행 (한줄평) 재귀함수 그대로 구현하면 되지만 오류를 스스로 해결하지 못했던 문제..! 꼭 복습이 필요하다~ 풀이 시간: 60분 이내 1) 문제 해결 아이디어 이 문제는 a, b, c가 주어졌을 때 w(a, b, c)를 구하는 문제다. 이 문제는 아래의 재귀함수 그대로 구현을 하면 되지만 이렇게만 구현하게 되면 동일한 작업을 계속 반복하게 되어 그 값을 구하는데 매우 오랜 시간이 걸리게 되는 문제가 발생한다. 그래서 다이나믹 프로그래밍으로 해결해야하는데 다이나믹 프로그래밍의 핵심은 반복되는 계산을 피하기 위해서 dp테이블에 계산한 값을 저장해두고 나중에 그 값이 필요하다면 바로 그 값을 가져다 쓰는 것이다. if a 20, then w(a, b, c) returns:..
[백준] 1003번 - 피보나치 함수 (한줄평) 피보나치 수를 구하는 문제에서 약간 변형된 문제로 피보나치 수열 문제 풀 때 한번쯤 다시 풀어보면 좋을 것 같은 문제! 40이하의 자연수/0 이 n으로 주어질 때, fibo(n)이 호출되었을 때 fibo(0)과 fibo(1)이 호출되는 횟수를 구하는 문제다. 재귀 혹은 반복문을 이용하여 풀 수있고 두 방식 모두 메모리나 시간 측면에서는 동일하니 편한 방식으로 풀면 될 것 같다. (풀이1) 재귀 이용(내 풀이) 풀이 시간: 20분 이내 1) 문제 해결 아이디어 재귀를 이용한 풀이 방식이다. n번째 피보나치 수를 저장하는 dp 테이블(d)에 기존에는 피보나치 수 1개 값만 저장했다면 이 문제에서는 [피보나치 수, 0 호출 횟수, 1 호출 횟수] 3개 값을 저장..
[이코테] 문제6 - 병사 배치하기(59:50) (한줄평) 아이디어를 떠올리기 어려웠던 문제로 답을 봤음에도 이해하는데 어려움이 있어서 꼭 복습이 필요!! 풀이 시간: 1) 문제 해결 아이디어 예를 들어 수열 array = {4, 2, 5, 8, 4, 11, 15} 라면 가장 긴 증가하는 부분 수열은 {4, 5, 8, 11, 15} 이다. 이 문제는 가장 긴 감소하는 부분 수열을 찾는 문제로 LIS 알고리즘을 조금 수정하여 정답을 도출할 수 있다! 가장 먼저 입력받은 병사 정보의 순서를 뒤집고 최장 증가 부분 수열(LIS) 알고리즘을 수행하여 정답을 도출한다! 병사 정보의 순서를 뒤집는 이유는 LIS는 가장 긴 오름차순 수열을 찾는 것이지만 실제로 우리는 가장 긴 내림차순 수열을 찾아야 한다. 그러므로 ..
[이코테] 문제5 - 금광(52:30) (한줄평) 혼자서 푸는데는 성공했지만 책 코드와 약간 다른 부분이 있어 복습이 필요한 문제!! (풀이1) 내 풀이 틀린 코드(1차원 리스트) 풀이 시간: 50분 이내 1) 문제 해결 아이디어 문제 자체는 2차원 리스트이지만 입력을 1차원 리스트로 받았기 때문에 금의 최대 크기를 담은 dp테이블도 1차원 리스트로 생성하여 풀었다. 2) 소스코드 t = int(input()) # 테스트 케이스 수 for _ in range(t): n, m = map(int, input().split()) # 세로, 가로 graph = list(map(int, input().split())) # n * m 개의 금 개수 d = [0] * (n * m) # 금의 최대 크기 for i in..
