파이썬 코딩테스트 공부하기 3편 - 알고리즘 기본이론 (자료구조) *

비전공자의 현란한 똥싸기를 해야할 듯한 상황 ㅎㅎ

하지만 해야한다 ㅎ

뭔가 잘못된것 같아도 그냥 내맘대로 정리할 필요성을 느끼는 이론 파트이다 

 

나중에 문제를 풀다보면 하나씩 고쳐지지 않을까 하는 대책없음으로 도전해보았다.

(다소 표현이 수학스러움 유의 ㅠ)

자료구조 (data structure)

데이터를 표현, 관리, 처리 하기 위한 구조

 

1. 스택 stack  - list

선입후출(First In Last Out)구조, 파이썬의 기본형중 하나인 list가 스택의 자료구조를 취하고 있는것 같다.

따라서 선언, 삽입, 삭제 등등 이용할 때 기본 함수를 이용하여 구현할 수 있는 자료구조이다.

 

삽입 - 리스트.append(내용)

삭제 - 리스트.pop()

뒤에 추가가 되고, 삭제도 뒤에서 하나씩 제거되는 모습 확인

 

 

2. 큐 Queue - list , deque

선입선출(First In First Out)구조

 

from collections import deque  # 이왕이면사용하자

deque로 변환 - 변수이름 = deque()

삽입 - 큐.append(내용)

삭제 - 큐.popleft()

다시리스트로 돌리기 - list(큐)

popleft 하나 쓰기위한 절차가 벌써머리가..ㅠ

 

 

3. deque - list

스택과 큐의 아이디어를 합친 유형이라고 한다. 말그대로 추가도 양쪽중에 원하는 방향으로, 삭제도 양쪽중에 원하는 방향으로 한다. 상황에 따라서는 필요할 듯하지만 아직은 모르겠다. 일단 이런게 있다는 정도만 알아두기로 했다.

 

 

그래프 Graph - Adjacency list, Adjacency matrix

 

 

node(=vertex), edge로 인접성(위상성)을 그린 추상화

예시1.

예시에서 왼쪽에 그림이 바로 그래프이다.

 

동그라미는 node 이며 동그라미 사이 연결한 선이 edge이다. 탐색해야할 지점이나 경로 등등을 최소한의 필요한 연결관계만 남긴채 지점과 지점사이에 연결선으로만 표현한 것이라고 생각하면 쉬울듯 하다. 수학에서는 이를 행렬로 표현하여 수학이 가진 여러 접근방식으로 그래프를 해석할 수 있는지 연구한것 같다.

 

오른쪽의 표는 노드 0,1,2 사이의 연결갯수를 표현한 표를 작성한 것이다. 이를 그대로 3*3 행렬로 표현하게 되면 이를 인접행렬이라고 한다.

 

- 표를 장성하는 방법은 다음과 같다

① 각 노드를 넘버링한 후에 노드의 갯수만큼 가로 세로 정사각 표를 그린다.

    (예시1의 왼쪽그림도 사실은 사용자가 직접 넘버링한 것이라고 생각하면 좋겠다)

    표의 가로 세로 같은 순서대로 노드넘버를 똑같이 쓴다. 

② 인접한 갯수만큼 써서 표의 내용을 채운다.

   가로2, 세로3 이 만나는 지점의 경우 노드2, 노드3사이를 직접 연결한(인접한)  edge의 갯수를 그대로 쓰면 된다.

   대각선을 기준으로 대칭이되는 표가 작성되어야 잘된것이다. 

③ 내용을 채울때는 다음에 유의한다.

   대각선(예를들어, 2와2의 인접갯수, 3과3의인접갯수)은 해당 node에서 나가서 바로 되돌아오는 edge갯수를 세는것이다. 참고로, 예시의 경우는 모두 0이다.

   다른 node끼리의 연결갯수를 쓸때, 직접 연결된 edge가 없다면 이는 무한으로 작성한다.

 

- 특히 리스트로 파이썬에서 표현할 경우:

edge와 연결된 다른 edge들을 튜플형으로 가지고, 이 튜플들의 리스트로서 그래프를 구현하는게 특징

(파이썬에는 리스트가 기본자료형으로 있기 때문이다)

작성방식을 확인해둘 필요가있다.

graph = [[] for i in range(3)] 로 선언해도 됨

***

연결갯수가 다 1개나 0개인경우 튜플없이 표현한다.

[[0이랑 연결된 노드 리스트], [1이랑 연결된 노드 리스트], [2랑 연결된 노드 리스트], ...]

 

- 행렬로 표현할 경우:

인접된 선의 수를 그대로 행렬에 표현

그대로 matrix 작성!!

 

