투투

퀵 정렬은 합병 정렬과 같이 분할 정복 알고리즘을 적용한 정렬 기법이며 평균적으로 매우 빠른 속도를 갖고있다. 또한 정렬 대상에 동일한 키 값이 존재할 경우 키 값의 순서가 바뀌는 불안정 정렬이다. 개념 퀵 정렬은 피벗(pivot)을 설정하여 피벗을 기준으로 작은 값은 피벗의 왼쪽으로 큰 값은 피벗의 오른쪽으로 이동시킨다. 아래에 정렬할 대상이 있다. 여기서는 가장 앞에 있는 값을 피벗으로 설정해보자. [3, 1, 10, 6, 4, 7, 8, 2, 5, 9] 그렇다면 3이 피벗이되고 3을 기준으로 작은 값은 왼쪽으로 큰 값으 오른쪽으로 이동시키면 아래와 같은 결과를 갖는다. [1, 2] < [3] < [10, 6, 4, 7, 8, 5, 9] 위와 같이 분리가 되었다면 왼쪽은 왼쪽끼리 오른쪽은 오른쪽끼리 ..

정렬을 위한 알고리즘은 다양하다. 따라서 각각의 상황에 맞는 정렬 알고리즘을 적절히 사용해야 한다. 이번에는 내림차순으로 정렬된 수들을 다시 오름차순으로 정렬하기 위해서는 어떠한 기법이 효율적이며 왜 그런 것인지 알아보려고 한다. 잘못된 내용은 댓글에 적어주시면 감사하겠습니다. 아래처럼 10부터 내림차순으로 정렬되어 있는 것을 오름차순으로 정렬하려고 한다. 어떻게 하는 것이 가장 효율적인 방법일지 생각해보자. [10, 9, 8, 7, 6, 5, 4, 3, 2, 1] 빈번한 교환은 비효율적 정렬을 할 때 두 수를 비교하여 두 수의 위치를 변경하는 횟수가 많을수록 비효율적인 알고리즘이 된다. 두 수를 교환하기 위해서는 임시 변수를 생성해야 하고 A를 임시 변수에 저장하고 A에 B를 저장 후에 B에 임시 변수..

프림과 크루스칼 알고리즘은 최소 신장 트리를 구하는 대표적인 알고리즘이다. 먼저 최소 신장 트리가 무엇인지 알아본 후에 유니온 파인드를 적용시킨 크루스칼 알고리즘을 알아본다. 최소 신장 트리 N개의 노드로 이루어진 그래프가 있다. 이 그래프에는 다양한 부분 그래프가 존재할 수 있다. 이때 부분 그래프를 신장 트리라하며 N개의 노드글 N-1개의 간선으로 연결하고 순환되지 않는 구조를 가져야만 신장 트리라 할 수 있다. 이러한 신장 트리 중에서 연결하는데 가장 적은 비용이 드는 신장 트리를 최소 신장 트리라 한다. 개념 크루스칼 알고리즘은 유니온 파인드와 그리디 알고리즘의 개념을 활용하였다. 먼저 신장 트리가 되기 위해서는 N-1개의 간선으로 N개의 노드를 연결해야 하며 순환되지 않는 구조를 가져야 한다. ..

서로소 집합은 공통 원소가 없는 두 집합을 의미한다. 즉 {1, 2}와 {3, 4}는 서로소 집합이지만 {1, 2}와 {2, 4}는 서로소 집합이 아니다. 이러한 서로소 집합을 구할 때 유니온 파인드 알고리즘을 사용할 수 있다. 유니온 파인드의 개념을 알아보고 코드를 통해 구현해보자. 또한 유니온 파인드 알고리즘을 활용한 또 다른 알고리즘을 소개한다. 개념 유니온 파인드 알고리즘은 서로소 집합을 찾기위해 사용되는 알고리즘이다. 유니온 파인드는 Find과 Union라고 불리는 두 가지 연산으로 이루어져 있다. Find: 원소 x가 어느 집합에 포함되어 있는지 찾는다. Union: 원소 x가 포함된 집합과 원소 y가 포함된 집합을 합친다. 위의 연산을 통해 그래프 내에서 부분집합을 쉽게 구할 수 있다. 이제..

합병 정렬은 분할 정복 알고리즘을 활용한 정렬 방법이다. 먼저 원소들을 반으로 나누고 두 개의 부분 배열을 비교하여 정렬된 상태로 만들어 가는 것이다. 개념 오름차순 기준으로 설명한다. N개의 원소가 있을 때 N//2를 기준으로 원소들을 반으로 나눈 값을 인덱스로 하고 위에서 구한 인덱스를 기준으로 리스트를 반으로 나눈다. 반으로 나눈 리스트를 또 다시 반으로 나누고 리스트 원소의 개수가 1일 때 해당 원소를 반환한다. 이렇게 반으로 나눈 원소들을 합쳐 나간다. 초기에 1개의 원소들로 이루어진 리스트를 비교하여 정렬 후에 2개의 원소를 갖는 리스트로 만든다. 이후에는 2개의 원소를 갖는 리스트끼리 비교하여 정렬하여 4개의 원소를 갖는 리스트로 만든다. 위의 과정을 반복하는 것이 합병 정렬이다. 구현 me..

