알고리즘 공부 202

(Python)백준 코딩테스트 연습 - ATM(11399)

1. 문제 https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 2. 풀이 # n : 사람 수 n = int(input()) # p_l : 인출 시간 리스트 p_l = list(map(int, input().split())) p_l.sort() # t_sum : 총 인출 시간 t_sum = 0 for i, v in enumerate(p_l): t_sum += v * (n - i) print(t_sum) 3. 후기 - 어렵지 않은 문제였다. 가장 작은 인출 시간을 구하기 위해서는 ..

(Python)백준 코딩테스트 연습 - 큐(10845)

1. 문제 https://www.acmicpc.net/problem/10845 10845번: 큐 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 2. 풀이 from collections import deque import sys input = sys.stdin.readline # n : 명령 입력 개수 n = int(input()) que = deque() for i in range(n): order = input().strip() if 'push' in order: que.append((order.split()..

(Python)백준 코딩테스트 연습 - 나는야 포켓몬 마스터 이다솜(1620)

1. 문제 https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 2. 풀이 import sys input = sys.stdin.readline # n : 포켓몬 개수, k : 문제의 수 n, k = map(int, input().split()) # n_l : 포켓몬을 저장할 dict n_l = {} # re_n_l : key, value를 뒤집어 저장할 dict re_n_l = {} for i in range(n): pr..

(Python)백준 코딩테스트 연습 - 제로(10773)

1. 문제 https://www.acmicpc.net/problem/10773 10773번: 제로 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경 www.acmicpc.net 2. 풀이 from collections import deque import sys # n : 수의 개수 n = int(sys.stdin.readline()) # n_l : 수를 저장할 deque n_l = deque() for i in range(n): # num : 입력받은 수 num = int(sys.stdin.readline()) # num이 0..

(Python)백준 코딩테스트 연습 - 카드2(2164)

1. 문제 https://www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 2. 풀이 from collections import deque import sys # n : 카드 개수 n = int(sys.stdin.readline()) # n_l : 카드들을 저장할 리스트 n_l = deque([i for i in range(1, n+1)]) while True: # 카드가 한개만 남은 경우 반복 종료 if len(n_l) == 1: break # 카드 중 멘 ..

(Python)백준 코딩테스트 연습 - 균형잡힌 세상(4949)

1. 문제 https://www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 각 줄은 마침표(".")로 끝난다 www.acmicpc.net 2. 풀이 while True: # 각 문자열 한 줄씩 입력 s = input() # 입력된 문자열이 .인 경우 반복문 break if s == '.': break # 대괄호, 소괄호를 append, pop할 list s_list = [] balance = True for i in s: if i == '(': s_list.append('(') elif i == ')..

(Python)백준 코딩테스트 연습 - 동전 0(11047)

1. 문제 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 2. 풀이 import sys # n : 돈 종류의 개수, k : 목표 가치 n, k = map(int, sys.stdin.readline().split()) # m_list : 돈의 종류 m_list = [] for i in range(n): m_list.append(int(sys.stdin.readline())) # m..

(Python)백준 코딩테스트 연습 - 돌 게임(9655)

1. 문제 https://www.acmicpc.net/problem/9655 9655번: 돌 게임 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 2. 풀이 # n : 돌의 개수 n = int(input()) if n % 2 == 1: print('SK') else: print('CY') 3. 후기 - 해당 문제는 다이나믹 프로그래밍을 사용하여 풀이를 권장하고 있다. 하지만 손으로 프로세스를 정리하던 중 돌의 개수가 1개씩 늘어날 때마다 이기는 사람이 바뀌는 것을 확인할 수 있었고, 다이나믹 프로그래밍보다 더 효율적으로 코딩을 진행하였다.

(Python)백준 코딩테스트 연습 - 수 정렬하기 4(11931)

1. 문제 https://www.acmicpc.net/problem/11931 11931번: 수 정렬하기 4 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 2. 풀이 import sys n = int(sys.stdin.readline()) n_l = [] for i in range(n): n_l.append(int(sys.stdin.readline())) n_l.sort(reverse=True) for i in n_l: print(i) 3. 후기 - 처음 문제를 확인하고 일단 정렬 함수를 사용하여 풀어 보았지만, 시간 초과..

(Python)백준 코딩테스트 연습 - 행렬 곱셈

1. 문제 https://www.acmicpc.net/problem/2740 2740번: 행렬 곱셈 첫째 줄에 행렬 A의 크기 N 과 M이 주어진다. 둘째 줄부터 N개의 줄에 행렬 A의 원소 M개가 순서대로 주어진다. 그 다음 줄에는 행렬 B의 크기 M과 K가 주어진다. 이어서 M개의 줄에 행렬 B의 원소 K개 www.acmicpc.net 2. 풀이 n, m = map(int, input().split()) a_list = [] for i in range(n): a_list.append(list(map(int, input().split()))) m, k = map(int, input().split()) b_list = [[] for i in range(k)] for i in range(m): b = li..