본문 바로가기

알고리즘/개념

 (18)
[정렬] stable vs not stable 1. stable vs not stable 중복된 키값이 있을 때 이를 원래 순서대로 정렬하는 알고리즘 정렬 전처럼 주황색 3이 초록색 3보다 앞에 있다. 2. in-place vs not in-place 중복된 키값이 있을 때 이를 원래 순서와 다르게 정렬하는 알고리즘 정렬 전과 다르게 주황색 3이 초록색 3보다 뒤에 있다.
[정렬] 퀵 정렬 [Quick Sort] 퀵 정렬에 대해 알아보자. 이는 분할 정복을 통해 구현한다. (분할 정복은 큰 문제를 작은 문제 단위로 쪼개면서, 쉽게 풀 수 있는 문제 단위로 나눈 뒤 그것들을 다시 합치는 방식이다.) 불안정 정렬이고 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬이다. 그리고 병합 정렬과 함께 빠른 정렬에 해당한다. 병합 정렬과는 분할 정복을 통해 해결한다는 공통점이 있다. 차이점은 아래와 같다. 1) 병합 정렬 : O(n)의 시간이 걸리는 과정을 재귀호출 후에 한다. (분할 후 병합 시점에서 비교 연산 발생) 2) 퀵 정렬 : O(n)의 시간이 걸리는 과정을 재귀호출 전에 한다. (분할 시점부터 비교 연산 발생) 따라서 퀵 정렬이 병합에 들어가는 비용이 적거나 구현 방법에 따라서 아예 병합하지 않을 수도 있다...
[정렬] 병합 정렬 [Merge Sort] 병합 또는 합병 정렬에 대해 알아보자. 이는 분할 정복 방법을 통해 구현한다. (분할 정복은 큰 문제를 작은 문제 단위로 쪼개면서, 쉽게 풀 수 있는 문제 단위로 나눈 뒤 그것들을 다시 합치는 방식이다.) 퀵 정렬과 함께 빠른 정렬에 해당한다. 예를 들어보자. [6, 5, 3, 1, 8, 7, 2, 4] 숫자 1 ~ 8까지 들어있는 배열이 있다. 먼저 하나의 배열을 두 개로 쪼갠다. [6, 5, 3, 1] [8, 7, 2, 4] 그리고 다시 각 배열을 두 개로 쪼갠다. [6, 5] [3, 1] [8, 7] [2, 4] 또다시 각 배열을 두 개로 쪼갠다. [6] [5] [3] [1] [8] [7] [2] [4] 이제 더 이상 배열을 쪼갤 수 없다. 이제 두 개의 배열씩 합친다. 합칠 때는 둘 중에 값이 더..
[최소 신장 트리] 프림[Prim] 알고리즘 최소 신장 트리란? 주어진 그래프의 모든 정점을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리이다. 최소 신장 트리를 구하는 방법은 여러 가지가 있다. 그중에 프림 알고리즘에 대해 알아보자. 프림 알고리즘은 그리디 알고리즘이다. 동작 순서 1. 그래프에서 임의의 정점을 선택하여 집합 A에 넣는다. 2. 그 정점과 연결된 변들을 집합 B에 넣는다. 3. 집합 B에서, 변의 양쪽 정점이 모두 집합 A에 있지 않은 것 중에 가장 가중치가 작은 변을 찾는다. 4. 3번에서 찾는 변의 양쪽 정점 중 집합 A에 없는 정점을, 집합 A에 넣는다. 모든 정점이 집합 A에 들어올 때까지 2~4번을 반복한다. 알고리즘이 종료됐을 때 만들어진 트리는 최소 신장 트리가 된다. 아래는 코드이다. https://so..
[정렬] 위상 정렬(Topological Sort) 위상 정렬은 사이클이 발생하지 않는 방향 그래프에서 사용한다. 순서를 결정할 때 사용하는 알고리즘으로, 순서가 정해져 있는 작업을 신경 쓴다. 위상 정렬은 아래처럼 동작한다. 1. 진입차수가 0인 정점(들)을 큐에 넣는다. (진입차수란 상대 정점에서 자신의 정점으로 오는 간선의 수이다.) 2. 큐에 있는 원소를 꺼낸다. 3. 진입차수가 0인 정점(들)을 큐에 삽입한다. 4. 큐가 빌 때까지 2~3번을 반복한다. 위상 정렬이 모든 원소를 방문했다면, 큐에서 꺼낸 순서가 결과이다. (모든 원소를 방문하기 전에 큐가 빈다면, 사이클이 존재하는 것으로 위상 정렬을 사용할 수 없다.) 동작 방식을 보면 알 수 있듯이, 위상 정렬은 답이 여러 개가 될 수 있다.
[최단 경로 트리] 다익스트라 알고리즘[Dijkstra] 다익스트라 알고리즘을 설명하기 전에, 최단 신장 트리에 대해 설명해보자. 신장 트리란 그래프 내의 모든 정점이 연결되어 있으면서 사이클이 존재하지 않는 트리이다. 따라서 신장 트리는 N개의 정점을 정확히 N-1개의 간선으로 연결하게 된다. 다익스트라 알고리즘은 출발 지점을 정하여, 다른 모든 지점까지의 최단 경로를 찾는 것이다. 예를 들어보면, A를 출발 지점으로 두고 시작해보자. A의 최단 거리값은 0으로, 나머지 최단 거리값은 무한으로 설정한다. 이제 A와 연결된 B, C의 거리 값을 조정하자. 여기서, 시작점 거리값 + 아크 값 < 도착점 거리값이라면, 도착점 거리값을 더한 값으로 낮춘다. 방금 했던 것을 무한 반복할껀데, 이번에는 B를 기준으로 한다. 최종적으로, 이런 결과가 나오게 된다. 거리가..
[이진 탐색] 이진 탐색[Binary Search] 정렬된 배열에서 특정 값을 찾아내는 알고리즘이다. 위 설계를 옮긴 코드이다. def BSearch(array, check): low = 0 high = len(array) -1 while(low check): high = mid - 1 else: low = mid + 1 return -1 시간복잡도는 O(logN)이다. 응용 문제 sojeong-lululala.tistory.com/14 [BOJ] [Python] 13706번 : 제곱근 이진탐색을 이용하여 풀었다. num = int(input()) def BSearch(num): low = 0 high = num while low num: high = mid - 1 else: lo.. sojeong-lululala.tistory.com
[그래프 탐색] 깊이 우선 탐색[DFS], 너비 우선 탐색[BFS] 그래프 탐색 방법 1. 깊이 우선 탐색[DFS (Depth-First Search)] 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다른 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식이다. 스택(선입후출), 재귀함수로 구현한다. sojeong-lululala.tistory.com/5 [BOJ] [Python] 2775번 : 부녀회장이 될테야 간단한 예시를 만들어 작성하면서, 어떻게 문제를 풀어야 할 지 생각했다. 그렇게 떠올린 방법은 '재귀함수 사용' loop = int(input()) #test def people(a, b): global result if(a == 0): return b else: for i.. sojeong-lululala.tistory.com 2. 너비 ..

티스토리툴바