차곡차곡

백준 #2512 예산 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net import sys input = sys.stdin.readline n = int(input()) # 지방의 수 reqs = list((map(int, input().split()))) # 각 지방의 예산 요청 m = int(input()) # 총 예산 left = 0 right = max(reqs) while left mid: # 요청액이 상한액보다 클 경우 상한액으로 계산 req_sum += mid else: # 요청액이 상한액보다..

백준 #9205 맥주 마시면서 걸어가기 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net from collections import deque import sys input = sys.stdin.readline def can_go(now, dest): if abs(now[0] - dest[0]) + abs(now[1] - dest[1])

그래프를 표현하는 방법은 크게 인접 행렬과 인접 리스트 2가지가 있다. 인접 리스트를 파이썬 딕셔너리 자료형으로 나타내면 다음과 같다. graph = { 1: [2, 3, 4], 2: [5], 3: [5], 4: [], 5: [6. 7] 6: [], 7: [3], } DFS (깊이 우선 탐색) 일반적으로 DFS는 스택으로 구현하거나 재귀로 구현하며, 백트래킹을 통해 뛰어난 효용을 보인다. 코딩 테스트 시에 재귀 구현이 더 선호되는 편이다. 하지만 실행 속도는 스택을 이용한 구현이 더 빠른 편이다! // 재귀를 이용한 DFS 구현 def dfs(v, discovered=[]): discovered.append(v) for w in graph[v]: if w not in discovered: discover..

백준 #13414 수강신청 13414번: 수강신청 입력 데이터는 표준 입력을 사용한다. 입력은 1개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 과목의 수강 가능 인원 K(1 ≤ K ≤ 100,000)와 학생들이 버튼을 클릭한 순서를 기록한 대기목 www.acmicpc.net import sys input = sys.stdin.readline k, l = map(int, input().split()) # k: 수강 가능 인원, l: 대기 목록 길이 dict = {} for i in range(l): dict[input().strip()] = i sorted_dict = sorted(dict.items(), key=lambda x: x[1]) for i in range(k): if i < len(s..

백준 #2002 추월 2002번: 추월 입력은 총 2N+1개의 줄로 이루어져 있다. 첫 줄에는 차의 대수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 대근이가 적은 차량 번호 목록이 주어지고, N+2째 줄부터 N개의 줄에는 영식이 www.acmicpc.net import sys input = sys.stdin.readline n = int(input()) # 차의 대수 in_cars = {} out_cars = [] for i in range(n): in_cars[input().strip()] = i for _ in range(n): out_cars.append(input().strip()) cnt = 0 # 추월한 자동차 개수 for i in range(n-1): for j i..

백준 #16206 롤케이크 16206번: 롤케이크 오늘은 재현이의 생일이다. 재현이는 친구 N명에게 롤케이크를 1개씩 선물로 받았다. 롤케이크의 길이는 A1, A2, ..., AN이다. 재현이는 길이가 10인 롤케이크만 먹는다. 따라서, 롤케이크를 잘라서 www.acmicpc.net import sys input = sys.stdin.readline n, m = map(int, input().split()) # n: 롤케이크 개수, m: 자를 수 있는 최대 횟수 length = list(map(int, input().split())) # 롤케이크 길이 l1 = [] # 10의 배수 리스트 l2 = [] # 10의 배수가 아닌 리스트 for l in length: if l < 10: continue eli..

해시 테이블의 핵심은 해시 함수다. 해시 함수란 임의 크기 데이터를 고정 크기 값으로 매핑하는 데 사용할 수 있는 함수를 말한다. 해시 테이블의 가장 큰 특징은 대부분의 연산이 분할 상환 분석에 따른 시간 복잡도가 O(1)이라는 점이다. 덕분에 데이터 양에 관계 없이 빠른 성능을 기대할 수 있다는 장점이 있다. 해시 함수에서 무엇보다 중요한 것은 충돌을 최소화하는 것이다. 해시 테이블을 인덱싱하기 위해 해시 함수를 사용하는 것은 해싱이라 하며, 해싱은 정보를 가능한 한 빠르게 저장하고 검색하기 위해 사용하는 기법 중 하나다. 충돌 처리 방법 개별 체이닝 : 충돌 발생 시 연결 리스트로 연결하는 방식 오픈 어드레싱 : 충돌 발생 시 탐사를 통해 빈 공간을 찾아나서는 방식 (전체 슬롯의 개수 이상 저장할 수..

백준 #18115 카드 놓기 18115번: 카드 놓기 수현이는 카드 기술을 연습하고 있다. 수현이의 손에 들린 카드를 하나씩 내려놓아 바닥에 쌓으려고 한다. 수현이가 쓸 수 있는 기술은 다음 3가지다. 제일 위의 카드 1장을 바닥에 내려놓는다. www.acmicpc.net from collections import deque import sys input = sys.stdin.readline n = int(input()) # 카드 수 skill = list(map(int, input().split())) # 기술 card = deque() num = 1 for i in range(n-1, -1, -1): if skill[i] == 1: card.insert(0, num) elif skill[i] == 2..