오늘은 알고리즘에 관해 공부해 보겠습니다!
가장 먼저, 알고리즘이 무엇인지 알아보겠습니다.
1. 알고리즘이란?
어떤 문제를 해결하기 위한 절차, 방법, 명령어들의 나열입니다.
같은 문제를 풀더라도 알고리즘을 어떻게 구성하는지에 따라
오래 걸릴 수도 있고, 오류가 생길 수도 있습니다.
따라서 알고리즘은 효율적이고
정확하게 만드는 것이 중요합니다.
아래 예시를 통해 같은 문제에 대해 다른 알고리즘을 적용하면
어떻게 되는지 살펴보겠습니다.
1-1. 정확한 알고리즘
전화번호부에서 ‘홍길동’을 찾는다고 가정해 보겠습니다.
이때 ‘홍길동’이라는 이름이 나올 때까지 맨 앞 페이지부터 한 장씩 펼쳐 볼 수 있습니다.
첫 번째 페이지를 펼쳤을 때 ‘홍길동’이라는 이름이 있는지 확인하고,
없으면 다음 페이지로 넘기는 방식으로 ‘홍길동’이 나올 때까지 계속 반복하는 것이죠.
이 방법을 사용한다면 전화번호부에 ‘홍길동’이라는 이름이 있다면
언젠가는 찾을 수 있을 것입니다.
하지만 이렇게 한 번에 한 페이지씩 보는 알고리즘은
정확하지만 매우 오래 걸리고 비효율적입니다.
최악의 경우 가장 마지막 페이지에 찾는 이름이 있을 수 있기 때문이죠.
이 문제를 개선하기 위해 한 번에 두 페이지를 넘기게끔 알고리즘을 개선하면
1페이지 > 3페이지 > 5페이지
이런 식으로 페이지를 넘기며 찾을 수 있습니다.
하지만 이렇게 두 페이지씩 넘기게 되면
‘홍길동’이 있는 페이지를 그냥 넘어갈 수도 있을 것입니다.
물론 ‘홍길동’이 있는 페이지를 넘어갔을 경우
이전 페이지를 확인하라는 명령을 추가하면 되지만
이 알고리즘도 문제를 해결하기에 가장 효율적인 방법은 아닌 것 같습니다.
1-2. 정확하고 효율적인 알고리즘
이번에는 더 효율적인 알고리즘을 적용하여 ‘홍길동’을 찾아보겠습니다.
전화번호부가 이름순으로 정렬되어 있다고 하면
전화번호부 가운데를 펼쳐서 ‘홍길동’이 지금 페이지보다 앞부분에 있는지,
뒷부분에 있는지 체크할 수 있습니다.
(만약 가운데를 펼쳤을 때 ‘최철수’가 있다면 홍길동은 뒷부분에 있겠죠!)
홍길동이 지금 페이지보다 뒷부분에 있다면
남은 절반에 대해 똑같은 알고리즘을 수행합니다.
마지막 한 페이지가 남을 때까지 동일하게 계속 수행하면
마지막 남은 한 페이지는 ‘홍길동’이 있거나 없거나 둘 중 하나일 것입니다.
이 알고리즘을 사용하면 전화번호부가 총 1,024 페이지고
가장 마지막 페이지에 ‘홍길동’이 있다고 가정해도
10단계 만에 페이지를 찾을 수 있습니다.
즉, 최악의 상황에도 10단계만 거치면 되는 것입니다.
이는 처음에 생각했던 알고리즘보다 효율적입니다.
2. 알고리즘의 속도는 어떻게 표현할까?
알고리즘이 어떤 문제를 해결하는 데 걸리는 시간을 시간 복잡도라고 합니다.
알고리즘에 있어서 시간복잡도는 매우 중요한데요.
그 이유는 바로 컴퓨터 효율과 관련이 있습니다.
만약 문제를 해결하는 데 시간이 오래 걸린다면,
그 프로그램이 CPU를 차지하는 시간이 길어지고
그렇게 되면 결국 CPU가 다른 일을 처리하지 못하기 때문에
그만큼 컴퓨터의 효율이 떨어질 수 있습니다.
따라서 알고리즘에 있어서
문제를 해결하는 데 걸리는 시간은 매우 중요하며,
이를 고려해서 만들어야 합니다.
이번 포스팅에서는 특정 알고리즘의 실행시간을 표기하는 여러 방법 중
Big-O(빅오) 표기법과 Ω(오메가) 표기법에 대해서 알아보겠습니다.
3. Big O 표기법
Big O표기법은
알고리즘 실행 시간의 상한을 나타내는 방법입니다.
즉, 최악의 실행시간을 나타내는 표기법이죠.
일반적으로 빅오 표기법은 다음과 같이
알고리즘으로 작업을 완료할 때까지 걸리는
절차 수 n을 이용해서 표기합니다.
3-1. 예시를 통해 빅오 표기법 살펴보기
[첫 번째 알고리즘 - 빨간색 선]
가장 먼저, 한 번에 한 페이지씩 넘겨서 찾는 방법입니다.
이 방법은 최악의 경우, ‘홍길동’이 마지막 페이지에 있어
전화번호부의 모든 사람의 이름을 확인해야 합니다.
따라서 소요 시간의 상한은 O(n)가 됩니다.
[두 번째 알고리즘 - 노란색 선]
두 페이지씩 넘기는 방법의 경우에도
첫 번째 방법과 마찬가지로 소요 시간의 상한은 O(n)입니다.
두 페이지씩 넘기면서 찾는데
왜 소요 시간의 상한은 첫 번째 방법과 동일할까요?
문제가 계속 커진다고 가정해 보겠습니다.
즉, n이 계속 커지는 거죠.
이렇게 문제가 계속 커진 그래프를 줌아웃하게 되면 다음과 같이
노란색 선(n/2)과 빨간색 선(n)은 계속 가까워질 것이고
결국 겹쳐 보이게 될 것입니다.
즉, n이 매우 커지면 1/2은 큰 의미가 없어지겠죠.
따라서 소요 시간의 상한은 O(n)가 됩니다.
[세 번째 알고리즘 - 초록색 선]
문제를 절반씩 줄이는 걸 반복한 마지막 알고리즘의 경우
소요 시간의 상한은 O(log n)입니다.
정확하게 말하면 O(log2 n)이지만,
두 번째 알고리즘과 마찬가지로 문제가 커지면
결국 밑이 뭐든 상관이 없어지기 때문에
O(log n)로 표현합니다.
3-2. 자주 사용되는 Big O표기
다음은 실행 시간을 나타내기 위해
자주 사용되는 Big O 표기입니다.
O(1) 상수시간
O(log n) 로그 시간
O(n) 선형 시간
O(n log n) 선형 로그 시간
O(n^2) 2차 시간
물론 위에 적은 다섯 개 말고 다른 실행 시간도 있습니다.
다음 포스팅에서는 다양한 알고리즘에 대해 배우면서
알고리즘별로 소요 시간의 상한을 함께 알아보겠습니다!
4. Ω (오메가) 표기법
Big O표기법이 알고리즘 실행 시간의 상한을 나타낸 것이라면,
Ω표기법은 알고리즘 실행 시간의 하한을 나타내는 것입니다.
즉, 최상의 경우를 나타냅니다.
위에서 봤던 전화번호부에서 ‘홍길동’을 찾는
세 개의 알고리즘 모두 운이 좋으면 처음 펼친 페이지에
원하는 이름이 있을 수 있기 때문에
실행 시간의 하한은 Ω(1)가 됩니다.
오늘은 알고리즘 공부에 있어서 기초적인 내용을 알아봤습니다!
다음 포스팅에서는 오늘 배운 내용을 기반으로
선택 정렬, 버블 정렬 등 더 다양한 내용을 공부해 보겠습니다!
출처: CS50
'Algorithm' 카테고리의 다른 글
| Swift) 재귀란?/재귀 함수/팩토리얼/꼬리 재귀 (0) | 2024.06.28 |
|---|---|
| Swift) 병합 정렬(합병 정렬/Merge Sort) (0) | 2024.06.06 |
| Swift) 버블 정렬이란/버블 정렬 구현해 보기 (0) | 2024.05.29 |
| Swift) 선택 정렬이란/선택 정렬 구현해 보기 (0) | 2024.05.16 |
