크래프톤 정글 WIL_Week02

Week_02 주차를 마치며 내가 일주일 동안 공부 해온 내용들을 글로 작성해보며 기록을 남기려고 한다.

week_02 이번 주 백준 문제 풀이 카테고리는 다음과 같이 명시되어 있다.

1. 이분 탐색
2. 분할정복
3. 스택
4. 큐
5. 우선순위 큐

2주차부터 문제들의 난이도가 점점 높아지고 몇몇 문제들은 문제 이해조차 쉽지 않고 접근하기 힘든 그런 문제들도 출제가 됐다. 알고리즘을 처음 공부해 보는 나 같은 경우 자료구조 또한 많이 부족하고 그걸 배워야 알고리즘 공부할 때도 훨씬 도움 될 거로 생각했다. 그래서 자료구조 위주로 개념 공부를 먼저 해보고 문제를 풀어보기로 생각했다.

---

1. 이분 탐색

백준 1920 (수 찾기):

문제 출처: https://www.acmicpc.net/problem/1920

처음 이분 탐색을 접하면서 이분 탐색에 대한 개념조차 없어서 어떻게 문제에 접근해야 할까 보단 먼저 이분 탐색이 뭔지 찾아보고 공부했던 것 같다. (1주차에 비해 확실히 문제 난이도 밸런스 조절 실패,,)

이분 탐색에 대한 간단한 개념:
1: https://namu.wiki/w/%EC%9D%B4%EC%A7%84%20%ED%83%90%EC%83%89
2: https://yoongrammer.tistory.com/75

이분 탐색은 정렬된 리스트에서 검색 범위를 줄여 나가면서 검색값을 찾는 알고리즘이다.
이분 탐색은 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 검색 범위가 절반으로 줄기 때문에 속도가 빠르다는 장점이 있다.
이분 탐색을 사용하면 시간복잡도는 logN 이 나온다.

내 정답 코드)

# 입력
N = int(input()) # 5
A = list(map(int, input().split())) # [4, 1, 5, 2, 3]
M = int(input()) # 5
arr = list(map(int, input().split())) # [1, 3, 7, 9, 5]
A.sort()			# A 정렬 [1, 2, 3, 4, 5]

# arr의 각 원소별로 이분탐색
for i in arr:
	first, end = 0, N - 1			# first는 맨 앞, end는 맨 뒤
	cnt = 0		# 찾음 여부

	# 이분탐색 시작
	while first <= end:		# first가 end보다 커지면 다돌고 반복문 탈출
    	mid = (first + end) // 2	# mid는 first와 end의 중간값
    	if i == A[mid]:	# i(목표값)이 A[mid]값과 같다면 (목표값 존재여부를 알았다면)
        	cnt = 1	    # cnt 1 변경
        	print(1)		# 1 출력
        	break		# 반복문 탈출
    	elif i > A[mid]:	# A[mid]가 num보다 작으면
        	first = mid + 1	# first를 높임
    	else:			# A[mid]가 num보다 크다면
        	end = mid - 1	# end를 낮춤

	if not cnt:		# 찾지 못한 경우
    	print(0)		# 0 출력

# 5
# 4 1 5 2 3
# 5
# 1 3 7 9 5

# if i == 1 => [4,1,5,2,3]:
#     i = True # i = 1, True = 	1
# if i == 3 => [4,1,5,2,3]:
#     i = True # i = 3, True = 	1
# if i == 7 => [4,1,5,2,3]:
#     i = False # i = 7, False 	= 0
# if i == 9 => [4,1,5,2,3]:
#     i = False # i = 9, False 	= 0
# if i == 5 => [4,1,5,2,3]:
#     i = True # i = 5, True = 	1

이분 탐색의 개념을 공부하고 이 알고리즘을 왜 사용하는지 사용했을 때 시간복잡도는 얼마나 나오는지 이런 것들을 인지한 상태로 공부하니 문제에 접근하기 조금 더 수월해지는 것 같다. (하지만 바로 다음 문제에서 막혀 버린 나…) 아직 알고리즘과 자료구조의 유형들이 익숙지 않아서 숙달하려면 시간이 더 필요하고 그만큼 더 열심히 해야 한다는 것을 느낀다,,

---

2805 백준 (나무 자르기):

문제 출처: https://www.acmicpc.net/problem/2805

나무 자르기 같은 경우 처음에 문제를 보자마자 이해가 잘 안가서 구글링 해보니 생각 보다 간단해서 문제를 파악 하고 이해 하는 능력을 더 키워야겠다 다시 한번 생각했다.. 문제를 다시 돌려보고 이해 하려고 더 노력 해봐야겠다.

내 정답 코드)

