[AI 부트캠프] DAY 41 - 코딩 테스트 2

[오늘의 일지]

코딩 테스트 - 해시테이블, 재귀, 트리, 그래프 공부하기

[상세 내용]

코딩 테스트 사전 지식

해시테이블

- 해시 테이블(Hash Table), 또는 해시 맵(Hash Map)은 데이터를 효율적으로 저장하고 검색하기 위한 자료구조 중 하나입니다. 해시 테이블은 키(key)와 값(value)의 쌍을 저장하는 데 사용되며, 키를 사용하여 값을 빠르게 검색할 수 있습니다. 해시 테이블은 데이터를 빠르게 검색하고 삽입하는 데 뛰어난 자료구조이며, 많은 프로그래밍 언어와 라이브러리에서 제공됩니다.

 

출처:https://www.tutorialspoint.com/data_structures_algorithms/hash_data_structure.htm

 

재귀

- 재귀(Recursion)란, 어떤 문제를 해결하는 과정에서 그 문제 자체를 해결하기 위해 동일한 방법이나 함수를 반복적으로 호출하는 프로그래밍 기법입니다. 이러한 재귀 호출은 보통 문제를 더 작은 하위 문제로 분할하고, 기본 사례(base case)에서 재귀 호출을 종료하는 방식으로 작동합니다. 이것은 프로그램의 논리를 보다 간결하게 나타내고, 일부 문제를 보다 쉽게 해결할 수 있게 도와줍니다. 수업시간에도 나온 예시지만 이해하기 가장 쉬운 예시가 팩토리얼입니다. 그림을 보면 왜 그런지 알 수 있습니다.

 

출처:https://studyalgorithms.com/theory/recursion-and-memory-vizualization/

 

트리

- 트리(Tree)는 그래프 이론에서 파생된 데이터 구조로, 계층적인 구조를 나타내기 위해 사용됩니다. 트리는 노드(node)들의 모음으로, 이러한 노드들은 부모(parent)와 자식(children) 관계로 연결되어 있습니다. 트리는 계층적인 데이터를 표현하기 위한 자료구조로 주로 사용되며, 컴퓨터 과학 및 알고리즘에서 다양한 응용 분야에 활용됩니다. 예를 들어, 파일 시스템, 데이터베이스 인덱스, 계층 구조적인 데이터 모델, 그래프 알고리즘, 정렬 알고리즘 등에서 트리가 중요하게 사용됩니다.

 

출처:https://subscription.packtpub.com/book/programming/9781788623872/10/ch10lvl1sec62/tree-terminology

 

그래프

- 사실 그래프는 자료구조나 알고리즘의 측면에서 바라보면 여러 가지 종류들과 정의들은 다 설명하고 넘어가야 되는 게 맞지만 지금은 초점이 코딩 테스트에서 주로 사용하는 개념만 간단하게 알아보고 넘어가는 것이 좋을 거 같습니다.  그래프의 종류에는 방향이 없는 무향 그래프와 방향이 있는 방향 그래프가 있는데 코딩 테스트에서는 주로 무향 그래프를 다룹니다. 그리고 단순 그래프와 다중 그래프라는 개념이 있는데 코딩 테스트에서는 주로 단순 그래프만 다루는 것으로 알고 있습니다. 이 두 그래프의 차이는 indegree, outdegree를 하나씩만 사용하는 것을 단순으로 여러 개를 사용하는 것을 다중으로 말하고 있습니다. 아래는 단순과 다중의 그래프를 표현한 그림입니다. 마지막으로 가중치라는 것이 있는데 코딩 테스트 심화 과정에서 나올 예정이라고 합니다.

 

출처:https://mathworld.wolfram.com/SimpleGraph.html

 

그래프의 구현

- 인접 그래프에서 인접 리스트와 인접 행렬 구현 가능합니다.

출처:https://algorithmtutor.com/Data-Structures/Graph/Graph-Representation-Adjacency-List-and-Matrix/

 

그래프의 순회

