24.07.25 day33 스터디 회고 3주차, 안전 영역, 최소 회의실 개수

오늘 스터디는 도현이까지 참여해서 4명이서 시작했다. 도현이는 이번 주차 내용으로 진행하고 만석, 재희님은 첫주차부터 모든 키워드로 진행, 본인은 중간에 끼어든 4주차부터 이번주까지 진행하는 걸로 했다. 다른 날에 비해 스터디 시간이 짧아 빠르게 시작했는데, 이번 키워드는 쿠키와 세션, HTTP에 대한 내용으로 진행했는데 http의 stateless에 대해 질문받았다. 근데 설명하면서 정글의 나만무 프로젝트 때가 생각나 그 부분을 토대로 설명하다가 세션에 대한 내용을 잘못 전달했었다. 정확히 숙지하고 있었어야 헀는데 비슷한 단어에 혼동됐다.. 

그리고 이번 주차꺼만 생각하다가 저번주에 학습한 공유 메모리에 대해 망각해버린게 너무 아쉽다. 그래서 학습할 때 좀 더 집중하고 깊게 파고드려고 한다.

이번 주차의 알고리즘 문제는 진짜 어려웠다. 어느정도 간단한 코드의 DP문제는 풀 수 있었는데 "합이 0"이라는 백준 문제가 너무 안풀렸다. 문제를 확인했을 때 브루트포스 문제여서 그대로 진행했으나 시간 초과가 발생, 좀 더 나은 방식으로 이분 탐색으로 진행했으나 이것도 시간 초과, 한 문제로 계속 붙잡고 있다가 도저히 못풀 것 같아 포기했었는데 만석님이 설명해준 투 포인터라는 방식으로 푼 코드를 보니 코드가 길어도 그나마 이해가 되는 코드였다. DP방식이나 다른 방식으로 풀었던 것도 설명해줬는데 이 부분은 이해가 잘 되진 않았다. 그 외에 dfs 문제는 dfs코드를 복기하며 풀었고 보너스 문제의 최소 회의실 개수는 정글에서 열심히 풀었던 비슷한 문제가 생각나 재밌게 풀었던 것 같다. 이번주부터 이력서 넣기 시작했으니 얼른 취업했으면 좋겠다..

---

안전 영역

import sys
input = sys.stdin.readline

n = int(input())
arr = [list(map(int, input().split())) for _ in range(n)]

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

def dfs(x, y, h):
    stack = [(x, y)]
    while stack:
        x, y = stack.pop()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n and arr[nx][ny] > h and not visited[nx][ny]:
                visited[nx][ny] = True
                stack.append((nx, ny))

total_cnt = 0

for h in range(101):
    cnt = 0
    visited = [[False for _ in range(n)] for _ in range(n)]
    for j in range(n):
        for k in range(n):
            if arr[j][k] > h and not visited[j][k]:
                dfs(j, k, h)
                cnt += 1
    total_cnt = max(total_cnt, cnt)

print(total_cnt)

이 문제는 물에 잠기지 않은 안전한 영역의 최대 갯수를 구하는 문제이다.

n개의 줄에 걸쳐 영역인 배열의 요소를 입력받아 2차원 리스트에 저장한다.

dfs 함수에 사용할 수평과 수직의 방향을 지정하는 dx, dy를 만들어준다.

이 후 dfs함수에서 스택을 사용하여 시작 지점을 스택에 추가해준다. 그리고 4방향으로 이동하면서 새로운 위치를 계산하여 새로운 위치가 배열의 범위 내에 있고, 높이가 h보다 크며, 방문하지 않은 경우 방문값을 True로 변경 후 스택에 새로운 위치를 추가해준다.

높이가 100까지라고 지정해주었으니 100까지 순회해야 한다. 현재 높이의 안전 영역을 카운트할 변수와 방문 값을 초기화해준다.

배열의 모든 요소를 순회하면서 현재 위치가 높이 h보다 크고 방문하지 않은 경우 dfs함수를 수행하고 안전 영역 카운트를 증가시켜준다. 모든 순회가 끝나면 현재 안전영역 카운트와 전역변수의 영역 카운트 중 최대 값을 업데이트하여 출력해준다.

---

최소 회의실 개수

import sys
input = sys.stdin.readline
import heapq

n = int(input())
arr = []

for i in range(n):
    start, end = map(int, input().split())
    arr.append((start, end))
    
arr.sort(key=lambda x: x[0])

heap = []
heapq.heappush(heap, arr[0][1])

for i in range(1, len(arr)):
    if arr[i][0] >= heap[0]:
        heapq.heappop(heap)
        
    heapq.heappush(heap, arr[i][1])
    
print(len(heap))

회의할 수 있는 최소 회의실 개수를 구하는 문제이다.

각 강의의 시작 시간과 끝 시간을 입력받아 리스트에 (start, end) 형태의 튜플로 저장한다. 이 후 리스트를 시작시간을 기준으로 정렬하는데, 이는 강의를 순서대로 배치해 끝 시간을 맞추기 위함이다.

heapq 라이브러리를 이용해 최소 힙 heap을 초기화하고 시작 시간을 정하기 위해 첫 번째 강의의 끝 시간을 힙에 초기화한다.

첫 번째 강의의 끝 시간이 힙에 들어있기 때문에 두 번째 강의부터 순회해야 한다. 순회하면서 현재 강의의 시작 시간이 힙의 끝 시간보다 크거나 같으면 회의실을 사용할 수 있다는 말이므로 힙에서 최소값을 제거하고 현재 강의의 끝 시간을 힙에 추가해준다.

이 방식으로 힙을 업데이트해주면서 가능한 끝 시간을 넣어준 후 다 순회했으면 회의실의 개수인 해당 힙의 길이를 출력해준다.