접근

a-1 부터 b까지 슬라이싱 후 reversed 함수로 뒤집고 원본 리스트를 변경한다.

코드

import sys

input = sys.stdin.readline

N, M = map(int, input().split())

lst = [x for x in range(1, N + 1)]

for _ in range(M):
    a, b = map(int, input().split())
    for i, n in enumerate(reversed(lst[a - 1 : b])):
        lst[a - 1 + i] = n

print(*lst)

Error validating datasource 'db': the URL must start with the protocol 'mysql://'.

해결

.env 파일의 DATABASE_URL 값에 쌍따옴표("") 를 제거해주니 해결되었다.

추가로 아래의 오류도 발생했는데 주석을 제거해주니 해결되었다.

Error querying the database: Server error: 'ERROR HY000 (1105): VT05003: unknown database 'lnd%20' in vschema'

onClick 이벤트 핸들러의 콜백 함수가 제대로 동작하지 않을 때

<F.FileNameSection>
        {fileList.map((file, i) => (
          <F.FileItem
            key={i}
            onClick={(event) => handleFileItemClick(event, file)}
            selected={file.key === activeFile?.key}
          >
            <ImgWrapper width='20px'>
              <img src={''} alt='' />
            </ImgWrapper>
            <span>{file.name}</span>

              // 제대로 동작하지 않음
            <F.CloseBtn onClick={() => closeFile(file)}>✕</F.CloseBtn>
          </F.FileItem>
        ))}
      </F.FileNameSection>

위의 예제에서 F.CloseBtn 의 onClick 메소드가 이상하게 동작했다.

이유는 부모 태그인 F.FileItem 의 onClick 메소드가 자식한테도 전파되었기 때문이다. F.CloseBtn 을 클릭하면 두개의 콜백 함수가 한 번에 작동되는 오류였다.

해결 1

부모 태그의 이벤트 핸들러 실행 시 event.target을 검사한다.

event.currentTarget 은 이벤트 핸들러가 부착된 태그 event.target 은 이벤트가 실행된 태그(이벤트를 위임받은 자식 태그에서 실행되면 event.target 은 자식 태그를 가리킴)

두 값을 비교해서 이벤트 핸들러가 부착된 태그를 클릭했을 때만 실행되게 구현한다.

function handleFileItemClick(event: React.MouseEvent<HTMLElement>, file: CustomFile) {

      // target 검사
    if (event.target !== event.currentTarget) return;
    selectItem('editor', file);
  }

하지만 이 방법은 자식 태그 중에 button 태그의 클릭만 막는게 아니라 모든 자식 태그의 클릭을 막는다. 따라서 자식 태그 중에 span 태그를 클릭해도 클릭이 취소된다.

해결 2

두 번째 해결 방법은 event.stopPropagation() 메소드를 사용하는 방법이다.

event.stopPropagation() 메소드는 자식 태그에 부착된 이벤트 핸들러가 실행될 때 이벤트가 부모 태그로 전파되는 것을 막아준다.

따라서 이 메소드를 (자식 태그에서) 사용하면 자식 버튼을 클릭했을 때 부모 버튼의 onClick 이 실행되지 않는다.

function handleCloseBtnClick(event: React.MouseEvent<HTMLElement>, file: CustomFile) {
    event.stopPropagation();
    closeFile(file);
  }

알고리즘

• 그래프 탐색

Tip

• 입력으로 주어진 노드 중 부모가 -1인 노드가 루트 노드

풀이

1. 입력을 받아서 부모가 -1인 노드를 root_node 변수에 저장한다.
2. 삭제할 노드가 아닌 노드로 그래프를 만든다.

1, 2번을 동시에 진행한다.

import sys

input = sys.stdin.readline

N = int(input())


# 부모 -> 자식
graph = [[] for _ in range(N)]  # graph[i] -> i 번째 노드의 자식 노드들 번호 리스트
parents = list(map(int, input().split())) # 부모 노드
root_node = 0 # 루트 노드
delete_node = int(input()) # 삭제할 노드


for i in range(N):
    if parents[i] == -1: # 부모 노드가 -1이면 루트 노드
        root_node = i
    else:
        # 삭제할 노드가 아닌 경우만 부모의 자식 리스트에 추가
        if i != delete_node:
            graph[parents[i]].append(i)

2. 삭제할 노드가 루트 노드라면 0을 출력하고 프로그램을 종료한다.

   if delete_node == root_node:
    print(0)
    exit(0)

3. 모든 노드를 dfs로 순회하면서 자식 노드가 없는 노드를 발견하면 결과에 1을 추가한다.

순회가 끝나면 결과를 출력한다.

res = 0 # 리프노드의 개수


def dfs(node: int):
    global res

    # 자식이 없으면 리프노드
    if len(graph[node]) == 0:
        res += 1
        return

    # 자식 노드들을 dfs로 재귀 호출
    for n in graph[node]:
        dfs(n)


dfs(root_node)

print(res)

전체 코드

import sys

input = sys.stdin.readline

N = int(input())


# 부모 -> 자식
graph = [[] for _ in range(N)]  # graph[i] -> i 번째 노드의 자식 노드들 번호 리스트
parents = list(map(int, input().split())) # 부모 노드
root_node = 0 # 루트 노드
delete_node = int(input()) # 삭제할 노드


for i in range(N):
    if parents[i] == -1: # 부모 노드가 -1이면 루트 노드
        root_node = i
    else:
        # 삭제할 노드가 아닌 경우만 부모의 자식 리스트에 추가
        if i != delete_node:
            graph[parents[i]].append(i)

if delete_node == root_node:
    print(0)
    exit(0)


res = 0


def dfs(node: int):
    global res

    # 자식이 없으면 리프노드
    if len(graph[node]) == 0:
        res += 1
        return
    for n in graph[node]:
        dfs(n)


dfs(root_node)

print(res)

알고리즘

• 구현
• 그래프 탐색

Tip

• 치즈와 치즈의 안 공기는 서로 접촉해도 녹지 않으므로 바깥 공기와 따로 구분할 수 있는 로직을 적용한다.

CHEESE = 1 # 치즈
OUTER_AIR = 2 # 바깥 공기
INNER_AIR = 0 # 안 공기

풀이

1. 입력을 이차원 리스트로 변환한다.

import sys
from collections import deque

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

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

direction = [(1, 0), (0, -1), (-1, 0), (0, 1)]

queue = deque()
queue.append([0, 0])

while queue:
    i, j = queue.popleft()
    if paper[i][j] != 0:
        continue
    paper[i][j] = OUTER_AIR # 바깥 공기 모두 2로 변경
    for d in direction:
        next_i, next_j = i + d[0], j + d[1]
        if 0 <= next_i < N and 0 <= next_j < M and paper[next_i][next_j] == 0:
            queue.append([next_i, next_j])

cheeses = deque()

# 치즈 위치 찾기
for i in range(N):
    for j in range(M):
        if paper[i][j] == CHEESE:
            cheeses.append((i, j))

4. 큐에서 치즈를 하나씩 꺼내고 녹는지 검사한다. (바깥 공기와 두 면 이상 접촉하는지)

녹는 치즈는 melting 리스트에, 아닌 치즈는 다시 큐에 넣는다.

melting 리스트를 순회하면서, 녹는 치즈를 모두 2(바깥 공기)로 변경한다.

이 때 치즈가 녹으면 연결된 공기는 모두 바깥 공기에 오염된다.

따라서 녹는 치즈의 상하좌우 중에 0(안쪽 공기)가 있다면 BFS를 실행해서 연결된 안쪽 공기 모두 2(바깥 공기)로 변경한다.

한 턴(한 시간)이 끝나면 결과에 1을 추가한다.

마지막에 결과를 출력하면 끝.

while cheeses:
    melting = []
    for _ in range(len(cheeses)):
        cheese = cheeses.popleft()

        # 치즈가 녹는지 검사
        if is_melting(*cheese):
            melting.append(cheese)
        else:
            cheeses.append(cheese)

    for c in melting:
        paper[c[0]][c[1]] = OUTER_AIR
        for d in direction:
            ny, nx = c[0] + d[0], c[1] + d[1]
            if paper[ny][nx] == INNER_AIR:

                # 오염된 안쪽 공기를 모두 바깥 공기로 변환 (BFS)
                change_inner_air_to_outer_air(ny, nx)

    # 결과에 1 추가
    res += 1

# 모든 치즈가 다 녹으면 결과 출력
print(res)

# 치즈가 녹는지 검사하는 함수 - 상하좌우 중에 두 면이 바깥 공기(0)인지
def is_melting(i, j):
    cnt = 0
    for d in direction:
        if paper[i + d[0]][j + d[1]] == OUTER_AIR:
            cnt += 1
    if cnt >= 2:
        return True
    return False

# 오염된 안쪽 공기를 모두 바깥 공기로 변환하는 함수 (BFS)
def change_inner_air_to_outer_air(y, x):
    queue = deque()
    queue.append([y, x])
    while queue:
        i, j = queue.popleft()
        if paper[i][j] != INNER_AIR:
            continue
        paper[i][j] = OUTER_AIR
        for d in direction:
            ny, nx = i + d[0], j + d[1]
            if paper[ny][nx] == INNER_AIR:
                queue.append([ny, nx])

전체 코드

import sys
from collections import deque

input = sys.stdin.readline

CHEESE = 1
OUTER_AIR = 2
INNER_AIR = 0


# 치즈가 녹는지 검사하는 함수 - 상하좌우 중에 두 면이 바깥 공기(0)인지
def is_melting(i, j):
    cnt = 0
    for d in direction:
        if paper[i + d[0]][j + d[1]] == OUTER_AIR:
            cnt += 1
    if cnt >= 2:
        return True
    return False

# 오염된 안쪽 공기를 모두 바깥 공기로 변환하는 함수 (BFS)
def change_inner_air_to_outer_air(y, x):
    queue = deque()
    queue.append([y, x])
    while queue:
        i, j = queue.popleft()
        if paper[i][j] != INNER_AIR:
            continue
        paper[i][j] = OUTER_AIR
        for d in direction:
            ny, nx = i + d[0], j + d[1]
            if paper[ny][nx] == INNER_AIR:
                queue.append([ny, nx])


N, M = map(int, input().split())

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


direction = [(1, 0), (0, -1), (-1, 0), (0, 1)]


# 둘러쌓인 곳 찾기
# 처음에 바깥의 공기 모두 2로 변경
queue = deque()
queue.append([0, 0])
while queue:
    i, j = queue.popleft()
    if paper[i][j] != 0:
        continue
    paper[i][j] = OUTER_AIR
    for d in direction:
        next_i, next_j = i + d[0], j + d[1]
        if 0 <= next_i < N and 0 <= next_j < M and paper[next_i][next_j] == 0:
            queue.append([next_i, next_j])


cheeses = deque()


# 치즈 위치 찾기
for i in range(N):
    for j in range(M):
        if paper[i][j] == CHEESE:
            cheeses.append((i, j))

res = 0

while cheeses:
    melting = []
    for _ in range(len(cheeses)):
        cheese = cheeses.popleft()

        # 치즈가 녹는지 검사
        if is_melting(*cheese):
            melting.append(cheese)
        else:
            cheeses.append(cheese)

    for c in melting:
        paper[c[0]][c[1]] = OUTER_AIR
        for d in direction:
            ny, nx = c[0] + d[0], c[1] + d[1]
            if paper[ny][nx] == INNER_AIR:
                # 오염된 안쪽 공기를 모두 바깥 공기로 변환 (BFS)
                change_inner_air_to_outer_air(ny, nx)

    res += 1


print(res)

알고리즘

• 다익스트라

Tip

• 하얀 방으로 이동할 때를 가중치 0으로, 검은 방으로 이동할 때를 가중치 1로 설정하고 목표 지점까지의 최단 거리를 구하면 해결할 수 있는 문제
• 우선순위 큐를 사용해서 가중치가 0인 간선(경로)를 우선적으로 택한다. ( 다익스트라 알고리즘 )
• 파이썬의 내장 자료구조인 heapq를 사용한다.

가중치가 0이나 1일 경우 큐를 두 개 생성해서 BFS로 해결하는 방법도 있지만 우선순위 큐를 사용한 다익스트라 알고리즘을 사용했다.

풀이

최소 힙(우선순위 큐)에는 cost(거리), r(행 인덱스), c(열 인덱스) 정보가 들어있다.

-> 출발지로부터 r행 c열까지의 거리

큐에 있는 것들 중 cost(거리)가 가장 작은 요소를 꺼낸다. 이 때 꺼낸 요소 -> 출발지로부터 r행 c열까지의 최단거리

꺼낸 요소에서 상하좌우 4방향에 대해 각각 인덱스 초과, 방문 여부를 조사하고 가능하다면 우선순위 큐에 넣는다.

이 때 큐에 새로 넣는 cost는 현재 cost + (0 or 1) 으로 설정한다. (흰 방 or 검은 방)

만약 큐에서 꺼낸 행과 열이 도착지와 같다면 출력 후 프로그램을 종료한다.

코드

import sys
import heapq

input = sys.stdin.readline
N = int(input())

# 미로 생성
maze = [list(map(int, list(input().rstrip()))) for _ in range(N)]

# 미로를 탐색할 큐를 생성
queue = [[0, 0, 0]]

# 방문처리할 리스트 NxN
visited = [[False for _ in range(N)] for _ in range(N)]