- 여기서 개인적인 고찰,

 세가지 자료구조에서 앞선 두가지와 뒤에그래프는 정의에서 알수있든 차원이 다르다는 특징이 있다. 하지만 코드를 구성하면 결국엔 세가지가 리스트의 형태로서 표현되고 있다.

 

 물론 그래프는 행렬로 표현하기도 하지만, 그림을 그리는 것이 아닌 줄글을 쭉 써내려가는 코딩의 특성상 2차원을 상상하면서 이를 작성하는것은 쉽지 않을것 같다.

 

 이러한 특징때문에 그래프와 관련한 수학적 이론들을 활용하여 효율적이고 획기적인 아이디어를 구성하는 것이 가능하다는 장점에도 불구하고 결국엔 1차원 구조 정도 사용하는 코드에 그치고말 수도 있다는 생각을 했다. 혹은 각 상황에 따른 쉬운 예제 한두가지 정도만 암기하는식으로 사용하게 될 것 같다. (일단 내 능력에서는 ㅋㅋㅋ )

 

 이를 극복하기 위해서는 결국엔 난이도를 상승시켜가면서 예제나 문제풀이를 공부해야만 할 것 같다.

 

 또 한가지 리스트를 너무나 쉽게 접근할 수 있는건 파이썬이 가징 특징이다. 따라서 C++을 이용해야할 경우에는 더 복잡해질 수 밖에 없다. 필요하다면 이또한 만만치 않을것 같았다.

 

탐색 알고리즘 DFS/BFS - 그래프+자료구조

 

자료를 그래프나 리스트 등등으로 정리한 후에는 자료를 이리저리 조작하여 원하는 수행 목표를 이루기위해서는 조작하는 방법? 을 연구해야한다.

그리고 이때 조작방법으로 DFS, BFS를 사용할 지, 다른 방법은 없는지 등등 알고리즘 기법이 본격적으로 등장한다고 이해했다.

 

1. DFS = Depth-First Search

O(N)

DFS는 깊이 우선탐색으로, 갈림길에서 갈라져 최대한 깊게 들어갔다가 다시 돌아와 다른 갈림길로 또 들어가고 돌아오는 것이라고 한다. 미로찾기에서 우리가 가장 이상적으로 생각하는 방식이 아닐까 한다. 하지만 실제에서는 쉽게 실현하지 못하는 ㅋㅋㅋㅋ 하지만 컴퓨터는 할 수 있다!!! 메모리만 있다면 기억력은 인간보다 좋으니까ㅋㅋㅋ

 

핵심은 갈림길 처리를 어떻게 할까? 라고 볼 수 있다. 그리고 아래와 같은 아이디어를 따른다고 한다.

- 스택, 방문처리 두가지 리스트를 개념에 사용한다.

- 모든 갈림길은 노드(넘버링)가 된다. 그리고 앞으로 방문한 노드를 방문처리 한다.

-* 갈림길에서 방문하지 않은 인접 + 낮은 숫자 의 노드 우선 탐색하기로 한다.(정하기 나름이지만 가장 흔하게 낮은 숫자 먼저 방문한다.)

-* 방문하지않은 인접 노드가 없는 경우 스택에서 해당 노드를 지우면서 되돌아간다. (이를 통해 가장 깊숙히 위치함이 자동 확인된다)

- 위의 *두가지 수행을 순서대로 방문한 노드마다 다시 수행하면 처음으로 점점 되돌아가면서 선택한 갈림길에 해당하는 모든 노드를 다 방문하게 된다. 

- 최종적으로 스택에 남아있는 노드가 없는 경우 모든 노드를 방문하고 끝난셈이다.

 

def dfs(graph, vv, visited):
	visited[vv] = True  # 방문 처리
    for i in graph[vv]:
    	if not visited[i]: # 방문 안했으면 같은 행동 재귀로 반복
        	dfs(graph, i visited)
        # 방문하면 나옴, 그리고 그래프에서 vv 갈림길에서 다 확인되면 for가 끝나는 셈

graph = [행렬로 선언]
visited = [false] * 노드갯수 

dfs(graph, 1, visited)

[참고]이것이 취업을 위한 코딩 테스트다 with 파이썬

 

낮은 숫자방문은 사실상 배열 순으로 하게하다보니 특별히 구현하지 않아도 되는 부분이 되었다. 마찬가지로 사용 스택 역시 배열순으로 돌면서 방문안한 노드가 없다면 나가서 상위 함수 수행으로 다시 돌아가게하는 재귀함수로 구현하면서 필요없게 되었다. 또한 연결되었는지의 확인은 이미 리스트형으로 선언된 그래프 표현의 특성상 해당 노드가 가진 연결리스트에 다른 노드가 없으면 수행을 끝내면서 이루어진다.

 

세가지 아이디어를 종합해 너무나도 간단하게 끝나버린 함수... 멋있다.

 

 

