ALGORITHM?

알고리즘이라는 말은 많이 들어봤을 것이다. 나도 단순한 흐름이라고만 알고 있었지 이게 왜 필요한 것인지 알아보자!

 

알고리즘

• 유한한 단계를 통해 문제를 해결하기 위한 절차나 방법
• 주로 컴퓨터 용어로 쓰이며, 컴퓨터가 어떤 일을 수행하기 위한 단계적 방법
• 즉, 어떠한 문제를 해결하기 위한 절차

컴퓨터 분야에서 알고리즘을 표현하는 방법을 크게 두 가지이다.

1. 의사 코드(슈도 코드, Pseudocode)
2. 순서도

APS(Algorithm Problem Solving) 과정의 목표 중의 하나는 보다 좋은 알고리즘을 이해하고 활용하는 것!!

그렇다면 좋은 알고리즘이란 무엇일까?

1. 정확성 : 얼마나 정확하게 동작하는가
2. 작업량  : 얼마나 적은 연산으로 원하는 결과를 얻어내는가
3. 메모리 사용량 : 얼마나 적은 메모리를 사용하는가
4. 단순성 : 얼마나 단순한가
5. 최적성 : 더 이상 개선할 여지없이 최적화되었는가

대충 어떤 것이 있는지만 알고 있자! 하나씩 배우면서 이해하게 될 것이다.

우리는 주어진 문제를 해결하기 위해 여러 개의 다양한 알고리즘이 가능한데 어떤 알고리즘을 사용해야 할까?

 

바로 알고리즘의 성능 분석이 필요하다!

특히 많은 문제에서 성능 분석의 기준으로 알고리즘의 작업량을 비교한다.

1부터 100까지의 합을 구하는 과정을 보면 왼쪽과 오른쪽의 차이는 무려 97번이나 차이 난다.

우리는 이런 작업량을 표현하기 위해서 시간 복잡도(Time Complex)를 알아야 된다.

• 실제 걸리는 시간을 측정
• 실행되는 명령문의 개수를 계산

시간 복잡도를 표시하기 위해 약속되어 있는 것이 있는데 빅-오(O) 표기법이다.

• 빅-오 표기법(Big-Oh Notation)
• 시간 복잡도 함수 중에서 가장 큰 영향력을 주는 n에 대한 항만을 표시
• 계수(Coefficient)는 생략하여 표시

만약 n개의 데이터를 입력받아 저장한 후 각 데이터에 1씩 증가시킨 후 각 데이터를 화면에 출력하는 알고리즘의 시간 복잡도는 어떻게 될까? O(n)이다.

 

요소 수가 증가함에 따라 각기 다른 시간 복잡도의 알고리즘은 아래와 같은 그래프를 보이고, 그 후 실제 실행시간을 보자.

O(1) 상수 시간 - 리스트에서 사람 1명을 찾는 시간

O(logn) 로그 시간 - 반씩 줄여가면서 검색하는 데 걸리는 시간 (이진 탐색), 피보나치 최적 탐색

O(n) 선형 시간 - 한 명이 모든 사람과 악수하는 데 걸리는 시간

O(nlogn)로그 선형 시간 - 가장 큰 수를 제 위치에 배치하는데 걸리는 시간

O(n²) 제곱 시간 - 모든 사람이 다른 모든 사람과 악수하는 데 걸리는 시간

O(n³) 세제곱 시간 - 3차원 그래프

O(2ⁿ) 지수 시간

O(n!) 계승

 

알고리즘에 대한 간단한 것들을 알아보았다. 다음 글부터는 알고리즘의 종류를 배우며 어떤 상황에서 쓰면 좋을지 알아보자!!