✅문제 - 파일 합치기 (11066번) ✅필요 알고리즘 개념 - DP🔵특정 경로를 지나는 DP◼ 예제 입력 40 30 30 50의 경우위의 경우에 3가지 케이스가 존재할 수 있다.1) (1) + (2 + 3 + 4)2) (1+2) + (3+4)3) (1+2+3) + (4) 즉 중간 경로로 k를 선택해 지나가는 것이다. 그러므로 dp를 1차원 배열이 아닌 2차원 배열로 만들어 준다.dp[start][end] = min(dp[start][mid] + dp[mid+1][end]) + cost[start][end]를 만족하는 dp를 만든다. ✅필요 알고리즘 개념 - Knuth optimizationdp[start][end] = min(dp[start][mid] + dp[mid+1][end]) + cost[st..
✅문제 - K번째 수 (1300번) ✅필요 알고리즘 개념 / 풀이 알고리즘🔵이분탐색◼ 소주병 뚜껑의 숫자 맞추기 처럼 Up Down 식으로 원하는 값을 찾아 가는 것이다.◼ 정렬된 리스트에서만 사용이 가능하다. 🔵아이디어 - 이분탐색의 적용◼ 숫자가 N^2개 존재하므로 1~N^2 번째 숫자까지 존재한다.◼ k번째를 찾는 것이 아니라 1~N^2까지의 숫자를 선택해 해당 숫자보다 작은 숫자가 k개인 숫자를 찾는다. 🔵아이디어 - 특정 숫자보다 작은 숫자의 탐색◼ 입력 받은 2차원 배열은 구구단의 성질을 띈다. ◼ 이 성질을 이용하면 구구단 i단 에서 k보다 작은 숫자의 갯수는 k//i가 된다.◼ 이 성질을 이용하여 1~N을 탐색하며 k보다 작은 숫자의 갯수를 센다. ✅코드import sysinput =..
✅문제 - 공유기 설치 (2110번) ✅필요 알고리즘 개념 - 이분탐색◼ 이 문제의 키 포인트는 공유기 사이의 거리를 이분 탐색으로 찾는 것이다.◼ 공유기 간의 가장 가까운 거리는 1 가장 먼 거리는 마지막 좌표 - 첫 좌표가 된다. 이 거리 사이에서 이분탐색을 통하여서 최대 거리를 구하면 된다. ✅코드import sysimport bisectinput = sys.stdin.readlinen,c = map(int,input().rstrip().split())house_distance = []for _ in range(n): house_distance.append(int(input().rstrip()))# 이분 탐색은 정렬된 list에서 사용하는 것이므로 정렬한다.house_distance.sort..
✅문제 - 히스토그램에서 가장 큰 직사각형 (6549번) ✅필요 알고리즘 개념 - (분할 합 / 스택)🔵 풀이 1 - 스택을 이용한 풀이1. stack에 높이가 담겨진 num_list의 idx를 push 하다가 num_list[stack[-1]] 의 값이 num_list[idx] 보다 큰 경우 stack을 pop하여 tmp에 저장한다.(이 때 num_list[stack[-1]] 의 값이 num_list[idx]의 값 이하가 될 때까지 pop을 진행한다. )--> 이 말 뜻은 pop하여 얻은 tmp 값은 stack에 남아 있는 값들보다 크다는 것을 의미한다.2. 직사각형의 너비와 높이를 구한다.높이는 num_list[tmp]이 된다. ( 우리가 push 하는 것은 높이가 아니라 높이가 들어있는 idx 값..
✅문제 - 피보나치 수 6 (11444번) ✅필요 알고리즘 개념 - 분할 합🔵 자연수 a의 1024제곱을 구하는 상황 ◼ Dynamic Programming이나 재귀를 이용하면 최소 1024번의 연산을 진행해야 한다.◼ (a^2)^2 = a^4 인 성질을 이용하면 a^1024 를 10번의 계산으로 구할 수 있다. 이는 제곱 연산의 분할 합 개념을 이용한 것이다. 🔵 피보나치 수열의 분할 합 개념피보나치 수열을 행렬을 통하여 구할 수 있다.이 개념을 적용하면 피보나치 수열을 다음과 같이 표현할 수 있다.이 때 행렬의 n제곱을 하는 과정에서 위에 말한 분할 합의 개념을 적용하면 행렬의 n제곱을 쉽게 구할 수있다.이를 통해 피보나치 수열의 n항을 쉽게 구할 수 있다. ✅코드import sysinput..
