✅문제 - 공유기 설치 (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..
✅문제 - AC(5430번) ✅아이디어🔵문제 조건시간제한이 1초 이므로 연산을 2000만 번 안에 끝내야 한다. (Python 은 1초에 2000만 번의 연산을 한다고 가정하자)이때 함수의 최대 길이가 100,000이므로 시간 복잡도가 O(N^2)을 넘으면 시간 초과에 걸리게 된다.🔵실패 했던 아이디어실제로 R인 경우에는 reverse를 D인 경우에는 pop을 실행했다. 이때 함수의 길이만큼 for문을 돌려야 하고 그 안에서 if 문을 돌려야 하므로 시간 복잡도가 O(N^2)이 된다.정말 처참한 결과다🔵성공한 아이디어실제로 pop 이나 reverse를 진행하지 않는 방법을 생각했다.1. 함수에서 RR이 나오면 순서가 바뀌지 않으므로 입력받은 함수에서 replace("RR","")을 통해 모든 RR을..
✅문제 - 나머지 합 ✅필요 알고리즘 개념 - 누적합🔵Prefix Sum (구간 합)◼ 누적합 문제의 경우 Prefix Sum을 이용해 문제를 푼다. 아래의 예시를 보자num_list = [1,2,3,4,5]accum = 0for i in range(n): accum += num_list[i] print(accum,end=" ")위와 같은 코드를 실행시키면 아래와 같은 결과를 얻을 수 있다.✅코드import sysinput = sys.stdin.readlinen,m = map(int,input().rstrip().split())num_list = list(map(int,input().rstrip().split()))rem_list = [0 for i in range(m)]rem_list[0]..
✅문제 - 평범한 배낭(12865번) ✅필요 알고리즘 개념 - 다이나믹 프로그래밍(Dynamic Programming)🔵What is Dynamic Programming ? ◼다이나믹 프로그래밍이란 한 번 해결된 문제의 정답을 메모리에 기록하여, 한 번 계산한 답은 다시 계산하지 않도록 하는 기법이다. ◼Dynamic Programming Table 을 만들어 상태를 이전 결과들을 저장한다. ◼푸는 방식은 크게 2가지 방법으로 바텀업/탑다운 방식으로 풀고 탑다운 방식은 주로 재귀함수를 이용 한다. ✅코드import sysinput = sys.stdin.readlinen,k = map(int,input().rstrip().s..
