[ 1주차 ] 완전탐색, 정렬, 문자열

[ 완전탐색 ]

무식하게 모두 대입해보는  'brute-force' 와같은 방법을 이용해서 컴퓨터의 빠른 계산 능력을 이용해 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법을 의미. 이렇게 가능한 방법을 전부 만들어 보는 알고리즘을 뜻한다.

완전 탐색의 방법에는 다음과 같은 방법들이 있다.

1. Brute Force: for문과 if문을 이용하여 처음부터 끝까지 탐색하는 방법
2. 비트마스크 : 비트마스크란 정수의 이진수 표현을 자료구조로 사용하는 기법이다.
3. 순열 : Permutation, 서로 다른 원소를 가진 집합에서 대상들을 선택하여 순서 있게 배열하는 방법
4. 백트래킹 : 주어진 문제의답을 구하기 위해 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘 

[ 정렬 ]

무작위로 섞여있는 숫자들을 오름차순 또는 내림차순으로 정렬해 주는 방법들

 

♥ 버블 정렬 ( Bubble Sort )

버블정렬은 가장 쉬운 알고리즘이지만 시간복잡도가 좋지않아서 실제로는 잘 사용되지 않는다. 

시간복잡도는 O(n²)이며 공간복잡도는 하나의 배열만 사용하여 정렬을 진행하기 때문에 O(n)이다.

 

♥ 선택 정렬 ( Selection Sort )

선택정렬은 시간복잡도가 O(n²)으로 버블정렬과 정렬하는 알고리즘이 버블정렬과 유사하다. 한번 순회를 하면서 가장 큰 수 또는 작은수를 찾아서 배열의 마지막 위치와 교환한다.

 

♥ 삽입 정렬 ( Selection Sort )

삽입정렬은 1부터 n까지 Index를 설정하여 현재위치보다 아래쪽을 순회하며 현재위치의 값을 현재위치보다 아래쪽으로 순회하며 알맞은 위치에 넣어주는 정렬알고리즘이다.

삽입정렬은 이미 정렬이 되어있다면 O(n)의 시간복잡도를 가지게된다. 정렬이 되어있는 경우라면 한번 순회하며 체크만 하기 때문이며 Big-O 시간복잡도는 O(n²)이다.

 

♥ 병합 정렬 ( Selection Sort )

병합정렬은 정렬할 리스트를 반으로 쪼개나가며 좌측과 우측 리스트를 계속하여 분할해 나간 후 각 리스트내에서 정렬 후 병합(merge) 정렬 후 병합하는 과정을 통해 정렬하는 알고리즘이다.

병합정렬은 가장 많이 쓰이는 정렬 알고리즘 중 하나 이며 시간복잡도는 최소 O(nlogn)을 보장하게 된다.

 

♥ 퀵 정렬 ( Quick Sort )

퀵정렬은 real-world 데이터에서 빠르다고 알려져 있어 가장 많이 쓰는 정렬알고리즘이다.
퀵정렬은 pivot을 선정하여 pivot을 기준으로 좌측과 우측으로 pivot보다 작은값은 왼쪽 pivot보다 큰값은 오른쪽으로 재배치를 하고 계속하여 분할하여 정렬하는 알고리즘이다.
최악의 경우에는 O(n²)의 비교를 수행하지만 일반적으로 O(nlogn)의 시간복잡도를 가진다.

 

[ 문자열 ]

KMP 알고리즘

 

참고  : https://takhyeongmin.github.io/2019/02/01/bitmask/, https://brenden.tistory.com/10, https://jinhyy.tistory.com/9, https://blog.encrypted.gg/732