개발 일지

문제 1931번: 회의실 배정 (acmicpc.net) 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 풀이 최대한 많은 회의실 예약을 받으려면 회의시간이 짧고 일찍 끝나는 회의를 받으면 된다. 우선순위 큐에 회의가 끝나는 시간, 시작하는 시간 순으로 넣어주면 된다. import heapq import sys input = sys.stdin.readline N = int(input().rstrip()) heap = [] for _ in range(N): start,end = map(int,input().split()) heapq.heappush(heap,(end,start)) answer = 0 now = 0 while he..

문제 10986번: 나머지 합 (acmicpc.net) 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 풀이 구간합이 M으로 나누어 떨어지려면, 슬라이딩 윈도우를 이용하되 A[i]와 A[j]의 M으로 나누었을 때 나머지가 서로 같아야 한다. 예를 들어 어떤 수 a와 b가 각각 a = 3*n + 1, b = 3*m + 2 라고 할 때, a-b = 3*(n+m) - 1로 3으로 나누어 떨어질 수 없다. a = 3*n + 1, b = 3*n + 1 이라면 가능하다. 이..

문제 11659번: 구간 합 구하기 4 (acmicpc.net) 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 풀이 일반적인 구간 합 문제이다. 다만 입력이 많아 sys 모듈 사용이 권장된다. import sys input = sys.stdin.readline N,M = map(int,input().split()) dp = [0] for elem in map(int,input().split()): dp.append(dp[-1] + elem) for _ in range(M): i,j = ..

문제 12865번: 평범한 배낭 (acmicpc.net) 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 풀이 이미 다룬 적 있는 알고리즘이다. 0/1 Knapsack Problem - Dynamic Programming (tistory.com) 0/1 Knapsack Problem - Dynamic Programming 얼만큼의 비용과 보상이 정해진 여러개의 물체가 있다고 하자. 특정 용량까지 수용 가능한 마대에 이 물체들을 마대의 최대 수용량..

문제 채점 현황 (acmicpc.net) 채점 현황 www.acmicpc.net 풀이 두 개의 포인터 i와 j가 있을 때, ACAYKP와 CAPCAK 를 각각 A 와 B 라고 했을 때 LCS를 찾는 과정은 다음과 같을 것이다. i : 0, j : 0 이고, A[i] = 'A', B[j] = 'C' 이므로, 이제 i에 1을 더한 경우와 j에 1을 더한 경우 각각을 살펴 봐야한다. 먼저 i 에 1을 더한 경우를 살펴본다. i : 1, j : 0 이고, A[i] = 'C', B[j] = 'C' 이므로 i와 j 모두 1 씩 더한다. i : 2, j : 1 이고, A[i] = 'A', B[j] = 'A' 이므로 i와 j 모두 1 씩 더한다. i : 3, j : 2 이고, A[i] = 'Y', B[j] = 'P' ..

문제 2565번: 전깃줄 (acmicpc.net) 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 풀이 전깃줄이 어떤 상황에 교차되는지 따져보면 금방 LIS 문제라는 것을 알 수 있다. 따라서 전선을 나타내는 리스트를 만들어 가장 긴 증가하는 부분수열을 찾아주면 된다. N = int(input()) graph = [0]*501 for _ in range(N): a,b = map(int,input().split()) graph[a] = b dp = [1]*501 for i in range(1,501): for j in..

문제 11054번: 가장 긴 바이토닉 부분 수열 (acmicpc.net) 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 풀이 LIS를 각각 0번 왼쪽 -> 오른쪽으로, 오른쪽->왼쪽으로 한번씩 하면 된다. 일반적인 LIS와 마찬가지로 이진탐색을 쓸 수 있고, 두 번 해주면 되겠다. N = int(input()) A = [0] + list(map(int,input().split())) left = [1]*1001 right = [1]*1001 for i in range(1,N+1): for j in range(1,i): if A[..

문제 11053번: 가장 긴 증가하는 부분 수열 (acmicpc.net) 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 풀이 18353번 - 병사 배치하기 (tistory.com) 18353번 - 병사 배치하기 문제 N명의 병사가 무작위로 나열되어 있다. 각 병사는 특정한 값의 전투력을 보유하고 있으며, 병사를 배치할 때는 전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치를 하고자 한다. 다 forteqook.tistory.co..

문제 코딩테스트 연습 - 두 큐 합 같게 만들기 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 큐에서 popleft 해서 다른 큐에 append 하는 과정은 마치 두 큐를 하나의 리스트로 이어놓은 다음, 두개의 포인터를 계속해서 옮겨가는 과정과 같다. 따라서 start, end를 queue1의 첫번째 인덱스와 마지막 인덱스로 초기화한 뒤, 만약 두 큐 원소들의 합의 절반 값인 target 보다 start부터 end까지의 구간 합 now 가 크다면 start에 1을 더하면서 원래 start에 있..

풀이 2156번: 포도주 시식 (acmicpc.net) 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 문제 dp[i]를 i 번째 와인을 골랐을 때 마실 수 있는 와인 양의 최대값으로 한다.3 잔 연속으로 마실 수 없다는 점에 착안하여 점화식을 세우되, i-1 번째 와인을 마시면 i-4 번째 와인을 마시는 경우와 i-3 번째 와인을 마시는 경우 두가지가 존재한다는 점을 주의하자. N = int(input()) wine = [0]*10001 for i in range(1,N+1): wine[i] = int(inp..