알고리즘과 데이터구조

알고리즘이란 간단하게 말하면 문제를 해결하기 위한 논리적 단계이다. 알고리즘은 자연어, 코드등으로 표현할 수 있는데 어렵고 이해하기 힘든 알고리즘 보다 간단하고 이해하기 쉬운 알고리즘이 더 강력하고 유용하다.

데이터구조와 알고리즘은 서로 다른 개념이면서 상호 보완적이다. 데이터구조는 알고리즘이 다루는 데이터를 구성하며 알고리즘이 데이터를 처리하고 원하는 정보를 산출하는 과정에서 필요한 부분을 담당한다.

함수는 입력을 받아 어떤 처리과정을 수행한 후 출력한다. 함수는 매개변수(파라미터) 또는 인수라고 하는 데이터를 입력으로 사용하며 때로는 결과를 반환한다. 프로그래밍에서의 함수는 입력이 있어도 출력이 없을 수 있다. 이를 void함수라 한다.

• 매개변수: 함수를 정의할 때 사용하는 변수
• 인수: 함수를 호출하며 전달하는 매개변수의 실제 값

재귀는 실행도중 자기 자신을 호출하는 것이다. 보통 특정 조건을 만족할 때 까지 끊임없이 동작하는데, 컴퓨터의 메모리는 한계가 있으므로 최대 재귀 깊이를 초과하면 스택 오버플로우 에러가 발생 할 수 있다.

반복은 재귀와 혼동해서는 안되는 또 다른 개념으로, 특정 조건을 충족할 때까지 코드 덩어리의 실행이 되풀이되는 것을 뜻한다.

알고리즘의 세가지 유형

• 분할 정복 알고리즘: 큰 문제를 여러개의 작은 문제로 나눠 해결하고 결과를 결합해 하나의 해결방법을 얻는다.
• 탐욕 알고리즘: 실행되는 순간마다 최상의 결정을 내린다. 그러나 문제 전체를 해결하는 최적의 결정일지는 장담할 수 없다.
• 동적 프로그래밍 알고리즘: 과거에 내린 결정이 앞으로의 결정에 영향을 준다. 다양한 해결방법을 찾아 저장한 후 나중에 재사용한다.

탐욕 알고리즘은 근사치를 구하는데 유용하고, 동적 프로그래밍 알고리즘은 최적화 하는데 유용하다.

알고리즘 분석

알고리즘의 효율성을 분석할 때는 시간 복잡도와 공간 복잡도를 이용한다.

• 시간 복잡도: 주어진 입력에 따라 알고리즘이 문제를 해결하는데 걸리는 시간
• 공간 복잡도: 알고리즘이 문제를 해결할 때 점유하는 컴퓨터 메모리

가장 자주 사용되는 것은 시간 복잡도이며, 공간 복잡도는 자원이 제한된 시스템에서 프로그램이 구현하는 것과 같이 특별한 경우에 사용한다.

알고리즘의 효율성을 수학적으로 판단하는 방법은 최악의 경우, 최상의 경우, 평균을 측정하는 등 여러가지가 있다. 이런 효율성을 설명할 때는 보통 빅 오 표기법을 이용한다.