알고리즘 1 (그래프, DFS)

1. 그래프

2. DFS

3. BFS(다음 글)

4. 백트레킹(다음 글)

5. 이진탐색(다음 글)

 

 

1. 그래프: 비선형 구조 중 연결 관계에 집중이 되어있는 자료구조

 

 

1-1 그래프 용어 정리

노드(Node): 연결 관계를 가진 각 데이터를 의미. 정점(Vertex)이라고도 함.

간선(Edge): 노드 간의 관계를 표시한 선.

인접 노드(Adjacent Node): 간선으로 직접 연결된 노드(또는 정점)

             C - D
             ⎜       
         B - A

A는 연결 관계를 가진 데이터, 노드
A와 B는 간선으로 연결됨
A와 C는 인접 노드

 

 

1-2 그래프의 종류

유방향 그래프(Directed Graph): 간선이 방향을 가짐. 간선은 단방향 관계를 나타내며, 각 간선은 한 방향으로만 진행함

무방향 그래프(Undirected Graph): 간선이 방향이 없음.

 

 

1-3 그래프 표현 방법

 

1) 인접 행렬(Adjacency Matrix): 2차원 배열로 그래프의 연결 관계를 표현

2) 인접 리스트(Adjacnecy List): 링크드 리스트로 그래프의 연결 관계를 표현

          2 - 3
          ⎜       
      0 - 1
(무방향 그래프)
1. 위의 그래프를 인접 행렬, 2차원 배열로 나타내면 아래와 같음
  0  1  2  3
0 X  O  X  X
1 O  X  O  X
2 X  O  X  O
3 X  X  O  X

배열로 표현하면
graph = [
    [False, True, False, False],
    [True, False, True, False],
    [False, True, False, True],
    [False, False, True, False]
]

2. 같은 그래프의 인접 리스트로 나타내면 아래와 같음
(인접 리스트는 모든 노드에 연결된 노드에 대한 정보를 차례대로 다음과 같이 저장)

0 -> 1
1 -> 0 -> 2
2 -> 1 -> 3
3 -> 2

이를 딕셔너리로 표현하면
graph = {
    0: [1],
    1: [0, 2]
    2: [1, 3]
    3: [2]
}

 

 

1-4 두 표현 방법의 차이점

인접 행렬(Adjacency Matrix): 즉각적으로 노드들이 연결되었는지 여부 BOOLEAN으로 바로 알 수 있음
하지만, 모든 조합의 연결 여부를 저장해야 되기 때문에 O(노드^2) 만큼의 공간을 사용함

인접 리스트(Adjacency List): 즉각적으로 연결되었는지 알 수 없고, 각 리스트를 돌아봐야 함
따라서 연결되었는지 여부를 알기 위해서 최대 O(간선) 만큼의 시간을 사용 함
대신 모든 조합의 연결 여부를 저장할 필요가 없으니  O(노드 + 간선) 만큼의 공간만 사용

즉 시간적 효율은 인접 행렬, 공간적 효율은 인접 리스트

 

 

 

2. DFS(깊이 우선 탐색), BFS(너비 우선 탐색)란: 자료의 검색, 트리나 그래프를 탐색하는 방법. (노드를 다 탐색해야 할 때)

 

 

2-1 DFS: 갈 수 있는 만큼 계속해서 탐색하다가 갈 수 없게 되면 다른 방향으로 다시 탐색하는 구조

- 노드를 방문하고 깊이 우선으로 인접한 노드를 방문
- 또 그 노드를 방문해서 깊이 우선으로 인접한 노드를 방문
- 만약 끝에 도달했다면 리턴

DFS 의 반복 방식은 방문하지 않은 원소를 계속해서 찾아가면 됨

즉, 
DFS(node) = node + DFS(node와 인접하지만 방문하지 않은 다른 node)
로 반복

방문 여부를 확인할 방도가 없기에
방문하지 않았다는 조건을 알기 위해 visited 라는 배열을 만들어 방문한 노드를 기록

1. 시작 노드를 정하고 여기에서 출발
2. 현재 방문한 노드를 visited 에 추가
3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드에 방문
4. 2부터 반복

