오늘은 화요일로 퀴즈를 푸는 날입니다.
9:30 ~
김정민 주니어 코치님을 뵀다. 숙소 2층에 사시나보다. 갑작스럽게 만나서 당황스러웠지만, 이런저런 얘기를 했다.(문제가 너무 어려워서 다 못풀었다… 그러면 어려운건 건너뛰고 해보시라)카페를 간다고 하니 가서 빵이랑 커피를 사주셨다. 너무 감사드린다… 아침에 배고파서 머리 안돌아가는데, 코치님은 따로 아침을 안드신다고 한다. 나중에 뭐라도 사드려야겠다.
오늘은 문제수를 많이 풀어야해서 어려운 문제는 과감히 스킵했다. 나중에 포스팅하겠다.
12번 (10828) 스택
그냥 스택을 구현하라는거랑 다름이 없다. 난 간단할 줄 알았는데, 생각보다 어려웠다. 명령어를 리스트 형식으로 인식해서 명령어를 나누는 생각이 주 핵심인 것 같다. 또한 파이썬은 스택이 따로 없으므로 리스트로 구현할 수 있다.
import sys
N = int(sys.stdin.readline())
stack = []
for _ in range(N):
cmd = sys.stdin.readline().strip().split() # 명령어를 받음
if cmd[0] == "push": # cmd받은 명령어의 0번째 요소가 push일시
stack.append(int(cmd[1])) # 정수 X를 스택에 push
elif cmd[0] == "pop":
print(stack.pop() if stack else -1) # pop으로 스택의 정수를 뺀다.(없으면 -1을 한다)
# 파이썬은 음수 인덱싱을 지원하기 때문이다.
elif cmd[0] == "size":
print(len(stack)) # 스택의 길이를 출력합니다.
elif cmd[0] == "empty":
print(1 if not stack else 0) # 스택에 없으면 1 있으면 0 출력
# print(1 if stack != 0 else 0) 이렇게 쓰면 리스트는 0과 비교할 수 없어, 항상 참이라서 쓸수 없다고한다.
elif cmd[0] == "top":
print(stack[-1] if stack else -1) # 최근 넣은 값을 보여주고 없으면 -1그나마 쉬운문제를 빠르게 풀기위해(개념을 한번 훝기위해)12번 우선으로 풀었습니다.
13번 (10773) 제로
일단 재현이는 잘못된 수를 부르면 0을 통해 최근 수를 지운다.(pop) 모두 적고 난 이후의 수들의 합을 알고 싶다.(sum)
K = int(input())
stack = []
for _ in range(K):
cmd = input()
if cmd == "0":
stack.pop() # 0일시 하나 뽑아낸다.
else:
stack.append(int(cmd)) # 그외의 경우 입력된 값을 넣는다.
print(sum(stack))자력으로 풀었다. 간단하지만, 뭔가 뿌듯하다.
14번 (9012) 괄호
제대로 열리거나 닫힌 괄호는 VPS라고 하며 이번 문제는 VPS인지 아닌지 확인하는 문제이다. 해당문제는 스택을 통해 해결한다. 먼저 스택으로 여는 괄호를 push한다. 그리고 닫는 괄호를 확인되면 여는 괄호를 그만큼 pop한다.
import sys
# 1. 올바른 괄호 문자열(VPS) 판별 함수
def is_vps(string):
stack = [] # 스택 선언
# for문을 통해 여는 괄호와 닫는 괄호의 수를 비교한다.
for char in string:
if char == "(": # 여는 괄호이면 push
stack.append("(")
else: # 닫는 괄호이면 스택의 여는 괄호를 pop 수행
if not stack: # 닫는 괄호가 더 많다면 NO 리턴(스택에 뺄게 없음)
return "NO"
stack.pop() # 정상적인 경우 스택에서 '(' 제거
return "YES" if not stack else "NO" # 스택이 비어있으면 YES, 아니면 NO(닫는 괄호가 많았다면)
# 2. 입력 받기
N = int(sys.stdin.readline().strip()) # 테스트 케이스 개수
# 3. 여러 개의 테스트 케이스 실행 N 줄만큼 실행
for _ in range(N):
string = sys.stdin.readline().strip()
print(is_vps(string))인터넷을 보니까 엄청 다양한 방법이 있다. 하나하나 빼서 새는법, 짝을 찾아서 빼면서 True/False 등 다양한 방법이 있는데, 나는 GPT가 추천한 스택에 넣어서 계산하는 것이 이 문제의 의도와 비슷하다고 생각되어 적합하다고 생각한다. 스택에 여는 괄호 넣고 닫는 괄호만큼 빼는 이론이 신박한 것 같다.
본격적인 퀴즈를 보기에 앞서 컴퓨터 시스템에 대해서 공부한 내용이 있다. 해당내용은 추후에 따로 올리도록 하겠다.
Week02 퀴즈타임
퀴즈에 관련된 내용도 추후에 정리해보겠다. 지금 당장은 백준 문제 풀고 개념 정리하기에도 바쁘다...
퀴즈 내용에 나온 해시테이블과 머지 소트 내용을 공부를 아직 하지 않았기 때문에 잘 쓰질 못했다. 특히, 머지소트 내용 보강이 필요할 것 같다.
또한, 퀴즈 종료 후 다른 조에서 5번 가장 긴 증가하는 부분 수열 이진탐색 방법 설명을 해달라하셔서 설명하고 왔다.
이어서 백준 문제를 풀어보겠다.
15번 (17608) 막대기
보는 방향에서 봤을때 보이는 막대의 갯수를 구하는 문제이다. 스택으로 쌓아서 마지막 부분부터 스캔하면서 제일 막대보다 큰것을 업데이트하면서 기존값보다 큰값이 있으면 갯수를 한개씩 올리면 되지 않을까싶다.
import sys
sysinput = sys.stdin.readline
# 인풋값
N = int(sysinput())
stack = []
for _ in range(N): # N만큼 스택에 막대 높이를 추가합니다.
stack.append(int(sysinput()))
last = stack[-1] # 스택에서 마지막 값
count = 1 # 뒷 첫 블럭은 무조건 보이므로 미리 1을 넣어줌
for i in reversed(range(N)): # N줄 범위를 stack i의 역으로 확인한다.(하나씩 비교)
if stack[i] > last: # 직전막대보다 새로 비교하는 값이 크다면
count += 1 # 카운트를 1올린다
last = stack[i] # 전 막대보다 크므로 비교할 값으로 업데이트한다.
print(count)이론은 이해됐는데, 코드로 어떻게 구현할지 몰랐다. 근데, 완성된 코드를 보니 이해가 된다. 스택쌓은걸 역으로 확인하면서 큰값을 업데이트하며 비교하는 것이 중요한 포인트 같다.
16번 (2493) 탑
문제 길이가 길어서 이해하는데 시간이 좀 걸린다. 레이저 탑의 길이가 주어지고 레이저를 쏘는데 왼쪽으로 밖에 못 쏜다고 한다. 왼쪽의 레이저 타워가 크면, 수신이 가능하다. 그러나 작다면 수신 불가하다. 무조건 왼쪽 편에는 본인보다 큰 레이저 타워가 있어야한다. 출력은 본인의 레이저를 받은 타워의 번호를(인덱스 아님) 출력한다. 그림을 그리면 이해하기 수월하다. 레이저 타워 크기가 6 9 5 7 4 이면 답은 0 0 2 2 4이다. 6과 9는 레이저를 못주기 때문이다.
1. 스택에 탑의 높이와 인덱스를 저장한다.
2. 현재의 탑이 스택의 top보다 크면, 스택에서 pop하고 수신 가능한 탑을 찾는다.
3. 스택의 top이 현재 탑보다 크면, 해당 탑이 수신한다.
4. 탑을 스택에 push하면서 다음 탑을 검사한다.
import sys
# 1. 입력 받기
N = int(sys.stdin.readline().strip()) # 탑 개수
heights = list(map(int, sys.stdin.readline().strip().split())) # 탑들의 높이 인풋
# 2. 결과 저장 배열 & 스택 초기화
result = [0] * N # 수신한 탑의 인덱스를 저장 (기본값 0)
stack = [] # (탑의 높이, 탑의 인덱스) 저장
# 3. 각 탑에 대해 왼쪽에서 수신할 수 있는 탑 찾기
for i in range(N):
while stack and stack[-1][0] < heights[i]: # 현재의 탑보다 작은 탑을 찾는다.(왼쪽부터 오른쪽으로)
# stack[-1][0]인 이유는 스택안에 탑의 높이와 탑의 인덱스를 같이 저장하기 때문이다. 해당 코드는 마지막 탑의 높이를 불러오는 코드이다.
stack.pop() # 현재 탑보다 낮은 탑은 의미 없음 → 제거
# 스택이 비어있지 않다면, 스택의 top이 현재 탑이 신호를 받는 탑
if stack:
result[i] = stack[-1][1] # 수신한 탑의 인덱스 저장 (1-based)
# 마지막 탑의 인덱스를 가져와서 result에 덮어 씌웁니다.
# 현재 탑을 스택에 추가 (1-based index 사용)
stack.append((heights[i], i + 1)) # 현재 탑을 스택에 저장합니다(높이,인덱스)
# 인덱스는 1 ~ N이므로 i + 1을 저장합니다.
# 4. 결과 출력
print(*result) # 리스트 대괄호를 없애고 출력합니다.이론은 쉬운것 같은데 코드구현이 어려웠던 문제였던 것 같습니다. 솔직히 지금도 70퍼센트는 이해한것 같은데 다음에 다시 이해해보겠습니다.
17,18,19번도 어렵다 느껴져서 스킵하고 나중에 풀어서 올릴예정이다.
20번 (18258) 큐 2
금일 퀴즈때문에 큐를 구현할 줄 알아야할 것 같아 먼저 풀어보았다. 생각보다 스택이랑 다를게 거의 없고, deque를 써서 popleft로 처음에 들어간것이 나오는 것을 구현했음을 알게되었다. 이 문제는 스택과 다르게 큐를 구현하는 것이다. 명령어를 통해 구현하면 되겠다. 그러나 여기서는 일반 리스트로 구현하면 시간초과가 나오므로 from collections import deque를 사용한다.
import sys
from collections import deque
N = int(sys.stdin.readline())
que = deque()
for _ in range(N): # 여기가 문제였다...
cmd = sys.stdin.readline().split()
if cmd[0] == "push":
que.append(int(cmd[1]))
elif cmd[0] == "pop":
print(que.popleft() if que else -1)
elif cmd[0] == "size":
print(len(que))
elif cmd[0] == "empty":
print(1 if not que else 0)
elif cmd[0] == "front":
print(que[0] if que else -1)
elif cmd[0] == "back":
print(que[-1] if que else -1)구현하고 나서 타입에러가 나서 당황했다. GPT에 물어보니 단순한 소괄호를 대괄호로 써서 나온 오류였다.
21번 (2164) 카드2
큐로 주어진 N까지 쌓은 다음에 디큐를 시키고 다음 수를 디큐해서 다시 추가하면 한 싸이클이 되지 않을까 싶다. 싸이클은 popleft 2번, 마지막으로 버린 값 push 1번 해당 과정을 길이가 1 될때까지 반복하면 된다.
import sys
from collections import deque
N = int(sys.stdin.readline())
que = deque()
for i in range(N): # 카드가 될 que를 1부터 N까지 추가
que.append(int(i+1)) # 0을 포함해서 5를 넣으면 0~4이므로 각각 +1씩을 해서 1~5되게 맞춰주었다.
while len(que) > 1: ### que의 길이가 N이라서 == 1로 하면 루프가 실행안된다고 한다.
que.popleft()
que.append(que.popleft()) # 두 번째 카드를 뒤로 보낸다.
print(que[0]) # 마지막으로 남은 카드 출력큰 뼈대는 내가 만들었고 오류가 나서 GPT를 통해 수정하였다. 위에도 써놨으나 len(que) == 1로하면 N으로 인풋을 받아서 작동되지 않는 다는 사실을 깨달았다.
22번 (11866) 요세푸스 문제 0
요세푸스 문제는 N명의 사람들이 K번째 사람이 될때마다 제거하는 것이다. 제거된 사람의 인덱스를 순서대로 출력만 하면 끝이다. 확인을 해보니 rotate를 통해 리스트를 회전해서 빼는 방식이 좋다.
import sys
from collections import deque
# 1. 입력 받기
N, K = map(int, sys.stdin.readline().strip().split())
queue = deque(range(1, N + 1)) # 1부터 N까지 큐에 저장(0제외하고 입력)
result = [] # 제거된 순서를 저장할 리스트
# 2. 요세푸스 순열 생성
while queue: ### queue 리스트에 아무것도 남지 않을때까지 순환한다.
queue.rotate(-(K-1)) # K-1번 앞 요소를 뒤로 이동 (K번째 사람이 맨 앞에 오게)
# 예를 들어 K가 3이면 로테이션 -2가 되어서 3이 첫번째로 이동된다.
result.append(queue.popleft()) # K번째 사람 제거
# 로테이션되어서 3번이 맨앞에 있으므로 제거한다.
# 3. 출력 형식에 맞게 출력
print("<" + ", ".join(map(str, result)) + ">") # '구분자'.join을 통해 숫자 사이 콤마를 넣을수 있다.맨첨엔 3번째 인덱스를 빼고 리스트를 새로 만들어서 3을 빼야되나... 어떻게 요세푸스를 코드로 구현하나 고민을 했는데, rotate함수를 통해 빼야되는 수를 앞으로 당겨서 큐의 popleft에 따라 K번째를 뺄 수 있음을 알았습니다. rotate함수와 while 리스트: 로 리스트에 요소가 없을때까지 반복할 수 있음을 나중에 써먹어야겠습니다.
23번 뱀문제도 고려할 사항이 많아서 나중에 하고, 힙정렬에 대한 개념을 공부했다. 해당 내용은 다음 포스팅 내용을 참고하면 좋을 것 같다. 따로 포스팅했다.
24번 (11279) 최대 힙
N만큼 배열에 자연수 x를 넣어야하고 0이 입력되면 0이 주어진 횟수만큼 가장 큰 값을 출력하고 출력된 값은 배열에서 제거되어야 한다. 힙배열은 heap함수를 통해 파이썬에서 구현가능합니다. 여기서 주의할 점은 원래 힙정렬이 기본은 최솟값 정렬이다. 그러므로 -을 사용하여 최댓값 정렬로 바꾸어서 풀고 나중에 -를 다시 붙여 원래값으로 되돌려야한다.
import sys
import heapq
n = int(sys.stdin.readline())
max_heap = [] # 최대힙이 저장될 리스트
for _ in range(n):
number = int(sys.stdin.readline()) # n의 길이만큼 숫자 입력을 받습니다
if number > 0: # 0보다 클때
heapq.heappush(max_heap, -number) # number를 힙에 추가한다(최대 힙구해서 -붙임)
else: # 0보다 크지 않을때(0일때)
if not max_heap: # 만약 리스트에 요소가 없을때
print(0) # 0을 출력
else: # 리스트에 요소가 있을때
print(-heapq.heappop(max_heap))
# 힙에서 가장 작은 아이템을 팝하고 그 값을 반환한다. 함수 자체에 값반환이되어
# print랑 같이 쓸 수 있다고 한다.(-로 계산해서 값 출력시 -를 다시 붙인다)힙의 개념을 이해하는데에도 시간이 꽤 걸렸다. 주 핵심은 부모가 자식보다 크다는 사실이다. 다행히 임포트할 수 있는 함수가 있어 복잡한 코드를 사용하지 않고도 구현 가능했지만, 이해하는 것이 쉽지 않았다.
24번 (1655) 가운데를 말해요
문제에 있는 글 그대로이다. 계속해서 정수를 입력할텐데 홀수면 중간값을 출력하면되고 만약 짝수값이라면 중간 두수중 작은 수를 출력하면된다. 문제는 이것을 힙정렬로 어떻게 구현하는가이다...
찾아보니 이 문제의 핵심은 left(중앙이하)와 right(중앙이상)를 나누어서 입력되는 값마다 번갈아가며 입력한다. left의 루트값보다 작으면 left 아니면 right에 저장 두 힙의 쿠기를 조절하여 중앙값을 유지합니다. left는 right보다 같거나 많아야합니다.(만약 left가 right보다 2개 이상 크면 left에서 하나 빼서 옯김) 그런데 left는 -로 저장하여 최댓값이 루트로 오게합니다.
import sys
import heapq
# 1. 두 개의 힙 초기화
left_heap = [] # 최대 힙 (중앙값 이하의 값들) → 파이썬은 최소 힙만 지원하므로 음수 저장
right_heap = [] # 최소 힙 (중앙값 이상의 값들)
# 2. 입력 받기
N = int(sys.stdin.readline().strip())
# 3. 입력값을 처리하며 중앙값 출력
for _ in range(N):
num = int(sys.stdin.readline().strip())
# 4. 최대 힙(left_heap)과 최소 힙(right_heap)에 번갈아 가며 삽입(균형 조절)
if not left_heap or num <= -left_heap[0]:
# left힙이 비어있거나 num이 left힙의 루트값(최대값)보다 작거나 같다면
# 최대 힙이 비어있거나, 현재 입력값이 최대 힙의 최대값 이하라면
heapq.heappush(left_heap, -num) # 최대 힙(left)에는 음수로 저장 (파이썬에서 최대 힙 구현)
else:
heapq.heappush(right_heap, num) # 최소 힙(right)에는 그대로 저장
# 5. 힙의 크기 조절 (최대 힙이 최소 힙보다 크거나 같아야 함)
if len(left_heap) > len(right_heap) + 1:
# left힙의 길이가 right힙의 길이 +1 보다 크다면
heapq.heappush(right_heap, -heapq.heappop(left_heap)) # left → right 이동
elif len(left_heap) < len(right_heap):
# left힙의 길이가 right힙의 길이보다 작다면
heapq.heappush(left_heap, -heapq.heappop(right_heap)) # right → left 이동
# 6. 중앙값 출력 (항상 left_heap의 루트가 중앙값)
print(-left_heap[0])결국 left힙의 루트(최댓값)은 항상 중앙값이 된다. 이러한 로직과 코드를 짤 생각하는게 대단한 것 같다. 내 머리가 안좋아서 그런가... 문제를 보고 코드를 구현할 수 있는 경지에 오를때까지 열심히 학습해보겠다.
25번 (1715) 카드 정렬하기
두 묶음 카드 A, B를 하나로 만들기 위해 만들어지는 경우의 수를 구합니다. 3묶음의 A,B,C(최솟값순으로 정렬된)가 있다면 (A+B)+((A+B)+C)일 때의 값이 최소 비교 횟수를 출력합니다. 솔직히 문제 이론이 어렵습니다. 최소 비교 횟수를 출력하려면 더해지는 두개의 카드 값은 3개의 카드값중에 제일 작은 두개여야합니다. N이 얼마냐에 따라 묶어야되는 카드 묶음수가 늘어나므로 힙 정렬로 최솟값을 찾아야합니다.
import sys
import heapq
# 1. 입력 받기
N = int(sys.stdin.readline().strip())
heap = []
for _ in range(N):
heapq.heappush(heap, int(sys.stdin.readline().strip())) # 카드 묶음 최소 힙에 삽입
# 2. 최소 비교 횟수 계산(초기값은 0)
total_comparisons = 0
while len(heap) > 1: # 묶음이 1이상일때까지 실행(즉, 카드가 하나로 합쳐질 때까지 실행)
# 3. 가장 작은 두 묶음을 꺼내어 합침
first = heapq.heappop(heap) # 첫 최솟값을 꺼낸다
second = heapq.heappop(heap) # 두번째 최솟값을 꺼낸다
sum_cards = first + second # 현재 묶음의 비교 횟수
total_comparisons += sum_cards # 총 비교 횟수 누적
heapq.heappush(heap, sum_cards) # 합친 카드 묶음을 다시 힙에 넣음
# 4. 결과 출력
print(total_comparisons) # 최종 비교 횟수 총합 출력해당 문제는 문제 설명도 이해하기 어려워서 다른 동료의 설명을 듣고 이해했다. 이 문제의 핵심은 최소 비교 횟수를 출력하기 위해 힙정렬을 통해 첫번째와 두번째의 최솟값을 추출해서 더한다는 사실이다. 해당 과정을 묶음이 1이될 때까지 하면된다.
문제를 빠르게 다양한 개념을 풀어봐야된다고 생각들었고 중이나 상급 문제는 과감히 건너뛰었기 때문에 문제 순서가 뒤죽박죽이다. 그러나 문제 순서보다는 효율적으로 풀어나가는게 좋다고 생각된다. 다양한 학습 과정을 도입해보고 있으니, 제일 적절한 방법을 찾으면 그 루팅을 따를 예정이다.
낼 모레 시험이 있으니, 백준 문제를 빠르게 풀고, 해시테이블, 링크드리스트, 컴퓨터 시스템 일부 개념을 학습하겠다. 밀리면 안된다ㅏㅏ(이미 밀렸지만)
