알고리즘
[Graph] BFS (너비 우선 탐색)
너비 우선 탐색은 탐색 시작점의 인접한 정점들을 먼저 모두 차례로 방문한 후에, 방문했던 정점을 시작점으로 하여 다시 인접한 정점들을 차례로 방문하는 방식이다. 그래프를 탐색하는 방법에는 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)로 크게 2가지가 있다. 인접한 정점들에 대해 탐색을 한 후, 차례로 다시 너비 우선 탐색을 진행해야 하므로, 선입선출 형식의 자료구조인 큐를 활용한다. BFS는 시작 정점 기준 거리가 가까운 곳부터 먼곳으로 탐색을 진행하기 때문에, 특정정점까지 가는 최단거리를 구하는데 용이하며, BFS 탐색이 종료된 경우 직전에 방문한 정점이 시점과 가장 먼 정점이라는 것을 알 수 있다. 개요 시작정점 v를 결정하여 방문한다. 정점 v에 인접한 정점 중에서 방문하지 않은 정점 w가 있..
[Power Set] 부분집합을 생성하는 다양한 방법
부분집합을 만들고, 모든 원소를 탐색한다. 리스트 or 스트링의 원소들의 모든 조합(순서X)을 확인해야 하는 문제에 적합합니다. 라이브러리 없이 부분집합을 생성하는 방법을 알아보자! 부분집합? n개의 원소를 가진 집합의 원소를 일부 또는 전체로만 이루어진 집합이다. 원소가 n개인 집합의 모든 부분집합의 수는 2^n 개이다. 해당 원소를 포함하거나, 안하거나의 2가지 경우이기 때문에 각각의 경우의 수를 곱한 것이 된다. 구현 ✅ 다중 반복문 원래 집합의 갯수에 따라 반복문의 횟수를 지정한다. 가장 단순한 방법이지만 비효율적이고, 재사용이 불가능하다. bit = [0, 0, 0, 0] for i in range(2): bit[0] = i for j in range(2): bit[1] = j for k in ..
[Search] Binary Search Tree (트리에서의 이진탐색)
01. 이진 탐색 트리 탐색 작업을 효율적으로 하기 위한 자료 구조 모든 원소는 서로 다른 유일한 키를 갖는다. key(왼쪽 서브트리) 루트노드의 키값)인 경우 : 루트노드의 오른쪽 서브트리에 대해서 탐색 연산 수행 서브트리에 대해서 순환적으로 탐색연산을 반복한다. 03. 탐색 성..
[Search] Binary Search (이진 탐색)
자료의 가운데에 있는 항목의 키값과 비교하여 다음 검색의 위치를 결정하고 검색을 계속 진행하는 방법. 목적 키를 찾을 때까지 이진 검색을 순환적으로 반복수행함으로써 검색 범위를 반으로 줄여가면서 보다 빠르게 검색을 수행함. 이진 검색을 하기 위해서는 반드시 자료가 정렬된 상태여야한다. 정의 자료의 중앙에 있는 원소를 고른다. 중앙 원소의 값과 찾고자 하는 목표값을 비교한다 목표값이 중앙 원소의 값보다 작으면 자료의 왼쪽 반에 대해서 새로운 검색을 수행하고, 크다면 자료의 오른쪽 반에 대해서 새로 검색을 수행한다. 찾고자하는 값을 찾을때까지 1~3의 과정을 반복한다. 설명 간단하게 생각하면 소주 병뚜껑에 적힌 숫자로 UP&Down을 하는 것과 동일하다 일반적인 방법으로 숫자의 범위를 반씩 잘라가며 타겟이 ..
[Sort] Topology Sort (위상 정렬)
그래프에서의 정렬 방법으로, 유향 그래프의 꼭짓점 변의 방향을 거스르지 않도록 나열 하는 것이다. 정의 자기 자신을 가리키는 변이 없는 꼭짓점을 찾음. 찾은 꼭짓점을 출력하고 출력한 꼭짓점과 그 꼭짓점에서 출발하는 변을 삭제 아직 그래프에 꼭짓점이 남아있으면 단계 1로 돌아가고, 아니면 알고리즘을 종료시킨다. 설명 위상 정렬(topological sorting)은 유향 그래프의 꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. 하나의 방향 그래프에는 여러 위상 정렬이 가능하다. 위상 정렬의 과정에서 선택되는 정점의 순서를 위상 순서(Topological Order)라 한다. 위상 정렬의 과정에서 그래프에 남아 있는 정점 중에 진입 차수가 0인 정점이 없다면, 위상 정렬 알고리..
[Sort] Merge Sort (병합 정렬)
리스트를 반으로 나눈다. 가장 작은 조각으로 나누어졌을때(원소가 2개 이하) 정렬한다. 정렬된 두 리스트를 정렬한다. 정의 리스트의 길이가 1 이하이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는 분할(divide) : 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다. 정복(conquer) : 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다. 결합(combine) : 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 이때 정렬 결과가 임시배열에 저장된다. 복사(copy) : 임시 배열에 저장된 결과를 원래 배열에 복사한다. 설명 여러개의 정렬된 자료의 집합을 병합하여 한개의 정렬된 집합으로 만드는 방식이다. 분할 정복 알고리즘을 활용하여 자료를 최소단위로 ..
[Sort] Quick Sort (퀵 정렬)
분할정복 알고리즘을 이용하여, 기준점(피봇)을 잡고 왼쪽, 오른쪽을 나누어 각각 정렬한다. 정의 리스트에서 기준점을 설정한다. 리스트를 순회하며 기준점보다 작은 원소는 왼쪽에, 큰것을 오른쪽에 둔다. 설명 퀵정렬은 리스트가 고정 크기인 경우(대부분의 프로그래밍 언어)와 가변 리스트인 경우(파이썬)으로 나눌 수 있다. 파이썬 같은 경우 분할정복 아이디어로 피봇 보다 작은 원소, 피봇보다 큰 원소를 각각 새로운 리스트로 만들어서 합치는 방법으로 한다. 이외의 경우, 투포인터를 이용하여 좌, 우에서 피벗쪽으로 탐색을 진행하고 L, R이 교차될 때까지 탐색하며 자리를 교환한다. 피봇은 0번 인덱스, 중간 인덱스, 마지막 인덱스 무엇으로 잡아도 상관 없으나 파이썬 알고리즘에는 0번 인덱스로 잡는 것이 가장 편하다..
[Sort] Counting Sort (카운팅 정렬)
항목들의 순서를 결정하기 위해 집합에 각 항목이 몇 개씩 있는지 세는 작업을 하여, 선형 시간에 정렬하는 효율적인 알고리즘 정의 일반적으로 정렬 대상이 integer이고 최대값이 크지 않을때 사용한다. 정렬 대상을 인덱스로 하는 카운팅 배열을 생성하여, 정렬 대상의 갯수를 센다(카운팅) 카운팅 배열을 누적값으로 만들면 각 인덱스가 최대 누적값 번째에 있는 숫자가 된다. 제한 사항 정수나, 정수로 표현할 수 있는 자료에 대해서만 적용 가능 : 각 항목의 발생 회수를 기록하기 위해, 정수 항목으로 인덱스 되는 카운트들의 배열을 사용하기 때문 카운트들을 위한 충분한 공간을 할당하려면 집합 내의 가장 큰 정수를 알아야한다. 시간복잡도 O(n + k) : n은 리스트의 길이, k는 정수의 최대값 구현 def Co..