시험 전날이다보니 여러 문제들을 풀었고, Week 02에서 못풀었던 문제 3개가 있는데, 코드까진 올려두겠다.
이해는 다음에 해보겠다.
9:40 ~
아침에 일어났는데, 목이 너무 아팟다. 요즘 감기가 유행이라 걸린것 같다. 목조심하고 따듯한 물 많이 마셔야겠다.이번주 백준문제는 한바퀴를 돌았다. 어려웠던 문제 8문제를 박차를 가하여 풀고, 못봤던 개념을 재정리하겠다. 복습까지!!
9번 (6549) 히스토그램에서 가장 큰 직사각형
해당문제는 히스토그램에서 높이가 같은 도표를 묶어서 제일 큰 넓이를 찾는 것이 목표이다. 스택을 쌓아서 같은 층인 값의 연속을 찾아서 높이와 너비를 곱해 찾으면 좀더 수월하다고 한다.
import sys
# 여러 줄 입력을 처리하기 위해 while 루프 사용
def largest_rectangle(hist):
stack = [] # 스택이 들어갈 리스트 (막대의 인덱스를 저장)
max_area = 0 # 최대 넓이 저장
index = 0 # 현재 검사 중인 인덱스
# 3. 모든 히스토그램 막대를 순회
while index < len(hist):
if not stack or hist[index] >= hist[stack[-1]]:
# 스택이 비어있지 않고 현재 막대가 스택의 마지막 막대보다 낮으면 처리
stack.append(index)
index += 1 # 다음 인덱스 확인
else:
# 4. 스택에서 pop하여 넓이 계산
top = stack.pop()
height = hist[top] # pop한 막대의 높이
width = index if not stack else (index - stack[-1] - 1)
# 스택이 비었을 경우 width = index
# 스택이 남아있을경우 width = index - stack[-1] -1
# 즉 전단계까지의 스택을 빼고 그 값을 인덱스에 빼고 -1을 한다.
# 최대 직사각형 넓이를 구할 때, 현재 막대의 너비를 계산하는 과정
max_area = max(max_area, height * width)
# 5. 남은 요소 처리
while stack: # 스택이 빌때까지
top = stack.pop()
height = hist[top]
width = index if not stack else (index - stack[-1] - 1)
max_area = max(max_area, height * width)
return max_area # 최대 넓이 반환
# 6. 여러 개의 테스트 케이스 처리
while True:
data = list(map(int, sys.stdin.readline().strip().split()))
if data[0] == 0: # 종료 조건 (첫 번째 값이 0이면 종료)
break
N = data[0] # 히스토그램 개수
histogram = data[1:] # 히스토그램 높이 리스트
print(largest_rectangle(histogram)) # 결과 출력해당문제를 시도하다가 중단한지 3번인데, 3번째에야 한 50퍼센트 이해한것 같다. 해당문제에서 width를 구하는 로직을 정확하게 모르겠다. 시간이 없기때문에 다른 문제로 넘어가지만 나중에 다시 봐야겠다.
10번 (10830) 행렬 제곱
이 문제를 풀기 위해서는 행렬제곱이 어떤 것이고 어떻게 푸는지 알아야한다. 행렬 제곱을 어떻게 하는지 기억이 안나서 찾고 다시 왔다. 행렬 A에 B를 제곱하는 프로그램을 만든는데, A^B의 각 원소를 1000으로 나눈 나머지를 출력한다. 행렬을 빠르게 구하기 위해서는 B가 짝수일시(B % 2 == 0) -> A^B=(A^(B/2))×(A^(B/2)) B가 홀수일시(B % 2 == 1) -> A^B=(A^((B-1)/2))×(A^((B-1)/2))×A 짝수는 그냥 반으로 나누고, 홀수면 반으로 나눈것에 한 번 더 곱해주면된다. 라는 특징을 생각하여 재귀적으로 B를 줄이면서 연산하면 빠르게 값을 구할 수 있습니다. A를 B만큼 곱하면 느리니, 쪼개서 계산한다고 생각하면 편하다.
import sys
# 1. 입력 받기
N, B = map(int, sys.stdin.readline().split()) # 행렬 크기 N, 거듭제곱 B
matrix = [list(map(int, sys.stdin.readline().split())) for _ in range(N)] # 행렬 입력(2차원배열)
# 2. 행렬 곱셈 함수 (A × B)
def matrix_mult(A, B):
size = len(A)
result = [[0] * size for _ in range(size)] # 결과 행렬 초기화
for i in range(size):
for j in range(size):
for k in range(size): # 행렬 곱셈 규칙 적용
result[i][j] += A[i][k] * B[k][j] # 2차원 배열로 요소가 2개이다
result[i][j] %= 1000 # 문제 조건: 모든 원소는 1000으로 나눈 나머지
return result
# 3. 행렬 거듭제곱 함수 (A^exp)
def matrix_pow(A, exp):
if exp == 1: # ✅ A^1 = A
return [[element % 1000 for element in row] for row in A] # ✅ 1000으로 나눈 나머지 처리
half = matrix_pow(A, exp // 2) # A^(B/2) 계산
half = matrix_mult(half, half) # A^(B/2) × A^(B/2)
return matrix_mult(half, A) if exp % 2 else half # B가 홀수면 A 한 번 더 곱함
# 4. 결과 계산 및 출력
result = matrix_pow(matrix, B)
for row in result:
print(*row) # 행렬 출력솔직히 이해가 잘 되지않는다. 애초에 행렬제곱 이론이 쉽지 않다. 다 알지 못하지만 해당문제도 시간이 지나 다시 이해해보러 오겠다.
12:00 ~ 13:00
오늘은 랜덤 런치날이다. 랜덤 팀원과 함께 식사를 했다. 배재준님, 김예찬님, 정소영님이었다.
11번 (2261) 가장 가까운 두 점
문제 원리는 간단하다. 그냥 좌표들 중 첫 째 줄에 가장 가까운 두 점의 거리의 제곱을 출력한다.
import sys
# 입력 처리
n = int(sys.stdin.readline().strip())
points = [tuple(map(int, sys.stdin.readline().split())) for _ in range(n)]
# p1, p2 두 점 사이의 거리 제곱을 계산(거리 계산 함수)
def dist(p1, p2):
return (p1[0] - p2[0])**2 + (p1[1] - p2[1])**2
# x좌표끼리 마이너스해서 제곱, y좌표끼리 마이너스해서 제곱하고 더한다.
def closest_pair(points):
# 가장 가까운 두 점의 거리 제곱을 구하는 함수
def solve(start, end):
# 분할 정복 방식으로 최소 거리 구하기
if end - start + 1 <= 3: # 점이 3개 이하라면 브루트포스로 계산
min_dist = float('inf') # 양의 무한대로 설정
for i in range(start, end): # 시작지점부터 끝지점까지 확인
for j in range(i + 1, end + 1): # 1씩 더해서 확인
min_dist = min(min_dist, dist(points[i], points[j]))
# 가장 가까운 두점의 좌표를 구한다.
return min_dist # 구해진 좌표를 돌려준다.
# 중간 기준으로 분할
mid = (start + end) // 2
mid_x = points[mid][0]
d = min(solve(start, mid), solve(mid + 1, end)) # 좌우 각각 최소 거리 구하기
# x축 기준으로 d 이내에 있는 점들을 모아줌
candidates = []
for i in range(start, end + 1):
if (points[i][0] - mid_x) ** 2 < d:
candidates.append(points[i]) # x 축기준으로 d이내에 있는 점들을 카디날리티 리스트 추가
# y축 기준 정렬(최소 거리 검사)
candidates.sort(key = lambda p : p[1])
# 스트립 내에서 최소 거리 계산
len_c = len(candidates)
for i in range(len_c - 1):
for j in range(i + 1, len_c):
if (candidates[j][1] - candidates[i][1]) ** 2 >= d:
break # y좌표 차이가 d 이상이면 더 볼 필요 없음
d = min(d, dist(candidates[i], candidates[j]))
return d
return solve(0, len(points) - 1)
# x좌표 기준으로 정렬
points.sort()
# 최소 거리 출력 (제곱근을 씌우지 않은 상태로 출력)
print(closest_pair(points))
반정도 이해했다. 오늘 어려운 문제 한바퀴 돌고, 개념, 북습하고 다시 확인해보겠다.
★★★17번 (10000) 원 영역
# 문제의 예시도 그렇고 친절하지 않은 문제인 것 같다.
# x축위에 원을 N개 그릴 수 있고, 교차하는 경우는 없지만 접할 수는 있다고 한다.
# 주어진 x좌표와 r(반지름)에 따라 원을 그릴 수 있고 바깥부분도 세어야한다.
# 예를 들어 큰 원안에 작은원 둘이 접하면 영역은 2개가 된다.
# 문제에 예시로 보여준 그림은 6가지이다.
# 그러면 원이 접하는 경우 영역의 갯수를 2로 올리고, 접하지 않으면 1로 올리는 코드를 작성해야한다.
import sys
# 1. 입력 받기
N = int(sys.stdin.readline().strip())
events = []
# 2. 원의 시작점과 끝점을 events 리스트에 저장(입력은 원의 중앙값과 반지름을 입력하므로)
for _ in range(N):
x, r = map(int, sys.stdin.readline().split())
events.append((x - r, 1, x)) # 원의 시작점(x - r), 시작점을 의미하는 1, x좌표
events.append((x + r, -1, x)) # 원의 끝점(x + r), 끝점을 의미하는 -1, x좌표
# 3. x 좌표 기준 정렬 (같은 좌표라면 끝(-1)이 먼저)
events.sort(key = lambda e: (e[0], -e[1]))
# 람다를 정렬 기준으로 삼는 이유는 간단한 정렬 기준을 설정하기 위해서이다.
# def 정렬함수로 하면 길어지기 때문이다.
# 끝점은 -1로 처리되어 있기 때문에 올바른 순서로 좌표를 지정하기 위해 끝점에 -1처리를 하여 순서대로 x좌표 정렬이 되게끔한다.
# (안그러면 x좌표가 꼬인다)
# 4. 스택을 이용한 독립적인 영역 계산
stack = []
area_count = 1 # 최소 하나의 영역은 존재(바깥)
# 원의 시작점(1)이 나오면 스택에 올린다
# 원의 끝점(-1)이 나오면 스택에서 뺀다
# 새로운 원이 시작시, 기존 원과 겹치면 +1
# 원 하나가 끝나도 중첩된 원이 존재하면 +1
# 더나아가서 내부적으로 포함된 원은 +2가 될 것이다.
# 여기 코드를 할 때 주로 생각해야하는 건 접하면 +1이라는 것이다.
# 다음 원을 비교하더라도 시작점엔 이미 빼진 원이기 때문에 종료지점만 접하는지 판단해서 +1을 한다.
for x, event_type, center in events: # 여기서 event_type은 1이면 시작점, -1이면 끝점을 의미한다.
if event_type == 1: # 원이 시작됨 (1 열림)
if stack: # 스택이 비어있지 않다면, 기존 원 위에 새로운 원 추가됨
area_count += 1 # 영역 +1
# 스택의 최상단 원의 중심과 현재 원의 중심이 다르면 내부적으로 포함된 원 (접하는 것이 아닌 완전히 포함)
if stack[-1] != center:
area_count += 1 # 내부에 포함된 경우 +1
stack.append(center) # 시작점을 스택에 push
else: # 원이 끝남 (-1 닫힘)
stack.pop() # 스택에서 원을 제거
if stack: # 스택이 비어있지 않다면, 중첩된 원이 끝났으므로 새로운 영역 추가
area_count += 1 # 영역 +1
# 5. 결과 출력
print(area_count)
# 문제 해석도 주어진 정보가 적고 제대로 안적혀있어서 이해하는데 시간을 좀 썻다.
# 코드 구현도 스택을 합쳐서 구현해서 시간이 좀 걸렸는데, 몇줄 코드 이해하는데 한시간 걸린 것 같다.
# 이문제는 시작점과 끝점을 분리해서 순서대로 정렬하고 스택을 통해 접하는 지점을 찾으며 찾으면 구역을 +1을 한다.
# 특히나 밑의 for문이 이해하는데 시간이 오래걸렷고 다시 이문제를 만난다면 단번에 이해하기는 어려울 것 같다.
# 다음에 만난다면 직접 그리면서 이해하고 코드를 작성해보겠다.
# 원이 들어오는 모양을 괄호로 변환하여 공간 계산
import sys
input = sys.stdin.readline
n = int(input())
circles = []
# 원의 왼쪽은 '(' 모양의 괄호 오른쪽은 ')' 모양의 괄호로 만든다.
for i in range(n):
x, r = map(int, input().split())
circles.append((x-r, '('))
circles.append((x+r, ')'))
# 좌표기준으로 오름 차순으로 정렬하되 좌표가 같으면 ')'모양이 앞에 오게 정렬한다.
circles = sorted(circles, key= lambda x:(x[0], -ord(x[1])))
stack = []
# 스택에는 좌표, 괄호 모양, 상태값이 들어감
answer = 1
for i in range(n*2):
position, bracket = circles[i]
if len(stack) == 0:
stack.append({'pos':position,'bracket':bracket,'status':0})
continue
# status 0: 기본값 ->
# status 1: 원 안의 원이 연결 되어 있는 지 확인
# 괄호가 닫히면 status 값을 확인하고 0 이면 +1 1이면 +2
if bracket == ')':
if stack[-1]['status'] == 0:
answer +=1
elif stack[-1]['status'] == 1:
answer +=2
stack.pop()
# 원이 이어져 있는지 확인
if i != n*2-1:
if circles[i+1][0] != position:
stack[-1]['status'] = 0
else:
if stack[-1]['pos'] == position:
# 좌표값이 같으면 원이 접해있는 상태
stack[-1]['status'] = 1
stack.append({'pos':position,'bracket':bracket,'status':0})
else:
# 좌표값이 같지 않으면 원이접하지 않음
stack.append({'pos':position,'bracket':bracket,'status':0})
print(answer)해당 문제를 푸는 데에 문제가 생겼다. 그래서 다른 문제를 풀고 다시 돌아오겠다.
18:00 ~ 19:00
팀원분들과 저녁식사 시간을 가졌다. 몸상태가 급격히 안좋아졌다. 편의점에서 꿀물 사마시려했는데, 따듯하지 않아서 뜨거운물 마시면서 버티고 있다.
18번 (2504) 괄호의 값
올바른 괄호열을 찾고 고라호열의 값을 찾는 것이 목적이다. 그러나 괄호열이 맞지 않는 다면 0으로 출력한다. ()는 2이고 []는 3 인데, 문제만 보고는 이해하기 힘드니, 입력과 출력을 비교하면서 이해하는 것이 좋다. 왜냐하면, 괄호의 위치에 따라 곱하는지 더하는지가 다르다.
스택을 활용하여 여는 괄호를 만나면 스택에 push하고 닫는 괄호면 올바른 구조인지 확인하고 계산합니다. 형식이 앞의 괄호문제와 유사합니다. ()와 []를 겹치면 판단할 수 없으니 스택에 쌓아서 짝을 찾는 것이다.
import sys
# 입력단
UVPS = sys.stdin.readline().strip()
def cal_UVPS_value(UVPS):
stack = []
temp = 1
result = 0
for i in range(len(UVPS)):
char = UVPS[i]
if char == '(':
stack.append(char)
temp *= 2 # ()는 2를 곱한다.
elif char == '[':
stack.append(char)
temp *= 3 # []는 3을 곱한다.
elif char == ')':
if not stack or stack[-1] != '(': # 스택이 비어있지 않거나 최근 값이 (이 아닌경우
return 0 # 아무것도 리턴하지 않음
if UVPS[i-1] == '(': # 즉시 계산 가능시 추가
result += temp # 현재의 temp값을 더합니다.
stack.pop() # (를 제거합니다.
temp //= 2 # 닫힌 괄호가 나왔으므로 2로 나눕니다.(원상태 복구)
elif char == ']':
if not stack or stack[-1] != '[': # 스택이 비어있지 않거나 최근 값이 [이 아닌경우
return 0
if UVPS[i-1] == '[': # 즉시 계산할 수 있는 `[]` 패턴
result += temp # 현재 temp 값을 추가
stack.pop() # [를 제거합니다
temp //= 3 # 닫힌 괄호가 나왔으므로 3으로 나눈다.
# 모든 연산이 끝났을 때 스택이 비어있어야 함 (올바른 괄호 문자열인지 체크)
if stack:
return 0
return result
print(cal_UVPS_value(UVPS))해당 공식은 작동 방식이 신기하다. 그런데 답은 맞다.
(()[[]])를 예시로 설명하겠다.
1. 여는 소괄호로 temp = 2
2. 여는 소괄호로 temp = 4, result = 0
3. 닫는 소괄호로 temp = 4 // 2 = 2, result = 4
4. 여는 대괄호로 temp = 6
5. 여는 대괄호로 temp = 18
6. 닫는 대괄호로 temp = 18 // 3 = 6, result = 4 + 18 = 22
7. 닫는 대괄호지만, 스택 = ['(']이므로 temp = 6 // 3 = 2, result = 22
8. 닫는 소괄호고 스택도 없지만, 최근값이 (이 아니므로 return 0으로 결과에 반영이 안됨
결과는 22이다.이론은 직접해보니 이해하기 쉬웠는데, 코드로는 좀 복잡해서 코드를 이해하는데 시간이 좀 걸렸다.
19번 (2812) 크게 만들기
해당 문제를 풀기 위해서는 지워져야하는 숫자보다 이상의 값들중 제일 큰수가 앞에 나오기만 하면된다. 그럼 스택으로 넣어서 계산해서 제일 큰 수 나오게 하면될 것 같은데... GPT에 물어보니 앞에서부터 숫자를 확인하면서 앞에 숫자가 현재 숫자보다 크면 이전 숫자를 제거한다고 한다. 제거를 하다가 K == 0(즉, 지워야하는 K가 없으면) 지우는 과정을 중단하고 출력한다. 그러나 K만큼 지우지 못했다면, 지우지 못한 K만큼 뒤에서 지우면 된다.
import sys
N, K = map(int, sys.stdin.readline().strip().split())
number = sys.stdin.readline().strip() # 문자열 형태로 입력 받음
stack =[] # 스택 넣을 공간
# 모든 숫자를 반복해서 넣어봅니다
for i in number:
while K > 0 and stack and stack[-1] < i:
# K는 0보다 크고(K가 0일 때 삭제하면 안되므로), 스택이 비어있으면 종료(스택 비었는데 돌아가면 오류난다)(범위)
# stack[-1] < i은 앞전값과 비교하여 현재값이 크면 앞의 현재값보다 작은 수를 모두 삭제한다.(조건)
stack.pop() # 작은수를 뺀다
K -= 1 # 뺏으니 지워야하는 K에서 1을 뺀다
stack.append(i) # 그리고 다 돌아간 수는 스택에 추가한다.
answer = ''.join(stack[:len(stack) - K])
# answer를 stack에 K 남은 만큼 빼서 넣습니다
# 마지막 확인과 같습니다
print(answer)이론은 이해하기 어렵지 않은데, 막상 코드를 구현하려니 쉽지 않았습니다. 특히 while문의 조건이 왜 저렇게 긴지, 최종답확인전에 K만큼 빼졌는지 확인하고 지우는 과정이 구현하기 어렵다고 생각됩니다. 익숙해지도록 노력하겠습니다.
★★★23번 (3190) 뱀
# 고려할 사항이 여러가지다.
import sys
from collections import deque
# 1. 입력 받기
N = int(sys.stdin.readline().strip()) # 보드 크기
K = int(sys.stdin.readline().strip()) # 사과 개수
board = [[0] * N for _ in range(N)] # 보드 초기화 (0: 빈 칸, 1: 사과)
# 2. 사과 위치 입력
for _ in range(K):
x, y = map(int, sys.stdin.readline().split())
board[x - 1][y - 1] = 1 # 1-based → 0-based로 변환
# 3. 방향 변환 정보 입력
L = int(sys.stdin.readline().strip()) # 방향 변환 개수
turns = {} # {X초: "L" 또는 "D"}
for _ in range(L):
X, C = sys.stdin.readline().split()
turns[int(X)] = C
# 4. 방향 관련 변수 (오른쪽 → 아래 → 왼쪽 → 위쪽)
dx = [0, 1, 0, -1] # X 변화량 (동, 남, 서, 북)
dy = [1, 0, -1, 0] # Y 변화량 (동, 남, 서, 북)
direction = 0 # 초기 방향 (오른쪽)
# 5. 뱀의 몸을 관리할 큐
snake = deque([(0, 0)]) # 초기 위치
time = 0 # 게임 시간
# 6. 게임 루프
while True:
time += 1 # 1초 증가
head_x, head_y = snake[-1] # 현재 머리 위치
# 다음 이동 위치 계산
new_x = head_x + dx[direction]
new_y = head_y + dy[direction]
# 7. 게임 종료 조건 (벽 또는 몸과 부딪힘)
if new_x < 0 or new_x >= N or new_y < 0 or new_y >= N or (new_x, new_y) in snake:
break
# 8. 이동 수행
snake.append((new_x, new_y)) # 머리 이동
if board[new_x][new_y] == 1: # 사과가 있으면
board[new_x][new_y] = 0 # 사과 제거 (몸 길이 유지)
else:
snake.popleft() # 사과 없으면 꼬리 이동 (길이 유지)
# 9. 방향 전환 확인
if time in turns:
if turns[time] == "L": # 왼쪽 회전
direction = (direction - 1) % 4
else: # 오른쪽 회전
direction = (direction + 1) % 4
# 10. 결과 출력
print(time)
★★★26번 (13334) 철로
import sys
import heapq
# 입력 받기
n = int(sys.stdin.readline().strip())
lines = []
# 주어진 n개의 직장-집 좌표 입력 받기
for _ in range(n):
a, b = map(int, sys.stdin.readline().split())
start, end = sorted([a, b]) # 항상 작은 값이 시작점이 되도록 정렬
lines.append((start, end))
# 철로 길이 d 입력
d = int(sys.stdin.readline().strip())
# 1. 끝점을 기준으로 정렬 (끝점이 같다면 시작점이 작은 순)
lines.sort(key=lambda x: x[1])
# 2. 최소 힙을 활용한 탐색
heap = []
max_count = 0
for start, end in lines:
# 현재 끝점(end)에서 d 이내에 포함되지 않는 시작점들을 제거
while heap and heap[0] < end - d:
heapq.heappop(heap)
# 현재 시작점을 힙에 추가
heapq.heappush(heap, start)
# 힙의 크기가 현재 철로 내에서 포함되는 구간의 수
max_count = max(max_count, len(heap))
# 최대 포함 개수 출력
print(max_count)
어려운 문제까지 한바퀴를 돌았지만 원,뱀, 철로는 다 풀지 못했다… 개념 못한게 있어서 링크드리스트랑 해시테이블을 다시한번 봤는데, 별로 많은 내용을 보진 않았다. 가벼운 이론정도?
몸상태가 좋지 않아서 블로그 정리는 내일 해야겠다. 내일 시험이니 복습 좀 하다가 가겠다…
모든걸 기록하며 성장하고 싶은 개발자입니다. 현재 크래프톤 정글 8기를 수료하고 구직활동 중입니다.