AIB 섹션 5 컴퓨터공학 N524 Algorithm Intermediate

1 분 소요

오늘: 코드 분석에 익숙해지기. 분할정복과 재귀, 퀵정렬과 병합정렬

알고리즘: 어떤 문제를 해결하기 위한 단계적 절차. brute force algorithm. 가장 쉽게 생각해서 직관적이지만 전혀 효율적이지 않을 수 있는 알고리즘. 좋은 알고리즘은 정확성과 효율성이 좋다. 효율성 판단은 코드 길이, 몇 초 걸리는지로 가능.

복잡한 문제를 여러 부분으로 나누어서 해결하는 방법.

재귀와 분할정복의 차이: 재귀는 자기 자신을 호출하여 같은 코드를 사용하는데, 분할정복은 비슷한 작업을 이어서 진행한다. 나누어서 문제를 풀고 답에 병합시키기. 더이상 진행될 수 없거나 전체 답을 구한 경우 종료.

문제를 분할할 수 있는지, 병합하여 답을 구하는게 효율적인지.

시간복잡도 최악 $O(n^2)$: 나눌 때 1개와 n-1개로 계속 나누는 경우 그렇게 된다. 이미 정렬된 데이터에 대해 그러함. 평균 $O(n \log n)$: 절반으로 계속 분할하는 경우

작동: 기준(피벗)을 정해서 그 값보다 큰 list, 작은 list로 나누어 각각의 list에 대해 다시 진행

불안정정렬: 즉 동일한 값에 대해서도 정렬을 진행함.

피벗이라는 별도의 노드를 정하고 이에 대해 재귀적으로 수행하기 때문에 평균적으로 병렬정렬보다는 빠르다. 한정적인 범위 내에서 데이터를 정렬하기 때문에 캐시를 덜 사용하고 하드웨어적으로 효율적이다.

시간복잡도 항상 $O(n \log n)$.

작동: 2씩 나누어서 맨 끝에서부터 한 단계씩 올라가면서 2분할 된 것의 각각을 비교해서 나열한다.

안정정렬: 동일한 값에 대해 기존 순서가 유진된다.

안정적이기 때문에 중복에 영향을 덜 받는다. 퀵정렬은 성능 편차가 크고 피벗을 다루기 어려울 수 있기 때문에 이 경우 병합정렬을 선호한다.

이것들을 의사코드로 구현할 수는 있어야 한다. 즉 개념 알고 있어야 함.

참고