# 상하좌우 4방향
direction = [(1, 0), (0, -1), (-1, 0), (0, 1)]

while queue:
    cost, r, c = heapq.heappop(queue)

    # 도착지면 출력 후 프로그램 종료
    if r == N - 1 and c == N - 1:
        print(cost)
        exit(0)

    # 상하좌우 4방향 탐색 (인덱스 초과, 방문 했는지 검사)
    for d in direction:
        next_r = r + d[0]
        next_c = c + d[1]
        if 0 <= next_r < N and 0 <= next_c < N and not visited[next_r][next_c]:
            # 흰 방, 검은 방 종류에 따라 가중치 0 or 1로 설정
            next_cost = 0 if maze[next_r][next_c] == 1 else 1
            visited[next_r][next_c] = True
            heapq.heappush(queue, [cost + next_cost, next_r, next_c])

알고리즘

• 그래프 탐색

• 너비 우선 탐색

아기 상어는 개인적으로 굉장히 재밌게 풀었다.

최근에 많이 풀었던 너비 우선 탐색 (BFS) 알고리즘을 다시 한 번 복습할 수 있는 기회였다.

처음에는 문제가 길고 규칙이 많아서 복잡하다고 느꼈었는데 하나하나 구현해가면서 해결할 수 있었다.

또 무작정 코드를 치는 것보다 먼저 어떻게 구현할지 정리하는게 훨씬 효율적이라는 것을 다시 한번 느낄 수 있었다.

Tip

• 다음 물고기까지의 최단거리를 구할 때의 시간복잡도를 최소로 하는 것이 중요
• 한 번의 Step에 무조건 1의 시간이 소요된다. 즉 가중치가 모두 1로 같은 그래프이므로 BFS를 사용하는 것이 효율적이다. ( BFS를 사용하면 방문하지 않은 곳만 방문할 수 있다 )

풀이

코드가 많으므로 나눠서 정리했다.

전역 변수 세팅

import sys
from collections import deque
input = sys.stdin.readline

N = int(input())


space = [list(map(int, input().split())) for _ in range(N)]  # 공간의 상태
direction = [(1, 0), (0, -1), (-1, 0), (0, 1)]  # 상하좌우

curr_pos: tuple[int] = ()  # 아기 상어의 위치
level = 2  # 아기 상어의 레벨
exp = 0  # 경험치, 레벨만큼 쌓이면 레벨이 1 증가하고 경험치는 초기화된다.
time = 0  # 아기 상어가 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는 시간

# 상어 위치 세팅 
def set_baby_shark_pos():
    global curr_pos
    for i in range(N):
        for j in range(N):
            if space[i][j] == 9:
                curr_pos = (i, j)
                space[i][j] = 0 # 아기 상어 위치는 0으로 초기화
                return

set_baby_shark_pos() 

"""

어느 물고기를 잡아먹을지 결정하는 함수
fish_A를 잡아먹어야 한다면 True, 반대면 False를 리턴
1. 거리가 가까운 물고기를 잡아먹는다
2. 거리가 같다면 위에 있는 물고기, 같다면 가장 왼쪽에 있는 물고기를 잡아먹는다.

"""
def compare_fish(fish_A, fish_B) -> bool:
    if fish_A["distance"] < fish_B["distance"]:
        return True
    if fish_A["distance"] > fish_B["distance"]:
        return False
    if fish_A["idx"][0] < fish_B["idx"][0]:
        return True
    if fish_A["idx"][0] > fish_B["idx"][0]:
        return False
    if fish_A["idx"][1] < fish_B["idx"][1]:
        return True
    if fish_A["idx"][1] > fish_B["idx"][1]:
        return False

"""

다음에 먹을 물고기의 위치와 걸리는 시간을 리턴하는 함수
먹을 물고기가 없다면 (-1,-1)를 리턴한다
다음에 먹을 물고기의 위치 -> 아기상어보다 레벨이 낮고 거리가 가장 가까운 물고기
거리가 같다면 -> 가장 위에 있는 물고기 -> 가장 왼쪽에 있는 물고기
아기상어보다 레벨이 더 높다면 지나갈 수 없다.


구현 방법 -> bfs
큐를 생성한다. 초기값은 아기 상어의 현재 위치
각각의 인덱스에 방문처리를 할 NxN 리스트 생성
min_fish <- {idx:(-1,-1), dist: 1e9} 가장 가까운 물고기의 인덱스, 거리
1. 큐에서 위치 (i,j)를 꺼낸다.
2. 현재 위치에 물고기가 있다면 min_fish.dist 와 비교 -> 최신화
3. 상하좌우 4방향에 대해서 다음 위치를 구한다. (next_i,next_j)
4. 다음 위치에 대해서 검사
4.a 인덱스 검사
4.b 다음 위치를 방문했었는지(방문 안 한 경우만 진행)
4.c 다음 위치에 자신보다 레벨이 높은 상어가 있는지
5. 가능하다면 방문 처리하고 큐에 다음 위치 추가
6. 큐가 비었다면 min_fish.idx, time 리턴

"""

def get_min_fish():
    # 최단 거리의 물고기를 저장
    # idx -> 인덱스 | dist -> 거리
    min_fish = {"idx": (-1, -1), "distance": 1e9}
    visit = [[False for _ in range(N)] for _ in range(N)]

    # 큐의 초기값 -> 현재 위치, 총 거리
    queue = deque([[curr_pos[0], curr_pos[1], 0]])
    while queue:
        pos_y, pos_x, dist = queue.popleft()

        # 큐에서 빼낸 위치에 아기 상어보다 레벨이 낮은 물고기가 있다면
        # min_fish와 비교 -> 업데이트
        if (
            space[pos_y][pos_x] != 0
            and space[pos_y][pos_x] < level
            and compare_fish({"idx": (pos_y, pos_x), "distance": dist}, min_fish)
        ):
            min_fish["idx"] = (pos_y, pos_x)
            min_fish["distance"] = dist

        # 상하좌우 4곳을 각각 탐색
        for d in direction:
            next_pos_y = pos_y + d[0]
            next_pos_x = pos_x + d[1]
            if (
                # 인덱스 검사
                0 <= next_pos_y < N
                and 0 <= next_pos_x < N
                # 방문하지 않은 곳이라면
                and not visit[next_pos_y][next_pos_x]
                # 아기 상어보다 레벨이 높은 물고기가 있다면 접근 불가
                and space[next_pos_y][next_pos_x] <= level
            ):
                # 방문처리
                visit[next_pos_y][next_pos_x] = True
                # 큐에 다음 방문할 곳 추가
                queue.append((next_pos_y, next_pos_x, dist + 1))

    # (잡아먹을 물고기 y, 잡아먹을 물고기 x, 걸린 시간) return
    next_fish_y = min_fish["idx"][0]
    next_fish_x = min_fish["idx"][1]
    return (next_fish_y, next_fish_x, min_fish["distance"])

"""
1. 먹을 수 있는 레벨의 상어 중 거리가 가장 최소인 상어를 고른다.
2. 상어를 그 자리로 이동시키고 먹이가 된 상어를 삭제한다.
3. 먹을 수 있는 상어가 없다면 종료한다.
"""

while True:
    next_fish = get_min_fish()  # 잡아먹을 물고기
    if next_fish[0] == -1:  # 잡아먹을 물고기가 없다면 종료
        break

    # 잡아먹은 물고기가 있던 곳은 빈곳으로 바꾸기
    space[next_fish[0]][next_fish[1]] = 0

    # 잡아먹은 시간 결과값에 추가
    time += next_fish[2]

    # 아기상어 위치 업데이트
    curr_pos = (next_fish[0], next_fish[1])

    # 경험치 1 추가
    exp += 1

    # 경험치가 레벨과 같아지면 레벨 1 추가, 경험치 초기화
    if level == exp:
        level += 1
        exp = 0

print(time)  # 총 시간을 출력

전체 코드

import sys
from collections import deque

input = sys.stdin.readline


# 상어 위치 세팅 & 맵 생성
def set_baby_shark_pos():
    global curr_pos
    for i in range(N):
        for j in range(N):
            if space[i][j] == 9:
                curr_pos = (i, j)
                space[i][j] = 0
                return


"""
어느 물고기를 잡아먹을지 결정하는 함수
fish_A를 잡아먹어야 한다면 True, 반대면 False를 리턴
1. 거리가 가까운 물고기를 잡아먹는다
2. 거리가 같다면 위에 있는 물고기, 같다면 가장 왼쪽에 있는 물고기를 잡아먹는다.
"""


def compare_fish(fish_A, fish_B) -> bool:
    if fish_A["distance"] < fish_B["distance"]:
        return True
    if fish_A["distance"] > fish_B["distance"]:
        return False
    if fish_A["idx"][0] < fish_B["idx"][0]:
        return True
    if fish_A["idx"][0] > fish_B["idx"][0]:
        return False
    if fish_A["idx"][1] < fish_B["idx"][1]:
        return True
    if fish_A["idx"][1] > fish_B["idx"][1]:
        return False


"""
다음에 먹을 물고기의 위치와 걸리는 시간을 리턴하는 함수
먹을 물고기가 없다면 (-1,-1)를 리턴한다
다음에 먹을 물고기의 위치 -> 아기상어보다 레벨이 낮고 거리가 가장 가까운 물고기
거리가 같다면 -> 가장 위에 있는 물고기 -> 가장 왼쪽에 있는 물고기
아기상어보다 레벨이 더 높다면 지나갈 수 없다.


구현 방법 -> bfs
큐를 생성한다. 초기값은 아기 상어의 현재 위치
각각의 인덱스에 방문처리를 할 NxN 리스트 생성
min_fish <- {idx:(-1,-1), dist: 1e9} 가장 가까운 물고기의 인덱스, 거리
1. 큐에서 위치 (i,j)를 꺼낸다.
2. 현재 위치에 물고기가 있다면 min_fish.dist 와 비교 -> 최신화
3. 상하좌우 4방향에 대해서 다음 위치를 구한다. (next_i,next_j)
4. 다음 위치에 대해서 검사
4.a 인덱스 검사
4.b 다음 위치를 방문했었는지(방문 안 한 경우만 진행)
4.c 다음 위치에 자신보다 레벨이 높은 상어가 있는지
5. 가능하다면 방문 처리하고 큐에 다음 위치 추가
6. 큐가 비었다면 min_fish.idx, time 리턴
"""


def get_min_fish():
    # 최단 거리의 물고기를 저장
    # idx -> 인덱스 | dist -> 거리
    min_fish = {"idx": (-1, -1), "distance": 1e9}
    visit = [[False for _ in range(N)] for _ in range(N)]

    # 큐의 초기값 -> 현재 위치, 총 거리
    queue = deque([[curr_pos[0], curr_pos[1], 0]])
    while queue:
        pos_y, pos_x, dist = queue.popleft()

        # 큐에서 빼낸 위치에 아기 상어보다 레벨이 낮은 물고기가 있다면
        # min_fish와 비교 -> 업데이트
        if (
            space[pos_y][pos_x] != 0
            and space[pos_y][pos_x] < level
            and compare_fish({"idx": (pos_y, pos_x), "distance": dist}, min_fish)
        ):
            min_fish["idx"] = (pos_y, pos_x)
            min_fish["distance"] = dist

        # 상하좌우 4곳을 각각 탐색
        for d in direction:
            next_pos_y = pos_y + d[0]
            next_pos_x = pos_x + d[1]
            if (
                # 인덱스 검사
                0 <= next_pos_y < N
                and 0 <= next_pos_x < N
                # 방문하지 않은 곳이라면
                and not visit[next_pos_y][next_pos_x]
                # 아기 상어보다 레벨이 높은 물고기가 있다면 접근 불가
                and space[next_pos_y][next_pos_x] <= level
            ):
                # 방문처리
                visit[next_pos_y][next_pos_x] = True
                # 큐에 다음 방문할 곳 추가
                queue.append((next_pos_y, next_pos_x, dist + 1))

    # (잡아먹을 물고기 y, 잡아먹을 물고기 x, 걸린 시간) return
    next_fish_y = min_fish["idx"][0]
    next_fish_x = min_fish["idx"][1]
    return (next_fish_y, next_fish_x, min_fish["distance"])


N = int(input())


space = [list(map(int, input().split())) for _ in range(N)]  # 공간의 상태
direction = [(1, 0), (0, -1), (-1, 0), (0, 1)]  # 상하좌우

curr_pos: tuple[int] = ()  # 아기 상어의 위치
level = 2  # 아기 상어의 레벨
exp = 0  # 경험치, 레벨만큼 쌓이면 레벨이 1 증가하고 경험치는 초기화된다.
time = 0  # 아기 상어가 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는 시간
set_baby_shark_pos()  # 아기 상어 위치 세팅


"""
1. 먹을 수 있는 레벨의 상어 중 거리가 가장 최소인 상어를 고른다.
2. 상어를 그 자리로 이동시키고 먹이가 된 상어를 삭제한다.
3. 먹을 수 있는 상어가 없다면 종료한다.
"""


while True:
    next_fish = get_min_fish()  # 잡아먹을 물고기
    if next_fish[0] == -1:  # 잡아먹을 물고기가 없다면 종료
        break

    # 잡아먹은 물고기가 있던 곳은 빈곳으로 바꾸기
    space[next_fish[0]][next_fish[1]] = 0

    # 잡아먹은 시간 결과값에 추가
    time += next_fish[2]

    # 아기상어 위치 업데이트
    curr_pos = (next_fish[0], next_fish[1])

    # 경험치 1 추가
    exp += 1

    # 경험치가 레벨과 같아지면 레벨 1 추가, 경험치 초기화
    if level == exp:
        level += 1
        exp = 0

