DFS는 깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. DFS는 스택 자료구조(혹은 재귀 함수)를 이용하며, 구체적인 동작 과정은 다음과 같다. 탐색 시작 노드를 스택에 삽입하고 방문처리를 한다. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다. def dfs(graph, v, visited): # 현재 노드를 방문 처리 visited[v] = True print(v, end=' ') # 현재 노드와 연결된 다른 노드를 재귀적으로 방문 for i in graph[v]: if not vis..
ProblemSolving/AlgorithmTheory
이진 탐색(binary search)이란, 정렬된 자료를 반으로 나누어 탐색하는 방법을 말한다. 자료는 오름차 순으로 정렬되어있어야 하는 전재가 깔려야 한다. 시간 복잡도는 O(logN)으로 순차 탐색과 비교했을때 퍼포먼스가 좋다. (순차탐색(linear search): 순서대로 찾는 방법. 순차탐색의 시간복잡도는 O(N))
정렬 (sorting)이란 , 데이터를 특정한 기준에 따라 순서대로 나열하는 것을 말한다. 데이터의 개수가 적을 때, 많을 때, 데이터의 범위가 특정 범위로 한정되어 있을때, 거의 정렬되어 있을 때,,, 등 과 같은 문제 상황에 따라 적절한 정렬 알고리즘이 공식처럼 사용된다. 1-1. 선택 정렬(Selection Sort) 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복한다. 선택 정렬은 N번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다. 1-2. 선택 정렬 시간복잡도 구현 방식에 따라 사소한 오차는 있지만, 전체 연산 횟수는 다음과 같다. N +(N-1)+(N-2)+...+2 이는 (N^2+ N-2)/2로 표현 할 수 있는데, 빅오 표기법에 따라서..