슬라이딩 윈도우는 어떠한 배열에서 일정 범위의 값을 비교할 때 유용하게 사용될 수 있는 방법이다. 투 포인터와 비슷하다고 생각할 수 있지만 투 포인터는 정렬된 배열 내에서 가변적인 범위를 탐색하는 반면 슬라이딩 윈도우는 정렬의 유무와 상관없이 고정적인 범위를 탐색한다는 것에 차이가 있다. 개념 슬라이딩 윈도우는 어떠한 배열에서 고정된 크기의 범위를 탐색할 때 유용하게 사용된다. 아래의 그림과 같은 배열을 예시로 확인해보자. 아래의 배열 중에서 연속된 세개의 수를 선택하여 그 합이 최대가 되는 구간이 어디인지 구하려고 한다. 이를 위해 아래의 그림처럼 처음부터 세개의 수를 선택하여 합을 구할 수 있을 것이다. 순서대로 (3 - 1 + 8)을 계산하고 (-1 + 8 - 2)를 계산하면서 진행하는데 (-1 +..

삽입정렬은 원소가 자신의 자리를 찾고 해당 자리에 삽입되면서 정렬하는 기법이다. 숫자 카드를 손에 들고 있을 때 숫자들을 오름차순으로 정렬한다고 생각해보면 쉽게 연상할 수 있다. 개념 오름차순 기준으로 설명한다. N개의 원소가 있을 때 1번 인덱스의 원소부터 N-1번 인덱스의 원소까지 탐색을 진행한다. 현재 인덱스를 기준으로 이전 인덱스와 비교를 한다. 만약 이전 인덱스가 더 크다면 현재 인덱스의 원소가 있어야하는 자리는 이전 인덱스이기 때문에 자리를 스왑한다. 스왑 후에도 이전 인덱스가 더 크다면 계속해서 자리를 스왑한다. 이 과정에서 이전 인덱스가 더 작거나 더 이상 비교할 원소가 없을 때는 비교를 종료한다. 위의 과정을 반복하면 정렬이 된다. 구현 10개의 숫자가 랜덤하게 나열되어 있다. for문을..

선택 정렬은 오름차순 기준일 때 범위 내에서 최솟값을 찾아 앞자리의 숫자와 자리를 변경해 나간다. 최솟값 또는 최댓값을 선택한다는 의미로 선택 정렬이라는 이름이 붙었다. 개념 오름차순 기준으로 설명한다. N개의 원소가 있을 때 0~N-1까지 탐색을 진행하여 최솟값을 찾는다. 찾은 최솟값과 0번째 인덱스에 있는 숫자와 스왑을 한다. 위의 과정을 통해 첫 번째 자리는 정렬이 된 것이다. 이후 1~N-1까지 탐색을 진행하여 최솟값을 찾고 1번째 인덱스에 있는 숫자와 스왑을 한다. 위의 과정을 반복하여 정렬을 한다. 구현 10개의 숫자가 랜덤하게 나열되어 있다. 첫 번째 for문의 i인덱스는 최솟값을 찾아서 해당 인덱스와 i 인덱스와 자리를 변경할 때 사용된다. 두 번째 for문은 i인덱스부터 탐색을 진행한다...

버블 정렬은 오름차순 기준일 때 인접한 두 개의 인접한 원소를 비교하여 더 큰 원소를 뒤로 보내는 방식을 취하고 있다. 두 개의 인접한 원소를 비교해 나가는 모습이 버블 같기 때문에 버블 정렬이라는 이름이 붙었다. 개념 오름차순 기준으로 설명한다. 첫 번째 원소와 두 번째 원소를 비교했을 때 첫 번째 원소가 크다면 두 번째 원소와 자리를 바꾼다. 이어서 두 번째 원소와 세 번째 원소를 비교한다. 위와 같은 과정을 거치면 마지막부터 가장 큰 원소들이 정렬될 것이다. 즉, N개의 원소가 있다고 가정했을 때 한 번의 순환을 통해 N번째 자리에 가장 큰 숫자가 저장되고 이제 첫 번째 원소부터 N-1까지의 수들을 비교하여 N-1번째 자리를 채운다. 구현 10개의 숫자가 나열되어 있다고 가정한다. 2중 for문을 ..

어떠한 알고리즘을 작성했을 때 알고리즘의 성능은 어떻게 측정할 수 있을까? Big-O 표기법은 알고리즘의 수행 시간을 측정하여 성능을 표기하는 것이다. 그렇다면 Big-O 표기법을 사용하는 이유와 대략적으로 본인이 설계한 알고리즘의 시간 복잡도를 어떻게 구하는지 알아보자. Big-O를 사용하는 이유 알고리즘의 성능을 측정하기 위해서 Big-O, Big-Ω, Big-θ 를 사용할 수 있다. Big-Ω : 빅 오메가는 어떠한 알고리즘이 최적의 조건에서 실행될 때 사용할 수 있는 표기법이다. 예를 들어 이미 정렬되어 있는 숫자들에 퀵 정렬을 진행하면 N만큼의 시간 복잡도를 갖게되며 더 이상 빠르게 할 수 없을 것이다. 이처럼 알고리즘이 최선의 경우 수행되는 시간을 측정할 때 사용할 수 있다. Big-θ : 빅..