[week02/03.26]TIL

오늘 한줄 요약

답이 아닌 접근법을 공부하자.

오늘 공부한 것

• 이분탐색(8983 사냥꾼 ,2110 공유기 설치)
• 스택(2504 괄호 찾기, 2812 크게 만들기)

새로 배우게 된 것

이분 탐색 (8983 사냥꾼 && 2110 공유기 설치)

https://www.acmicpc.net/problem/8983
https://www.acmicpc.net/problem/2110

두 문제 다 이분 탐색을 활용해서 풀어야 했다.
그러나 이분 탐색 과정에서 명확한 차이가 있다.

• 8983 사냥꾼
  사대와 동물들의 위치가 주어졌을 때, 잡을 수 있는 동물의 수 를 구해야한다

알고리즘 설계는 아래와 같이 진행했으며,

1. 입력받기
2. 사대 리스트 정렬
3. 사대~동물 거리 계산 함수
4. 사대 이분 탐색 함수
    1. 입력 : 동물 좌표값(a, b)
    2. 가장 중간 사대부터 거리 계산
        1. 만약 사정거리 내부에 동물 좌표 존재시 Count += 1
        2. 사정거리 외부
            1. mid 보다 a가 더 큰 경우(사대 범위 오른쪽) ⇒ 오른쪽 사대로 이동
            2. mid가 a 보다 더 큰 경우(사대 범위 왼쪽) ⇒ 왼쪽 사대로 이동
5. for문으로 모든 동물 좌표 돌려보기

import sys
input = sys.stdin.readline

M, N, L = map(int, input().split())
# 사대 리스트 입력받고 정렬
shot_place = sorted(list(map(int, input().split())))
animals = [list(map(int, input().split())) for _ in range(N)]

#  거리 구하는 함수
def get_distance(M, a ,b):
  return abs(M - a) + b

count = 0

def search_shot(a, b, list, start, end):
  global count
  while start <= end:
    mid = (start + end) // 2
    dist = get_distance(list[mid], a, b)
    # 사정거리 안에 있다면 count ++
    if dist <= L:
      count += 1
      return
    # 사정거리 밖,  동물이 사대 오른쪽 위치시
    elif list[mid] < a:
      start = mid + 1 # 오른쪽으로 사대 이동
    else: # 동물이 사대 왼쪽 위치시
      end = mid - 1


start = 0
end = len(shot_place) - 1

for a, b in animals:
  search_shot(a, b, shot_place, start, end)


print(count)

코드를 O(N log N)의 시간 복잡도로 구현했다.
이 문제는 분할정복의 전형적인 예제로, '무엇을 분할할 것인가?' 에 집중하여 구현하였다.

주어진 정보는 동물의 좌표, 사대의 좌표, 그리고 사정거리이다.
여기서 중요한 기준은 동물이며, 문제의 핵심은 '이 동물이 어떤 사대의 영역에 들어가는가?' 를 찾는 것이다.

이를 해결하기 위해, 동물의 좌표를 기준으로
해당 동물이 어느 사대의 영역에 포함되는지를 이분 탐색으로 찾았다.
탐색 과정에서는 사대의 인덱스를 절반씩 나누며 범위를 좁혀가는 방식으로 진행하였다.

이 방식으로 문제를 효율적으로 해결할 수 있었다.

• 2110 공유기 설치

가장 인접한 두 공유기 사이 최대 거리를 구해야 했다.

알고리즘 설계는 아래와 같이 했으며,

1. 입력받기
2. 집 x 좌표 정렬
3. 이분 탐색 ⇒ 두 인접한 공유기의 거리를 이진탐색
    1. 거리가 mid 이상인 집에 설치
    2. 설치한 공유기 개수와 C를 비교
        1. 설치 공유기 개수 ≥ C ⇒ answer 갱신, mid +1 ~ end 짤라서 또 탐색
        2. 설치 공유기 개수 < C ⇒ start ~ mid - 1 짤라서 또 탐색

코드 역시 이분 탐색을 활용하여 구현하였다.

import sys
input = sys.stdin.readline

N, C = map(int, input().split())
home = sorted([int(input()) for _ in range(N)])

start = 1
end = home[-1] - home[0]
answer = 0

def binary_search(list, start, end):
  global answer
  while start <= end:
    mid = (start + end) // 2
    cur = home[0] # 첫 집 주소
    installed = 1 # 첫집에 하나 기본으로 깔고 시작
    for i in range(1, N):
      if list[i] - cur >= mid: # mid보다 크거나 같은 거리 떨어진 곳에 설치
        installed += 1 
        cur = list[i] # 설치위치 갱신
    if installed >= C: # C의 개수보다 설치 개수가 많다면 
      answer = mid # answer 갱신
      start = mid + 1 # 1을 증가시켜 더 큰 값 확인
    else:
      end = mid - 1 # Mid가 너무 크기에 Mid값 감소

binary_search(home, start, end)

print(answer)
      

위에서 살펴본 사냥꾼 문제와의 차이점은,
공유기 문제의 경우 '인덱스를 반씩 잘라서 탐색하는 방식' 이 아닌,
'거리'를 절반씩 줄여가며 최대 거리를 탐색한다는 점이다.

