💻💭🎧🌏

문제 https://www.acmicpc.net/problem/1041 1041번: 주사위 첫째 줄에 N이 주어진다. 둘째 줄에 주사위에 쓰여 있는 수가 주어진다. 위의 그림에서 A, B, C, D, E, F에 쓰여 있는 수가 차례대로 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, 쓰여 있는 수 www.acmicpc.net 코드 import sys N = int(sys.stdin.readline()) array = list(map(int, sys.stdin.readline().split())) one = min(array) two = 100 # 50 * 2 = 두 면의 최대 합 three = 150 # 50 * 3 = 세 면의 최대 합 if N == 1: # N==1이라면 총 주사위 숫자..

문제 https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 코드 import sys import heapq n = int(sys.stdin.readline()) array = [] for i in range(n): array.append(list(map(int, sys.stdin.readline().split()))) array.sort() room = [] heapq.heappush(room,array[0][1]) for i in range(1,n): if array[i][0] < room[0]..

우선순위 큐란? 우선 순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조 우선순위 큐는 데이터를 우선순위에 따라 처리하고 싶을 때 사용함. 구현 하는 방법 1) 단순히 리스트를 이용하여 구현 2) 힙(heap)을 이용하여 구현 우선 순위 큐 구현 방식 삽입 시간 삭제 시간 리스트 O(1) O(N) 힙(Heap) O(logN) O(logN) 단순히 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 정렬과 동일하다. 이 경우 시간 복잡도는 O(NlogN) 힙(Heap)의 특징 힙은 완전 이진 트리 자료구조의 일종이다. 힙에서는 항상 루트 노드(root node)를 제거한다. 최소 힙(min heap) 루트 노드가 가장 작은 값을 가진다 따라서 값이 작은 데이터가 우선적으로 제거된다. 최대 힙(max he..

문제 https://www.acmicpc.net/problem/1461 1461번: 도서관 세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책 www.acmicpc.net 코드 풀이의 논리는 맞으나 틀린 코드이다. 틀린 이유와 정답 코드는 가장 아래에서 ! import sys from collections import deque n, k = map(int,sys.stdin.readline().split()) init = list(map(int,sys.stdin.readline().split())) init.sort() array = deque(init) count ..

문제 https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 코드 st1 = list(input()) st2 = list(input()) if len(st1)

문제 https://www.acmicpc.net/problem/2631 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net 코드 n = int(input()) array = [0] * n dp = [1] * n for i in range(n): array[i] = int(input()) for i in range(1,n): for j in range(0,i): if array[j] < array[i]: dp[i] = max(dp[i],dp[j]+1) print(n-max(dp)) 풀이 번호 순서대로 줄을 세우기 위해 옮..

문제 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 코드 a = int(input()) dp = [1] * a array = list(map(int, input().split())) for i in range(1,a): for j in range(0,i): if array[j] < array[i]: dp[i] = max(dp[i], dp[j]+1) print(max..

문제 45656이란 수를 보자. 이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다. N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다. 입력 첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다. 출력 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. 풀이 dp[자릿수][앞에 오는 숫자] = 경우의 수 자릿수가 1일 때에는 앞에 오는 숫자가 1에서 9인 경우는 하나뿐이므로 for문을 이용해 1을 넣어준다. (자리수가 1일 때 앞에 오는 숫자가 0인 경우는 없으므로 그대로 0으로 둔다.) 앞에 오는 숫자가 0 인 경우에는 그 뒤에 1만 올 수 있고, 앞에 오는 숫자가 9인..

문제 RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다. 집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자. 1번 집의 색은 2번 집의 색과 같지 않아야 한다. N번 집의 색은 N-1번 집의 색과 같지 않아야 한다. i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다. 입력 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 ..

다이나믹 프로그래밍 다이나믹 프로그래밍은 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법이다. 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다. 다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식으로 구성된다. Top-down (하향식) Botton-up (상향식) 다이나믹 프로그래밍은 동적 계획법이라고도 불린다. 일반적인 프로그래밍 분야에서의 동적(Dynamic) 의미와 차이점 자료구조에서 동적 할당(Dynamic Allocation)은 '프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법' 다이나믹 프로그래밍에서 '다이나믹'은 별다른 의미가 없음 - 최적 부분 구조 (Optimal Substructure) : 큰 문제를 작..