- DFS : 깊이 우선 탐색(DFS, Depth-First Search)은 그래프나 트리 등의 자료구조에서 사용되는 탐색 알고리즘 중 하나로, 시작 노드에서부터 시작하여 한 경로를 따라 더 이상 탐색할 노드가 없을 때까지 탐색을 진행하고, 그 후 다음 경로로 넘어가는 방식입니다. DFS는 더 이상 탐색할 노드가 없을 때까지 깊이를 우선적으로 탐색하며, 이후 다시 돌아와 다른 경로로 탐색을 계속합니다. DFS엔 전위 순회, 중위 순회, 후위 순회라는 것이 있는데 아래의 사진을 보면 이해하기 쉽습니다. 

 

- BFS : 너비 우선 탐색(BFS, Breadth-First Search)은 그래프나 트리와 같은 자료구조에서 사용되는 탐색 알고리즘 중 하나로, 시작 노드로부터 출발하여 인접한 노드를 먼저 모두 탐색한 후에, 그 인접한 노드들을 기반으로 더 멀리 있는 노드들을 탐색하는 방식입니다. 즉, 같은 레벨의 노드들을 모두 방문한 후 다음 레벨의 노드로 넘어가는 방식입니다.

 

출처:https://zhang-xiao-mu.blog/2019/01/20/tree-traversal-preorder-postorder/

 

- 라이브러리처럼 사용하는 DFS 코드

# 명시적 그래프에서 사용
def dfs(cur_v):
    visited[cur_v] = True
    for next_v in graph[cur_v]:
        if next_v not in visited:
            dfs(next_v)

visited = {}
graph = {...}
dfs(0)

# 암시적 그래프에서 사용
def dfs(r, c):
    visited[r][c] = True

    dr = [0, 1, 0, -1]
    dc = [1, 0, -1, 0]
    for i in range(4):
        next_r = r + dr[i]
        next_c = c + dc[i]
        if 0 <= next_r < row_len and 0 <= next_c < col_len:
            if grid[next_r][next_c] == 1:
                if not visited[next_r][next_c]:
                    dfs(next_r, next_c)

grid = [...]
row_len, col_len = len(grid), len(grid[0])
visited = [[False] * col_len for _ in range(row_len)]
dfs(0, 0)

 

- 라이브러리처럼 사용하는 BFS 코드

from collections import deque
# 명시적 그래프에서 사용
def bfs(graph, start_v):
    q = deque()
    q.append(start_v)
    visited = {start_v: True}


    while q:
        cur_v = q.popleft()
        for next_v in graph[cur_v]:
            if next_v not in visited:
                q.append(next_v)
                visited[next_v] = True
                
# 암시적 그래프에서 사용
def bfs(grid):
    def isValid(r, c):
        return (
            (r >= 0 and r < row_len)
            and (c >= 0 and c < col_len)
            and grid[next_r][next_c] == 1
        )
    row_len, col_len = len(grid), len(grid[0])
    visited = [[False] * col_len for _ in range(row_len)]
    dr = [0,  1,  1,  1,  0, -1, -1, -1]
    dc = [1,  1,  0, -1, -1, -1,  0,  1]

    queue = deque()
    queue.append(0, 0)
    visited[0][0] = True
    while queue:
        cur_r, cur_c = queue.popleft()
        for i in range(8):
            next_r = cur_r + dr[i]
            next_c = cur_c + dc[i]
            if isValid(next_r, next_c):
                if not visited[next_r][next_c]:
                    queue.append((next_r, next_c))
                    visited[next_r][next_c] = True

 

연습문제

- 해시테이블

Longest Consecutive Sequence - LeetCode

 

- 그래프

Keys and Rooms - LeetCode

 

[마무리]

 오늘은 어제에 이어서 코딩 테스트를 위한 중요한 개념들과 여러 가지 연습문제를 풀어보는 과정을 보냈습니다. 기본적으로 개념들이 알고리즘과 자료구조에 관한 부분이 많아서 가볍게 넘어갈 수도 없는 상황인데 코딩 테스트 문제들도 쉬운 것이 아니어서 적응하는데 오래 걸릴 것 같습니다. 그래도 긍정적으로 생각해 보면 이번에 큰 틀을 잡아놓으면 앞으로 혼자서 코딩 테스트를 할 때나 다른 사람들의 코드를 보면서 이해하는데 도움이 많이 될 것 같습니다.