[이코테] 문제2 - 개미 전사(220p) (한줄평) 다이나믹 프로그래밍을 풀어야함을 알고 점화식을 도출해낼 수있는 능력을 요구하는 문제로 복습이 꼭 필요한 문제! (풀이1) 내 풍이 풀이 시간: 30분 이내 1) 문제 해결 아이디어 처음에 내가 생각해냈던 아이디어는 창고 최대 개수인 100개 크기로 생성한 리스트(d)에 해당 번호의 창고를 털었을 때 얻을 수 있는 식량의 최댓값을 기록하는 것이었다. 사실 예제로는 답이 맞게 나오는데 정확히 맞는 코드인지는 모르겠다.... 2) 소스코드 n = int(input()) # 창고 개수 graph = list(map(int, input().split())) # n개의 식량 개수 d = [0] * 100 d[0], d[1] = graph[0], graph[1] ..
[이코테] 문제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. 이 문제를 다이나믹 프로그래밍으로 ..
[이코테] 예제1 - 피보나치 수열 (한줄평) 다이나믹 프로그래밍의 대표적인 예제로 어렵지 않게 풀 수 있는 문제 (풀이1) 단순 재귀 풀이 시간: 1분 이내 1) 문제 해결 아이디어 단순 재귀 함수로 구현했을 때 시간복잡도는 O(2**n)이다. 이미 계산한 것에 대해 호출할 때마다 또 계산을 하기 때문에 n이 커질수록 수행 시간이 기하급수적으로 늘어나는 문제가 있다. 예를 들어, f(6)을 호출할 때 f(3)이 3번이나 호출된다. f(100)이라면 어마어마한 연산을 수행하는데 수백억년이 넘어간다. 2) 소스코드 # 1. 피보나치 수열(단순 재귀) def fibo(x): if x == 1 or x == 2: return 1 return fibo(x - 1) + fibo(x - 2) print(fibo(4..
[이코테] 문제3 - 정렬된 배열에서 특정 수의 개수 구하기 (한줄평) 라이브러리를 이용하면 쉽게 풀 수 있는 문제! 하지만 라이브러리를 사용하지 않고 푸는 법도 알아야 함 시간 복잡도 O(logN)을 요구하기 떄문에 일반적인 선형 탐색으로는 시간초과 판정을 받는다. 데이터가 오름차순 정렬되어 있기 떄문에 이진 탐색을 수행할 수 있다. (풀이1) bisect 라이브러리 이용 풀이 시간: 15분 이내 1) 문제 해결 아이디어 특정 값이 등장하는 첫 번째 위치와 마지막 위치를 찾아 위치 차이를 계산해 문제를 해결할 수 있다. bisect_left와 bisect_right를 이용해 각각의 위치를 구한다. 2) 소스코드 # 1. bisect 라이브러리 이용 from bisect import bisect_left..
[이코테] 문제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 연산의 시간복잡도는..
[이코테] 예제2 - 값이 특정 범위에 속하는 데이터 개수 구하기 (한줄평) bisect 라이브러리 사용법을 익힐 수 있는 기초 문제! 사용하지 않으면 잊어버릴 듯 하니 추후 복습 필요! 풀이 시간: 10분 이내 1) 문제 해결 아이디어 오름차순 정렬되어있는 리스트(a)에서 특정 범위(left_value ~ right_value)에 속하는 데이터 개수를 구하는 문제다. bisect는 정렬된 배열에서 특정 원소를 찾을 때 사용한다. bisect_left(a, x) 정렬된 순서를 유지하면서 리스트 a에 데이터 x를 삽입할 가장 왼쪽 인덱스 리턴 bisect_right(a, x) 정렬된 순서를 유지하면서 리스트 a에 데이터 x를 삽입할 가장 오른쪽 인덱스 리턴 [참고] https://velog.io/@woo0..
[이코테] 예제1 - 이진 탐색 (한줄평) 이진 탐색 기초 문제로 재귀, 반복문 구현 방식 둘다 풀어보면 좋은 문제! 이 문제는 n개의 숫자에서 찾으려고 하는 값(target)이 있으면 해당 인덱스를 출력하는 문제다. (풀이1) 재귀 함수로 구현 풀이 시간: 15분 이내 1) 문제 해결 아이디어 1. 타겟을 찾으면 인덱스를 리턴한다. 2. 타겟이 중간점 값보다 작으면 왼쪽 부분에 대해 이진 탐색 수행을 위해 끝점을 (mid - 1)로 넘겨 binary_search()를 리턴한다. 3. 타겟이 중간점 값보다 크면 오른쪽 부분에 대해 이진 탐색 수행을 위해 시작점을 (mid + 1)로 넘겨 binary_search()를 리턴한다. 2, 3번에서 binary_search()를 그냥 호출하는 것이 아니라 bin..
