알고리즘이란?

많이들 들어봤을 알고리즘이란 문제를 해결하기 위한 방법을 논리적 절차에 따라 체계적으로 정리한 것을 말한다. 주로 입력(Input) - 처리(Process) - 출력(Output) 과정을 거치며 다양한 정렬 시스템을 가지고 있다.
쉽게 말해서 우리가 무슨 일을 하기 위해서는 생각을 하고 과정을 거쳐서 결과를 만들어 내는 것이다. 예를 들어서 우리가 회사에 나가기 위해서는
1. 일어난다.
2. 아침밥을 먹는다.
3. 샤워를 한다.
4. 화장품을 바른다.
5. 옷을 입는다.
6. 밖으로 나간다.
이렇게 무언가의 결과를 내기 위해서 순서를 갖추는 것도 알고리즘 이라고 할 수 있다.

재귀함수

함수 내에서 자기 자신을 호출하는 방법이다. 그렇기에 반복적으로 동일한 코드 블록이 실행되기에 종료 조건이 필요하다. 재귀함수는 순환적인 문제들을 수행하는데 특별화 되어 있어서 병합 정렬, 퀵 정렬 등의 알고리즘에서 활용된다.

분할 정복

문제를 작은 문제로 분할하여 푸는 것을 말한다. 작은 문제는 즉시 결과를 가져와서 구하고, 그러지 아니한 것은 분할하여 문제를 풀어 전체 문제의 답을 구한다. 즉, 재귀적인 구조를 가지며 크기에 따른 성능 향상이 가능하다.

정렬 알고리즘

정렬에 완벽한 정렬은 없다 상황에 따라 가장 적합한 정렬은 있을지라도 어떤 상황에서든 좋은 최고의 정렬은 없다. 그렇기에 설명할 정렬은 전부 외워두는게 좋다.

선택정렬

시간복잡도 - 0(n^2)
공간복잡도 - 0(1)
불안정 정렬
첫 번째 숫자를 마지막 자료까지 차례대로 비교하여 가장 작은 값을 찾아 첫 번째에 놓고,
두 번째 자료를 마지막 자료까지 차례대로 비교하여 작은 값부터 하나씩 선택하여 정렬하고 이 반복을 마지막까지 반복하여 오름차순으로 만드는 것을 선택 정렬이라고 한다.

( 2, 3, 1, 4, 5) 의 순서대로 있다면 1을 처음으로 보낸다
( 1, 3, 2, 4, 5) 다음은 두 번째 자리에서 3과 2를 바꾼다
( 1, 2, 3, 4, 5)

삽입정렬

시간복잡도 - 0(n^2)
공간복잡도 - 0(1)
안정 정렬
데이터를 하나씩 꺼내어 정렬된 자료 중 적합한 위치에 삽입하여 정렬

(5, 4, 1, 2, 3) 의 순서대로 있다면 1을 첫 번째 자리로 옮기고 나머지 숫자르 밀어낸다
(1, 5, 4, 2, 3) 다음으로 2를 두 번째 자리로 보내고 나머지를 밀어낸다
(1, 2, 5, 4, 3) 오름차순이 될 때까지 반복한다
(1, 2, 3, 4, 5)

버블 정렬

시간복잡도 - 0(n^2)
공간복잡도 - 0(1)
안정정렬

• 서로 인접한 데이터를 비교하며 오름차순으로 정렬

  (6, 3, 1, 7, 9, 2, 4, 5, 8) 이룬 순서로 있으면 맨앞의 6과 3이 바뀌어서
  (3, 6, 1, 7, 9, 2, 4, 5, 8) 이 되고 6과 1이 바뀌어서
  (3, 1, 6, 7, 9, 2, 4, 5, 8) 순서가 된다 이를 반복하여
  (1, 2, 3, 4, 5, 6, 7, 8, 9) 순서가 되면 정렬은 멈춘다

병합 정렬

시간복잡도 - 0nlog^2n
공간복잡도 - 0nlog^2n
안정정렬
데이터를 2분할하여 정렬 후 각각 해결한 다음, 결과를 모아서 가장 처음의 문제를 해결하는 방식이다.

(3, 2, 5, 4, 1, 8, 7, 6) 를 2분할로 나뉘어서
(3, 2, 5, 4), (1, 8, 7, 6,)으로 나눈다 여기서 한번 더 나누고
(3, 2), (5, 4), (1, 8), (7, 6)으로 나눈 다음 정렬한다
(2, 3), (4, 5), (1, 8), (6, 7)다음에 나눈 것을 합친다
(2, 3, 4, 5), (1, 6, 7, 8)
(1, 2, 3, 4, 5, 6, 7, 8)이 된다.

퀵 정렬

시간복잡도 - 0nlog^2n
공간복잡도 - 0nlog^2n
불안정 정렬
피벗을 설정한 뒤 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮겨지고 큰 요소들은 모두 피벗의 오른쪽으로 옮겨진다.

(1, 3, 8, 4, 5, 2, 9, 7, 6) 에서 5를 피벗으로 세운 뒤 왼쪽에는 작은 수 오른쪽에는 높은 수로 정렬한다
(1, 3, 4, 2) (5) (8, 9, 7, 6) 다음으로 왼쪽에는 3을 피벗으로 오른쪽은 7을 피벗으로 세운다
(1, 2, 3, 4) (5) (6, 7, 8, 9) 오른차순으로 순서대로 완료했으면 최종적으로 합친다
(1, 2, 3, 4, 5, 6, 7, 8, 9)