깊이 우선 탐색 (DFS) 이란? *그래프 탐색 하나의 정점에서 시작하여 모든 정점들은 한 번씩 방문하는 작업 Depth First Search. 현재 탐색하고 있는 경로를 끝까지 탐색한 후 다른 경로를 탐색하는 방법. 깊이를 우선적으로 탐색한다. 방법 노드와 연결된 탐색하지 않은 이웃 노드 중 하나를 탐색한다. 탐색하지 않은 이웃 노드가 없는 경우, 이전 노드로 돌아간다. 위 작업을 모든 노드를 방문할 때까지 반복한다. 그림으로 표현하기 그림 예제로 이해하기 예제 1 : 연결 요소의 개수 (백준 11724번) 문제 방향 없는 그래프가 주어졌을 때, 연결 요소의 개수를 구하는 프로그램을 작성하시오. 해결 방법 연결되어 있는 영역이 몇 개인지 구하는 문제이다. 방문되지 않은 노드마다 해당 노드와 연결된 모..

합병 정렬(Merge Sort)이란? 배열을 2개의 하위 배열로 재귀적으로 나눈 후, 다시 각 배열을 합치면서 정렬한다. 분할 정복 (Divide and Conquer)에 해당한다. *분할 정복이란? 문제를 작게 분할한 후 각각을 해결하고, 그 결과를 이용해 전체 문제를 해결하는 알고리즘 방법 주어진 배열을 균등한 크기의 2개의 배열로 분할한다. 분할된 부분 배열을 반복해서 2개의 배열로 분할한다. 더 이상 분할할 수 없을 때, 다시 2개의 배열을 합쳐서 정렬한다. ([3], [1] -> [1, 3]) 재귀적으로 정렬된 부분 배열을 하나로 합치면서 전체가 정렬된 배열을 만든다. ([1, 3], [2, 4] -> [1, 2, 3, 4]) 파이썬으로 구현하기 def merge_sort(arr, start, ..

퀵 정렬(Quick Sort)이란? 분할 정복 (Divide and Conquer) 기법과 재귀 알고리즘을 이용한 정렬 알고리즘 *분할 정복 이란? 문제를 작게 분할한 후 각각을 해결하고, 그 결과를 이용해 전체 문제를 해결하는 알고리즘 방법 피봇(pivot)이라는 값을 하나 정한다. (임의로 정할 수 있지만, 여기서는 중간에 있는 값을 하나 정해보자.) 피봇보다 작은 값을 left 배열에, 피봇보다 큰 값을 right 배열에 추가한다. left(피봇보다 작은 값들), 피봇, right(피봇보다 큰 값들) 로 만들어진다. left, right 배열에 대해 위 작업을 재귀적으로 반복한다. 파이썬으로 구현하기 방법1 pivot 보다 작은 값을 왼쪽 배열에, 큰 값을 오른쪽 배열에 추가한다. 각 배열에 대해 ..

삽입 정렬(Insertion Sort)이란? 원소를 하나씩 확인하면서, 각 원소를 적절한 위치에 삽입하는 알고리즘 방법 2번째 원소부터 시작한다. 해당 원소의 왼쪽으로 하나씩 확인하면서, 자신보다 작은 원소가 존재하는 경우 그 오른쪽에 삽입한다. 자신보다 큰 원소인 경우 오른쪽으로 한 칸 밀고, 다음 원소를 확인한다. 위 작업을 n번째 원소까지 반복한다. 파이썬으로 구현하기 def insertion_sort(arr): n = len(arr) for i in range(1, n): # arr[i]의 위치를 찾는다. for j in range(i, 0, -1): if arr[j] < arr[j-1]: # 자신(arr[j])보다 더 큰 원소인 경우, 큰 원소를 오른쪽으로 한 칸 이동시킨다. arr[j], ar..

선택 정렬(Selection Sort)이란? 배열의 각 위치마다 어떤 원소를 넣을지 선택하는 알고리즘 방법 주어진 배열 중 최소값을 찾는다. 그 값을 첫 번째 원소와 교체한다. 첫 번째 원소를 제외하고 위 작업을 반복한다. 버블 정렬과 유사한 알고리즘이다. (참고 글 : 버블 정렬이란?) 파이썬으로 구현하기 def selection_sort(arr): n = len(arr) for i in range(n-1): min_idx = i # i ~ n-1 구간 중 가장 작은 값의 위치를 찾는다. for j in range(i, n): if arr[j] < arr[min_idx]: min_idx = j # 가장 작은 값을 arr[i] 위치로 이동시킨다. arr[i], arr[min_idx] = arr[min_i..

버블 정렬이란? 인접한 두 원소를 비교하며 정렬하는 알고리즘 방법 arr = [1,6,4,2,3,5] 1) arr[0]와 arr[1] 를 비교하여 큰 원소를 오른쪽에 위치시킨다. 2) 1번과 동일하게 arr[1]과 arr[2], arr[2]과 arr[3], ... , arr[n-2]과 arr[n-1]를 비교하여 정렬한다. 3) 모두 수행하고 나면 arr[n-1] 위치에는 가장 큰 원소가 위치하게 된다. (이제 arr[n-1]은 비교할 필요가 없다.) 4) arr[n-1]를 제외한 리스트에서 1~2의 작업을 수행한다. 5) 확인해야 하는 원소를 하나씩 줄여나가면서 위 작업을 총 n번 수행한다. 파이썬으로 구현하기 def bubble_sort(arr): n = len(arr) for i in range(..

빅오(Big O) 란? 알고리즘에서 '시간 복잡도'란 주어진 문제를 해결하기 위한 연산 횟수를 말한다. 빅오는 이 시간 복잡도를 정의하여 표현하는 방법 중 하나이며, 최악(worst case)일 때 연산 횟수를 나타내는 표기법이다. *빅-오메가 : 최선(best case)일 때 연산 횟수를 나타내는 표기법 *빅-세타 : 보통(average case)일 때 연산 횟수를 나타내는 표기법 빅오 차수 n : 입력 데이터의 크기 O : 차수 또는 대략의 차수 알고리즘의 시간복잡도에 따라 아래와 같이 표기할 수 있다. O(1), 상수 시간 (가장 낮은 차수) O(log n), 로그 시간 O(n), 선형 시간 O(n log n), 선형로그 시간 O(n^2), 다항 시간 O(2^n), 지수 시간 O(n!), 팩토리얼 ..

"파이썬 텍스트 마이닝 완벽 가이드" 도서를 읽고 정리한 글입니다. 이 글을 통해 얻을 수 있는 내용 - 카운트 기반 문서 표현이란 무엇인가 - 카운트 벡터를 생성하는 방법과 코드 이해 - 카운트 벡터와 TF-IDF 방법의 차이 4장. 카운트 기반의 문서 표현 4-1. 카운트 기반 문서 표현의 개념 카운트 기반 문서 표현이란? 단어의 통계를 이용해 문서의 내용을 이해하고자 하는 시도이다. 카운트 기반 문서 표현은 단어의 빈도를 세어 벡터로 표현하는 방법이다. 텍스트의 특성을 무엇으로 정의할까? 텍스트의 특성을 단어로 표현하고, 특성이 갖는 값을 그 단어가 텍스트에서 나타나는 횟수로 표현한다. ex) 정치(특성) : 4(특성이 갖는 값, 빈도) 문서마다 특성이 제각각인데, 어떻게 비교하지? 전체 문서에서 ..