N, M = map(int, input().split()) # N 나무의 개수, M 집에 가져가기 위한 나무의 미터 길이
tree = list(map(int, input().split())) # [20, 15, 10, 17]
start, end = 1, max(tree) #이분탐색 검색 범위 설정 [1, 20]

while start <= end: #적절한 벌목 높이를 찾는 알고리즘 # 1 <= 20
	mid = (start+end) // 2 # 10 = (1+20) // 2

	log = 0 #벌목된 나무 총합 (초기화)
	for i in tree: # [20, 15, 10, 17] => tree[0], tree[1], tree[2], tree[3]
    	if i >= mid: # 20 >= 10
        	log += i - mid # 10 += 20 - 10

	#벌목 높이를 이분탐색
	if log >= M: # 10 >= 7
    	start = mid + 1 # 11 = 10 + 1
	else:
    	end = mid - 1
print(end)

코드를 보면 확실히 이해가 쉽지만 문제만 보고 코드를 짜기 쉽지 않은것 같다,, 최대한 스스로 코드를 짜보려고 더 노력 해봐야겠다.

---

백준 2110 (공유기 설치):

문제 출처: https://www.acmicpc.net/problem/2110

공유기 설치 문제를 봤을때 여러개의 공유기를 각 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 최대 거리를 구하는 문제여서 처음엔 공유기를 각 집에 설치한 후 공유기가 터지는 범위를 구하는 문제 라고 생각 했는데 (사실 이건 함정이고) 실제론 각 집에 공유기를 설치 할수 있는 최대 범위를 구하는 것이였다,,

내 정답 코드)

import sys
N, C = map(int, sys.stdin.readline().split())
house = []
for i in range(N) :
	house.append(int(sys.stdin.readline()))
house.sort()
def wifi(house, c) :
	# 공유기를 설치할 수 있는 최소 거리, 최대 거리
	min_len, max_len = 1, house[N-1] - house[0]
	length = 0
	while min_len <= max_len :
    	# 현재 공유기를 설치할 수 있는 거리
    	mid_len = (min_len + max_len) // 2
    	# 설치된 공유기 개수
    	count = 1
    	current = house[0]
    	for i in range(1, N) :
        	# 현재 위치에서 공유기를 설치할 수 있는 거리보다 멀리 있으면
        	if current + mid_len <= house[i]:
            	count += 1
            	current = house[i]
    	# 현재 설치된 공유기의 개수가 가지고 있는 공유기의 개수보다 많은 경우
    	# 즉, 더 멀찍이 설치할 수 있다.
    	if count >= c :
        	min_len = mid_len + 1
        	length = max(length, mid_len)
    	# 현재 설치된 공유기의 개수가 가지고 있는 공유기의 개수보다 적은 경우
    	# 설정된 거리가 너무 멀기에 좀 가까워져야한다.
    	else :
        	max_len = mid_len -1
	return length
print(wifi(house, C))

공유기 설치 문제도 마찬가지로 문제를 잘못 파악해서 처음에 애먹었지만, 구글링도 해보고 Chat-GPT도 사용해서 문제를 제대로 이해하고 푸니 훨씬 뭘 구해야 하는지 간단명료 해져서 문제 이해도에 따라 확실히 문제를 풀 수 있냐 없냐 (의 차이가 나는 걸 매번 느끼는 것 같다.) 가 정해지는 것 같다. 문제를 잘 읽어보면 언제나 답은 문제 속에 있다.

---

백준 2470번 (두 용액):

문제 출처: https://www.acmicpc.net/problem/2470

두 용액 문제 같은 경우 각 용액 마다 특성값이 있고 혼합을 했을때 혼합 용액의 특성값은 각 용액의 특성값을 더한값이며 혼합용액의 특성값이 0의 가까운 용액을 만들수 있는 두 용액을 구하는 문제이다. 문제를 풀기전 나는 투포인터 알고리즘을 이용 해서 풀기 위해 개념 공부를 먼저 하였다. 투포인터에 잠깐 설명해 보자면 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘 이다.

투포인터 알고리즘 참고:
1: https://butter-shower.tistory.com/226
2: https://velog.io/@leeeeeyeon/%ED%88%AC-%ED%8F%AC%EC%9D%B8%ED%84%B0-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EA%B3%BC-%EC%8A%AC%EB%9D%BC%EC%9D%B4%EB%94%A9-%EC%9C%88%EB%8F%84%EC%9A%B0-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

내 정답 코드)

n = int(input()) # 5

arr = list(map(int, input().split(' '))) # [-2, 4, -99, -1, 98]
arr.sort() # [-99, -2, -1, 4, 98]

left = 0
right = n-1 # 4 = 5-1

answer = abs(arr[left] + arr[right]) # ans = abs(-99 + 98) => 1 = abs(-1)
final = [arr[left], arr[right]] # final = [-99, 98] 