# 위의 그래프를 예시로 삼아 인접 리스트 방식으로 표현
graph = {
    1: [2, 5, 9],
    2: [1, 3],
    3: [2, 4],
    4: [3],
    5: [1, 6, 8],
    6: [5, 7],
    7: [6],
    8: [5],
    9: [1, 10],
    10: [9]
}
visited = [] # 방문한 걸 저장하기 위한 배열

1. 탐색 시작 노드: 1

2. 현재 방문한 노드 1을 visited 에 추가 # visited -> [1]

3. 인접한 노드들인 [2, 5, 9] 에서 방문하지 않은 것들은 [2, 5, 9]이므로, 2 에 방문

4. 현재 방문한 노드인 2을 visited 에 추가 # visited -> [1, 2]

5. 인접한 노드들인 [1, 3] 에서 방문하지 않은 것들은 [3]이므로, 3에 방문

6. 현재 방문한 노드인 3을 visited 에 추가 # visited -> [1, 2, 3]

7. 인접한 노드들인 [2, 4] 에서 방문하지 않은 것들은 [4]이므로, 4에 방문

8. 현재 방문한 노드인 4을 visited 에 추가 # visited -> [1, 2, 3, 4]

9. 인접한 노드들인 [3] 에서 방문하지 않은 것들이 없음. 3로 돌아감

10. 인접한 노드들인 [2, 4] 에서 방문하지 않은 것들이 없음. 2로 돌아갑니다.

11. 인접한 노드들인 [1, 3] 에서 방문하지 않은 것들이 없음. 1로 돌아갑니다.

12. 인접한 노드들인 [2, 5, 9] 에서 방문하지 않은 것들은 [5, 9]이므로 5에 방문

.
.
.

 

DFS 코드 구현

#graph는 위를 참조

#재귀방식(함수안에서 자기자신을 부르는 방식)의 DFS
def dfs_recursive(graph, node, visited):
    # visited에 노드를 넣으면서 방문했다고 가정
    visited.append(node)

    # 인접 노드 방문
    for adj in graph[node]:
        #방문한 적이 없다면
        if adj not in visited:
            dfs_recursive(graph, adj, visited)

    return visited

#스택방식의 DFS
def dfs_stack(graph, start):
    visited = []
    # 방문할 순서를 담아두는 용도
    stack = [start]

    # 방문할 노드가 남아있는 한 아래 로직을 반복한다.
    while stack:
        # 제일 최근에 삽입된 노드를 꺼내고 방문처리한다.
        top = stack.pop()
        visited.append(top)
        # 인접 노드를 방문한다.
        for adj in graph[top]:
            if adj not in visited:
                stack.append(adj)

    return visited

 

 

DFS문제 예시: https://zhelddustmq.tistory.com/14

 

 

 

 

----------------------------------------------------------

나만의 필수암기노트

 

1. DBeaver, VS CODE, Pycharm 등 주석 처리하고 싶으면 그 줄을 드래그 후 Ctrl + /를 하면 됨

 

 

 

2. SQL정규식 함수 REGEXP

 

regexp : like 검색과는 달리 정규식을 이용한 검색 방식

regexp 를 이용한 검색의 예제

select * from test where name regexp '가'
--name 필드에 '가'를 포함한 모든 레코드를 출력
--(select * from test where name like '%가%') 의 쿼리와 동일

 

select * from test where name regexp '가|나|다|라'
--name 필드에 가,나,다,라 중 한개 이상을 포함한 레코드를 모두 출력한다.
--(select * from test where name like '%가%' or name like '%나%' or name like '%다%' or name like '%라%') 쿼리와 동일

 

select * from test where name regexp '[가-힇]'
--name 필드에 한글이 포함된 모든 레코드를 검색

 

select * from test where name regexp '^[가-힇]+$'
--name 필드에 한글로만 구성된 모든 레코드를 검색

 

--regexp 정규식 기호에 대한 간단한 소개
. : 문자 하나
* : 앞에 나온 문자의 0개 이상 
^ : 문자열의 처음
$ : 문자열의 끝
[.] : 괄호 안의 문자열 일치를 확인
{.} : 반복
| : 또는

• 참고사항
  정규식의 검색을 이용할때 절대 사용자에게 정규식 기능을 제공해선 안된다.
  각 종 오류를 포함할 수 있고 sql 인젝션에 취약해지기 때문에
  정규식의 검색을 개발자가 미리 정한 테두리 안에서 행해져야 함