알고리즘이란?

 

우주의 비밀을 파헤치든 21세기의 직업을 구하든
기본적인 컴퓨터 프로그래밍은 반드시 배워야 합니다.
-스티븐 호킹

 

 

알고리즘이란?

어떤 문제를 해결하기 위해 밟아 나가는 연속적인 단계

 

알고리즘은 컴퓨터 과학의 기본 개념이지만,

공식적으로 정의되지는 않았다.

 

그 중 잘 알려진 것은 도널드 커누스의 정의이다.

: '입력을 기반으로 출력을 생성하는 명확하고, 효율적이며 유한한 프로세스'

 

즉, 명확함, 효율성, 유한함이라는 키워드가 중요하며 + 정확성을 추가로 하는 경우도 있음.

 

시간의 복잡도(Time Complexity)

상수시간 → 로그시간 → 선형시간 → 선형 로그 시간 → 2차 시간 → 3차 시간 → 지수 시간

 

공간 복잡도(Space Complexity)

: 알고리즘의 실행을 완료할 때까지 필요한 자원의 양,

즉 고정 공간, 데이터 구조 공간, 임시 공간의 메모리를 얼마나 사용하는지 나타낸다.

 

고정공간: 프로그램 자체가 차지하는 메모리

자료구조 공간: 데이터 세트,

                      예를 들어 탐색의 대상이 되는 리스트를 저장하는데 필요한 메모리

임시 공간: 알고리즘에서 중간 처리를 위해 사용하는 메모리,

                예를 들어 데이터 전송을 위해 임시로 리스트 사본을 만들 때 필요한 메모리

 

복잡도가 중요한 이유

알고리즘을 최적화하기 위해서는 먼저 '규모'에 대해 이해해야 한다.

 

예를 들어,

for 루프가 두 번 중첩된 0(n**2) 알고리즘을 고려해보자.

이 알고리즘을 최적화 하기 위해서는

중첩된 for 루프를 사용하지 않을 수 있는지

즉! 알고리즘의 규모를 줄일 수 있는지 판단하는 것이 중요하다.

중첩되지 않는 알고리즘의 시간 복잡도는 0(n)이 되고

0(n**2)인 알고리즘을 조정하여 아무리 효율을 올린다고 해도

0(n)으로 고쳐 쓰는 것에는 비교할 수 없다.

 

 

 

출처: Althoff, C. (2023). 나의 첫 알고리즘+자료구조 with 파이썬. 한빛미디어.