2805 나무 자르기 1. 문제유형 Binary Search 2. 자료구조 left (int): 가장 작은 트리의 높이 right (int): 가장 높은 트리의 높이 mid (int): 트리의 중간 높이 3. 해결과정 ⭐ 실수한 점) 트리의 높이가 최대여야 나무를 가장 적게 가져간다. 따라서, 자른 나무 길이가 M보다 작을 경우 right의 크기를 감소시킨다. 반대로 자른 나무 길이가 M보다 클 경우, left 크기를 증가시켜 나무를 절약한다. ⭐ list(tree-mid for tree in trees if tree-mid>0)으로 계산한 뒤, sum 계산 시 시간 초과가 발생했다. 따라서 바로 sum(tree-mid for tree in trees if tree-mid>0)으로 계산해주니 바로 통과했..

4. 1300 K번째 수 4.1. 문제유형 Binary Search 4.2. 자료구조 left (int): 각 행의 최소값 인덱스 == 1 right (int): 각 행의 최대값 인덱스 == n mid (int): (left+right)//2 == 중간값으로 탐색해 나갈 값 4.3. 해결과정 핵심 아이디어는 행별로 mid값보다 작은 값의 개수를 세는 것이다. 각 행의 값은 i의 배수이며 작은 값들의 개수는 최대 n, 최소 mid // i이다. left

1. 12018 Yonsei TOTO 12018번: Yonsei TOTO 연세대학교 수강신청이 얼마 전부터 바뀌어, 마일리지 제도로 바뀌었다. 이 제도는 각각의 학생들에게 마일리지를 주어 듣고 싶은 과목에 마일리지를 과목당 1~36을 분배한다. 그리고 모두 분배 www.acmicpc.net 1.1 자료구조 mylect (max heap) : 내 강의를 담을 힙 자료구조 milege (min heap) : 수강 신청한 마일리지 점수를 저장한 힙 자료구조 → mylect가 max heap인 경우 : 마일리지를 초과할 경우 큰 마일리지가 소모되는 강의를 우선적으로 제거하기 위함 1.2 해결과정 신청인원(P)과 수강인원(L) 차이를 구해 마일리지와 함께 heap에 저장한다. heap은 마일리지를 최소로 사용하므..

12906 새로운 하노이 탑 12906번: 새로운 하노이 탑 첫째 줄에 막대 A에 놓여져 있는 원판의 개수와 막대 A의 상태, 둘째 줄에 막대 B에 놓여져 있는 원판의 개수와 막대 B의 상태, 셋째 줄에 막대 C에 놓여져 있는 원판의 개수와 막대 C의 상태가 주 www.acmicpc.net 📌문제유형 set, map bfs queue 📌자료구조 q (queue) : 방문할 하노이 탑을 담는 Queue 자료구조 visited (set) : 이미 방문한 하노이 탑을 담는 Set 자료구조 count (int) : 이동횟수를 저장하는 변수 📌해결과정 queue에 각 막대별 처음 원판 상태와 이동횟수를 tuple로 저장한다. q가 존재할 동안 다음 loop를 반복한다. q를 꺼낸 후 A,B,C 막대 상태를 조합해..

📌문제설명 📌문제풀이 소스코드 import sys class Queue: def __init__(self): self.queue = [] def push(self, x): self.queue.append(x) def pop(self): if len(self.queue) !=0: print(self.queue.pop(0)) else: print(-1) def size(self): print(len(self.queue)) def empty(self): if len(self.queue) == 0: print(1) else: print(0) def front(self): if len(self.queue) == 0: print(-1) else: print(self.queue[0]) def back(self): i..

📌문제설명 📌문제접근방식 핵심은 Valid한 PS임을 검증하는 것이다. 그래야 VPS와 VPS를 결합해도 VPS가 나오기 때문이다. 문자열 중 '(' 와 ')'를 스택을 이용해 검증했다. (가 나오면 스택에 넣고, )를 만나면 (를 꺼냈다. 단, 다음과 같은 경우 NO를 출력한다. 1. 스택에 (가 없는데 )를 만났다. 2. 검증이 끝난 후 스택에 (가 남아있다. 위 과정이 끝난 후 문제가 없으면 YES를 출력한다. 즉, '(' 와 ')' 의 개수가 같아야 하며 '('가 오기 전에 ')'가 오면 안된다. 📌문제풀이 import sys n = int(sys.stdin.readline().rstrip()) exlist = [sys.stdin.readline().rstrip() for x in range(n)..

📌문제설명 📌문제접근방식 정렬 문제였고, 기존에 풀었던 문제들처럼 기준을 2개로 설정하면 되는 문제였다. x 좌표 비교 후 같다면 y 좌표를 정렬했다. 📌문제풀이 소스코드 import sys n = int(input()) locations = [list(map(int,sys.stdin.readline().rstrip().split())) for x in range(n)] locations.sort(key = lambda location : (location[0], location[1])) for x in locations: print(x[0], x[1])

📌문제설명 📌문제접근방식 문제를 보자마자 들었던 생각은 원형 큐 자료구조를 이용해야겠다였다. 이유는 원을 계속해서 돌면서 k번째 사람들 제외해나가기 때문이었다. 하지만 원형큐로 구현할 경우 인덱스를 계속해서 바꿔주어야했다. 따라서 큐를 순회하며 방문한 값을 맨 뒤로 이동시켜주도록 구현했다. 📌문제풀이 소스코드 import sys from collections import deque n, target = map(int, sys.stdin.readline().rstrip().split()) data = deque() for i in range(1, n+1): data.append(i) def solution(target, data): result = [] i = 1 while data: if i==targe..

📌문제설명 📌문제풀이 소스코드 import sys class Deque: def __init__(self): self.deque = [] def push_front(self, x): self.deque.insert(0, x) def push_back(self, x): self.deque.append(x) def pop_front(self): if len(self.deque) == 0: print(-1) else: print(self.deque.pop(0)) def pop_back(self): if len(self.deque) == 0: print(-1) else: print(self.deque.pop()) def size(self): print(len(self.deque)) def empty(self):..

📌문제설명 📌문제접근방식 1차시도 3단계에 걸쳐 문제를 해결하려고 했다. 하지만 결과적으로 문제를 복잡하게 만들었다. 1. 입력받은 값을 정렬한다. 2. (입력받은 값, 개수)를 저장한 리스트를 생성한다. 3. 2번의 리스트에서 입력받은 값을 기준으로 이진탐색을 수행하고, 개수를 반환한다. 첫 시도는 이진 탐색을 사용했다. 이유는 숫자 카드 개수가 50만이었고, 숫자 카드의 범위가 -천만~+천만이었기 때문이다. 따라서 최악의 경우 50만 x 7log10을 계산하면 된다고 생각했다. 하지만 시간초과가 발생했다. 따라서 해쉬로 구현해야겠다는 생각이 들었다. 소스코드 import sys n = int(sys.stdin.readline().rstrip()) cards = list(map(int, sys.stdi..