[TIL] [CS] 검색, 알고리즘

1. 이진검색

이진검색은 정렬 등과 함께 가장 기초인 알고리즘으로 꼽히는 문제.
검색 범위를 줄여 나가면서 원하는 데이터를 검색하는 과정으로 순서대로 정렬되어있는 리스트를 두부분으로 나누고 필요한 부분에서만 탐색하도록 한 다음 원하는 값을 찾는 알고리즘 방식.
우리가 흔히 술자리에서 하는 UP & DOWN 게임을 생각하면 이해하기가 쉽다.

2. 선택정렬

선택 정렬은 여러 개의 데이터가 무작위로 있을 때 전체 데이터에서 매번 가장 작은(또는 가장 큰) 데이터를 선택하여 데이터 간의 위치를 변경하는 과정을 반복하여 데이터를 오름차순(또는 내림차순)으로 정렬할 때 사용합니다. 선택 정렬의 종류는 2가지로 나눌 수 있습니다.
초등학교 시절 키순서 친구끼리 비교하면서 섰던걸 생각하면 이해하기 쉽다.

3. 퀵정렬
기준이 되는 값을 뽑고 기준보다 작은 값을 순서 상관 없이 왼편에 기준보다 큰 값을 순서에 상관없이 오른편에 세운다.

계속해서 같은방법으로 배열을 2부분으로 쪼개는 방법이다. 여기서 기준의 값을 피벗(Pivot) 이라고 한다.

4. NP문제

각 단계에서 여러가지의 가능성을 동시에 고려할 수 있는 비결정적 알고리즘으로 다항시간내에 문제를 해결할 수 있는 문제

여행하는 외판원 문제
여러 개의 도시와 그 도시 간의 거리가 주어졌을 때, 각 도시를 정확히 한 번씩 방문하는 가장 짧은 경로를 찾는 문제이다.