이 문제는 이것이 코딩테스트다. 259페이지 문제이다. 이 문제는 E,V(간선,노드)가 100이하로 작다. 전형적인 플로이드 워셜문제이다. 일반적으로 500정도면 플로이드워셜을 사용하여도 된다. 아래는 나의코드이다. import sys INF = int(1e9) companyNum,wayNum = map(int,sys.stdin.readline().split()) myMap= [[INF]*(companyNum+1) for _ in range(companyNum+1)] for i in range(1,companyNum+1): myMap[i][i]=0 for _ in range(wayNum): temp=list(map(int,sys.stdin.readline().split())) myMap[temp[0]][..
Problem Solving
이 문제는 이것이 코딩테스트다.226문제이다. 거스름돈 문제와 비슷하지만, 거스름돈은 최소단위의 돈이 있기에 그리디를 사용할 수 있다. 예를 들면 6원을 받았을때 거스름돈 문제는 1원단위의 돈이 있기때문에 어떤경우에도 거스름돈을 줄 수 있다. 하지만 이 문제에서는 1원단위의 돈이없을 수 있다. 그렇기에 다이나믹프로그래밍을 이용하여 풀어야 한다. 아래는 나의 코드이다. import sys moneyNum, moneyVal=map(int,sys.stdin.readline().split()) money=[] for i in range(moneyNum): money.append(int(sys.stdin.readline().rstrip())) money.sort() dp=[-1]*10001 # 초기값 설정 동전화..
이 문제는 이것이 코딩테스트다 223페이지 문제이다. 아래는 나의 코드이다. import sys N= int(sys.stdin.readline().rstrip()) dp=[0]*1001 dp[0]=0 dp[1]=1 dp[2]=3 for i in range(3,N+1): dp[i]=dp[i-1]+ 2*dp[i-2] print(dp[N]%796796) 아래는 예시코드이다. # 정수 N을 입력 받기 n = int(input()) # 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화 d = [0] * 1001 # 다이나믹 프로그래밍(Dynamic Programming) 진행 (보텀업) d[1] = 1 d[2] = 3 for i in range(3, n + 1): d[i] = (d[i - 1] + 2 * d[..
이것이 코딩테스트다. 220페이지 문제이다. 스키장 3,5,7일권 최저가 구하기 문제와 비슷하다. 다이나믹프로그래밍의 정석 문제 같다. 다이나믹 프로그래밍은 보통 min(나올수있는 경우들) 또는 max(나올 수 있는 경우들)을 이용한다. 이 문제는 바텀업방식문제이다. 아래는 나의 코드이다. import sys N=int(sys.stdin.readline().rstrip()) food = list(map(int,sys.stdin.readline().split())) dp=[0]*N dp[0]=food[0] dp[1]=max(food[0],food[1]) for i in range(2,N): dp[i] = max(dp[i-2]+food[i],dp[i-1]) print(dp) print(dp[N-1]) 아래는..
이 문제는 이것이 코딩테스트다. 217페이지 문제이다. 문제 난이도는 높지 않았다. 아래는 나의 코드이다. import sys N=int(sys.stdin.readline().rstrip()) dp=[0]*(N+1) dp[1]=0 dp[2]=1 for i in range(2,N+1): temp = [N] * 4 if i%5 == 0: temp[0] = dp[i//5] + 1 if i%3 == 0: temp[1] = dp[i//3] + 1 if i%2 == 0: temp[2] = dp[i//2] + 1 temp[3]=dp[i-1]+1 dp[i]=min(temp) print(dp[N]) 아래는 예시코드 # 정수 X를 입력 받기 x = int(input()) # 앞서 계산된 결과를 저장하기 위한 DP 테이블 ..
이 문제는 이것이 코딩테스트다 201페이지 문제이다. 이 문제는 구현자체는 쉽지만 입력의 최대값이 20억이여서 최악의 경우 최대 20억의 실행이 발생할 수있다. 그러므로 이진탐색을 사용하여야 한다. 아래는 나의 코드이다. # 떡의 개수(N)와 요청한 떡의 길이(M)을 입력 n, m = list(map(int, input().split(' '))) # 각 떡의 개별 높이 정보를 입력 array = list(map(int, input().split())) # 이진 탐색을 위한 시작점과 끝점 설정 start = 0 end = max(array) # 이진 탐색 수행 (반복적) result = 0 while(start mid: total += x - mid # 떡볶이 양이 부족한 경우 더 많이 자르기 (오른쪽 부..
이 문제는 이것이 코딩테스트다. p197페이지 문제이다. 이진탐색을 이용하지 않고도 쉽게 풀 수 있기만 오늘은 이진탐색을 연습하는 날이기에 이진탐색을 이용하여 풀었다. 이진탐색을 구현할 수만 있다면 문제의 난이도는 쉽다. 아래는 나의 코드이다. import sys seller_N = int(sys.stdin.readline().rstrip()) seller = list(map(int,sys.stdin.readline().split())) customer_N=int(sys.stdin.readline().rstrip()) customer=list(map(int,sys.stdin.readline().split())) seller.sort() def search(searchList,target): low=0 h..
이것이 코딩테스트다. 182페이지문제이다. 시간체한이 2초인 문제였다. 아래는 나의 코드이다. import sys M,N= map(int,sys.stdin.readline().split()) A=list(map(int,sys.stdin.readline().split())) B=list(map(int,sys.stdin.readline().split())) for i in range(N): min_a= min(A) max_b= max(B) A.remove(min_a) A.append(max_b) B.remove(max_b) B.append(min_a) print(sum(A)) 시간이 꽤 걸리는 코드이다. 지금보니 N과 리스트 크기에 따라 시간초과가 날수도 있을 듯하다.... 아래는 예시코드이다. n, k =..
