문제링크:https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 다루는 주제: 그리디 import sys input = sys.stdin.readline for _ in range(int(input())): n = int(input()) # 지원자 수 apply = [0] * (n + 1) # 미리 0부터 n+1까지 배열 만들어놓기 for _ in range(n): a, b = map(int, input().split()) app..
문제링크:https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 다루는 주제: 그리디 import sys # 첫줄 가지고 있는 동전 종류 n개 만들고자하는 k # 둘쨰 줄 부터 동전의 가치 오름차순으로 나타남 # coin(i)는 coin(i-1)의 배수라는 조건이 중요하다 # 따라서 코인중 가장 큰놈부터 나눈만큼 카운팅하며 나머지를 k에 저장 반복 n, k = map(int, sys.st..
문제링크:https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 다루는 주제: 그리디 import sys # N개의 회의 # meeting # 각 회의의 시작 시간 start, 끝난 시간 end 같을수있다 # 겹치지않게 회의 최대 개수 찾아보자 N = int(sys.stdin.readline()) # 회의 개수 meetings = [] # 회의 리스트 for _ in range(N): start, end = map(int, sys.stdin.readline().split()) meetings.append([start, end]) meetings = sorted(mee..
문제링크:https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 다루는 주제: DP # import sys # # # 첫줄에 물건의 개수 N , 버틸수있는 무게 K # # 두번째 줄부터 물건 무게 W, 가치 V 입력받기 import sys n, k = map(int, sys.stdin.readline().split()) # 물건의 개수 n, 버틸수있는 무게 k arr = [] # 물건 ..
문제링크:https://www.acmicpc.net/problem/9084 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net 다루는 주제:DP import sys # 테스트케이스 T, 동전가짓수 N 동전 , 금액 오름차순으로 입력 coin ,금액 M, 만드는 가짓수 출력 T = int(sys.stdin.readline()) for _ in range(T): N = int(sys.stdin.readline()) coin = list(map(int, sys.stdin.readline().split(..
문제링크:https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 다루는 주제: DP import sys n = int(sys.stdin.readline()) nazzi = [0] * (n + 1) # 리스트 n +1 만큼 만들어두고 ==> nazzi[0] = 0 부터 시작 nazzi[1] = 1 # 1일땐 1 타일 1개 if n > 1: nazzi[2] = 2 # 2일땐 1, 00 2개 # 3일땐 100, 001, 111 3개 # 4일땐 0011, 0000..
문제링크:https://www.acmicpc.net/problem/2748 2748번: 피보나치 수 2 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 다루는 주제: DP # 동적 프로그래밍 import sys n = int(sys.stdin.readline()) # n번째 피보나치 수 nazzi = [0, 1] # 리스트 for i in range(2, n + 1): # 리스트에 피보나치 수를 계산하여 저장 nazzi.append(nazzi[i - 1] + nazzi[i - 2]) print(nazz..
문제링크:https://www.acmicpc.net/problem/1388 1388번: 바닥 장식 형택이는 건축가이다. 지금 막 형택이는 형택이의 남자 친구 기훈이의 집을 막 완성시켰다. 형택이는 기훈이 방의 바닥 장식을 디자인했고, 이제 몇 개의 나무 판자가 필요한지 궁금해졌다. 나 www.acmicpc.net 다루는 주제: DFS # 두개의 -- 가 같은 행에 인접해 있으면 두개는 같은 나무 판자이다 , 두개의 |이 같은 열에 인접해 있으면 같은 나무 판자이다. # dfs 사용해서 다음 노드 확인 후 조건이 맞으면 재귀 import sys n, m = map(int, sys.stdin.readline().split()) # 세로 n 가로 m place = [] for _ in range(n): pla..
