B_log

최적 부분 구조 - 각 부분 문제의 최적해만 있으면 전체 문제의 최적해를 쉽게 얻어낼 수 있을 경우 최적 부분 구조 조건을 성립한다고 한다. (예시) - 서울에서 부산을 가는 최단 경로의 경우 이 최단 경로가 대전을 지난다고 가정한다. 이 때, 최단 경로는 (서울, 대전)의 최단경로, (대전, 부산)의 최단 경로를 찾아서 이으면 구할 수 있다. 즉 부분문제를 통해 전체의 최적해를 구할 수 있으므로 이는 최적 부분 구조라고 할 수 있다. 최적 부분 구조가 존재하지 않을 경우 - 서울에서 부산으로 향하는데 고속도로의 통행료 합이 3만원을 초과하지 않는 최단경로를 찾을 때, 대전에서 부산으로 가는 경로가 2가지 있다. 통행 시간 통행료 경로 A 2 시간 1만원 경로 B 1 시간 2만원 - 이 두 경로 중 어느..

문제 문제 상황 - 숫자 string과 제거할 숫자의 개수를 입력받아 숫자를 제거하여 얻을 수 있는 가장 큰 숫자를 찾는다. 해결 전략 - number의 자리가 최대 100만 자리 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 def solution(number, k): stack = ["0"] # 처음 빈문자를 넣었으므로 0을 지우기 위해 k를 하나 증가시킨다. k += 1 for i in range(len(number)): if k == 0: stack.append(number[i]) continue while k > 0: # 비어있지 않으면 number[i]로 계속 비교해 나간다. stack의 마지막 값보다 # number[i]가 더 크면 stack..

문제 문제 상황 - 하노이의 탑을 옮기는 과정을 리스트에 담아 출력한다. 해결 전략 - 하노이의 탑에서 중요한 것은 시작점, 경유점, 도착점이 바뀐다는 사실과 전체 문제가 부분 문제로 이루어져있다는 사실이다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 # 출발노드, 경유노드, 도착노드, 판의 수 def hanoi(start_node, pass_node, desti_node, n): global result if n == 1 : return [start_node, desti_node] else : result.append(hanoi(start_node, desti_node, pass_node,n-1)) result.append([start_node, desti_node]) ..

문제 문제 상황 - 주어진 문자열 내에 존재하는 회문을 찾아 그 가장 긴 길이를 반환하는 문제이다. 해결 전략 - 주어진 조건이 2,500자로 O(N^2)을 해도 6,250,000로 매우 안정적인 범위이다. 회문을 검사하는 함수를 만들고 검사할 시작점과 끝점을 탐색하며 양 끝이 같아질 경우만 그 사이 리스트를 회문 검사 하였다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 def is_palindrome(lst): if len(lst)%2 == 0 and lst[:len(lst)//2] == lst[len(lst)//2:][::-1]: return True elif len(lst)%2 == 1 and lst[:len(lst)//2] == lst[(len(lst)//2)+1:][:..

code 문제 문제 상황 - 총 합이 주어지고 요소의 수가 주어졌을 때 곱이 최대가 되는 집합을 찾는 문제 해결 전략 - 몇차 함수인지를 떠나 해의 개수가 늘어날 수록 자연수 범위에서 함수의 증가속도는 떨어진다. 즉, 요소의 곱은 모든 항이 다 같을 때, 가장 크면 같지 않더라도 그 차이가 적을수록 결과가 크게 된다. - 최소 요소가 1이므로 총 합은 최소 1*n = n보다 커야하므로 n > s이면 [-1]을 반환한다. - 고르게 나눠 몫을 배치하고 나머지를 1씩 배치하면 곱이 최대가 되는 집합이 된다. 코드 1 2 3 4 5 6 7 8 def solution(n, s): if n > s: return [-1] q, r = divmod(s, n) result = [q] * n for i in range(..

문제 문제 상황 - works에 존재하는 숫자들은 남은 업무량을 의미하고 야근 지수는 이 숫자들의 제곱의 합을 의미한다. 즉, works에 존재하는 요소들에서 n 만큼을 제거하여 각 요소의 제곱의 합을 계산한 결과가 최소가 되게 한다. 해결 전략 - works의 길이가 20,000 이므로 O(N^2)면 400,000,000(4억)의 연산이 된다. 즉 N^2는 시간 초과가 날 가능성이 높다. 최대 NlogN안에서 해결해야한다. 코드 # 성공한 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 def solution(n,works): # 요소를 다 합친 값보다 줄일 수 있는 값이 더크면 ..

문제 문제 상황 - permutation은 O(N!)의 속도를 갖기 때문에 permutation을 전부 계산하고 인덱스로 찾으면 속도 이슈가 난다. 그래서 수학적 계산을 해야한다. 해결 전략 - 먼저 (n-1)!을 기준으로 나눠 몫만큼 아래로 내려간다. 만약 나머지가 0이라면 n-1번째 요소의 숫자를 리스트의 맨 앞에 두고 남은 리스트 값을 역순으로 하여 붙여준다. 나머지가 0이 아니라면 나머지를 새로운 k로 설정해준다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 import math def solution(n,k): # n명의 사람 리스트 lst = [i for i in range(1,n+1)] result = [] # 조건을 만족할..

문제 문제 상황 - 계단을 뛰는 방법이 1칸 또는 2칸일 때에 n번째 칸에 도달하는 방법의 수 해결 전략 - 전형적인 피보나치 문제로 매우 쉬운 문제 코드 1 2 3 4 5 6 7 8 def solution(n): cache = [0 for i in range(n+1)] cache[1] = 1 if n >=2: cache[2] = 2 for i in range(3,n+1): cache[i] = (cache[i-1] + cache[i-2])%1234567 return cache[n] Colored by Color Scripter cs 해설 - 선택지가 2개이고, 어떤 선택을 만드는 방법이 이전 부분 문제의 합이므로 dp를 사용한다. 새로 학습한 것 & 실수 - 처음에 n의 조건이 1이상인데 cache[2]..