[코드 없는] 알고리즘 1장 내용 정리

jskim4695 2024. 2. 19. 12:54

1. 데이터 구조와 알고리즘, 자료형, 빅 오 표기법

코드는 단지 문제를 해결하기 위해 프로그래머의 생각을 표현한 것에 불과하다. 이론을 포함한 배경지식을 더 많이 알수록 문제 해결을 위해 더 많은 시도를 할 수 있다. 데이터 구조와 알고리즘은 전혀 다른 개념인데, 프로그래밍의 본질은 알고리즘적 사고와 프로그래밍 언어의 문법으로 문제를 해결하는 것이다.

데이터 구조는 데이터를 구성하고 저장하는 방법을 설명하며, 데이터를 식별하는 방법을 제공하고 데이터의 관계를 보여주는 개념이다. 데이터를 담는 컨테이너쯤으로 생각하는 것이 가장 좋다.

알고리즘은 문제를 해결하기 위해 사용하는 일련의 단계다. 달리 말하면 정해진 순서대로 문제를 해결하는 방법이며 간단히 '절차'라고도 할 수 있다. 다양한 관점이 존재하지만, 항상 문제를 해결하는 논리적 단계라는 요소를 포함하고, 자연어,의사코드, 프로그래밍 언어 등으로 표현할 수 있다.

데이터 구조와 알고리즘의 관계는 서로 다른 개념이면서 상호보완적이다. 데이터 구조는 알고리즘이 다루는 데이터를 구성하며, 알고리즘이 데이터를 처리하고 사용자가 원하는 완전한 정보를 산출하는 과정에서 필요한 부분을 제공한다.

1) 기본자료형

자료형은 처리할 데이터의 속성이 무엇인지, 데이터로 수행하려는 작업이 무엇인지 컴퓨터에 알려주려고 만든 것이다. 알고리즘 동작에 필요한 데이터의 자료형이 정해져 있는 경우에는 아무리 훌륭한 알고리즘이라도 수행할 동작을 결정하지 못하고 무의미한 결과를 출력할 수 있다.

a) 불(boolean) : 논리 자료형으로 참과 거짓, 0과 1, 켜기와 끄기 등 두가지 상태를 표현할 수 있다. 이 개념은 모든 프로그래밍 언어에서 어떤 형태로든 표현할 수 있을 만큼 매우 강력하다.

b) 문자(character) : 전통적인 컴퓨터는 이진 비트로 구성된 정보를 처리하며 숫자 처리에 최적화된 반면, 자연어로 구성된 정보처리에 최적화된 자료형이다. 사람이 데이터를 더 쉽게 이해하고 기억할 수 있게 한다.

c) 정수(integer) : 숫자를 표현하는 데 정수보다 더 적합한 자료형은 없다. 단, 수학에서의 정수는 무한하지만, 컴퓨터 과학에서의 정수는 CPU 아키텍처와 메모리 용량의 한계, 프로그래밍 언어에 정해져있는 정수 범위의 제한 때문에 무한하지 않다.

d) 부동 소수점 수(floating-point number) : 소숫점을 포함한 수를 표현하는 자료형이며 정밀도는 단정도(float)/배정도(double)로 나뉜다. 단정도는 32비트로 1워드를 표현하고, 배정도는 64비트로 1워드를 표현한다. 이 밖에 128비트를 1워드로 표현하는 decimal이라는 자료형도 있다.

2) 함수

프로그래밍에서의 함수는 특정 동작을 수행하는 코드 덩어리를 뜻한다. 매개변수(파라미터) 또는 인수라고 하는 데이터를 입력으로 사용하며 때로는 결과를 반환하기도 한다. 입력을 기반으로 출력을 제공하는 수학에서의 함수와 달리 프로그래밍에서의 함수는 아무런 결과를 반환하지 않을 수 있다. 이를 C기반 언어에서는 void함수라고 한다.

매개변수(parameter)와 인수(argument)

- 매개변수 : 함수를 정의할 떄 사용하는 변수(함수 인터페이스로 쓰는 변수)를 뜻함. ex) 함수명(변수1, 변수2)
- 인수 : 함수를 호출하며 전달하는 매개변수의 실제 값을 뜻함 ex) 함수명(3, 4)

객체지향 프로그래밍 언어(OOPL)에 속하는 프로그래밍 언어에는 다른 초드의 청사진 역할을 하는 특수한 ㅋ토드가 존재한다. 이를 클래스라고 하며 클래스 내부에 있는 함수를 메소드라고 한다. 다시 말해, 메소드는 클래스의 객체 이름을 사용해 호출하는 함수를 말한다.

일부 프로그래밍 언어에선 함수를 프로시저 또는 서브루틴이라고 하기도 하는데, 일부 프로그래머 사이에선 프로시저가 값을 반환하지 않는 함수를 뜻하기도 한다.

3) 재귀와 반복

