알고리즘/BOJ

문제 링크 https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 소스 코드 from collections import deque def main(): n = int(input()) board = [[0 for _ in range(n)] for _ in range(n)] k = int(input()) for _ in range(k): r, c = map(int, input().split()) board[r-1][c-1] = -1 # 사과 위치 기록 turns..

문제 링크 https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net 소스 코드 def main(): formula = list(input()) stack = [] # 연산자, 괄호가 담길 스택 answer = '' for tmp in formula: if tmp.isalpha(): # 문자는 바로 정답 문자열에 추가 answer += tmp elif tmp == '(': # 여는 괄호는 스택에 추가 stack.append(tmp) elif tmp =..

문제 링크 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 소스 코드 import sys def main(): N,C = map(int, input().split()) house = [] for _ in range(N): house.append(int(sys.stdin.readline().strip())) house.sort() answer = 0 left, right = 1, house[-1..

문제 링크 https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 소스 코드 import sys sys.setrecursionlimit(10**6) def main(): n, m = map(int, sys.stdin.readline().strip().split()) parents = [x for x in range(n)] # 부모 노드 리스트 def root(x): if x != parents[x]: # 자기 자신이 될 때까지 재귀 parents..

문제 링크 https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 소스 코드 import sys def main(): n = int(input()) nums = sorted(list(map(int, sys.stdin.readline().strip().split()))) m = int(input()) low, high = 0, max(nums) # 최소, 최대 answer = 0 # 최종 정답 저장 while low

문제 링크 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 소스 코드 import sys sys.setrecursionlimit(10**6) def main(): n, m = map(int, input().split()) parents = [x for x in range(n+1)] # 부모 노드 저장 def find(x): # 부모 찾기 if parents[x] != x: # 자기자신과 같아질 때까지 par..