✅문제 - 히스토그램에서 가장 큰 직사각형 (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..
✅문제 - 문자열 집합(14425번)✅오늘 배운점문제에서 두 집합 간의 비교를 위해 in method를 사용하였다.하지만 처음에 list에서 in method를 사용한 경우에 시간이 3724ms나 소요 되어 문제가 있다고 판단했다.그래서 list를 set로 변경하였더니 시간이 116ms로 감소하였다.이유는 파이썬 홈페이지에서 확인할 수 있었다set 자료형에서 in method의 시간복잡도는 최선: O(1) 최악: O(N)이고list 자료형에서 in method의 시간복잡도는 O(N)인 것을 확인할 수 있었다. ❗❗❗ 앞으로 성분의 포함 여부를 사용할 때는 set를 사용하자!! ✅첫 코드 - (시간 3724ms)import sysindex = int(sys.stdin.readline().rstrip()..