print(time)  # 총 시간을 출력

알고리즘

• 그래프 탐색

• BFS

Tip

• BFS, 큐를 활용한 풀이
• 파이썬의 내장 자료구조인 deque를 활용해서 순간이동 시
• 관리할 리스트의 크기를 시작과 목표지점의 차이의 2배로 설정 (곱하기 2 연산 때문)

풀이

관리할 리스트 (dp)를 생성 ( dp[n] 은 시작 지점에서 n까지의 최단 거리를 뜻함 )

방문하지 않은 곳은 -1로 설정

시작 지점 dp[start] 을 0으로 설정

목표 지점 dp[finish] 초기값을 abs(start - finish) -> start와 finish의 차이로 설정

코드

# 그림
# 그림

from collections import deque

start, finish = map(int, input().split())

# -1 -> 방문을 한 번도 안함
# n >= 0 -> finish까지 걸리는 시간
dp = [-1] * (max(start, finish) * 2)
dp[start] = 0
dp[finish] = abs(start - finish)
queue = deque([start])
while queue:
    n = queue.popleft()
    if dp[n] >= dp[finish]:
        continue
    if n < finish:
        if dp[n * 2] == -1 or dp[n] < dp[n * 2]:
            dp[n * 2] = dp[n]
            queue.appendleft(n * 2)
        if dp[n + 1] == -1 or dp[n] + 1 < dp[n + 1]:
            dp[n + 1] = dp[n] + 1
            queue.append(n + 1)
        if n != 0 and (dp[n - 1] == -1 or dp[n] + 1 < dp[n - 1]):
            dp[n - 1] = dp[n] + 1
            queue.append(n - 1)
    elif n > finish:
        if dp[n - 1] == -1 or dp[n] + 1 < dp[n - 1]:
            dp[n - 1] = dp[n] + 1
            queue.append(n - 1)

print(dp[finish])



res = []
for n in range(N):
    for m in range(M):
        if not visited[n][m] and picture[n][m] == 1:
            res.append(dfs(1, n, m))
if len(res) == 0:
    print(0)
    print(0)
else:
    print(len(res))
    print(max(res))

알고리즘

• 백트래킹

백트래킹이란?

• 모든 경우의 수를 전부 고려하는 알고리즘
• 상태공간을 트리로 나타낼 수 있을 때 적합한 방식이다. (나무 위키)
  
• 구현 방식*
  
• DFS(깊이 우선 탐색 / 스택 활용)
• BFS(너비 우선 탐색 / 큐 활용) (큐를 사용하지 않을 수도 있음)
• Best First Search(최선 우선 탐색 / 우선 순위 큐 활용)
  많은 블로그에서 백트래킹 == DFS 라고 하지만 상황에 따라 BFS로도 백트래킹을 구현할 수 있다.

Tip

• 모든 경우의 수를 탐색하는 것이 백트래킹이다.
• 분기가 추가될 때마다 현재 분기가 유망한지 검사 후 유망하지 않다면 분기를 종료한다.(가지치기)
• 유망한지 검사하는 함수를 최적화하는 것이 중요*
• 분기가 종료(반환)되면 다시 이전 상태로 돌려놓는다.

풀이

1. 스도쿠를 돌면서 빈자리(0)를 탐색한다
2. 빈자리에 1~9 를 넣었을 때 세로,가로,칸에 대해 각각 가능한지 (중복되는 숫자가 있는지) 테스트한다.
3. 가능하다면 스도쿠판에 숫자를 넣고 재귀함수를 호출하고 가능하지 않다면 함수를 반환한다.
4. 3번에서 만약 호출한 함수가 반환되면 숫자를 넣었던 자리에 0을 넣어서 스도쿠판을 복구한다.
5. 가능한 케이스가 발견되면 출력 후 프로그램을 종료한다 exit(0)

코드

python은 시간초과나서 pypy로 제출함

import sys

input = sys.stdin.readline


# 같은 행에 중복되는 숫자가 없는지
def check_row(row, n):
    for i in range(9):
        if n == sudoku[row][i]:
            return False
    return True


# 같은 열에 중복되는 숫자가 없는지
def check_col(col, n):
    for i in range(9):
        if n == sudoku[i][col]:
            return False
    return True


# 같은 칸에 중복되는 숫자가 없는지
def check_rect(row, col, n):
    # 각 칸이 시작하는 인덱스를 구함
    # 012 345 678
    # 2 -> 0
    # 5 -> 3
    real_row = row // 3 * 3
    real_col = col // 3 * 3
    for y in range(3):
        for x in range(3):
            if n == sudoku[real_row + y][real_col + x]:
                return False
    return True


sudoku = [[] for _ in range(9)]  # 스도쿠 판
empty_place = []  # 빈자리[(row,col)]

# 스도쿠판에 숫자 채우기 & 빈자리는 따로 리스트에 보관
for n in range(9):
    for m, num in enumerate([int(x) for x in input().split()]):
        sudoku[n].append(num)
        if num == 0:
            empty_place.append((n, m))


def dfs(n):
    if n == len(empty_place):
        # 답을 찾으면 프로그램 종료
        for i in range(9):
            print(*sudoku[i])
        exit(0)

    # 빈자리에 1~9까지 넣어보고 가능하다면 재귀함수 호출
    row = empty_place[n][0]
    col = empty_place[n][1]
    for i in range(1, 10):
        if check_row(row, i) and check_col(col, i) and check_rect(row, col, i):
            sudoku[row][col] = i  # 1~9 숫자 넣고
            dfs(n + 1)  # 새로운 분기 시작
            sudoku[row][col] = 0  # 분기가 종료되면 (답이 없다면) 원상태 복구


dfs(0)

소감

함수가 반환되면 그 후에 다시 되돌려놓는 방식을 생각 못해서 분기마다 새 배열을 만들고 매개변수로 넘겨주고 있었다. 배열을 복사하는 과정에서 시간초과, 매 분기 복사된 배열 때문에 메모리 초과가 동시에 났다. 구글링 후 해결 방법을 봤을 때 정말 감탄스러웠고 앞으로 유용하게 써먹어야겠다.

알고리즘

• 그래프 탐색

tip

• visited 테이블로 방문처리를 하면서 방문하지 않은 곳만 탐색

풀이

이차원 리스트를 전부 순회하면서 방문하지 않았던 곳만 dfs() 함수를 실행한다.

dfs() 함수는 연결되어 있는 숫자 '1' 만 상하좌우 탐색해서 total에 추가한다.

코드

# 그림
# 그림
import sys

# 재귀 호출 횟수 제한 해제
sys.setrecursionlimit(10000000)
input = sys.stdin.readline


N, M = map(int, input().split())

## 도화지 (이차원 리스트)
picture = [list(map(int, input().split())) for _ in range(N)]

## 방문처리를 위한 리스트
visited = [[False for _ in range(M)] for _ in range(N)]

# 상하좌우 네 방향
direction = [(1, 0), (0, -1), (-1, 0), (0, 1)]


# 도화지의 각 지점마다 한번씩 호출
def dfs(cnt, n, m):
    total = 0

    # 방문 처리가 안 된 좌표를 돌면서 1의 총 개수를 저장(total)
    def _dfs(cnt, n, m):
        visited[n][m] = True  # 방문 처리
        nonlocal total
        total += 1
        for d in direction:  # 상하좌우 4방향
            next_n = n + d[0]
            next_m = m + d[1]
            if (
                # 리스트 인덱스 검사
                0 <= next_n < N
                and 0 <= next_m < M
                # 1인지 검사
                and picture[next_n][next_m] == 1
                # 방문하지 않았던 곳인지
                and not visited[next_n][next_m]
            ):
                _dfs(cnt + 1, next_n, next_m)

    _dfs(cnt, n, m)
    return total


res = []
for n in range(N):
    for m in range(M):
        if not visited[n][m] and picture[n][m] == 1:
            res.append(dfs(1, n, m))
if len(res) == 0:
    print(0)
    print(0)
else:
    print(len(res))
    print(max(res))

알고리즘

• 다이나믹 프로그래밍

tip

다이나믹 프로그래밍 문제 해결하는 방법

1. 큰 문제를 보다 작은 문제들의 합으로 재귀적으로 푸는 방법을 찾는다.
2. 이전의 값을 저장해서 반복적인 계산을 최소화한다.

풀이

N=3 일 때, 모든 경우의 수를 나타내면 다음과 같다.

N=3에서 총 경우의 수는 32 (밑의 가지들을 모두 더해서 구한다)

그렇다면 반복적인 계산은 어떤게 있을까?

그림과 같이 같은 라인의 숫자 2 이후부터 경우의 수가 1과 3으로 같다. 마찬가지로 같은 라인의 3,4,5,6,7,8 의 숫자들이 두번씩 반복된다.

반복되는 계산을 모두 제외하면 아래와 같다.

포인트
같은 라인(자릿수) 에서 같은 숫자가 나오면 값을 저장해 놓는다. 변수가 두 개 - 같은 자릿수 & 같은 숫자 이므로 이차원 리스트를 활용한다.

코드

n 자리에서의 경우의 수 = n-1 자리에서의 경우의 수 + n+1 자리에서의 경우의 수

메모이제이션 적용 전 코드

import sys

# 재귀 호출 제한 해제
sys.setrecursionlimit(100000000)
n = int(input())

res = 0

# s -> "0" ~ "9"
def dfs(s):

    # 목표 자릿수에 도달하면
    if len(s) == n:
        return 1

    # 9 -> 8
    if s[-1] == "9":
        return dfs(s + "8")

    # 0 -> 1
    if s[-1] == "0":
        return dfs(s + "1")

    else:
        return dfs(f"{s}{int(s[-1])+1}") + dfs(f"{s}{int(s[-1])-1}")


# 1부터 9까지의 경우의 수를 각각 구해서 합치기
for i in range(1, 10):
    res += dfs(str(i))

print(res % 1000000000)

입력으로 3을 넣으면 32가 알맞게 출력된다. 하지만 100을 넣으면 엄청 오래 걸린다.

메모이제이션 적용한 코드(정답 코드)

import sys

# 재귀 호출 제한 해제
sys.setrecursionlimit(100000000)
n = int(input())

# 메모이제이션
# 행 -> 자릿수
# 열 -> 숫자
memo = [[0 for _ in range(10)] for _ in range(n + 1)]
res = 0

# s -> "0" ~ "9"
def dfs(s, i):

    # 이전에 구했던 자릿수 & 숫자와 일치하면 결과 재사용
    if memo[i][int(s[-1])]:
        return memo[i][int(s[-1])]

    # 목표 자릿수에 도달하면
    if len(s) == n:
        # print(s) 
        return 1

    # 9 -> 8
    if s[-1] == "9":
        cnt = dfs(s + "8", i + 1)
        memo[i][int(s[-1])] = cnt
        return cnt

    # 0 -> 1
    if s[-1] == "0":
        cnt = dfs(s + "1", i + 1)
        memo[i][int(s[-1])] = cnt
        return cnt

    else:
        cnt = dfs(f"{s}{int(s[-1])+1}", i + 1) + dfs(f"{s}{int(s[-1])-1}", i + 1)
        memo[i][int(s[-1])] = cnt
        return cnt

# 1부터 9까지의 경우의 수를 각각 구해서 합치기
for i in range(1, 10):
    res += dfs(str(i), 1)

print(res % 1000000000)

최적화한 코드다.

함수 마지막 return 부분에 print 함수로 출력해보면

입력으로 100을 넣었을 때 최적화 없이 마지막까지 구한 경우가 18번 밖에 되지 않는다.

영상 설명: 빈 댓글을 입력하면 경고창이, 댓글 삭제에 성공하면 성공했다는 알림이 뜬다.

알림창을 전역 관리하는 목적

처음에는 알림창을 각각의 컴포넌트에서 호출하고 그에 따른 상태 관리도 따로 했었다. 이 방법에는 다음과 같은 단점이 있었다.

1. 알림창을 사용하는 컴포넌트마다 <Notice/> 를 호출하고 useState() 로 상태관리를 해줘야 하며 알림창을 띄우는 함수를 따로 구현해야 해서 코드가 상당히 복잡해진다.
2. 특정 컴포넌트에서 호출하기 때문에 해당 컴포넌트가 반환되면 알림창도 같이 꺼진다. (가장 큰 문제)

알림창을 사용할 때마다 아래의 세팅을 해줘야 한다.

// pages/posts/[id].tsx

import React, { useState } from 'react';
import Notice from '../components/notification/notice';

// 최초 useState에 들어가는 값
const initialNoticeState = {
  show: false,
  isSuccessed: false,
  header: '',
  message: '',
};

const PostDetail = () => {
  const [notice, setNotice] = useState(initialNoticeState);

  // 알림창을 닫는 함수 (몇초가 지나고 알림창이 스스로 이 함수를 호출한다.)
  function handleNoticeClose() {
    setNotice(initialNoticeState);
  }

  // 작업 성공 시 초록색 알림창을 보여준다.
  function showSuccessed(header: string, message: string) {
    setNotice({
      show: true,
      isSuccessed: true,
      header,
      message,
    });
  }

  // 작업 실패 시 빨간색 알림창을 보여준다.
  function showFailed(header: string, message: string) {
    setNotice({
      show: false,
      isSuccessed: false,
      header,
      message,
    });
  }


  // 알림창 띄우기
  function onSuccessed() {
    showSuccessed('Success', '성공했습니다!'); 
  }

  function onFailed() {
    showSuccessed('Error', '실패했습니다!'); 
  }

  return (
    <div>
      <Notice info={notice}/>
      <button onClick={onSuccessed}>성공</button> 
      <button onClick={onFailed}>실패</button> 
    </div>
  );
};

