전체 글
Champagne Supernova - Oasis (1995)
1995년에 발표된 Oasis의 두 번째 정규 앨범 '(What's The Story) Morning Glory?'의 마지막 수록곡이다. 해당 앨범이 브릿팝 최고의 명반으로 뽑히다 보니 이 앨범에 수록된 노래들을 팝송을 좀 들어봤다 하는 사람들이라면 잘 알고 있을 것이다. 대표적으로
(Python) 백준 1874번 - 스택 수열
문제 링크 : https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 풀이 deque를 stack으로 사용하여, 입력으로 들어오는 수열을 만들기 위해 발생할 수 있는 모든 경우를 생각하며 하나씩 구현하였다. import sys from collections import deque n = int(sys.stdin.readline()) stack = deque() # 입력 ..
(Python) 백준 10866번 - 덱
문제 링크 : https://www.acmicpc.net/problem/10866 10866번: 덱 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 풀이 Deque의 다양한 메서드들을 구현하는 문제이다. 파이썬의 deque와 sys.stdin.readline()을 통해 시간제한 안에서 여유롭게 통과할 수 있다. 실버 4 문제라기엔 파이썬 코더에겐 상당히 쉬운 문제라고 할 수 있다. import sys # sys.stdin.readline()을 사용해 더 빠르게 입력 받기 가능 from collections imp..
(Python) 백준 10845번 - 큐
문제 링크 : https://www.acmicpc.net/problem/10845 10845번: 큐 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 풀이 Queue의 다양한 메서드들을 구현하는 문제이다. 파이썬의 deque와 sys.stdin.readline()을 통해 시간제한 안에서 여유롭게 통과할 수 있다. 실버 4 문제라기엔 파이썬 코더에겐 상당히 쉬운 문제라고 할 수 있다. import sys # sys.stdin.readline()을 사용해 더 빠르게 입력 받기 가능 from collections imp..
(Python) 백준 10828번 - 스택
문제 링크 : https://www.acmicpc.net/problem/10828 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 풀이 Stack의 다양한 메서드들을 구현하는 문제이다. 파이썬의 deque와 sys.stdin.readline()을 통해 시간제한 안에서 여유롭게 통과할 수 있다. 실버 4 문제라기엔 파이썬 코더에겐 상당히 쉬운 문제라고 할 수 있다. import sys # sys.stdin.readline()을 사용해 더 빠르게 입력 받기 가능 from collections im..
(Python) 백준 10816번 - 숫자 카드 2
문제 링크 : https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 풀이 1. lower bound와 upper bound를 사용한 풀이 lower bound와 upper bound를 사용하여 해당 값이 존재하는 위치의 수를 계산하는 방식으로 문제 풀이를 진행했다. import sys def lower(arr, num): # lower bound : 해당 값이 처음으로 나타나는 인덱스 반환 low, high = 0,..
(Python) 백준 10773번 - 제로
문제 링크 : https://www.acmicpc.net/problem/10773 10773번: 제로 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경 www.acmicpc.net 풀이 스택을 사용해 0이 아닌 수는 저장하고, 0인 경우에는 pop()하는 것으로 풀이를 진행했다. import sys from collections import deque arr = deque() for _ in range(int(sys.stdin.readline())): n = int(sys.stdin.readline()) if n == 0: #..
(Python) 백준 9012번 - 괄호
문제 링크 : https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 풀이 저번에 풀었던 4949번 문제의 쉬운 버전이라고 생각하면 될 것 같다. 배열을 사용하여 '('를 담아두고, ')'이 나오면 저장되어 있는 값을 pop 해주는 형식으로 문제 풀이를 진행했다. import sys from collections import deque n = int(sys.stdin.readline()) for i in range(n):..
(Python) 백준 4949번 - 균형잡힌 세상
문제 링크 : https://www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 각 줄은 마침표(".")로 끝난다 www.acmicpc.net 풀이 배열을 사용하여 '(', '[' 가 나타나면 배열에 저장한 후, 그에 맞는 짝이 나오면 배열에 저장되어 있던 값들을 pop 시키는 형식으로 문제 풀이를 진행했다. import sys from collections import deque while True: s = sys.stdin.readline() if s == ".\n": # "."이 입력되면 종료 b..
(Python) 백준 2839번 - 설탕 배달
문제 링크 : https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 풀이 처음엔 그리디 알고리즘으로 접근하려다가, 문제에서 제시된 봉지의 용량이 3kg , 5kg으로 배수의 관계가 아니기 때문에 불가능함을 깨닫고 다이나믹 프로그래밍으로 풀이를 진행했다. import sys n = int(sys.stdin.readline()) arr = [5001] * (n+1) # 문제에서 주어지는 최대 무게가 5000kg이므로 만들 수 없는 경우를 5001로 설정 arr[0..