[이코테] 문제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..
[이코테] 문제4 - 효율적인 화폐 구성(226p) (한줄평) 점화식은 잘 세웠으나 책의 풀이가 더 간결하고 좋았던 문제로 한번쯤 복습이 필요한 문제! 풀이 시간: 40분 이내 1) 문제 해결 아이디어 이 문제는 그리디 거스름돈 문제와 거의 동일하지만 화폐단위의 큰 단위가 작은 단위의 배수가 아니기 때문에 무조건 큰 단위부터 거슬러주면 안된다!! 금액 1부터 m까지 만들수 있는 최소한의 화폐 개수를 찾아 d에 입력하면 된다. 아래의 점화식을 n개의 화폐 단위에 대하여 차례로 적용하면 된다. 각 금액을 만들 수 있는 최소 화폐 개수를 담는 리스트(d)를 (m + 1)의 크기로 10001로 초기화하여 생성한다. Q. dp테이블을 10001로 초기화하는 이유는? 화폐의 가치는 10,000보다 작은 자연수이고 ..
[이코테] 문제3 - 바닥 공사(223p) (한줄평) 코드는 짧으나 점화식을 떠올리기가 쉽지 않았던 문제로 복습이 꼭 필요!! 풀이 시간: 30분 이내 1) 문제 해결 아이디어 가로 길이: n, 세로 길이: 2 인 직사각형 바닥을 1*2, 2*1, 2*2 3가지 타일로 채울 수 있는 경우의 수를 구하는 문제다. 이 문제 또한 다이나믹 프로그래밍의 기초 예제에서 빠질 수 없는 타일링 문제 유형이다. 왼쪽부터 타일을 채운다고 했을 때 아래와 같이 2가지 경우로 나눠볼 수 있다. 1. i - 1까지 이미 채워져있다면, i번째를 채우기 위해 사용할 수 있는 타일은 (2 * 1) 1가지 경우다. 2. i - 2까지 이미 채워져있다면, i - 1 ~ i 번째를 채우기 위해 사용할 수 있는 타일은 (1*2) 2개, ..