export default PostDetail;

이러한 이유로 useContext를 활용해 알림창을 최상위 컴포넌트 _app.tsx 에서 관리하기로 결심했다.

Context 만들기

useContext와 useState로 코드를 짰다.

// store/notice-context.tsx

import { createContext, useContext } from 'react';
import React, { useState } from 'react';

// 알림창 Context의 State
interface State {
  show: boolean;
  isSuccessed: boolean;
  header: string;
  message: string;
  successed: (info: Info) => void;
  failed: (info: Info) => void;
  close: () => void;
}

export interface Info {
  header: string;
  message: string;
}

// 최초 useState에 들어가는 값
const defaultState: State = {
  show: false,
  isSuccessed: false,
  header: '',
  message: '',
  successed: (info: Info) => {},
  failed: (info: Info) => {},
  close: () => {},
};

// Provider에 들어갈 value를 생성한다.
const StateContext = createContext(defaultState);


const NoticeProvider: React.FC<{ children: React.ReactNode }> = ({
  children,
}) => {
  const [state, setState] = useState(defaultState);

  // 작업 성공 시 초록색 알림창을 띄우는 함수
  const successed = (info: Info) => {
    setState((prev) => ({
      ...prev,
      show: true,
      isSuccessed: true,
      header: info.header,
      message: info.message,
    }));
  };

  // 작업 실패 시 빨간색 알림창을 띄우는 함수
  const failed = (info: Info) => {
    setState((prev) => ({
      ...prev,
      show: true,
      isSuccessed: false,
      header: info.header,
      message: info.message,
    }));
  };

  // 알림창을 닫는 함수
  const close = () => {
    setState(defaultState);
  };

  const noticeCtx: State = {
    show: state.show,
    isSuccessed: state.isSuccessed,
    header: state.header,
    message: state.message,
    successed,
    failed,
    close,
  };

  return (
    <StateContext.Provider value={noticeCtx}>{children}</StateContext.Provider>
  );
};

// 사용하기 편하게 훅으로 만들어준다.
export const useNotice = () => {
  return useContext(StateContext);
};

export default NoticeProvider;

위에서 구현했던 함수들을 Context의 State에 모두 담아준다. 이제 알림창을 사용할 때마다 여기 작성해둔 함수를 갖다 쓰기만 하면 된다.

_App.tsx에 렌더링하기

위에서 작성한 Provider를 최상단 컴포넌트 _app.tsx 에 렌더링한다. 이로써 특정 컴포넌트가 반환되어도 알림창은 꺼지지 않고 유지된다.

// _app.tsx

import type { AppProps } from 'next/app';
import Notice from '../components/notification/notice';
import NoticeProvider from '../store/notice-context';

function App({ Component, pageProps }: AppProps) {
  return (
    <NoticeProvider> 
      <Notice />
      <Component {...pageProps} />
    </NoticeProvider>
  );
}

export default App;

알림창 Context를 모든 컴포넌트에서 사용할 수 있게 Provider로 감싸준다. 그리고 알림창 <Notice/> 를 최상단에서 관리한다.

Context 사용하기

이제 위에서 만든 Context를 사용한다. <Notice/> (알림창) 컴포넌트 내에서는 Context의 show, isSuccessed, header, message, close() 의 값을 받아오고 알림창을 띄울 컴포넌트에서는 successed(), failed() 함수를 실행한다.

먼저 알림창 컴포넌트이다. 나타나고 사라질 때 보이는 효과는 생략했다.

// components/notice.tsx

import React, { useEffect } from 'react';
import { useNotice } from '../store/notice-context';
import styles from './notice.module.scss';

const Notice: React.FC = () => {

  // Context 사용
  const { show, isSuccessed, header, message, close } = useNotice(); 

  // 3초뒤에 알림창을 스스로 닫는다.
  useEffect(() => {
    if (show) {
      setTimeout(() => {
        close();
      }, 3000);
    }
  }, [close, show]);

  return (
    <div>
      {show && (
        <div className={ isSuccessed ? styles.successed : styles.failed }> 
          <div>
            <div>{header}</div>
            <button onClick={close}>✕</button>
          </div>
          <div>{message}</div>
        </div>
      )}
    </div>
  );
};

export default Notice;

Context 파일에서 정의한 useNotice 훅으로 쉽게 useContext를 호출할 수 있다.

이제 알림창을 띄우는 것도 쉽게 구현 가능하다.

// pages/posts/[id].tsx

import React from 'react';
import { useNotice } from '../store/notice-context';

const PostDetail = () => {

  // Context 사용
  const { successed, failed } = useNotice();

  // 알림창 띄우기
  function onSuccessed() {
    successed({ header: 'Success', message: '성공했습니다!' });
  }

  function onFailed() {
    failed({ header: 'Error', message: '실패했습니다!' });
  }

  return (
    <div>
      <button onClick={onSuccessed}>성공</button>
      <button onClick={onFailed}>실패</button>
    </div>
  );
};

export default PostDetail;

</Notice> 컴포넌트를 직접 렌더링할 필요도 없고 함수를 따로 구현할 필요도 없어서 코드가 훨씬 깔끔해졌다. 맨 처음 코드와 비교해보길 바란다.

마치며

사이트에서 다양한 에러 처리에 알림창을 활용할 수 있다. 이번 기능을 만들면서 useContext에 대해서도 복습할 수 있었던 좋은 기회였다.

P.S. 알림창 외에도 사용자에게 한 번 더 확인하는 <Confirm/> 컴포넌트 등 최상단에서 관리하면 편리해질 것이 많아보인다. 기능 하나를 만들 때마다 _app.tsx 에 Provider로 감싸면 보기에 좋지 않을 것이므로 조만간 redux로 옮겨야 할 듯하다.

Next.js에서 카카오 로그인을 구현하기까지의 모든 과정과 코드를 공유한다. (카카오 홈페이지에서 사이트 등록을 하는 등의 작업은 다른 포스트에서 많이 다루기 때문에 패스했다.)

인증 순서

