정렬된 배열에서 특정 수의 개수 구하기
유형 분석 및 구현 이 문제는 직접 이진탐색을 구현한다기 보단, 파이썬에서 제공하는 이진탐색을 활용한 탐색 방법을 사용한다. 순차적 탐색과 비교해보면 최대 100만개에 데이터 중에서 최대 100만개의 데이터를 찾아야한다. 하지만 이진 탐색을 활용하면 확 줄어든다. 코드 from bisect import bisect_left, bisect_right n = 7 x = 2 array = [1, 1, 2, 2, 2, 2, 3] left_index = bisect_left(array, x) right_index = bisect_right(array, x) print(left_index, right_index) result = right_index-left_index if result == 0: print("-1..
못생긴 수
유형 파악 및 구현 이 문제는 생각해내는게 좀 어려웠던 것 같다. 못생긴 수는 2, 3, 5의 조합들을 의미한다. 못생긴 수의 리스트를 보면 1, 2, 3, 2x2, 5, 2x3, 2x2x2, 3x3, 2x5 이런식으로 진행된다. 즉 초기 못생긴 수를 넣고 (2, 3, 5) 이미 들어간 못생긴 수에 2, 3, 5를 곱하는 방식으로 진행된다. 구현을 하기 위해서는 2 or 3 or 5가 다음에 곱해져야하는 리스트 인덱스를 담는 변수 -> i2, i3, i5 결과마다 가장 작은 것을 뽑아서 리스트에 넣기 전 결과를 표현하는 변수 -> next2, next3, next5가 필요하다. 코드 # 찾으려는 인덱스 n = int(input()) # 못생긴 수 초기화 ugly = [0]*(n+1) # 첫번째 못생긴 수..
병사 배치하기
유형 파악 및 구현 예를 들어, [15, 11, 4, 8, 5, 2, 4]가 있을 때, 오른쪽으로 갈수록 수를 크게 만들면서, 리스트 내의 요소가 가장 많은 경우를 구하는 것이다. 이는 전형적인 다이나믹 프로그래밍의 문제 중 하나인 '가장 긴 증가하는 부분 수열 문제'이다. [15, 11, 4, 8, 5, 2, 4] dp 리스트는 아래와 같은 방식으로 채워진다. 4 - [1] : 마지막 요소 뒤에는 아무 요소가 없다. -> dp(n-1) 2- [1] : 2의 뒤에는 2보다 작은 요소가 없다. -> dp(n-2) 5 - [2] : 5의 뒤에는 2 or 4를 넣을 수 있다. -> dp(n-3) = dp(n-2) + 1 or dp(n-1) + 1 8 - [3] : 8의 뒤에는 (5, 2) or (5, 4)를 ..