while left < right: # 0 ~ 4
	left_val = arr[left] # left_val = -99
	right_val = arr[right] # right_val = 98

	s = left_val + right_val # -1 = -99 + 98

	if abs(s) < answer: # abs(-1) < 1 => 1 < 1
    	answer = abs(s)
    	final = [left_val, right_val]
    	if answer == 0:
      	break
	if s < 0: # -1 < 0
    	left += 1 # left += 1 => left[0] => left[1] 
	else:
    	right -= 1 # right -= 1 => right[4] => right[3] ... right[2]

print(final[0], final[1]) # (-99, 98)

이분 탐색은 아니지만 투포인터 라는 새로운 알고리즘을 공부 하고 배워서 한 문제에도 여러 알고리즘을 이용해서 풀수도 있구나 라는 생각을 하게 해준 문제 였다.

---

백준 11053 (가장 긴 증가하는 부분 수열):

문제 출처: https://www.acmicpc.net/problem/11053

가장 긴 증가하는 부분 수열 문제는 문제는 쉬워 보이지만 문제 안의 트릭이 존재한다. 이분 탐색을 이용해서 예외처리를 잘해주어야 풀수 있기 때문에 처음엔 간단하네 라고 생각했지만 실제론 그러지 않았다. 자세한 예외 처리 방법은 다음과 같다:

	else :
    	min, max = 0, len(d)-1  # 2-1 = 1
    	save = 0
    	while min <= max : # 0 <= 1
        	mid = (min + max) // 2 # mid = 0
        	if d[mid] < A[i] : # 10 < 10
            	min = mid + 1 
        	else :
            	max = mid -1 # max = -1
            	save = mid # save = 0
    	d[save] = A[i] # d[0] = 10

else 구문에 min, max값을 정해주고 save의 0을 넣어 초기화 해준다 이후에 while 문을 돌면서 min, max 값을 비교하는데 이때 이분탐색을 이용해서 최솟값 과 최대값의 mid 를 구해서 d[mid]값 과 A[i]값을 비교해서 d[mid] 값이 작을땐 min 값을 올려주고 클땐 max 값을 내려주고 해당 mid 값을 save 변수에 저장한다. 그리고 마지막으로 d[save]값을 A[i]의 값으로 교체 해준다. 그럼 d 리스트 안에는 항상 d[0] 값보다 큰 숫자들만 뒤에 모이게 된다. 그때 나올수 있는 d 리스트의 최대 길이를 구하는 것이다.

내 정답 코드)

import sys 

# A의 크기
N = int(sys.stdin.readline()) # 6
# 수열
A = list(map(int, sys.stdin.readline().split())) # [10, 20, 10, 30, 20, 50]
def LIS() :
	# d[i] = A[i]를 마지막 값으로 가지는 가장 긴 증가부분 수열 길이
	d = [A[0]] #[10]
	for i in range(1, len(A)) : # 1 ~ 6
    	# d에 저장된 가장 마지막 값보다 현재 값이 크면
    	if d[-1] < A[i] : # d[-1] < A[1]=> 10 < 20         20 < 10
        	d.append(A[i]) # [10, 20]
    	# 마지막 값보다 현재 값이 작으면
    	# -> 0 ~ len(d)-1 사이에서 현재값보다 작은 값 중 가장 큰 값을 찾는다  -> 이분탐색
    	else :
        	min, max = 0, len(d)-1  # 2-1 = 1
        	save = 0
        	while min <= max : # 0 <= 1
            	mid = (min + max) // 2 # mid = 0
            	if d[mid] < A[i] : # 10 < 10
                	min = mid + 1 
            	else :
                	max = mid -1 # max = -1
                	save = mid # save = 0
        	d[save] = A[i] # d[0] = 10
	# 최종적으로 구해야하는 값
	print(len(d))
LIS()

해당 문제를 풀면서 간단한 문제처럼 보여도 안에 숨겨진 트릭을 발견해서 풀어내는것이 이 문제의 핵심 포인트 인거 같다. (문제를 자세히 보아야 풀수있다)

---

백준 8983 (사냥꾼)

문제 출처: https://www.acmicpc.net/problem/8983

사냥꾼 문제는 사정거리안에 해당 동물들이 있을때 잡을수 있는 동물의 수를 구하는 문제이다. 사냥꾼이 가지고 있는 총의 사정거리가 L이라고 하면, 사냥꾼은 한 사대에서 거리가 L 보다 작거나 같은 위치의 동물들을 잡을 수 있다고 한다. 단, 사대의 위치 xi와 동물의 위치 (aj, bj) 간의 거리는 |xi-aj| + bj로 계산한다.

내 정답 코드)