프로그래밍 영역에는 실행 도중 자기 자신을 호출하는 함수인 재귀함수를 기본으로 제공하거나 직접 정의할 수 있다. 이 재귀 함수는 보통 특정 조건을 충족할 때까지 끊임없이 동작한다. 메모리는 한계가 있으므로 재귀함수가 자기자신을 호출하는 횟수가 늘어날수록 컴퓨터의 가용 메모리 공간은 점점 줄어든다. 결국 자기자신을 호출하는 횟수의 한계인 최대 재귀 깊이를 초과해 stack overflow 에러가 발생할 수 있다.

이에 반해 반복은 특정 조건이 충족될 때까지 코드 덩어리의 실행이 되풀이되는 것을 뜻한다. 유의할 점은 재귀와 마찬가지로 종료 조건을 지정하지 않으면 에러가 발생한다는 것이다.

4) 알고리즘의 세가지 유형

a) 분할 정복 알고리즘(divide and conquer) : 큰 문제를 여러 개의 작은 문제로 나눠 해결하고 결과를 결합해 하나의 해결방법을 얻는 알고리즘

b) 탐욕 알고리즘(greedy) : 실행되는 순간마다 최상의 결정(가장 적합한 동작)을 내리는 알고리즘이다.

c) 동적 프로그래밍 알고리즘(dynamic) = 동적 계획법

탐욕 알고리즘과 대조를 이루는 것으로 과거에 내린 결정이 앞으로의 결정에 영향을 주는 알고리즘이다. 둘 모두 문제를 더 작은 단위로 나누는 데 중점을 둔다는 공통점이 있지만 그리디는 특정 순간에 최적인 해결방법을 찾고 동적 프로그래밍은 다양한 해결방법을 찾아 저장한 후 나중에 재사용한다는 차이가 있다.

5) 알고리즘의 분석방법

시간 복잡도 : 주어진 입력에 따라 알고리즘이 문제를 해결할 때 걸리는 시간을 뜻한다. 시간 복잡도를 이용하는 알고리즘 분석은 알고리즘의 성능이 얼마나 효율적인지 알 수 있는 가장 일반적인 방법이다.
공간 복잡도 : 알고리즘이 문제를 해결할 때 점유하는 컴퓨터 메모리의 공간을 뜻한다. 그리 널리 사용되는 방식은 아닌데, 자원이 제한된 시스템에서 동작하는 프로그램을 구현하는 것과 같이 특별한 경우에 사용하는 분석방법이다.

알고리즘의 효율성을 수학적으로 판단하는 방법은 점근적 분석(asymptotic analysis)라고 하는데 본질은 수학적으로 알고리즘 성능의 한계를 증명하는 것이므로 실제적인 방법보다 많은 시간을 절약할 수 있다. 구체적으로는 성능이 최악이 되는 경계를 판단하거나 평균 성능으로 찾으며 이때 알고리즘 사이의 점근적 증가율을 비교하기 위해 빅 오 표기법을 사용한다.

6) 빅 오 표기법

알고리즘의 효율성을 설명할 때는 빅 오메가, 리틀 오메가, 빅 오, 리틀 오, 세타 등 다양한 표기법이 존재하며 각 표기법의 용도는 정해져있다. 이런 것들 중에 가장 많이 사용되는 것이 빅 오(O)인데, 대문자 O는 시간 복잡도의 정도를 나타내는 표기법인 차수(order)를 뜻하며 주로 이것으로 표기하는 관례가 생기면서 자연스레 빅 오 표기법이라 부르게 됐다.

오메가는 최소 시간, 세타는 최소 및 최대, 빅오는 최대시간을 측정한다. 빅 오 표기법의 본질은 알고리즘의 실행 시간이 최악인 경우를 나타내는 것이다.

분류는 다음과 같다.

O(1) : 상수형 알고리즘이며, 데이터 입력량과 무관하게 실행시간이 일정하다.
O(n) : 선형 알고리즘이며, 데이터 입력량에 비례하여 실행 시간이 늘어난다.
O(logn) : 로그형 알고리즘이며, 시간이 선형적으로 증가하면 n이 기하급수적으로 증가한다. 데이터 입력량이 늘어날수록 단위 입력당 실행 시간이 줄어든다는 뜻이다.
O(nlogn) : 선형-로그형 알고리즘이며, 데이터 입력량이 n배 늘어나면 실행 시간이 n배 조금 넘게 늘어난다.
O(n^2) : 2차 알고리즘이며, 데이터 입력량의 제곱에 비례하여 실행 시간이 늘어난다.
O(2^n) : 지수형 알고리즘이며, 데이터 입력이 추가될 때마다 실행 시간이 2배로 늘어난다.
O(n!) : 계승(팩토리얼)형 알고리즘이며, 데이터 입력이 추가될 때마다 실행시간이 n배로 늘어난다.

위에서부터 성능이 좋은 순서대로 나열한 것이다.

출처: <코드 없는 알고리즘과 데이터 구조> 암스트롱 수베로 | 동양북스