본문 바로가기

Study

(31)
[ 백준/python ] 1931 : 회의실 배정 - 문제 - 제출 이 문제를 처음 봤을 때는, 당연히 시작하는 시간을 기준으로만 생각했다. 시작 시간이 작은 순서대로 배열하고 시작 시간이 같다면 끝 시간이 작은 순서대로 배열하여 비교해가며 정렬하면 최대 횟수가 나올 것이라고 생각했다. 하지만 계속 생각을 해도 어디엔가 오류가 있었다. 따라서 반대로 끝나는 시간을 기준으로 생각해봤다. 끝나는 시간을 기준으로 배열하고 끝나는 시간이 같다면 시작하는 시간을 기준으로 배열하였다. 끝나는 시간이 빠를수록 같은 시간 범위 내에 많은 미팅 횟수를 넣을 수 있다. 따라서 끝나는 시간이 우선 기준이 되어야 한다. 배열을 마쳤다면, 가장 빠른 시간에 끝나는 미팅으로 end 값을 초기화하고 미팅을 한 번 시행했다고 카운팅한다. 그 후, 이전 미팅이 마친 시간과 다음 끝나..
[ 백준/python ] 1715 : 카드 정렬하기 - 문제 - 제출 최소한의 비교를 하려면 작은 묶음부터 나열한 후, 가장 작은 페어의 수를 더하고 더한 수를 나열된 리스트에 추가하고 또 나열하는 과정을 리스트에 숫자가 하나가 될 때까지 반복하면 된다. 하지만 이 문제의 포인트는 바로 시간 초과 ㅠㅠ 그래서 구글링을 했더니 우선순위 큐를 사용해야 한다고 했다. while문 안에서 계속 리스트에서 값을 꺼내고 넣고 정렬하는 과정을 반복하는 것이 시간이 너무 많이 걸려서 인 듯했다.. 그래서 값을 넣으면 가장 작은 값부터 자동으로 정렬되는 우선순위 큐를 사용해야 했다. ㅎㅎ 자료 구조 형태를 바꾸니 바로 해결! import heapq N = int(input()) cards =[] for _ in range(N): heapq.heappush(cards,in..
[ 백준/python] 2217 : 로프 - 문제 - 제출 N개의 로프가 주어졌을 때 k개의 로프에 모두 고르게 w/k 만큼의 중량이 걸리게 된다. 따라서, k가 달라짐에 따른 최대 중량을 구하고 그중에서 가장 최대인 값을 알아내는 것이 문제의 포인트이다. k개의 로프 중 가장 무게가 작은 로프를 k개가 모두 동일하게 들어 올리면, 즉 k * (k개 중 최소 w)가 k개의 로프가 들 수 있는 최대 무게라고 할 수 있다. 따라서, 주어진 로프를 무게가 무거운 순서대로 나열하고 위에서 찾아낸 법칙을 적용하면 최대 무게를 구할 수 있다. N = int(input()) rop = list(int(input()) for _ in range(N)) rop.sort(reverse = True) result = [] for k in range(N): resu..
[ 백준/python ] 5585 : 거스름돈 - 문제 - 제출 거스름돈 개수가 최소인 경우를 찾는 문제이다. 즉, 지불하고 남은 돈을 최대한 큰 단위의 잔돈으로 거슬러 주는 방법을 찾는 것이다. 따라서, 거슬러 줘야 할 금액이 잔돈 단위보다 크다면 해당 잔돈을 뺀 금액을 남은 금액이라고 하고 거스름돈 개수를 증가시키면 된다. N = int(input()) def changes(N): change = 1000 - N coins = [500,100,50,10,5,1] count = 0 for c in coins: while change >= c: change -= c count += 1 else: continue print(count) changes(N) 거스름돈의 단위도 제시되어 있고, 그리디 알고리즘의 가장 기본적인 규칙에 해당하는 문제인 것 같다..
[백준/python] 9251 : LCS * LCS = 두 수열에서 가장 긴 공통부분 수열. 즉, 연속적일 필요는 없으나 순서가 일치하는 부분 수열이어야 한다. - 문제 - 제출 두 문자열에 대해서 Matrix를 그려 생각해보자. (문제에 예시로 나와있는 문자열을 이용함) 두 문자열을 문자를 하나 씩 추가해서 완성한다고 생각했을 때, 각 단계에 대한 LCS의 길이는 아래의 표로 정리할 수 있다. C A P C A K A 0 1 1 1 1 1 C 1 1 1 2 2 2 A 1 2 2 2 3 3 Y 1 2 2 2 3 3 K 1 2 2 2 3 4 P 1 2 2 2 3 4 두 가지 경우로 나누어 생각해야 한다. 1. 마지막에 추가된 문자가 서로 같은 경우 서로 같다면, 공통된 마지막 문자는 LCS에 포함되게 된다. 따라서, LCS의 길이는 두 문자열에 ..
[백준/python] 10844 : 쉬운 계단 수 - 문제 - 제출 각 자리에 0부터 9까지의 자연수가 올 수 있으므로, 한 row에 10개의 space가 있는 matrix를 정의한다. 우선, 첫 번째 자리에는 0을 제외한 모든 수가 올 수 있으므로 matrix의 첫 번째 row에는 첫 번째 자리를 제외한 모든 자리에 1을 넣는다. 그다음은 3가지 경우로 나누어 생각해야 한다. 1. 0이 오는 경우 이 경우에는 이전 숫자가 1이었다가 down 하는 경우만 존재한다. 즉, 이전 숫자가 1이 되는 경우의 수와 같다는 의미이다. => cache[i][0] = cache[i-1][1] 2. 9가 오는 경우 이 경우에는 이전 숫자가 8이었다가 up 하는 경우만 존재한다. 즉, 이전 숫자가 8이 되는 경우의 수와 같다는 의미이다. => cache[i][9] = c..
[백준/python] 2225: 합분해 - 문제 - 제출 주어지는 정수 N & K 가 모두 1 이상 200 이하의 수임을 감안하여 저장공간 (cache)를 먼저 정의한다. 1. N == 1인 경우 0 또는 1을 K개 가지고 1을 만들어야 하므로, 1 하나와 K-1개의 경우만 존재한다. 이때, 문제에서 덧셈의 순서가 바뀐 경우는 다른 경우로 센다고 했으므로 모든 K에 대해 K개의 경우가 존재한다. 2. K == 1인 경우 [0,N] 사이의 정수 1개를 가지고 N을 나타내야 하므로 모든 N에 대하여 1 경우만 존재한다. 3. 그 외의 모든 경우 다른 경우는 어느 정도의 (N, K) 조합에 대해 표를 구성해보면 쉽게 점화식을 얻을 수 있다. 찾아낸 점화식 => cache[i][j] = cache[i-1][j] + cache[i][j-1] ( N &..
알고리즘(1) - 그리디 - 최적의 해에 가까운 값을 구하는 방법이나, 최적의 해라고 확신할 수는 없음 (근사치 추정) => 한계 - 매 순간 최적이라고 생각되는 경우 한 가지를 선택하는 방법 - 동적 계획법의 computation complexity를 극복하기 위해 나온 기법 1. 동전 문제 - 최종 지불 가격 = 4720 - 1원, 50원, 100원, 500원 동전을 가지고 최소한의 동전 개수로 지불하는 방법 => 가장 큰 동전으로 먼저 지불하고, 남은 금액이 해당 동전보다 적은 경우 다음 동전으로 지불하는 방식 => 그러면 일단 동전의 크기가 큰 순서대로 sorting def paiedCoin(coins, pay): result = list() count = 0 coins.sort(reverse = True) # 큰 순서대..