import sys
input = sys.stdin.readline
shooting_stand, animal, distance = map(int, input().split()) #사대, 동물 수, 사정거리 4, 8, 4
shooting_stand_list = list(map(int, input().split())) #사대 좌표 [6, 1, 4, 9]
shooting_stand_list.sort() #정렬 [1, 4, 6, 9]
animals = [list(map(int, input().split())) for i in range(animal)] #동물들 x, y 좌표 
animals.sort()

count = 0
for x, y in animals: # x, y 에 동물 좌표
	start = 0
	end = len(shooting_stand_list) - 1 #사대의 개수로 범위 지정
	while start <= end: #이분탐색 종료 시점 (*** start <= end, start = end가 같을때에도 포함이 되어야 while 문이 돌아감)
    	mid = (start + end) // 2 # 중간값
    	if abs(shooting_stand_list[mid] - x) + y <= distance or 	abs(shooting_stand_list[mid-1] - x) + y <= distance: #end와 end-1은 a의 왼쪽 오른쪽 값 ㅣxj - ajㅣ + bj <= l 이면 동물을 잡은거니 count +1
        	count += 1
        	break
    	if shooting_stand_list[mid] < x: #m_list의 중간 인덱스가 x보다 작으면 x보다 mid가 작으므로 스타트지점 옮김
        	start = mid + 1
    	else:
        	end = mid - 1 #m_list의 중간 인덱스가 x보다 크면 끝지점 옮김  end의 위치가 x랑 가장 가까운 수가 됨
print(count)

해당 문제가 이분 탐색을 이용해서 풀기에 가장 적절한 문제라고 생각한다. 범위를 좁혀 가면서 그 안에 있는 동물들을 찾아내 잡을수 있는 동물의 수를 출력해야 하는 문제이기에 좋은 예제라 생각한다.

---

2. 분할 정복

분할 정복을 들어 가기 앞서 분할 정복이 무엇인가 개념을 가볍게 공부 해봤다. 개념을 살짝만 봐도 엄청 깊이가 깊은 알고리즘 인거 같다. 분할 정복에서 파생되는 알고리즘도 많을 뿐더러 분할 정복 하나 만으로도 상당히 많은 내용이 담겨져 있다.

분할 정복 개념 참고:
1:https://namu.wiki/w/%EB%B6%84%ED%95%A0%20%EC%A0%95%EB%B3%B5%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
2:https://janghw.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Divide-and-Conquer-%EB%B6%84%ED%95%A0%EC%A0%95%EB%B3%B5
3:https://ttl-blog.tistory.com/934#%F0%9F%A7%90%20Master%20Theorem-1

마스터 정리란?

복잡한 알고리즘의 시간 복잡도를 구해주는 공식 같은것이다. 분할 정복을 공부 하면서 마스터 정리의 개념도 나오길래 같이 공부 해봤다.

마스터 정리 참고:
1: https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms)
2: https://velog.io/@tlsgn8483/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84-%EB%A7%88%EC%8A%A4%ED%84%B0-%EC%A0%95%EB%A6%AC
3: https://ttl-blog.tistory.com/934#%F0%9F%A7%90%20Master%20Theorem-1
4: https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=yyj9301&logNo=221240585554

---

백준 2630 (색종이 만들기):

문제 출처: https://www.acmicpc.net/problem/2630

아래 <그림 1>과 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다.

전체 종이의 크기가 N×N(N=2k, k는 1 이상 7 이하의 자연수) 이라면 종이를 자르는 규칙은 다음과 같다.

전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 <그림 2>의 I, II, III, IV와 같이 똑같은 크기의 네 개의 N/2 × N/2색종이로 나눈다. 나누어진 종이 I, II, III, IV 각각에 대해서도 앞에서와 마찬가지로 모두 같은 색으로 칠해져 있지 않으면 같은 방법으로 똑같은 크기의 네 개의 색종이로 나눈다. 이와 같은 과정을 잘라진 종이가 모두 하얀색 또는 모두 파란색으로 칠해져 있거나, 하나의 정사각형 칸이 되어 더 이상 자를 수 없을 때까지 반복한다.

위와 같은 규칙에 따라 잘랐을 때 <그림 3>은 <그림 1>의 종이를 처음 나눈 후의 상태를, <그림 4>는 두 번째 나눈 후의 상태를, <그림 5>는 최종적으로 만들어진 다양한 크기의 9장의 하얀색 색종이와 7장의 파란색 색종이를 보여주고 있다.

입력으로 주어진 종이의 한 변의 길이 N과 각 정사각형칸의 색(하얀색 또는 파란색)이 주어질 때 잘라진 하얀색 색종이와 파란색 색종이의 개수를 구하는 프로그램을 작성하시오.

내 정답 코드)

import sys

