시나위

https://www.acmicpc.net/problem/20438 20438번: 출석체크 1번째 줄에 학생의 수 N, 졸고 있는 학생의 수 K, 지환이가 출석 코드를 보낼 학생의 수 Q, 주어질 구간의 수 M이 주어진다. (1 ≤ K, Q ≤ N ≤ 5,000, 1 ≤ M ≤ 50,000) 2번째 줄과 3번째 줄에 각각 K명 www.acmicpc.net 동적계획법으로 누적합을 사용하는 문제이다. 출석체크 한 사람을 구한뒤에 출석하지 않은 학생을 하나하나 찾아서 계속 시간초과가 걸렸다. 누적합으로 구한뒤에 구간별로 출력하니 통과. import sys; input = sys.stdin.readline # 0 입력 N, K, Q, M = map(int, input().split()) sleep = set(m..

https://www.acmicpc.net/problem/9084 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net 동적 계획법은 볼때마다 새롭다. 요즘 계속 풀던 문제가 완전 탐색이었기 때문에 조금 더 오래 걸린 듯하다. 1, 5, 10 등 흔히 사용하는 동전만 나온다면 그리디 알고리즘으로 하는게 낫지만, 그렇지 않은 경우 동적 계획법을 사용해서 풀어야한다. 예를 들면 동전이 1, 4, 5이 있고 12원을 만들어야하는 경우 그리디 알고리즘으로 풀면 4개의 동전(5*2 + 1*2)이 필요하다. ..

https://www.acmicpc.net/problem/22862 22862번: 가장 긴 짝수 연속한 부분 수열 (large) 수열 $S$에서 최대 $K$번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 출력한다. www.acmicpc.net 투포인터를 시간초과가 되지 않고 풀 수 있다. 투포인터에 대한 내용은 최하단에 블로그를 참고하면 된다 N, K = map(int, input().split()) numbers = list(map(int, input().split())) ptr1, ptr2 = 0, 0 cnt, ans, dist = 0, 0, 0 while ptr1 != N and ptr2 != N: if numbers[ptr1] % 2: if cnt > 0: p..

https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 비트마스크를 사용한 조합문제이다. dp를 사용하지 않았고 비트마스크를 사용해서 모든 부분 수열의 합을 구했다. def main(): N, S = map(int, input().split()) seq = list(map(int, input().split())) answer = 0 for select in range(1, 1

https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 비트마스크와 동적 계획법을 사용해서 최소비용을 구하는 문제이다. 2차원 배열을 사용해서 푸는데, 상태는 지금까지 선택한 것들을 넣으면 되지만 row 값을 고르는게 오래걸렸다. 이전 값을 넣어야할지 현재 값을 넣어야할지 막막해서 결국 찾아보았고 현재 방문한 도시 번호를 넣는 걸로 하게 되었다. (이건 다른 문제를 더 많이 풀어보면서 감을 익혀야할거같다.) 알고리..

https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 동적 계획법을 사용한 문제인데 어떻게 짜야할지 막막했다. 그래서 구글링으로 LCS에 대해서 찾아보았고, 도움받은 것을 바탕으로 코드를 작성했다. 맨 아래 참고 블로그를 확인하자 a, b = input(), input() c, r = len(a), len(b) t = [[0 for _ in range(c + 1)] for _ in range(r + 1)]..

https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net import sys; input = sys.stdin.readline N = int(input()) node_parent = [-1 for _ in range(N)] node_son = [[] for _ in range(N)] root = 0 for son, parent in enumerate(map(int, input().split())): if parent == -1: root = son..

https://www.acmicpc.net/problem/6593 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net import sys;input = sys.stdin.readline from collections import deque # 탐색 def bfs(start, end, size, building): q = deque() q.append(start) visit = [[[0 for k in range(size[2] + 2)] for j in range(size[1] + 2)] for i in range(si..

https://programmers.co.kr/learn/courses/30/lessons/42628 코딩테스트 연습 - 이중우선순위큐 programmers.co.kr from heapq import heappush, heappop def solution(operations): answer = [0, 0] min_h, max_h = [], [] number_in_heap = dict() for op in operations: if op[0] == 'I': # 숫자 삽입 _, num = op.split() num = int(num) heappush(min_h, num) heappush(max_h, -num) if not number_in_heap.get(num): number_in_heap[num] = 0..

https://programmers.co.kr/learn/courses/30/lessons/42627 코딩테스트 연습 - 디스크 컨트롤러 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를 programmers.co.kr from heapq import heappush, heappop def solution(jobs): # jobs가 정렬이 안되어있음 jobs.sort(key=lambda x: (x[0], x[1])) # 0 변수 선언 min_h = [] jobs_idx = 0 cur = 0 s, rt = None, None running = False answer_list..