그림 출처(https://data-jj.tistory.com/53)

구현 과정은 위와 거의 동일하다. 다만 내 사이트에선 토큰 대신 세션을 사용해 유저를 인증한다. (6번만 다르고 카카오 인증 과정은 동일하다)

0. JS SDK 파일 다운로드

Kakao Developer -> 시작하기 / Javascript 먼저 카카오에서 제공하는 자바스크립트 SDK 파일을 다운로드한다. (Script 태그 사용) 그리고 앱 시작과 동시에 Kakao.init() 함수로 초기화한다.

// _app.tsx

import type { AppProps } from 'next/app';
import Layout from '../components/layouts/layout';
import Script from 'next/script';

declare global { // Kakao 함수를 전역에서 사용할 수 있도록 선언
  interface Window {
    Kakao: any;
  }
}
function App({ Component, pageProps }: AppProps) {

  function kakaoInit() { // 페이지가 로드되면 실행
    window.Kakao.init(process.env.NEXT_PUBLIC_KAKAO_JS_KEY);
    console.log(window.Kakao.isInitialized());
  }

  return (
    <Layout>
      <Component {...pageProps} />
      <Script
        src='https://developers.kakao.com/sdk/js/kakao.js'
        onLoad={kakaoInit} 
      ></Script>
    </Layout>
  );
}

export default App;

이제 다른 파일에서도 카카오에서 제공하는 함수를 사용할 수 있다. (백엔드는 따로 설정해야 한다)

1. 로그인 요청

유저가 카카오 로그인 버튼을 누르면 카카오 로그인 창을 띄워야 한다. 이때는 두가지 방법이 있는데

1. 리다이렉트 방식
   위의 그림에 나와있는 방식과 동일하며 Kakao.Auth.authorize() 함수를 사용한다. 별도의 팝업창 없이 같은 창 내에서 요청을 주고 받는다.

2. 팝업 방식
   Kakao.Auth.login() 함수를 사용한다. 별도의 팝업창을 열어서 로그인 로직을 구현하는 방식이다.

나는 리다이렉트 방식을 사용했다. 클라이언트에서 인가코드만 받아서 나머지는 백엔드에서 처리하는 리다이렉트 방식과 달리 클라이언트에서 직접 토큰을 받아오는 팝업 방식이 보안적으로 더 위험해 보였기 때문이다.

함수를 만들기 전에 먼저 카카오 Developer 홈페이지에서 Redirect URI를 등록해야 한다. 유저가 입력한 아이디/비번을 카카오 서버에서 확인하면 등록된 URL로 인가코드를 전송해준다. 코드는 URL 쿼리 형식으로 전달 받기 때문에 해당 로직을 처리할 프론트엔드 페이지를 하나 만들어야 한다.

나는 http://localhost:3000/kakao 페이지를 Redirect URI로 등록했는데 http://localhost:3000/kakao?code=nowiw9f92rjf 형식으로 인가코드를 전달받았다.

// pages/login.tsx

const Login = () => {

  // 등록한 redirectUri를 매개변수로 넣어준다.
  function kakaoLogin() {
    window.Kakao.Auth.authorize({
      redirectUri: 'http://localhost:3000/kakao', 
    });
  }

  return (
    <div className={styles.container}>
      <KakaoBtn title='카카오 로그인' onClickBtn={kakaoLogin} />
    </div>
  );
};

export default Login;

2. 백엔드에 인가코드 보내기 && 리다이렉트 처리하기

이제 등록된 redirectUri에서 인가코드를 받은 뒤 백엔드에 보내야 한다. (유저에 대한 정보는 모두 백엔드에서 처리한다) 그리고 백엔드에서 받은 응답(성공/에러)에 따라서 각각 처리해준다. 위의 그림에서 3번, 8번에 해당한다.

페이지가 호출될 때 한번만 요청을 보내므로 useEffect() 함수를 사용했다. 또 무한루프를 방지하기 위해 loginHandler() 함수를useCallback() 함수로 감싸서 재렌더링을 방지했다.

// pages/kakao.tsx

import { NextPage } from 'next';
import { useRouter } from 'next/router';
import { useCallback, useEffect } from 'react';


interface ResponseType {
  ok: boolean;
  error?: any;
}

const Kakao: NextPage = () => {
  const router = useRouter();
  const { code: authCode, error: kakaoServerError } = router.query;

  const loginHandler = useCallback(
    async (code: string | string[]) => {

      // 백엔드에 전송
      const response: ResponseType = await fetch('/api/users/kakao-login', {
        method: 'POST',
        headers: {
          'Content-Type': 'application/json',
        },
        body: JSON.stringify({
          authCode: code,
        }),
      }).then((res) => res.json());

      if (response.ok) { // 성공하면 홈으로 리다이렉트
        router.push('/');
      } else { // 실패하면 에러 페이지로 리다이렉트
        router.push('/notifications/authentication-failed');
      }
    },
    [router]
  );

  useEffect(() => {
    if (authCode) {
      loginHandler(authCode);

      // 인가코드를 제대로 못 받았을 경우에 에러 페이지를 띄운다.
    } else if (kakaoServerError) { 
      router.push('/notifications/authentication-failed');
    }
  }, [loginHandler, authCode, kakaoServerError, router]);

  return (
          <h2>로그인 중입니다..</h2>
  );
};

3. 카카오 서버에서 유저 정보 받아오기

프론트엔드에서 받아온 인가코드로 카카오 서버에서 유저 정보를 받아온다.

1. 먼저 인가코드를 사용해서 토큰을 받아온 뒤
2. 받아온 토큰으로 유저 정보를 받는다.

토큰을 받아올 때는 REST_API_KEY와 REDIRECT_URI를 URL에 넣어야 한다. 공식문서

// pages/api/users/kakao-login.ts

import { NextApiRequest, NextApiResponse } from 'next';

interface TokenResponse {
  token_type: string;
  access_token: string;
  refresh_token: string;
  id_token: string;
  expires_in: number;
  refresh_token_expires_in: string;
  scope: string;
}

interface UserInfo {
  id: number;
  connected_at: string;
  properties: {
    nickname: string;
    profile_image?: string; // 640x640
    thumbnail_image?: string; // 110x110
  };
}

async function getTokenFromKakao(authCode: string) {
  const tokenUrl = `https://kauth.kakao.com/oauth/token?grant_type=authorization_code&client_id=${process.env.KAKAO_RESTAPI_KEY}&redirect_uri=${process.env.NEXT_PUBLIC_KAKAO_REDIRECT_URI}&code=${authCode}`;
  const response: TokenResponse = await fetch(tokenUrl, {
    method: 'POST',
    headers: { 'Content-Type': 'application/json' },
  }).then((res) => res.json());
  return response;
}

async function getUserFromKakao({ access_token }: TokenResponse) {
  const userInfoUrl = 'https://kapi.kakao.com/v2/user/me';
  const response: UserInfo = await fetch(userInfoUrl, {
    headers: {
      'Content-Type': 'application/json',
      Authorization: `Bearer ${access_token}`,
    },
  }).then((res) => res.json());
  return response;
}

const handler = async (
  req: NextApiRequest,
  res: NextApiResponse
) => {
  const { authCode } = req.body; // 인가 코드

  // 토큰 받아오기
  const tokenResponse = await getTokenFromKakao(authCode);

  // 유저 정보 받아오기
  const userInfo = await getUserFromKakao(tokenResponse);
  const {
    id: kakaoId,
    properties: { nickname, profile_image, thumbnail_image },
  } = userInfo;

4. 데이터베이스에서 유저 정보 확인하고 세션 부여

(데이터베이스는 planetscale, ORM은 prisma를 사용했다)

이제 카카오 로그인은 끝났다. 하지만 카카오의 유저인 사실을 확인했을 뿐 우리 사이트의 유저인지 아닌지는 따로 확인해야 한다. 또 유저의 세션 정보도 업데이트 시켜야 한다.

카카오 서버에서 받아온 유저 정보를 활용해서 데이터베이스를 확인하는 작업이다. 나는 카카오의 고유한 회원 아이디를 이용해서 유저를 인증했다. (회원 아이디는 위의 getUserFromKakao() 함수로 불러올 수 있다)

데이터베이스를 많이 조회할수록 속도가 느려진다. 그래서 해당 유저가 존재하는지 확인(client.user.findUnique())하는 대신 이중 try, catch 문으로 한번에 처리했다.

1. 유저와 세션이 모두 존재할 경우 해당 유저와 연결된 세션만 업데이트 시킨다.
2. 유저만 존재할 경우 새로운 세션을 만들어서 유저와 연결한다. (세션이 해킹당했다고 의심될 경우 세션 저장소를 비워야 하기 때문에 세션 없이 유저만 존재할 수도 있다)
3. 둘 다 존재하지 않을 경우 유저와 세션을 새로 생성한다. (회원가입)

보통의 경우 사이트를 재방문하기 때문에 1번에서 끝난다. (데이터베이스와 한번만 통신한다)

만약 사이트를 처음 방문하는 경우 3번까지 가야 한다. (데이터베이스와 세번 통신한다)

// pages/api/users/kakao-login.ts
// 함수 선언

// 1. 세션만 업데이트하는 함수
async function updateSession(kakaoId: number, newSessionId: string) {
  const session = await client.session.update({
    where: {
      kakaoId,
    },
    data: {
      sessionId: newSessionId,
    },
  });
  return session;
}

// 2. 세션을 생성하고 유저와 연결하는 함수
async function createSessionAndConnectToUser(
  kakaoId: number,
  newSessionId: string
) {
  const user = await client.user.update({
    where: {
      kakaoId,
    },
    data: {
      session: {
        create: { kakaoId, sessionId: newSessionId },
      },
    },
  });
  return user;
}

// 3. 새로운 유저를 생성하는 함수 (회원가입)
async function createUser(
  {
    id: kakaoId,
    properties: { nickname, profile_image, thumbnail_image },
  }: UserInfo,
  newSessionId: string
) {
  const user = await client.user.create({
    data: {
      name: nickname,
      kakaoId,
      loggedFrom: 'Kakao',
      profileImage: profile_image || null,
      session: {
        create: { kakaoId, sessionId: newSessionId },
      },
    },
  });
  return user;
}

// pages/api/users/kakao-login.ts
// 로직 구현

import { createSession } from '../../../lib/secret/createSession';
import client from '../../../lib/server/client';

  let user;
  const newSessionId = createSession(kakaoId); // 새로운 세션 생성

  // 데이터베이스 조회를 최소화하기 위해 이중 try문으로 구현했다.
  try {
    // 1. 세션이 존재하면 업데이트만 해주면 됨
    await updateSession(kakaoId, newSessionId);
  } catch {
    try {
      // 2. 유저는 존재하는데 세션이 없는 경우 유저의 세션 값만 업데이트 해준다.
      user = await createSessionAndConnectToUser(kakaoId, newSessionId);
    } catch {
      // 유저가 존재하지 않으면 새로운 계정을 생성한다.
      user = await createUser(userInfo, newSessionId);
    }
  }

  // 유저에게 세션 부여
  req.session.user = { id: newSessionId };
  await req.session.save();
  return res.json({ ok: true });

백엔드 전체 코드

실제 코드에서 withApiSession(백엔드에서 세션을 사용할 수 있게 해주는 함수), withHandler(백엔드에서의 try,catch문 같은 귀찮은 코드를 사용하는 함수)를 사용했는데 다음 포스트에서 확인하기 바란다.

import { NextApiRequest, NextApiResponse } from 'next';
import { createSession } from '../../../lib/secret/createSession';
import client from '../../../lib/server/client';
import withHandler, { ResponseType } from '../../../lib/server/withHandler';
import { withApiSession } from '../../../lib/server/withSession';

interface TokenResponse {
  token_type: string;
  access_token: string;
  refresh_token: string;
  id_token: string;
  expires_in: number;
  refresh_token_expires_in: string;
  scope: string;
}

interface UserInfo {
  id: number;
  connected_at: string;
  properties: {
    nickname: string;
    profile_image?: string; // 640x640
    thumbnail_image?: string; // 110x110
  };
}

async function getTokenFromKakao(authCode: string) {
  const tokenUrl = `https://kauth.kakao.com/oauth/token?grant_type=authorization_code&client_id=${process.env.KAKAO_RESTAPI_KEY}&redirect_uri=${process.env.NEXT_PUBLIC_KAKAO_REDIRECT_URI}&code=${authCode}`;
  const response: TokenResponse = await fetch(tokenUrl, {
    method: 'POST',
    headers: { 'Content-Type': 'application/json' },
  }).then((res) => res.json());
  return response;
}

async function getUserFromKakao({ access_token }: TokenResponse) {
  const userInfoUrl = 'https://kapi.kakao.com/v2/user/me';
  const response: UserInfo = await fetch(userInfoUrl, {
    headers: {
      'Content-Type': 'application/json',
      Authorization: `Bearer ${access_token}`,
    },
  }).then((res) => res.json());
  return response;
}

async function updateSession(kakaoId: number, newSessionId: string) {
  const session = await client.session.update({
    where: {
      kakaoId,
    },
    data: {
      sessionId: newSessionId,
    },
  });
  return session;
}

async function createSessionAndConnectToUser(
  kakaoId: number,
  newSessionId: string
) {
  const user = await client.user.update({
    where: {
      kakaoId,
    },
    data: {
      session: {
        create: { kakaoId, sessionId: newSessionId },
      },
    },
  });
  return user;
}
async function createUser(
  {
    id: kakaoId,
    properties: { nickname, profile_image, thumbnail_image },
  }: UserInfo,
  newSessionId: string
) {
  const user = await client.user.create({
    data: {
      name: nickname,
      kakaoId,
      loggedFrom: 'Kakao',
      profileImage: profile_image || null,
      session: {
        create: { kakaoId, sessionId: newSessionId },
      },
    },
  });
  return user;
}

const handler = async (
  req: NextApiRequest,
  res: NextApiResponse<ResponseType>
) => {
  const { authCode } = req.body;

  const tokenResponse = await getTokenFromKakao(authCode);
  const userInfo = await getUserFromKakao(tokenResponse);
  const {
    id: kakaoId,
    properties: { nickname, profile_image, thumbnail_image },
  } = userInfo;

  let user;
  const newSessionId = createSession(kakaoId);

  try {
    await updateSession(kakaoId, newSessionId);
  } catch {
    try {
      user = await createSessionAndConnectToUser(kakaoId, newSessionId);
    } catch {
      user = await createUser(userInfo, newSessionId);
    }
  }

  req.session.user = { id: newSessionId };
  await req.session.save();
  return res.json({ ok: true });
};

export default withApiSession(withHandler({ methods: ['POST'], handler }));

알고리즘

• 구현

• 자료 구조
• 문자열
• 파싱
• 덱

tip

• 리스트의 양쪽 모두에서 삭제가 쉬운 deque 자료구조를 활용한다.

• 시간이 오래걸리는 reverse() 연산을 최소화한다.

구현할 것들

1. 입력받은 [1,2,3,4] 형태의 문자열을 deque로 변환
2. 입력받은 R,D 함수를 for문으로 처리
3. 최종적으로 남은 deque를 [1,2,3,5,8] 형태로 출력

풀이

from collections import deque
from sys import stdin


input = stdin.readline
T = int(input())

for _ in range(T):
    functions = input().rstrip() # 'RDDRR'

    # 연속으로 두번 나오는 'R'을 없애준다
    functions = functions.replace("RR", "") 

    cnt = int(input())
    lst = input().rstrip() # '[1,2,3,4]'

    if len(lst) == 2:  # 빈 리스트가 들어오면 바로 처리한다
        if "D" in functions:
            print("error")
        else:
            print([])
        continue

    # '[1,2,3,4]' 형태의 문자열을 조작해서 deque에 넣는다
    lst = map(int, lst[1:-1].split(","))
    deq = deque(lst)

입력을 받는 코드이다. functions 변수에 'RDDRR' 형태의 문자열을 받는다. 연속으로 나오는 'R' 은 의미가 없기 때문에 replace() 함수로 없애준다.

이제 '[1,2,3,4]' 형태의 문자열을 lst 변수에 담고 조작을 거쳐 deque로 변환한다. 만약 빈 리스트가 입력으로 들어오면 명령어에 'D'가 있는지만 확인해서 바로 처리한다.

    reversing = False # False면 왼쪽에서 삭제하고 True면 오른쪽에서 삭제한다.

    for f in functions:
        if f == "R": # 실제로 리스트를 뒤집지 않는다.
            reversing = not reversing
        else:
            if len(deq) == 0:
                print("error")
                # for else: break 문에 걸리면 else 문으로 넘어가지 않는다
                break 

            if reversing:
                deq.pop()
            else:
                deq.popleft()
    else:
        if reversing: # 만약 마지막에 'R'이 하나 남았다면 deque를 뒤집는다.
            deq.reverse()
        print_deque(deq) # deque를 출력해서 마무리

이제 함수를 처리한다. 'R' 함수에서 실제로 리스트를 뒤집지 않는다. 대신 reversing 변수의 값을 스위치하면서 왼쪽에서 값을 뺄 것인지 오른쪽에서 뺄 것인지를 결정한다.

그리고 리스트의 길이가 0일 때 'D' 함수가 들어오면 error를 출력하고 break 문을 통해 빠져나온다.

for 문이 끝나면 리스트를 한번 뒤집어야 하는지 확인하고 print_deque() 함수를 호출한다. 하지만 아까 break 문으로 빠져나와서도 출력하는 코드가 실행되면 안되기 때문에 for else 문으로 처리한다. (for 문에서 break 문으로 빠져나오면 else 문으로 넘어가지 않는다.)

def print_deque(deq):
    if len(deq) == 0:
        print([])
    else:
        res = "["
        for i in range(len(deq) - 1):
            res += f"{deq[i]},"
        res += f"{deq[-1]}]"
        print(res)

마지막으로 deque를 출력하는 함수이다. 단순히 리스트로 변환해서 출력하면 [1, 2, 3, 5, 8] 형태로 출력되는데 이는 빈칸 때문에 오답처리된다. 따라서 [1,2,3,5,8] 의 형태로 출력하는 함수를 따로 만들어준다.

전체 코드

from sys import stdin
from collections import deque

input = stdin.readline


def print_deque(deq):
    if len(deq) == 0:
        print([])
    else:
        res = "["
        for i in range(len(deq) - 1):
            res += f"{deq[i]},"
        res += f"{deq[-1]}]"
        print(res)


T = int(input())

for _ in range(T):
    functions = input().rstrip()
    functions = functions.replace("RR", "") 
    cnt = int(input())
    lst = input().rstrip()

    if len(lst) == 2:  # []
        if "D" in functions:
            print("error")
        else:
            print([])
        continue

    lst = map(int, lst[1:-1].split(","))
    deq = deque(lst)


    reversing = False

    for f in functions:
        if f == "R":
            reversing = not reversing
        else:
            if len(deq) == 0:
                print("error")
                break
            if reversing:
                deq.pop()
            else:
                deq.popleft()
    else:
        if reversing:
            deq.reverse()
        print_deque(deq)

1. Sass 설치

 npm i sass

2. 이미 있는 css 파일 모두 scss로 변경

styles/global.css styles/Home.module.css 를

styles/global.scss styles/Home.module.scss 이렇게 바꿔준다.

3. next.config.js 파일 수정

next.config.js에 sassOptions 옵션을 추가한다.

const path = require('path'); // 1. path 선언

const nextConfig = {
  reactStrictMode: true,
  sassOptions: {
    includePaths: [path.join(__dirname, 'styles')], // 2. sassOptions 옵션 추가
  },
};

module.exports = nextConfig;

모든 scss 파일에서 공통으로 사용할 _variables.scss, _mixins.scss 파일을 추가한다.

styles/_variables.scss styles/_mixins.scss

5. next.config.js 파일 수정

이제 next.config.js에 prependData 옵션을 추가한다. 이로써 모든 파일에서 _variables.scss, _mixins.scss 두 파일에서 선언한 변수를 모든 파일에서 사용할 수 있다.

const path = require('path'); 

const nextConfig = {
  reactStrictMode: true,
  sassOptions: {
    includePaths: [path.join(__dirname, 'styles')],
    prependData: `@import "styles/_variables.scss"; @import "styles/_mixins.scss";`, // prependData 옵션 추가
  },
};

module.exports = nextConfig;

🧩 목차

리스트 (List)

1. 파이썬 내장 리스트
2. 단순 연결 리스트
3. 원형 연결 리스트
4. 이중 연결 리스트

   스택 (Stack)

5. 내장 리스트 스택 (내장 리스트 사용)
6. 연결 리스트 스택 (단순 연결 리스트 사용)

   큐 (Queue)

7. 내장 리스트 큐 (내장 리스트 사용)
8. 연결 리스트 큐 (원형 연결 리스트 사용)
9. 양방향 큐(이중 연결 리스트 사용)

힙 (Heap)

1. 최대 힙
2. 최소 힙

   이진 탐색 트리 (Binary Search Tree)

3. 기본 이진 탐색 트리
4. AVL 탐색 트리

🧩 리스트 (List)

리스트(List)의 특징

• 여러 자료가 일직선으로 연결된 선형 자료구조

• Stack, Queue, Tree, Graph 등과 같은 다른 자료구조 구현에 활용되는 기초 자료구조

📌 파이썬 내장 리스트

특징

• 파이썬에 기본으로 내장되어있는 리스트

장점

• 사용이 간편하다.

단점

• 공간이 한정되어 있는 자료구조로 리스트가 커지거나 줄어들수록 시스템 내부에서 리스트의 크기를 계속 변경해줘야 한다.

• 메모리 주소의 순서를 사용하기 때문에 접근할 때 O(1)의 속도를 보여준다.

소요시간

• 접근 - O(1)

• 검색 - O(n) (정렬 시 O(log_n))
• 삭제 - O(n)

코드

📌 단순 연결 리스트

특징

• 각각의 원소가 노드들로 구성된다.

• 각 노드는 다음 노드를 가리키는 필드를 가진다.
• 삭제 연산 자체는 O(1)이지만 접근에 O(n)이 걸린다. 따라서 삭제도 O(n)이다.

장점

• 내장 리스트와 다르게 공간의 제약이 없다.

단점

• 이전 노드에 대한 정보가 없으므로 append() 연산에 O(n)의 시간이 걸린다. (다음 노드 대신 이전 노드를 저장하면 insert(0) 연산에 취약해진다)

소요시간

• 접근 - O(n)

• 검색 - O(n)
• 삭제 - O(n)
• 맨앞에 원소 추가(insert(0)) - O(1)
• 그 밖의 원소 추가 - O(n)

코드

📌 원형 연결 리스트

특징

• 단순 연결 리스트보다 발전된 자료구조

• 마지막 원소가 처음 원소를 가리킨다.

장점

• 리스트의 처음과 끝에 대한 정보를 가지고 있으므로 append(), insert(0) 연산 모두 강점을 보인다.

• 따라서 extend(), copy(), reverse() 연산에 부담이 줄어든다.

소요시간

• 접근 - O(n)

• 검색 - O(n)
• 삭제 - O(n)
• 맨앞, 맨끝에 원소 추가(insert(0), append) - O(1)
• 그 밖의 원소 추가 - O(n)

코드

📌 이중 연결 리스트

특징

• 이전 노드, 다음 노드를 가리키는 필드를 모두 가지는 자료구조

• 다양한 알고리즘에 유용하게 쓰인다.

장점

• 양방향 순회가 가능하다.

• 따라서 접근할 때의 소요시간을 최대 2배 단축할 수 있다.

단점

• 이전의 노드를 저장할 메모리 공간이 하나 더 필요하다.

소요시간

• 접근 - O(n)

• 검색 - O(n)
• 삭제 - O(n)
• 맨앞, 맨끝에 원소 추가(insert(0), append) - O(1)
• 그 밖의 원소 추가 - O(n)

코드

🧩 스택 (Stack)

스택(Stack)의 특징

• 가장 마지막에 삽입된 자료가 가장 먼저 삭제되는 후입선출 자료구조

• top으로 정한 곳을 통해서만 접근할 수 있다.
• 웹 브라우저의 방문 기록, 실행 취소(undo) 등에 쓰인다.

📌 내장 리스트 스택

특징

• 파이썬의 내장 리스트로 구현한 스택

장점

• 없다

단점

• 내장 리스트의 단점인 공간 제약을 피할 수 없다.

소요시간

• 삽입, 삭제, 접근 모두 O(1)

코드

📌 연결 리스트 스택

특징

• 단순 연결리스트로 구현한 스택

• 스택 연산은 단순 연결리스트로 충분하다. (굳이 원형 연결 리스트 사용할 필요 X)

장점

연결 리스트를 사용했기 때문에 공간의 제약에서 자유롭다.

소요시간

• 삽입, 삭제, 접근 모두 O(1)

코드

🧩 큐 (Queue)

큐(Queue)의 특징

• 가장 먼저 삽입된 자료가 가장 먼저 삭제되는 선입선출 자료구조

• 은행창구 번호표 대기, 프린터 출력, 선착순 프로그램 등에 쓰인다.

📌 내장 리스트 큐

특징

• 파이썬의 내장 리스트로 구현한 큐

장점

• 없다

단점

• 내장 리스트의 단점인 공간 제약을 피할 수 없다.

소요시간

• 삽입, 삭제, 접근 모두 O(1)

코드

📌 연결 리스트 큐

특징

• 원형 연결 리스트를 이용한 큐

• 원형 연결리스트는 맨 앞과 맨 끝에 원소를 삽입할 때 O(1)의 효율을 보인다.

• 큐에 적합한 자료구조

장점

• 연결 리스트를 사용했기 때문에 공간의 제약에서 자유롭다.

소요시간

• 삽입, 삭제, 접근 모두 O(1)

코드

📌 양방향 큐 (deque)

특징

• 양방향에서 요소를 추가하고 제거할 수 있다.

• 이중 연결리스트로 구현한다.

장점

• 일반적인 큐보다 다양한 곳에서 사용할 수 있다.

단점

• 이중 연결 리스트를 사용했기 때문에 메모리 공간을 더 차지한다.

소요시간

• 삽입, 삭제, 접근 모두 O(1)

코드

🧩 힙 (Heap)

힙(Heap)의 특징

• 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조 (우선순위 큐란 우선순위의 개념을 큐에 도입한 자료구조이며 힙으로 구현하는 것이 가장 효율적이다)

• 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어졌다.
• 부모 노드의 키 값이 자식 노드의 키 값보다 항상 크거나(작거나) 같은 완전 이진 트리다.
• 우선순위 큐는 시뮬레이션 시스템, 운영체제에서의 작업 스케줄링 등에 쓰인다.

📌 최대 힙

특징

• 가장 큰 값을 가진 노드가 우선순위를 갖는다.

• 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같다.

소요시간

• 힙 생성 - O(n)

• 삽입 - O(log_n)
• 삭제 - O(log_n)
• 접근 - O(n)

코드

📌 최소 힙

특징

• 가장 작은 값을 가진 노드가 우선순위를 갖는다.

• 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같다.

소요시간

• 힙 생성 - O(n)

• 삽입 - O(log_n)
• 삭제 - O(log_n)
• 접근 - O(n)

코드

🧩 이진 탐색 트리 (Binary Search Tree)

이진 탐색 트리 (Binary Search Tree)의 특징

• 항상 정렬된 상태를 유지하는 이진 트리로 탐색 연산에 강점을 가진 자료구조 (탐색할 때 이진 탐색 알고리즘을 사용할 수 있다)

• 각 노드는 키를 가지며 서로 중복되지 않는다.
• 각 노드의 왼쪽 자식 노드의 키는 오른쪽 자식 노드의 키보다 작다.

📌 기본 이진 탐색 트리

특징

• 기본적인 이진 탐색 트리

• 균형을 잡아주는 연산이 없기 때문에 트리의 균형이 무너지면 최악의 경우 탐색 연산에 O(n)의 시간이 소요된다.

소요시간

• 삽입, 검색, 삭제 모두 O(log_n)

• 균형이 무너질 시 검색에 O(n)

코드

📌 AVL 탐색 트리

특징

• AVL 검색 트리는 Basic 이진 검색 트리의 단점을 보완한 자료구조다.

• 삽입, 삭제 연산 시 트리의 균형을 체크, 만약 이상이 있으면 잡아주는 연산을 추가로 수행한다.
• 균형이 깨지는 조건 - 임의의 노드의 왼쪽 자식의 개수가 오른쪽 자식과 2이상 차이날 때
• 균형을 잡는 연산에 시간이 더 소요되긴 하지만 그럼에도 O(log_n)의 시간복잡도를 유지한다.

소요시간

• 삽입, 삭제, 접근 모두 O(log_n)

코드

1. useState() - 사용자가 입력할 때마다 값 받아오기
2. useRef() - 사용자가 입력을 마치고 Submit 버튼 누를 때 값 한번에 받아오기

useState() 를 사용하는 방법은 한글자 한글자 업데이트 될 때마다 유효성을 검사해서 조치를 취할 수 있다는 장점이 있다. (ex. 비밀번호 입력 받을 때)

하지만 input의 개수가 많을 때 모두 useState() 를 적용하면 사이트의 속도가 느려질 위험이 있다. 따라서 굳이 유효성 검사를 할 필요가 없는 input의 경우 useRef() 를 사용하는 것이 좋은 방법이다.

useRef 사용하는 방법

타입스크립트에서 useRef() 를 사용하는 방법이 복잡하진 않았다.

Todo 앱에서 input을 받는 NewTodo 컴포넌트를 간단하게 구현했다.

import React, { useRef } from 'react';

const NewTodo = () => {
  // input을 받으므로 HTMLInputElement의 제너릭 타입으로 설정해준다.
  const todoTextInputRef = useRef<HTMLInputElement>(null);

  // form 에서 주어지는 매개변수이므로 FormEvent의 타입으로 설정해준다.
  const submitHandler = (event: React.FormEvent) => {
    event.preventDefault();
    const enteredText = todoTextInputRef.current!.value;
  };
  return (
    <form onSubmit={submitHandler}>
      <input type='text' ref={todoTextInputRef} />
      <button>Add Todo</button>
    </form>
  );
};

export default NewTodo;

코드 설명

• useRef() 의 타입을 제너릭으로 설정할 수 있다. 여기서는 input에서 입력된 값이 들어갈 예정이므로 HTMLInputElement 의 제너릭 타입으로 설정한다.

• form이 submit 될 때 submitHandler() 함수가 실행된다. 여기서 들어오는 event 매개변수의 타입은 React.FormEvent 으로 설정해준다.

• const enteredText = todoTextInputRef.current!.value 위는 사용자의 입력값을 받아오는 코드이다. 우리가 useRef() 의 초기값을 null로 설정했기 때문에 타입스크립트는 value의 존재를 확신하지 못한다. 하지만 useRef() 와 input이 연결된 시점에는 value가 무조건 존재한다. (값을 입력하지 않아도 빈 문자열로 존재한다.) 따라서 물음표 대신 느낌표를 사용해서 타입스크립트에게 확신을 심어줄 수 있다.

강의 링크

변수

const a: any = 'a'; 

any는 모든 타입을 허용한다는 뜻이다. any를 사용하면 굳이 타입스크립트를 쓰는 이유가 없어지므로 웬만하면 사용하지 않는다. ( 자바스크립트는 모든 변수/함수의 타입이 any인 타입스크립트이다. )

아래와 같이 변수의 타입을 지정해줄 수 있다.

const b:string = 'b'
const c:number = 1
const d = 's' // 초기값을 지정해줄 경우 타입 명시할 필요 X

// readonly - 읽기 전용 (값을 바꿀 수 X)
const foods: readonly string[] = ['삼겹살', '피자'];

// unknown - 값에 뭐가 들어올지 모를 때
// 이후에 값이 들어오더라도 사용할 때마다 타입을 검사해줘야 하므로 any보다 안전한 타입이다.
let num: unknown;
num = 2;

if (typeof num === 'number') {
  let a = num + 1;
}

Tip

타입스크립트에는 타입 추론 기능이 있으므로 초기값을 지정해줄 경우 굳이 타입을 명시해주지 않아도 된다.

함수

함수는 매개변수와 리턴값의 타입을 명시해준다.

function plus(a: number, b: number): number {
  return a + b;
}

function print(a: string): void {
  console.log(a);
}

function _error(): never { // 항상 오류를 출력하거나 무한루프 등으로 
  throw new Error(); // 리턴값을 절대로 내보내지 않을 함수에 never 사용
}

type

type은 타입스크립트에서 가장 많이 사용하는 문법으로 타입 정의의 역할을 한다.

type S = string;
const a: S = 'abc';

Union 타입으로 사용할 수도 있다.

type Food = 'pasta' | 'pizza' // pasta or pizza 
const food:Food = 'pasta' // 자동완성 기능을 제공해준다.

type array = number[]; // number로 이루어진 리스트
const b: array = [1, 2, 3];

interface

type 만으로 모든 타입을 정의할 수 있다. 그러나 interface는 딕셔너리와 클래스를 표현할 때 더욱 편하게 사용할 수 있다. 객체지향 프로그래밍처럼 상속의 기능도 지원한다.

interface Dict {
  [key: string]: number; // 키의 개수 제한 X
}

const dict: Dict = {
  a: 1,
  b: 2,
  c: 3,
};

interface Person {
  name: string;
  age: number;
  weight?:number; // 있어도 없어도 되는 키는 옆에 ?를 붙여준다.
}

const a: Person = {
  name: '김범서',
  age: 19,
};

interface Person {
  name: string;
  age: number;
  weight?: number;
}

interface Korean extends Person { // Person을 상속받음
  favoriteFood: '순대국' | '삼겹살';
}

const a: Korean = {
  name: '김범서',
  age: 19,
  favoriteFood: '삼겹살',
};

위의 Korean interface를 type으로 선언하면 다음과 같다.

type Korean = Person & {
  favoriteFood: '순대국' | '삼겹살';
};

interface가 더 직관적이다.

클래스

접근제어자

타입스크립트의 class 접근제어자

private - 자기 자신 클래스에서만 호출 가능 protected - 자기 자신, 자기를 상속하는 클래스에서 호출 가능 public - 클래스 밖에서도 호출 가능

초기화

타입스크립트에서는 클래스를 더 쉽게 초기화할 수 있다.

일반 자바스크립트

class Person {
  constructor(firstName, lastName, nickName) {
    this.firstName = firstName;
    this.lastName = lastName;
    this.nickName = nickName;
  }
}

타입스크립트

class Person { 
  constructor( // 매개변수 자리에 접근제어자와 타입을 적어주면 알아서 초기화 됨
    protected firstName: string,
    protected lastName: string,
    protected nickName: string
  ) {}
}

추상 클래스

타입스크립트에서도 추상 클래스를 선언할 수 있다.

abstract class Person {
    constructor(
        protected name:string,
        protected age:number
    ){}
    abstract sayHi(name:string):string
    abstract getName():string
}

class Korean extends Person{ // 추상 클래스 Person을 상속 받음
    sayHi(name:string){
        return `${name}야, 밥 먹었냐?`
    }
    getName(){
        return this.name
    }
}

위의 추상 클래스를 interface로 대체할 수도 있다.

interface Person{
    name:string;
    age:number;
    sayHi(name:string):string;
    getName():string;
}

class Korean implements Person{
    constructor(
        public name:string,
        public age:number
    ){}
    sayHi(name:string){
        return `${name}야, 밥 먹었냐?`
    }
    getName(){
        return this.name
    }
}

🧩 색인

1부터 10까지 적힌 10개의 카드가 있다. 이 카드들이 무작위로 섞인 채 뒤집혀있다면 원하는 숫자를 찾을 때까지 하나하나 확인해 봐야 한다. 그래도 다행히 카드가 10개 밖에 없기 때문에 운이 나빠도 10번만에 원하는 숫자가 적힌 카드를 손에 넣을 것이다.

그러나 카드의 개수가 100개, 1000개, 10000개 까지 늘어난다면 하나하나 확인하기에는 너무 오래걸린다. 데이터를 카드에 빗대어 생각해보면 엄청나게 많은 데이터가 축적되어있는 데이터베이스에서 원하는 데이터를 찾아내는 일은 자료구조와 알고리즘의 핵심 역할 중 하나다. 이때 나중에 데이터를 잘 찾을 수 있도록 색인을 만드는 작업이 중요하다.

배열에 키를 정렬시키는 것이 가장 생각하기 쉬운 자료구조다. 만약 카드가 정렬되어 있었다면 원하는 카드를 찾는 시간은 평균 O(Log_N) 밖에 걸리지 않았을 것이다. 하지만 배열은 삽입과 삭제 시 평균 O(N) 의 시간이 소요되는 큰 단점을 가지고 있다. 이진 검색 트리는 이보다 개선된 저장 방법으로 검색, 삽입, 삭제 연산에 평균 O(Log_N)의 시간이 소요된다. 물론 운이 나쁘면 아주 비효율적일 수도 있다.

🧩 검색 트리의 활용

위에서 다뤘듯이 배열 자료구조는 검색에 특화되어있지만 삽입, 삭제 연산은 비효율적이다.

따라서 이진 검색 트리가 검색, 삽입, 삭제의 연산을 수행하는데 더 효율적인 자료구조라고 생각할 수 있다. 도서관에서 책을 검색하거나 학교에서 학생에 대한 정보를 저장하는 등 대량의 정보를 저장하고 검색할 때 이진 검색 트리가 활용되고 있다.

🧩 검색 트리의 종류

현재 가장 유명한 검색트리는 위의 5가지다. 오늘은 이 중 이진 검색트리와 AVL 트리를 다룬다. 먼저 위의 표에 대한 설명이다.

📌 이진 트리 && 다진 트리

한 노드가 칠 수 있는 가지의 수가 최대 2개인 트리를 이진 트리라고 한다. 반면에 다진 트리는 가지를 3개 이상 칠 수 있는 트리를 뜻한다. 용어가 헷갈릴 수 있는데 위의 이진 검색 트리가 가장 기본적인 이진 검색 트리이고 AVL 트리, 레드-블랙 트리가 더 발전된 이진 검색 트리라고 생각하면 된다.

📌 균형 검색 트리

이진 검색 트리는 검색할 때 이진 탐색 알고리즘을 사용한다. 그러나 만약 트리가 불균형하게 한쪽으로만 치우쳐져 있다면 검색 연산을 수행하는 평균 시간이 O(Log_N) 에서 점점 O(N) 으로 늘어날 것이다. 불균형한 트리가 스스로 균형을 맞추도록 만들어진 트리를 균형 검색 트리라고 한다.

📌 검색 위치

대부분의 트리는 컴퓨터가 RAM에 불러온 뒤 연산을 실행한다. 하지만 트리의 용량이 RAM을 초과한다면 불가피하게 하드 디스크 같은 외장 메모리에 넣어두고 사용해야 한다. B-트리는 이러한 연산을 위해 만들어진 자료구조이다.

🧩 이진 검색 트리의 특징

이진 검색 트리는 다음과 같은 특징이 있다.

• 각 노드의 왼쪽 자식 노드의 키는 오른쪽 자식 노드의 키보다 작다.

• 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.
• 중복된 키를 허용하지 않는다.

이진 검색 트리의 모습

또 이진 검색트리는 왼쪽 자식 < 자신 < 오른쪽 자식 의 크기를 따르므로 중위 순회를 했을 때 정렬되어 출력되는 특징이있다.

🧩 이진 검색 트리 (기본)

검색 트리의 주요 연산은 검색, 삽입, 삭제다.

📌 검색 (Search)

먼저 검색의 경우 이진 탐색 알고리즘을 사용할 수 있으므로 평균 O(Log_N) 의 시간이 걸린다. 하지만 기본적인 이진 검색 트리의 경우 아래와 같이 가지가 치우치면 최악의 경우 O(N) 의 시간이 소요된다.

📌 삽입 (Insert)

삽입은 검색과 비슷하다. 검색 연산처럼 키의 자리를 찾은 뒤 노드를 추가해주기만 하면 된다. 따라서 평균 O(Log_N), 최악의 경우 O(N) 의 시간이 소요된다.

📌 삭제 (Delete)

삭제는 검색이나 삽입보다 조금 더 복잡한 연산이 필요하다. 삭제 후에도 이진 검색 트리의 속성이 깨지면 안되기 때문에 그 자리를 대신할 노드를 찾고 바꿔주는데 시간이 소요된다. 삭제 연산은 당연히 검색, 삽입 연산보다 시간이 더 걸리지만 BigO 계산법으로 보면 똑같이 평균 O(Log_N), 최악의 경우 O(N) 의 시간이 소요된다.

📌 정리

기본 이진 검색 트리에 대해 정리해보면 다음과 같다.

📌 코드 구현 (Python)

node.py

각각의 노드는 item, left, right 의 멤버 변수를 갖는다.

class Node:
    def __init__(self, new_item, left, right):
        self.item = new_item
        self.left = left
        self.right = right

tree.py

from node import Node


class Tree:
    def __init__(self):
        self.__root = None
        self.__count = 0

    ## 같은 함수가 여러개인 이유
    ## 사용자는 매개변수로 찾고 싶은 값만 넣으면 된다.
    ## 하지만 재귀함수를 구현하려면 부모의 정보를 매개변수로 받아야 한다.

    # 검색
    def search(self, x) -> Node:
        return self.__search_item(self.__root, x)

    def __search_item(self, node: Node, x) -> Node:
        if node == None:
            return None
        elif x == node.item:
            return node
        elif x < node.item:
            return self.__search_item(node.left, x)
        else:
            return self.__search_item(node.right, x)

    # 삽입
    def insert(self, new_item):
        self.__root = self.__insert_item(self.__root, new_item)

    def __insert_item(self, node: Node, new_item) -> Node:
        if node == None:
            node = Node(new_item, None, None)
            self.__count += 1
        elif new_item < node.item:
            node.left = self.__insert_item(node.left, new_item)  # 왼쪽 가지
        elif new_item > node.item:
            node.right = self.__insert_item(node.right, new_item)  # 오른쪽 가지
        else:  # 중복되는 값 (x == node.item)
            print(f"{node.item}은(는) 중복되는 키이므로 insert 연산을 수행할 수 없습니다")
        return node

    # 삭제
    def delete(self, x):
        pre_cnt = self.__count
        self.__root = self.__delete_item(self.__root, x)
        if pre_cnt == self.__count:  # 이전 노드 개수랑 연산 후 노드 개수가 같으면
            print(f"{x}은(는) 존재하지 않는 키입니다!")

    def __delete_item(self, node: Node, x) -> Node:
        if node == None:  # item not found
            return None
        elif x == node.item:  # item found
            node = self.__delete_node(node)
            self.__count -= 1
        elif x < node.item:
            node.left = self.__delete_item(node.left, x)
        else:
            node.right = self.__delete_item(node.right, x)
        return node

    def __delete_node(self, node: Node) -> Node:
        if node.left == None and node.right == None:  # case 1(자식이 없음)
            return None
        elif node.left == None:  # case 2(오른쪽 자식만 있으면)
            return node.right
        elif node.right == None:  # case 2(왼쪽 자식만 있으면)
            return node.left
        else:  # case 3(두 자식 다 있으면)
            (item, r_node) = self.__delete_min_item(node.right)
            node.item = item
            node.right = r_node
            return node

    def __delete_min_item(self, node: Node) -> tuple:
        if node.left == None:  # 최솟값 노드를 찾음
            return (node.item, node.right)
        else:
            (item, r_node) = self.__delete_min_item(node.left)
            node.left = r_node
            return (item, node)

    # 빈 트리인지 확인
    def isEmpty(self) -> bool:
        return self.__root == None

    # 트리의 내용을 없앰
    def clear(self):
        self.__root = None

    # root를 반환
    def get_root(self):
        return self.__root

    # 노드의 개수를 반환
    def count(self):
        return self.__count

검색, 삽입, 삭제 연산 외에 isEmpty(), clear(), get_root(), count() 함수를 추가로 만들었다.

🧩 AVL 검색 트리

위에서 보았듯 일반적인 이진 검색 트리는 최악의 경우(트리의 균형이 치우쳐진 경우) 소요시간이 O(N) 에 가까워진다. AVL 검색 트리는 이같은 단점을 보완한 트리로 삽입과 삭제시 균형을 잡는 연산을 추가로 수행한다.

📌 검색 (Search)

검색 알고리즘은 위와 동일하게 이진 탐색을 사용한다. 그러나 AVL 트리는 항상 균형을 유지하고 있기 때문에 언제나 O(Log_N) 의 시간이 소요된다.

📌 삽입 (Insert)

삽입, 삭제 연산은 위에서 했던 것과 같다. 하지만 AVL 트리는 항상 균형을 유지하고 있어야하기 때문에 삽입, 삭제 직후 균형을 잡는 연산을 추가로 수행한다. 기본 이진 검색 트리보다는 오래 걸리긴 하지만 그래도 O(Log_N) 의 효율적인 속도를 보여준다.

📌 삭제 (Delete)

삽입 연산 시 깊이가 깊어져서 균형이 깨질 수 있다. 이때는 한번만 균형을 잡아주면 문제가 쉽게 해결된다. 하지만 삭제 연산은 깊이가 얕아져서 균형이 깨지는데, 균형을 잡아주는 과정에서 상위 트리까지 재귀적으로 균형이 깨질 수 있다. 그러나 삭제 연산 같은 경우에도 연산 시간은 O(Log_N) 으로 효율적인 속도를 보여준다.

📌 정리

AVL 트리에 대해 정리해보면 다음과 같다.

📌 코드 구현 (Python)

node.py

균형을 체크할 때마다 높이를 계산하면 수행 시간이 너무 길어진다. 그러므로 높이를 담을 height 멤버 변수를 추가했다.

class Node:
    def __init__(self, new_item, left, right, height):
        self.item = new_item
        self.left = left
        self.right = right
        self.height = height

from node import Node


class Tree:
    def __init__(self):
        self.__NIL = Node(None, None, None, 0)  # left = None, right = None 대신 참조할 노드
        self.__root = self.__NIL
        self.__count = 0  # 노드의 개수

        # 식별용 변수
        self.LL = 1
        self.LR = 2
        self.RR = 3
        self.RL = 4
        self.NO_NEED = 0
        self.ILLEGAL = -1

    # 검색
    def search(self, x):
        res = self.__search_item(self.__root, x)
        if res != self.__NIL:
            return res
        else:
            print(f"{x}은(는) 존재하지 않는 키입니다!")
            return None

    def __search_item(self, node: Node, x) -> Node:
        if node == self.__NIL:  # 없는 노드면
            return self.__NIL
        elif x == node.item:
            return node
        elif x < node.item:
            return self.__search_item(node.left, x)
        else:
            return self.__search_item(node.right, x)

    def insert(self, x):
        self.__root = self.__insert_item(self.__root, x)

    def __insert_item(self, node: Node, x) -> Node:
        if node == self.__NIL:
            node = Node(x, self.__NIL, self.__NIL, 1)
            self.__count += 1
        elif x < node.item:  # 왼쪽 가지로
            node.left = self.__insert_item(node.left, x)
            node.height = 1 + max(node.right.height, node.left.height)
            type = self.__check_balance(node)  # 수선할 AVL 타입 체크 (LL,LR,RR,RL)
            if type != self.NO_NEED:
                node = self.__balance_avl(node, type)
        elif x > node.item:  # 오른쪽 가지로
            node.right = self.__insert_item(node.right, x)
            node.height = 1 + max(node.right.height, node.left.height)
            type = self.__check_balance(node)  # 수선할 AVL 타입 체크 (LL,LR,RR,RL)
            if type != self.NO_NEED:
                node = self.__balance_avl(node, type)
        else:  # 중복되는 값 (x == node.item)
            print(f"{node.item}은(는) 중복되는 키이므로 insert 연산을 수행할 수 없습니다")
        return node

    def delete(self, x):
        pre_cnt = self.__count
        self.__root = self.__delete_item(self.__root, x)
        if pre_cnt == self.__count:  # 이전 노드 개수랑 연산 후 노드 개수가 같으면
            print(f"{x}은(는) 존재하지 않는 키입니다!")

    def __delete_item(self, node: Node, x) -> Node:
        if node == self.__NIL:
            return self.__NIL  # Item not found!
        if x == node.item:
            node = self.__delete_node(node)
            self.__count -= 1
        elif x < node.item:  # 왼쪽 가지로
            node.left = self.__delete_item(node.left, x)
            node.height = 1 + max(node.right.height, node.left.height)
            type = self.__check_balance(node)  # 수선할 AVL 타입 체크 (LL,LR,RR,RL)
            if type != self.NO_NEED:
                node = self.__balance_avl(node, type)
        else:  # 오른쪽 가지로
            node.right = self.__delete_item(node.right, x)
            node.height = 1 + max(node.right.height, node.left.height)
            type = self.__check_balance(node)  # 수선할 AVL 타입 체크 (LL,LR,RR,RL)
            if type != self.NO_NEED:
                node = self.__balance_avl(node, type)
        return node

    def __delete_node(self, node: Node) -> Node:
        if node.left == self.__NIL and node.right == self.__NIL:  # case 1(자식이 없음)
            return self.__NIL
        elif node.left == self.__NIL:  # case 2(오른자식뿐)
            return node.right
        elif node.right == self.__NIL:  # case 2(왼자식뿐)
            return node.left
        else:  # case 3(두 자식이 다 있음)
            (item, R_node) = self.__delete_min_item(node.right)
            node.item = item
            node.right = R_node
            node.height = self.__height(node)
            type = self.__check_balance(node)
            if type != self.NO_NEED:
                node = self.__balance_avl(node, type)
            return node

    def __delete_min_item(self, node: Node) -> tuple:
        if node.left == self.__NIL:  # 찾음
            return (node.item, node.right)

        (item, L_node) = self.__delete_min_item(node.left)
        node.left = L_node
        node.height = self.__height(node)
        type = self.__check_balance(node)
        if type != self.NO_NEED:
            node = self.__balance_avl(node, type)
        return (node, item)

    # 균형 잡기
    def __balance_avl(self, node: Node, type: int) -> Node:
        return_node = self.__NIL
        if type == self.LL:
            return_node = self.__right_rotate(node)  ## LL이면 우회전 한번
        elif type == self.LR:
            node.left = self.__left_rotate(node.left)
            return_node = self.__right_rotate(node)  ## LR이면 좌회전 한번, 우회전 한번
        elif type == self.RR:
            return_node = self.__left_rotate(node)  ## RR이면 좌회전 한번
        elif type == self.RL:
            node.right = self.__right_rotate(node.right)
            return_node = self.__left_rotate(node)  ## RL이면 우회전 한번, 좌회전 한번
        else:
            print("Imposible type! Should be one of LL,LR,RR,RL")

        return return_node

    # 좌회전
    def __left_rotate(self, node: Node) -> Node:
        R_child: Node = node.right
        if R_child == self.__NIL:
            raise Exception(node.item + "'s RChild shouldn't be NIL!")  # 논리 오류
        RL_child = R_child.left
        R_child.left = node
        node.right = RL_child
        node.height = 1 + max(node.left.height, node.right.height)
        R_child.height = 1 + max(R_child.left.height, R_child.right.height)
        return R_child

    # 우회전
    def __right_rotate(self, node: Node) -> Node:
        L_child: Node = node.left
        if L_child == self.__NIL:
            raise Exception(node.item + "'s RChild shouldn't be NIL!")  # 논리 오류
        LR_child = L_child.right
        L_child.right = node
        node.left = LR_child
        node.height = 1 + max(node.left.height, node.right.height)
        L_child.height = 1 + max(L_child.left.height, L_child.right.height)
        return L_child

    # 필요한 수선을 체크 후 반환 (LL,LR,RR,RL)
    def __check_balance(self, node: Node) -> int:
        type = self.ILLEGAL

        if node.left.height >= node.right.height + 2:  # L 유형
            if node.left.left.height >= node.left.right.height:
                type = self.LL
            else:
                type = self.LR
        elif node.right.height >= node.left.height + 2:  # R 유형
            if node.right.right.height >= node.right.left.height:
                type = self.RR
            else:
                type = self.RL
        else:
            type = self.NO_NEED
        return type

    # 노드의 높이
    def __height(self, node: Node) -> int:
        return 1 + max(node.left.height, node.right.height)

    def is_empty(self) -> bool:
        return self.__root == self.__NIL

    def clear(self):
        self.__root = self.__NIL

    def get_root(self):
        return self.__root

    # 전위순회
    def pre_order(self, node: Node):
        if node != self.__NIL:
            print(node.item)
            self.pre_order(node.left)
            self.pre_order(node.right)

    # 중위순회
    def in_order(self, node: Node):
        if node != self.__NIL:
            self.in_order(node.left)
            print(node.item)
            self.in_order(node.right)

    # 후위순회
    def post_order(self, node: Node):
        if node != self.__NIL:
            self.post_order(node.left)
            self.post_order(node.right)
            print(node.item)

    def count(self) -> int:
        return self.__count

react-router-dom 은 리액트 앱 내에서 부드러운 페이지 이동을 구현하게 해주는 라이브러리이다. 이를 응용해서 Pagination 기능을 만들어보았다.

Pagination은 많은 목록을 여러 페이지로 나누어서 정렬하는 기법이다.

📌 완성된 모습

📌 구현한 기능

• 한 페이지에 최대 5개의 목록을 표시한다.

• 숫자를 누르면 해당하는 목록을 표시한다. (숫자는 한 페이지 최대 5개)
• Start - 1 페이지로 이동
• Prev - 한 페이지 전으로 이동
• Next - 한 페이지 뒤로 이동
• End - 끝 페이지로 이동
• 숫자 1이 목록에 있으면 Start 버튼을 비활성화한다.
• 마지막 페이지에 해당하는 숫자가 목록에 있으면 End 버튼을 비활성화한다.
• 이전 페이지가 없으면 Prev 버튼을 비활성화한다.
• 다음 페이지가 없으면 Next 버튼을 비활성화한다.

🧩 Pagination 에 필요한 함수 만들기

📌 makePagination()

Pagination 기능을 구현하기 위해서 makePagination() 함수를 만들었다.

🧷 매개변수

🧷 반환 값

🧷 함수 본문

use-pagination.js

📌 usePagination()

다른 페이지에서도 로직을 재사용할 수 있게 커스텀 hook인 usePagination() 함수를 만들었다. 위에서 만든 makePagination() 함수의 반환값에 페이지 상태 함수와 페이지 이동 함수를 더해서 리턴해준다.

🧷 페이지 이동 함수

🧷 함수 본문

🧩 페이지에 렌더링하기

📌 QuoteList.js

QuoteList.js 에서는 다음과 같은 역할을 수행한다. (prop 으로 목록(quote) 전체를 받아온다.)

1. url에 표시된 페이지 정보를 받아온다.
   
2. prop으로 받아온 목록의 길이와 현재 페이지 정보를 usePagination() 함수에 매개변수로 넘겨서 리턴값들을 받아온다.
   
3. 사용자가 페이지를 이동하면 그에 따라서 실제 페이지를 이동시킨다. (useEffect() 활용)
   
4. 현재 페이지의 정보를 활용해서 해당 목록들을 화면에 렌더링한다. (페이지가 목록의 범위를 벗어나면 PageNotFound 컴포넌트를 리턴한다.
   
5. usePagination() 에서 받아온 값들을 Pagination 컴포넌트에 prop 으로 넘긴다. (페이지 리모컨은 Pagination 컴포넌트에서 렌더링한다.)

🧷 1. url에 표시된 페이지 정보 받아오기

page 쿼리의 값은 useLocation() 함수로 손쉽게 받아올 수 있다.

import { useLocation } from 'react-router-dom';

const location = useLocation();
const queryParams = new URLSearchParams(location.search);

이제 queryParams.get('page') 함수로 현재 페이지를 받아올 수 있다.

🧷 2. usePagination() 함수 사용하기

prop 으로 받아온 목록의 길이와 페이지 정보를 usePagination() 함수의 매개변수로 넘긴다.

import usePagination from '../../hooks/use-pagination';

 const {
    thisPage,
    setThisPage,
    goStart,
    goPrev,
    goNext,
    goEnd,
    startRange,
    endRange,
    lastPage,
    startIdx,
    lastIdx,
    showStartBtn,
    showEndBtn,
    pageNotFound,
  } = usePagination(
    props.quotes.length, // 목록의 길이
    5,                      // 숫자 목록에 나타낼 숫자의 범위 
    Number(queryParams.get('page')) || 1 // 현재 페이지 (없으면 1)
  );

🧷 3. 페이지 변경을 실제로 적용하기

사용자가 페이지를 이동하면 usePagination() 의 thisPage state 가 변경된다. useEffect() 함수로 thisPage 가 변경되는 것을 감지하면 useNavigate() 를 사용해서 실제로 페이지를 이동시킨다.

import { useEffect } from 'react';
import { createSearchParams, useNavigate } from 'react-router-dom';

const navigate = useNavigate();
// useLocation() 에서 현재 url을 받아옴 (쿼리 값 제외)
const { pathname } = location;  

// thisPage 가 변경되면 useEffect() 함수를 실행 (나머지는 종속 변수)
useEffect(() => {
    navigate({
      pathname: pathname,
      search: `?${createSearchParams({
        page: thisPage,
      })}`,
    });
  }, [navigate, thisPage, isSortingAscending, pathname]);

🧷 4. 현재 페이지에 해당하는 목록 렌더링하기

만약 현재 페이지가 목록의 범위를 벗어날 경우 PageNotFound 컴포넌트를 리턴한다. 이를 위해 목록을 렌더링하기 전 if 문으로 한번 확인해준다. (범위가 벗어난 지 확인하는 값은 usePagination() 함수에서 받아왔다.)

이제 usePagination() 에서 받아온 startIdx, lastIdx 값을 slice() 함수의 인자로 넣어준다. (간단한 기능이므로 다른 건 생략하겠다.)

5. Pagination 컴포넌트에 prop 넘기기

페이지 리모컨 기능은 Pagination 컴포넌트에서 구현할 것이므로 필요한 기능들을 prop 으로 넘겨준다.

사용자가 버튼을 누르지 않고 숫자를 직접 눌러서 페이지를 이동할 수 있게 onChangePage() 함수를 추가로 생성한다.

📌 Pagination.js

Pagination.js 에서는 페이지 리모컨을 생성한다.
필요한 모든 정보와 기능을 prop 으로 받아왔기 때문에 이제 간단히 구현할 수 있다.

🧷 버튼 표시하기

Start Prev Next End 버튼을 표시하는 코드이다. (실제로는 숫자 양옆에 표시한다.)

비활성 여부를 결정하기 위해 disabled prop 에 간단한 로직을 추가했다.

🧷 숫자 목록 표시하기

사용자가 숫자를 눌러서 페이지를 이동할 수 있게 해주는 숫자 목록이다.

prop 으로 받아온 startRange 와 endRange 를 사용해서 리스트를 만들어준다. 만약 현재 페이지가 3페이지면 pages 변수에는 [1,2,3,4,5] 의 값이 들어간다.

이제 생성한 리스트와 map() 메소드를 이용해서 숫자를 렌더링하면 끝이다. ( 현재 페이지에 해당하는 숫자의 색을 다르게 하기 위해서 className prop 에 로직을 추가했다. )

📌 완성된 모습

🧩 마치며

예전에 django 동영상 강의를 보면서 Pagination 기능을 만들어본 적이 있었지만 혼자서 구현해보니 아예 다른 느낌이었다. 어떤 식으로 코드를 짜야할지 처음 설계할 때 부터 많은 고민을 했고 결국에는 커스텀 훅으로 기능을 구현했지만 잘 한건지 아직도 모르겠다.

하지만 이번 프로젝트를 진행하며 확실히 느낀 점은 기능을 구현하는 것보다 useMemo() / useCallback() 으로 앱을 최적화하는 것이 더 어렵다는 점이다. (중간에 시도했다가 결국 다 없애버렸다.)

코드 최적화에 대해 더 공부해야겠다. ^^

끝.