N = int(sys.stdin.readline()) # 8
board = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
blue = 0 
white = 0

def solution(x, y, N): # (x, y, N) == input값 ex) 0,0,8
	global white, blue
	color = board[x][y] # color = 보드판 x, y 좌표
	for i in range(x, x+N): # (x, x+N) => 가로 좌표, 즉 i = 0 일때 x[0] = (0.0) 
    	for j in range(y, y+N): # (y, y+N) => 세로 좌표, 즉 j = 0 일때 y[0] = (0,0)
        	if color != board[i][j]: # if board[x][y] != board[i][j]
            	solution(x, y, N//2) # solution(0, 0, 8//2)
            	solution(x, y+N//2, N//2) # solution(0, 0+8//2, 8//2)
            	solution(x+N//2, y, N//2) # solution(0+8//2, 0, 8//2)
            	solution(x+N//2, y+N//2, N//2) # solution(0+8//2, 0+8//2, 8//2)
            	return
	if color == 0: # board[x,y] == 0
    	white += 1
	else:
    	blue += 1

solution(0, 0, N)
print(white)
print(blue)

색종이 자르기 문제는 분할 정복 중 재귀 함수를 이용해서 문제를 풀어보았다. 보드판을 2차원 배열로 만든후 x, y 좌표 값을 input 값으로 받아와서 잘라진 종이를 하얀색과 파란색으로 다르게 색칠하여 각각 white, blue 라는 변수명에 저장한후 프린트 해주면 되는 간단한 문제이다. 여기서 포인트는 재귀 호출 해주는 과정에서 시간 복잡도를 잘 고려 해야 한다는 것이다. 해당문제 에서 N이 나올수 있는 최댓값이 128 이기에 최악의 경우 3중 for문을 사용했다고 가정했을때 시간 복잡도를 계산해보면 (N^3) => 128^3 = 2097152 정도 걸리기때문에 현재 내가 쓴 2중 for문은 최악의 경우 시간복잡도가 (N^2) 정도 나오기에 시간 초과 걱정없이 풀수있었다.

---

백준 10830 (행렬 제곱):

문제 출처: https://www.acmicpc.net/problem/10830

행렬 제곱 문제 같은 경우 행렬의 곱셈을 알아야 풀 수 있는 문제이다. 행렬의 곱셈을 구하는 공식은 다음과 같다:

result[i][j] += a[i][k] * b[k][j]

행렬 곱셈 구하는법 참고: https://mathbang.net/562#gsc.tab=0

내 정답 코드)

import sys
input = sys.stdin.readline

n, b = map(int, input().split()) # n, b = 2, 5
c = []
for _ in range(n):
	c.append(list(map(int, sys.stdin.readline().split())))

# 행렬 곱하기(A*A) 알고리즘
def mul(a, b): # a, b 라는 배열 생성
	result = [[0 for _ in range(n)] for _ in range(n)] # result = [[0,0], [0,0]]
	for i in range(n): # a 배열의 (가로 = i)
    	for j in range(n): # b 배열의 (세로 = j)
        	for k in range(n):
            	result[i][j] += a[i][k] * b[k][j]
        	result[i][j] %= 1000
	return result

def cal(b, c):
	if b == 1:
    	return c
    	# 단순 2제곱일 경우
	elif b == 2:
    	return mul(c, c)
	else:
    	temp = cal(b // 2, c)
    	# b가 짝수일 경우 제곱수를 계속 곱하면 된다.
    	# AAAA = ((A^2)^2)
    	if b % 2 == 0:
        	return mul(temp, temp)
    	# b가 홀수일 경우 마지막에 A를 곱해줘야한다.
    	# AAAAA = ((A^2)^2)*A
    	else:
        	return mul(mul(temp, temp), c)

result = cal(b, c)

for row in result:
	for num in row:
    	print(num % 1000,end= ' ')
	print()

---

3. 스택

스택 개념 참고: https://velog.io/@alkwen0996/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%8A%A4%ED%83%9DStack

백준 17608번 (막대기):

문제 출처: https://www.acmicpc.net/problem/17608

막대기 문제는 N개의 막대기에 대한 높이 정보가 주어질 때, 오른쪽에서 보아서 몇 개가 보이는지를 알아내는 문제 이다. 이 문제를 풀때 어떻게 하면 오른쪽에서 부터 시작 할까 생각 하다가 for 문을 쓸때 reversed(range(N)) 를 써주면 거꾸로 시작 읽어 온다는 것을 배워서 알아 두면 나중에도 유용하게 쓸것 같다.

내 정답 코드)

import sys
input = sys.stdin.readline
N = int(input())
stack = []

for _ in range(N):
	stack.append(int(input()))

last = stack[-1]
count = 1
    
        
for i in reversed(range(N)):
	if stack[i] > last:
    	count += 1
    	last = stack[i]

print(count) 

---

백준 10000번 (원 영역):

문제 출처: https://www.acmicpc.net/problem/10000

x축 위에 원이 N개 있다. 원은 서로 교차하지 않는다. 하지만, 접할 수는 있다.

영역은 점의 집합으로 모든 두 점은 원을 교차하지 않는 연속되는 곡선으로 연결될 수 있어야 한다.

이번 문제는 원으로 만들어지는 영역이 몇 개인지 구하는 문제이다.

이 문제를 풀때 처음엔 내 손으로 풀기 너무 어려워서 구글링을 통해 코드를 참조 해서 이해하는데 좀 더 집중한 문제이다. 이 문제를 풀때 중요한 포인트는 다음과 같다:

1. 원이 다른 원과 접해있지 않을 경우
2. 원이 다른 원과 접해있을 경우
3. 현재 완성된 원이 다음 원과 접해있는지 확인 하는법
4. 접해 있을때 상태를 변경 하는법

해당 포인트를 생각 하면서 코드를 보면 이해하는데는 문제 없을것이다.

참고: https://wonyoung2257.tistory.com/79

내 정답 코드)

import sys

N = int(sys.stdin.readline())
circles = []
for i in range(N) :
	x, r = map(int, sys.stdin.readline().split())
	circles.append((x-r, '(')) # 중점을 기준으로 왼쪽에 있는 좌표
	circles.append((x+r, ')')) # 중점을 기준으로 오른쪽에 있는 좌표
	# x좌표 순으로 오름차순 정렬 & 같을 경우 ')' 문자를 가진 값이 앞으로 오도록
	# 아스키 코드 : '(' = 72, ')' = 73
circles.sort(key = lambda x: (x[0], -ord(x[1])))
	# {좌표, 괄호모양, 상태값}
	# 상태값 = 0 : 뒤의 원과 접해 있지 않는다. / 1 : 뒤의 원과 접한다.
stack = []
result = 1
	# 왼쪽, 오른쪽 저장을 따로 했기에 N*2번 반복
for i in range(N*2) :
	x, y = circles[i] # x: 좌표, y: 괄호
	# 스택이 비어있을 경우에는 무조건 push
	if len(stack) == 0 :
    	stack.append({'x' : x, 'y' : y, "status" : 0})
	# 스택에 값이 존재할 경우
	else :
    	# 괄호가 ')' 이면 원이 무조건 완성
    	if y == ')' :
        	# 원이 다른 원과 접해있지 않을 경우
        	if stack[-1]['status'] == 0 :
            	result += 1
        	# 원이 다른 원과 접해있을 경우
        	elif stack[-1]['status'] == 1 :
            	result += 2
        	# 앞에 사용한 '(' 값 pop
        	stack.pop()
        	#현재 완성된 원이 다음 원과 접해있는지 확인
        	if i != N*2-1 :
            	if circles[i+1][0] != x :
                	stack[-1]['status'] = 0
    	# 괄호 '('일 경우
    	else :
        	# 접해있을 경우 상태 변경
        	if stack[-1]['x'] == x :
            	stack[-1]['status'] = 1
        	stack.append({'x' : x, 'y' : y, "status" : 0})
print(result)

---

백준 2504 (괄호의 값):

문제 출처: https://www.acmicpc.net/problem/2504

괄호의 값 같은 문제는 다음과 같은 문제속의 정의가 있다:

1. ‘()’ 인 괄호열의 값은 2이다.
2. ‘[]’ 인 괄호열의 값은 3이다.
3. ‘(X)’ 의 괄호값은 2×값(X) 으로 계산된다.
4. ‘[X]’ 의 괄호값은 3×값(X) 으로 계산된다.
5. 올바른 괄호열 X와 Y가 결합된 XY의 괄호값은 값(XY)= 값(X)+값(Y) 로 계산된다.

위와 같은 정의들을 바탕으로 코드를 짜보면 실제로 조건문의 정의 를 준것이고 중간에 stack 을 이용하는 부분은 디버깅을 통해 데이터의 흐름을 파악해서 실제 데이터 값이 어떻게 흘러가는지 확인했다.

내 정답 코드)

bracket = list(input()) # (()[[]])([])

stack = []
answer = 0
tmp = 1

for i in range(len(bracket)):

	if bracket[i] == "(":
    	stack.append(bracket[i])
    	tmp *= 2

	elif bracket[i] == "[":
    	stack.append(bracket[i])
    	tmp *= 3

	elif bracket[i] == ")":
    	if not stack or stack[-1] == "[":
        	answer = 0
        	break
    	if bracket[i-1] == "(":
        	answer += tmp
    	stack.pop()
    	tmp //= 2

	else:
    	if not stack or stack[-1] == "(":
        	answer = 0
        	break
    	if bracket[i-1] == "[":
        	answer += tmp

    	stack.pop()
    	tmp //= 3

if stack:
	print(0)
else:
	print(answer)

---

4. 큐

큐 개념 참고:
1: https://velog.io/@suitepotato/00004
2: https://velog.io/@cha-suyeon/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%81%90Queue%EC%9D%98-%EA%B8%B0%EB%B3%B8-%EA%B0%9C%EB%85%90-%EA%B5%AC%EC%A1%B0-%EA%B0%84%EB%8B%A8-%EA%B5%AC%ED%98%84Python

백준 11866 (요세푸스 문제 0):

문제 출처: https://www.acmicpc.net/problem/11866

요세푸스 문제를 풀기 위해 우선 요세푸스 순열에 대해 읽어보고 다시 문제를 접했다.

참고: https://namu.wiki/w/%EC%9A%94%EC%84%B8%ED%91%B8%EC%8A%A4%20%EB%AC%B8%EC%A0%9C

요세푸스의 순열이란?

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

이 문제의 포인트는 N명의 사람들중 K 번째 사람을 제거 하는걸 코드로 구현하는것이 포인트 이다. 그 코드는 다음과 같다:

while L:
	if K == count: # 3번째 순서 일때
    	q.append(L.popleft()) # q리스트에 숫자 추가 (#3번째 순서일때 K == count)
    	count = 1
	else:
    	L.append(L.popleft()) # L 리스트에서 첫번째 숫자를 pop 하고 바로 맨 뒤로 그 숫자 추가 해준다.
    	count += 1 

내 정답 코드)

