[이코테] 문제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개, ..
[이코테] 문제1 - 1로 만들기(217p) (한줄평) 평소였으면 최소값을 구하는 문제니 BFS로 해결 했을테지만 전형적인 다이나믹 프로그래밍 문제! 추후 복습이 꼭 필요한 문제 풀이 시간: 40분 이내 1) 문제 해결 아이디어 정수 x가 주어졌을 때, 연산 4개를 적절히 사용해 1을 만드는데 사용되는 연산의 최솟값을 구하는 문제다. a. x가 5로 나누어 떨어지면, 5로 나눈다 b. x가 3으로 나누어 떨어지면, 3으로 나눈다 c. x가 2로 나누어 떨어지면, 2로 나눈ㄴ다 d. x에서 1을 뺀다 1. 최적 부분 구조 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제 해결O 2. 중복되는 부분 문제 동일한 작은문제를 반복적으로 해결해야 함 Q. 이 문제를 다이나믹 프로그래밍으로 ..
[이코테] 문제2 - 떡볶이 떡 만들기(201p) (한줄평) 탐색 범위를 보고 이진 탐색으로 풀어야함을 알아야 풀 수 있는 문제로 해결은 했지만 복습이 필요한 문제! 풀이 시간: 30분 이내 1) 문제 해결 아이디어 적절한 절단기 높이를 찾을 때까지 이진 탐색을 수행하여 높이 h를 반복해서 조정하면 된다. "현재 이 높이로 자르면 조건을 만족할 수 있는가?를 확인한 뒤 조건의 만족 여부(예/아니오)에 따라서 탐색 범위를 좁혀서 해결할 수 있다. 절단기의 높이는 0이상 10억이하의 정수인데 이렇게 큰 탐색 범위를 보면 가장 먼저 이진 탐색을 떠올려야 한다!! 그렇지 않으면 시간초과가 날 것이다! 여기서 기억할 점은 절단기의 높이가 커질 수록 잘린 떡의 길이의 총합이 작아진다는 점이다. 1. 시작점: 0, ..
[이코테] 문제1 - 부품 찾기(197p) (한줄평) 집합을 이용하여 쉽게 풀 수 있었던 문제! 하지만 다른 풀이 방법으로도 풀어보는 것을 추천! 이 문제는 부품 목록 n개, 손님이 구매를 원하는 부품 m개가 있을 때, 손님이 요쳥한 부품 번호의 순서대로 부품을 확인해 부품이 있으면 yes, 없으면 no를 출력하는 문제다. 이진 탐색, 집합, 계수 정렬 3가지 방법으로 모두 효과적으로 풀 수 있는 문제다. (풀이1) 집합(set)을 이용 풀이 시간: 5분 이내 1) 문제 해결 아이디어 단순히 특정 수가 있는지 여부를 검사하면 되기 때문에 부품목록(graph)를 집합으로 선언한다. Q. 리스트가 아닌 집합으로 선언한 이유는? 집합에서 in 연산의 시간복잡도가 O(1)이고 리스트에서 in 연산의 시간복잡도는..
[이코테] 예제1 - 이진 탐색 (한줄평) 이진 탐색 기초 문제로 재귀, 반복문 구현 방식 둘다 풀어보면 좋은 문제! 이 문제는 n개의 숫자에서 찾으려고 하는 값(target)이 있으면 해당 인덱스를 출력하는 문제다. (풀이1) 재귀 함수로 구현 풀이 시간: 15분 이내 1) 문제 해결 아이디어 1. 타겟을 찾으면 인덱스를 리턴한다. 2. 타겟이 중간점 값보다 작으면 왼쪽 부분에 대해 이진 탐색 수행을 위해 끝점을 (mid - 1)로 넘겨 binary_search()를 리턴한다. 3. 타겟이 중간점 값보다 크면 오른쪽 부분에 대해 이진 탐색 수행을 위해 시작점을 (mid + 1)로 넘겨 binary_search()를 리턴한다. 2, 3번에서 binary_search()를 그냥 호출하는 것이 아니라 bin..
