전체 글

(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..

(Python) Deque

파이썬에는 List라는 데이터를 담을 수 있는 자료형이 존재한다. 하지만 다양한 알고리즘 문제를 풀이하다보면, List 대신 Deque를 사용하는 경우가 있는데 과연 Deque란 무엇이고, 왜 이것을 사용하는걸까? Deque란? Deque는 Double-ended queue의 줄임말로써 큐의 앞과 뒤, 즉 양방향으로 삽입과 삭제가 가능한 큐이다. Deque 사용하기 Deque 자료형은 collection에서 불러와야하기 때문에 다음과 같은 선언문이 필요하다. from collections import deque 이후에 다음과 같이 선언하여 하나의 새로운 Deque를 만들 수 있다. arr = deque() Deque 메소드 Deque에도 List와 마찬가지로 내부의 데이터들을 관리하기 위한 다양한 메소드..

(Python) 백준 2164번 - 카드 2

문제 링크 : https://www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 풀이 처음에는 단순히 list를 사용하여 풀이를 진행하였으나, 시간제한이 2초로 매우 짧아서 log(N)으로 삽입과 삭제를 진행하는 list로는 시간 초과가 발생할 수밖에 없었다. 그래서 상수 시간으로 조회, 삽입, 삭제가 가능한 deque를 사용하여 풀이를 진행하였다. import sys from collections import deque # 1부터 n까지의 카드들을 deque를..

(Python) 백준 1920번 - 수 찾기

문제 링크 : https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 풀이 처음에 이진탐색 구현 시에 인덱스를 사용하지 않고, python의 리스트 슬라이싱을 활용한 풀이를 사용했는데 시간 초과가 발생하였다. 리스트 슬라이싱은 지정한 범위의 모든 리스트의 원소를 복사하여 새로운 리스트를 만드는 과정을 거친다고 한다. 그렇기 때문에 시간 초과가 발생한 것이다. 따라서 아래 풀이처럼 슬라이싱한 리스트를 넘겨..

(Python) 백준 1018번 - 체스판 다시 칠하기

문제 링크 : https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 풀이 브루트포스 문제이기 때문에 하나하나씩 계산하는 과정이 귀찮을 뿐 풀이가 어렵진 않았다. import sys def cnt_sqr(r, c, board, bw): # 8*8로 체스판을 자른 후에 다시 칠해야하는 칸의 수 계산 cnt = 0 if bw == 'B': # 8*8 체스판의 시작칸이 'B'인 경우 for i in range(8): for j in range(8):..

(Python) 백준 11866번 - 요세푸스 문제 0

문제 링크 : https://www.acmicpc.net/problem/11866 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net 풀이 오랜만에 정렬이 아닌 다른 유형의 문제를 풀다보니 조금 헤메었다. 리스트를 사용해 간단한 원형 큐와 원형 큐에서의 삭제를 구현하면 되는 문제였다. import sys def josephus(arr, k, order): # N명의 사람이 저장된 arr에서 (N, K)-요세푸스 순열을 order에 저장 arrow = 0 # 제거될 사람의 번호 while len(arr) != 0: # 모든 사람이 제거될 때까지 arrow += (k-1) # 다음 K번쨰 사람을 지목 ..

(Python) 백준 11651번 - 좌표 정렬하기 2

문제 링크 : https://www.acmicpc.net/problem/11651 11651번: 좌표 정렬하기 2 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net 풀이 11650번 문제와 정렬 순서가 바뀌었을 뿐, 동일한 정렬 문제로 볼 수 있다. sort() 함수에 key로 lambda 함수를 넘겨주게 되면, 이 함수의 반환값을 기준으로 순서대로 정렬하게 된다. 여기서는 x[1], x[0] 순으로, 즉 리스트의 두번째 요소인 y좌표로 정렬 후에 첫번째 요소인 x좌표를 기준으로 정렬하게..

(Python) 백준 11650번 - 좌표 정렬하기

문제 링크 : https://www.acmicpc.net/problem/11650 11650번: 좌표 정렬하기 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net 풀이 sort() 함수에 key로 lambda 함수를 넘겨주게 되면, 이 함수의 반환값을 기준으로 순서대로 정렬하게 된다. 여기서는 x[0], x[1] 순으로, 즉 리스트의 첫번째 요소인 x좌표로 정렬 후에 두번째 요소인 y좌표를 기준으로 정렬하게 되는 것이다. import sys num = int(sys.stdin.readlin..