import sys 
from collections import deque

input = sys.stdin.readline
N, K = list(map(int, input().split()))

L = deque( x+1 for x in range(N))
q = []
count = 1

while L:
	if K == count:
    	q.append(L.popleft())
    	count = 1
	else:
    	L.append(L.popleft())
    	count += 1 


print('<', end = '')
for i in q:
	if q[-1] == i:
    	print(i, end = '')
	else:
    	print(i, end = ', ')
print('>') 

---

백준 3190 (뱀):

문제 출처: https://www.acmicpc.net/problem/3190

뱀 문제를 풀때 포인트는 다음과 같다:

1. 사과의 위치 입력 받기.
2. 초기 뱀 위치 및 방향 설정 (오른쪽 회전, 왼쪽 회전)
3. 뱀의 머리 방향을 어떻게 바꿀것인가.
4. 벽에 부딪히면 게임 종료.
5. 뱀이 자기 몸통에 부딪히면 게임 종료.
6. 뱀 이동 및 길이 유지 하는법 (사과를 못먹은 경우 예외 처리 하는법).

뱀 문제는 구글링과 Chat-GPT을 사용해서 주석에 있는 내용들을 차근히 구현해 보았다.

참고: https://velog.io/@joniekwon/Python-%EB%B0%B1%EC%A4%80-3190%EB%B2%88-%EB%B1%80

