시작이 반

그리디 문제이다. 회의가 끝나는 시간을 기준으로 오름차순으로 정렬을 한 후 그 안에서 시작 시간을 기준으로 정렬을 다시한다. 그 후 제일 먼저 끝나는 회의를 선택하고 다음으로 선택했던 회의 시간의 끝나는 시간보다 큰 시작 시간을 선택한다.(이미 끝나는 시간으로 정렬이 되어있기 때문에 고려안해두됨) n = int(input()) input_list = list() result_list = list() for i in range(n): start, end = map(int, input().split()) term = end - start input_list.append((start, end, term)) input_list.sort(key=lambda x: (x[1], x[0])) for i in range..

그리디 문제의 기초이다. 최소의 동전개수로 해당 가격을 만드는 문제 주어진 제일큰 동전부터 시작하여 만들려고 하는 가격을 나눴을때 몫이 있다면 동전의 개수를 해당 몫만큼 더해주고 나머지를 가지고 다음 계산을 이어간다. ( 가장 큰 동전부터 선택하여 구하는 것 ) n, k = map(int, input().split()) a = list() for _ in range(n): a.append(int(input())) result = 0 def coin_zero(): global k, a, result for i in range(n-1, -1, -1): quotient = k // a[i] remainder = k % a[i] if quotient > 0: result += quotient k = remain..

knapsack알고리즘 문제이다. 1. 배낭에 물건을 넣는다. - 물건을 넣기전 상태에서 (가방 무게 - 해당 물건 무게)의 가치 + 해당 물건 가치 2. 배낭에 물건을 넣지 않는다. - 이전 값을 그대로 사용한다. ex) 물건 개수 : 4 가방에 들어갈 수있는 최대 무게 : 7 1번 물건 : 6 13 2번 물건 : 4 8 3번 물건 : 3 6 4번 물건 : 5 12 dp[i][j] 1. 물건을 넣는다 : dp[i-1][j - 해당 물건 무게] + 해당 물건 가치 2. 물건을 넣지 않는다 : dp[i-1][j] 1, 2중 최대값을 넣는다. 가방무게 물건 0 1 2 3 4 5 6 7 1번 물건 0 0 0 0 0 0 13 13 2번 물건 0 0 0 0 8 8 13 13 3번 물건 0 0 0 6 8 8 13 ..

연속된 숫자를 몇개 선택해서 더했을때 가장 큰 합을 구하는 것이다. 이는 양수는 계속 더해주고 음수일때 선택을 해야한다. 연속해서 더할 것인지 더하지 않을 것인지 정해야한다. 만약 숫자가 6 -5 1 2 3 -4 5 이렇게 있다면 1 2 3 은 더해서 6을 만든다. 이때 연속된 수로 -4가 나오게 되는데 계속 더해줄 것인지 빼고 다음 숫자부터 다시 시작할 것인지... 그렇다면 어떻게 정할까? 음수를 더했을때 보다 해당 음수 보다 클 경우 더해주면 된다. 1 + 2 + 3 = 6 (6 + -4 = 2 ) > -4 이기 때문에 계속 더해준다. 이런식으로 하면 1 2 3 -4 5 를 선택했을때 제일 큰 수 7이 나온다. 만약 음수를 기준으로 더하고 말지를 정한다면 ( 처음에 생각한 방법) 1 2 3 를 선택한..

처음에 무작위로 뽑았을때 만들수 있는 집합중 공통된 가장 긴 것을 찾는줄 알았다.. 풀이 만약 s1[i] == s2[j]라면 ( 추가한 문자가 같을때 ) dp[i][j] = dp[i - 1][j - 1] + 1 ( 추가되기전 값 + 1) 다르면 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) (추가되기 전 값들 중 가장 큰 값) dp[i]j] C A P C A K 0 0 0 0 0 0 0 A 0 0 1 1 1 1 1 C 0 1 1 1 2 2 2 A 0 1 2 2 2 3 3 Y 0 1 2 2 2 3 3 K 0 1 2 2 2 3 4 P 0 1 2 3 3 3 4 s1 = ' '+input() s2 = ' '+input() dp = [[0] * len(s2) for _ in rang..

전깃줄을 입력을 받아서 list(tuple)형태로 만들고 key = tuple[0]값으로 역으로 정렬시킨다. ex) 첫번쨰 원소의 [0] 값+1의 크기만큼 list를 생성한다. dp = [1] * (link[0][0] + 1) 1 ~ 해당 전깃줄 갯수만큼 반복문을 돌린다. for i in range(1, n): 정렬된 원소를 보면서 a = link[i][0] b = link[i][1] 이전 값들중 b 값보다 큰 값들중 생성한 list의 최대값을 구한다. for j in range(i): if b < link[j][1]: max_value = max(max_value, dp[link[j][0]]) list[i]에 max값을 더해준다. dp[a] += max_value n = int(input()) link..

수열중 가장 긴 증가하는 부분 수열을 구하는 문제 dp[i] = (a[i] > a[0:i-1]보다 작은 값들 중) max( dp[0 : i-1] ) + 1 n = int(input()) a = list(map(int, input().split())) dp = [0] * n def longIncSequence(): dp[0] = 1 for i in range(1, n): max_value = 0 for j in range(i): if a[i] > a[j]: max_value = max(max_value, dp[j]) dp[i] = max_value + 1 longIncSequence() print(max(dp))

dp1 리스트 A의 i : 0 ~ n-1 에서의 증가하는 수열의 값을 구한다. dp2 리스트 A의 i : n-1 ~ 0 에서의 증가하는 수열의 값을 구한다. ex) dp3 dp3[0] = dp2[0] dp3[n-1] = dp1[n-1] 리스트 A의 i :1 ~ n-2 에서 1. 리스트 A의 j : 1 ~ i 부분에서 a[i] 보다 작은 값중에서 최대값 dp1[j] 을 찾는다. 2. 리스트 A의 j : i ~ n-2 부분에서 a[i] 보다 작은 값중에서 최대값 dp2[j] 을 찾는다. dp3[i] = 1번과 2번을 더한후 1을 더해준다. n = int(input()) a = list(map(int, input().split())) reverse_a = list(reversed(a)) inc_dp = [0]..