2. BFS = Breadth First Search

O(N)

BFS는 너비우선탐색으로 가까운 노드를 우선 탐색한다. 방문처리한후에 해당 노드를 지우고 인접했던 노드에 모두 한번에 방문하는 방식이라는게 큰 차이점으로 보인다. 위의 DFS는 미로찾기에서 이상적일듯한 방법(깊이를 가늠하면서 가는느낌)이었다면 BFS는 미로찾기에서 찾아야하는 탈출구를 찾기에 거리보다 시간이 급한사람의 느낌이다.

빨리 찾아야겠다 일단 가까운거 뒤져서 나오면 좋고!!! 막 이런느낌ㅋㅋㅋ

BFS는 방문처리는 DFS과 같지만 사용하는 자료형은 큐이다. 일반적으로는 수행시간이 DFS 보다 좋은편이라고 한다.

 

아이디어를 살펴보자

- 큐, 방문처리 두가지 리스트를 개념에 사용한다.

- 모든 갈림길은 노드(넘버링)가 된다. 그리고 앞으로 방문한 노드를 방문처리 한다.

-* 갈림길에서 방문하지 않은 인접한 노드를 전부 삽입하고 방문처리 한다.

-* 동시에, 방금 체크한 노드를 큐에서 삭제한다. (되돌아가는 일은 없다.)

-* 큐에 들어있는 순서대로 하나씩 체크하여 지우면서 추가할게 있다면 추가할게 없다면 지우기만 하기를 반복한다.

-DFS와 마찬가지로 큐에 모든 요소가 삭제되고 없으면 끝난다.

from collections import deque

def bfs(graph, start, visited):
	queue = deque([start]) #start를 시작점으로, 해당 요소를 먼저가진 리스트를 우선 큐형을 사용하기 위해 선언
    	visited[start] = True
        while queue: #더이상 인접한 요소가 없는지는 체크하지 않는다 이전 방문한곳을 바로바로 지우기 때문에 리스트에 없으면 해당 함수는 끝난다
        	i = queue.popleft() # 현재지우면서, 동시에 i에 넣기
        	for j in graph[i]: # i의 인접리스트 체크
        		if not visited[j]: # 체크한 목록에 안간곳이 있다면 큐에 추가하고 방문처리
            		queue.append(j)
                	visited[j] = True

graph = [2차원 리스트]
visited = [False]*노드갯수

bfs(graph, 1, visited)

 

코드 줄수는 더 많지만 차근히 읽어보면 훨씬 직관적이라고 느꼈다. 그리고 일단 일반적으로는 BFS가 더 빠르다고 하니, 두 함수를 둘다 잘 외워두는것 나쁘지 않아 보인다.

고찰, 도움받는 책

 

- 자료구조는 쉽지만 코드 작성은 어렵다 고 생각했는데, 사실은 그게 문제가 아니었다.

많은 책에서 스택으로 그림을 그려가며 DFS, BFS 탐색과정을 자세하게 설명하는데는 이유가 있었다. 그 과정을 온전히 내가 스스로 그리고 설명할 수 있을정도로 이해해야만 했던 것이다. 알고나서야 깨닿을때가 가장 머쓱해지는 순간인 듯하다.

 

-음미를 하기 위해 나 나름의 각 정의와 알고리즘들의 느낌을 서술하면서 작성한 글이어서 공부하면서 재밌었다. 다만, 알고리즘에 대한 다소 평가스러운 표현들은 기억하기 좋으려고 나만의 표현을 사용한것 정도로 생각해주면 좋겠다. 이를 참고로 해서 우연으로라도 보시는 분들이 재미있었으면 좋겠다.

 

- 너무 초보가 장성한 글이라 아직도 정보가 부족하고, 또 부족할 것이라고 벌써 두려움을 느낀다. 몇년 뒤 이 글을 다시 볼때, '내가 참 더럽게 못했구나' 라고 느끼는 날이 오기를 ㅎㅎ

 

-코드에서 방문처리를 노드갯수+1로 하시던데 왜 그런지 정확하게는 모르겠다. 숫자를 세면서 발생하는 헷갈림때문인듯 한데 안전하게 하기 위해 그런거 같다. 내가 본 책에서는 노드 넘버링을 0이 아니라 1부터 시작했기 때문에 이래저래 헷갈리기 때문이다. 나중에는 정확한 이유를 확인할 수 있기를 바란다.

 

도움받는책 (시작하는분 완전 강추... 나를 이해시키신 책이다ㅋㅋㅋㅋㅋㅋ)

이것이 취업을 위한 코딩테스트다 with 파이썬 - ridibooks에서 구입

유투브는 아직 안들어봄 책만 봐도 충분해서...ㄷㄷ