내 정답 코드)

from collections import deque

# 보드의 크기 입력 받기
n = int(input())

# 보드 초기화
board = [[0] * (n+1) for _ in range(n+1)]

# 사과의 위치 입력 받기
k = int(input())
for _ in range(k):
	row, col = map(int, input().split())
	board[row][col] = 1

# 뱀의 방향 변환 정보 입력 받기
l = int(input())
turns = []
for _ in range(l):
	time, direction = input().split()
	turns.append((int(time), direction))

# 초기 뱀 위치 및 방향 설정
snake = deque([(1,1)])
direction = 1 # 1:동, 2:남, 3:서, 4:북

# 뱀 이동 함수
def move():
	global direction

	# 뱀 머리 위치
	row, col = snake[-1]

	# 뱀 이동
	if direction == 1: # 동쪽으로 이동
    	col += 1
	elif direction == 2: # 남쪽으로 이동
    	row += 1
	elif direction == 3: # 서쪽으로 이동
    	col -= 1
	else: # 북쪽으로 이동
    	row -= 1

	# 벽에 부딪히면 게임 종료
	if row < 1 or row > n or col < 1 or col > n:
    	return False

	# 뱀이 자기 몸통에 부딪히면 게임 종료
	if (row, col) in snake:
    	return False

	# 뱀 이동 및 길이 유지
	snake.append((row, col))
	if board[row][col] == 1: # 사과 먹은 경우
    	board[row][col] = 0
	else: # 사과 못 먹은 경우
    	snake.popleft()

	return True