이분 탐색 문제를 풀 때 보통 특정 값을 리스트로 받아
바로 인덱스를 반씩 잘라 탐색하는 방식으로 접근하는 경우가 많았다.
하지만 이번 문제를 풀면서, '무엇을 찾고자 하는가?' 에 집중하는 것이 중요하다는 교훈을 얻었다.
즉, 문제의 핵심을 정확히 이해하고,
그에 맞게 탐색의 기준을 설정하는 것이 중요하다는 점을 다시 한번 깨달았다.

스택(2504 괄호의 값, 2812 크게 만들기)

https://www.acmicpc.net/problem/2504
https://www.acmicpc.net/problem/2812

두 문제 모두 스택 자료구조를 사용해야 답을 구할 수 있거나, 시간 제한 안에 풀이가 가능했다.
스택 문제를 해결할 때는 다음과 같은 점에 집중해야 했다.

• Push와 Pop의 조건 설정:
  스택 문제는 보통 Push와 Pop을 특정 조건이 만족되었을 때 수행하는 방식으로 해결한다.
  따라서, 각 연산을 수행할 조건을 명확히 정의하고 코드로 구현하는 것이 핵심이다.

• Top 정보의 활용:
  문제를 풀 때, 스택의 Top에 있는 정보가 문제 해결의 열쇠가 되는 경우가 많다.
  따라서, Top 정보를 어떻게 활용할 것인지에 집중하여 문제를 분석하고 구현해야 한다.

• 예외 처리:

  • 스택의 크기가 정해져 있을 경우:
    Full 상태에서 Push 시도 시 예외 처리 필요.

  • 스택이 비어있는 경우:
    Pop 시도 시 예외 처리 필요.

이번 문제 풀이를 통해, 스택을 활용하는 문제는 단순히 Push와 Pop의 구현을 넘어서,
각 연산의 조건과 Top의 활용 방안을 잘 설정하는 것이 중요하다는 점을 배웠다.

• 2812 : 크게 만들기

1. 입력받기
2. 스택 초기화
3. 스택이 비어 있다면 Push
4. 스택이 비어있지 않다면
    1. TOP과 숫자의 자릿수를 비교
        1. TOP < 숫자
            1. POP
            2. K -= 1
        2. TOP ≥ 숫자
            1. PUSH

import sys
input = sys.stdin.readline

N, K = map(int,input().split())
digits = input().rstrip()
digits = list(map(int, digits))

stack = []

for digit in digits:
  # 스택이 비어있지 않고, TOP이 들어올 수(digit) 보다 작고, K가 남아있을 때
  while (len(stack) > 0 and stack[-1] < digit and K > 0):
    stack.pop() # 원소제거
    K -= 1 # POP 했으니 1 차감
  stack.append(digit) # 나머지는 스택에 PUSH

result = ''.join(map(str, stack))
result = int(result)
print(result)

• 2504 : 괄호의 값

1. 입력받기
2. 임시 변수(temp = 1), 점수 변수(result) 설정
3. `( ) [ ]`  4가지 케이스에 따라 진행
    1. `(`  ⇒ 2 * temp 한 뒤 스택에 푸시
    2. `[`  ⇒ 3 * temp 한 뒤 스택에 푸시
    3. `)` (닫힌 괄호가 들어왔을때)
        1. 스택이 비었거나 TOS 와 짝이 안맞는다면 ⇒ 0
        2. 직전 값이 `(` 으로 짝이 맞는 경우
            1. 점수 더하기
            2. 임시 변수 복구
    4. `]` (닫힌 괄호가 들어왔을때)
        1. 스택이 비었거나 TOS 와 짝이 안맞는다면 ⇒ 0
        2. 직전 값이 `]` 으로 짝이 맞는 경우
            1. 점수 더하기
            2. 임시 변수 복구

stack = [] # 스택
temp = 1 # result에 더해주기 전 임시 변수
result = 0 # 결과 변수
string = list(input()) # 입력값

for i in range(len(string)):
  # 여는 괄호일 경우, 괄호 종류 따라 temp에 점수를 저장

  if string[i] == '(':
    temp *= 2
    stack.append(string[i])
  elif string[i] == '[':
    temp *= 3
    stack.append(string[i])
  # 둥근 닫힌 괄호일 경우
  elif string[i] == ')':
    if not stack or stack[-1] != '(': # 스택이 비었거나 짝이 안맞는 경우
      result = 0
      break # 나가리
    if string[i - 1] == '(': # 짝이 맞는 경우, 바로 앞이 열린 둥근 괄호
      result += temp
    temp //= 2 # temp 1로 원상 복구
    stack.pop()
  # 각진 닫힌 괄호
  elif string[i] == ']':
    if not stack or stack[-1] != '[': # 스택이 비었거나 짝이 안맞는 경우
      result = 0
      break # 나가리
    if string[i - 1] == '[': # 짝이 맞는 경우, 바로 앞이 닫힌 각진 괄호
        result += temp
    temp //= 3
    stack.pop()

# 다 맞아도 스택에 뭐가 남아있다면 짝 안맞으니 0
if stack:
  print(0)
else:
  print(result)

공부하면서 어려운 점

문제를 풀때마다 막히는 부분이 있는데, 여기에 너무 매몰되어서 너무 많은 시간을 소비하거나,
집중력을 잃어버려 멍때리는 순간이 슬슬 발생한다...
2시간 넘으면 빠르게 포기하고 접근법을 보자, 어차피 잡고 있는다고 안보이니까...ㅠ