# 게임 시작
time = 0
turn_idx = 0
while True:
	time += 1

	# 뱀 이동
	if not move():
    	break

	# 방향 변환
	if turn_idx < len(turns) and time == turns[turn_idx][0]:
    	if turns[turn_idx][1] == 'D': # 오른쪽 회전
        	direction = direction % 4 + 1
    	else: # 왼쪽 회전
        	direction = direction - 1 if direction > 1 else 4
    	turn_idx += 1

# 결과 출력
print(time)

---

5. 우선 순위 큐

우선 순위 큐 개념:
1: https://velog.io/@april_5/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%9A%B0%EC%84%A0%EC%88%9C%EC%9C%84-%ED%81%90Priority-Queue
2: https://www.daleseo.com/python-heapq/

힙 개념: https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

우선 순위 큐 (자료구조) 사용하기 위해선 우선 힙 (자료구조) 개념을 먼저 알고 있어야 한다. 그래서 힙 개념을 먼저 공부 하고 우선 순위 큐를 그 다음에 공부 하였다.

---

백준 1655 (가운데를 말해요):

문제 출처: https://www.acmicpc.net/problem/1655

left = 최대 힙(내림차순), right = 최소 힙(오름차순) 을 이용해서 숫자가 들어올때 마다 비교해서 max_h, min_h 배열에 각각 저장 한다. 그리고 저장 할때 마다 max[0] * -1 을 프린트 출력 해준다.

내 정답 코드)

import sys
import heapq
input = sys.stdin.readline

n = int(input())
max_h = []
min_h = []

for i in range(n):
	num = int(input())
	if len(max_h) == len(min_h):
    	heapq.heappush(max_h, -num)
	else:
   	 heapq.heappush(min_h, num)

	if len(max_h) >= 1 and len(min_h) >= 1 and max_h[0] * -1 > 	min_h[0]:
    	max_value = heapq.heappop(max_h) * -1
    	min_value = heapq.heappop(min_h)
    
    	heapq.heappush(max_h, min_value * -1)
    	heapq.heappush(min_h, max_value)

	print(max_h[0] * -1)
    
# ex) [1, 5, 2, 10, -99, 7, 5]
# num = 1 👉🏻 left = [-1] / right = []
# num = 5 👉🏻 left = [-1], right = [5]
# num = 2 👉🏻 left = [-2,-1], right = [5]
# num = 10 👉🏻 left = [-2,-1], right = [5,10]
# num = -99 👉🏻 left = [-2,-1,99], right = [5,10]
# num = 7 👉🏻 left = [-2,-1,99], right = [5,7,10]
# num = 5 👉🏻 left = [-5,-2,-1,99], right = [5,7,10]

---

백준 13334 (철로):

문제 출처: https://www.acmicpc.net/problem/13334

철로 문제 같은 경우엔 문제는 이해 했지만 실제 코드를 쓰다 보니 막혀서 구글링을 통해 코드 분석을 해보았다.

철로 문제를 풀면서 포인트는 다음과 같다:

1. 시작점을 어디로 잡아도 상관없다. (나는 오른쪽을 시작점으로 잡음)
2. 각 사무실과 집 정보를 오름차순으로 정렬해준다.
3. 철로 범위 설정 및 철로 범위내에 각 사무실과 집의 거리에 깔린 철로 가 있는지 확인
4. 집과 사무실의 위치 모두 철로 선분에 포함되는 사람들의 수가 최대가 되도록 즉 heap 의 길이가 최대 일때 값을 출력 해준다.

참고: https://velog.io/@piopiop/%EB%B0%B1%EC%A4%80-13334-%EC%B2%A0%EB%A1%9C%ED%8C%8C%EC%9D%B4%EC%8D%AC

내 정답 코드)

import sys
import heapq

n = int(sys.stdin.readline()) # n = 8
road_info = [] 
for _ in range(n):
	road = list(map(int, sys.stdin.readline().split()))
	road_info.append(road)

d = int(sys.stdin.readline()) # 30
roads = []
for road in road_info:
	house, office = road
	if abs(house - office) <= d:
    	road = sorted(road)
    	roads.append(road)
roads.sort(key=lambda x:x[1])

answer = 0
heap = []
for road in roads:
	if not heap:
    	heapq.heappush(heap, road)
	else:
    	while heap[0][0] < road[1] - d:
        	heapq.heappop(heap)
        	if not heap:
            	break
    	heapq.heappush(heap, road)
	answer = max(answer, len(heap))

print(answer)

이 문제를 처음 봤을때 우선순위 큐를 떠오르기 정말 힘든거 같다 라는 생각이 들었고 코드를 분석하면서 내가 이해 한 부분과 이해 하지 못한 부분들이 합쳐지면서 머릿속이 조금 복잡해 진거 같은느낌,, 나중에 한번 더 복습 해야 겠다. (이해 하기 쉽지 않았지만 결국 이해 하고 나니 조금은 마음이 편할지도..)