Algorithm 기초

프로그래밍의 본질

프로그래밍의 본질 : 알고리즘적 사고와 프로그래밍 언어의 문법으로 문제를 해결하는 것. 코딩은 단지 언어일 뿐.

출처 : https://www.codeit.kr/community/questions/UXVlc3Rpb246NWUzNDUyMjU4MGU1MTMzNzNkOTYxZWJj

 

 

좋은 알고리즘

좋은 알고리즘의 기준

1. 알고리즘은 명확하며 모호하지 않아야 한다.
2. 단순하고 직관적이어야 하다.
3. 다른 프로그래머들이 모를만한 난해한 기술은 쓰지 않는다.

 

 

데이터

데이터 : 컴퓨터에 저장되어 있거나 컴퓨터가 가공 및 처리하는 모든 것

정보 : 가공이나 처리가 끝난 데이터.

데이터 구조 : 데이터를 구성하고 저장하는 방법. 데이터를 식별하는 방법을 제공하고 데이터의 관계를 보여준다.알고리즘이 데이터를 빠르게 사용할 수 있도록 데이터의 구조를 단순화시켜놓아야 한다.

알고리즘 : 정해진 순서대로 문제를 해결하는 논리적인 절차.

 

 

컴퓨터는 데이터를 입력 받고 처리 과정을 가진 후 출력한다. 올바른 데이터를 입력했으나 무의미한 출력이 나올 경우는 2가지다.

1. 알고리즘이 잘못되어서 문제 해결 과정에서 오류가 난다.
2. 처리할 데이터의 관리가 제대로 이루어지지 않아 오류가 난다.

 

알고리즘 설계와 분석

알고리즘을 설계하는 것과 분석하는 것은 별개의 과정. 

1. 알고리즘 설계의 세 가지 유형
   1. 분할 정복 알고리즘 ( divide and conque algorithm) : 큰 문제를 여러 개의 작은 문제로 나눠 해결하고 결과를 결합해 하나의 해결 방법을 얻는 알고리즘. 
   2. 탐욕 알고리즘 (greedy algorithrm) : 근사치 알고리즘. 해당 순간의 최상의 결정(가장 적합한 동작)을 내려서 결과적으로 모두 종합했을 때 전체 문제의 최상의 결정에 가까운 결론을 내리는 알고리즘. (방문 판매원 문졔)
   3. 동적 프로그래밍 ( Dynamin programming) : 최적화 알고리즘. 과거에 내린 결정이 앞으로의 결정에 영향을 주는 알고리즘. 문제를 해결하는 다양한 해결 방법을 찾아서 저장한 후, 나중에 재사용 한다. (음성인식, 유전자 염기서열 분석, 연쇄 행렬 곱셈에 주로 사용)
2. 알고리즘 분석
   1. 시간 복잡도 (time complexity) : 알고리즘이 문제를 해결할 때 걸리는 시간. 알고리즘의 성능이 얼마나 효율적인지 알 수 있는 가장 일반적인 방법.
      1. 시간 복잡도를 측정하는 실제적인 방법 : 입출력 데이터의 양이 알고리즘 동작에 미치는 영향을 관찰, 기록하는 것. 그러나 정확성이 떨어지고 사용 범위가 제한적이다.
      2. 시간 복잡도를 측정하는 수학적인 방법 : 점근적 분석. 알고리즘의 성능이 최악이 되는 경계를 판단하거나, 알고리즘의 평균 성능을 찾는다. 알고리즘 사이의 점근적 증가율을 비교하기 위해 빅 오 표기법을 사용한다. 실제적인 방법보다 시간을 절약할 수 있다.
   2. 공간 복잡도 (space complexity) : 알고리즘이 문제를 해결할 때 점유하는 컴퓨터의 메모리 공간. 널리 쓰이지는 않고, 자원이 제한된 시스템에서 동작하는 프로그램을 구현하는 등 특별한 경우에 사용하는 방법.

 

빅 오 표기법

빅 오 표기법 특징

1. O : 시간 복잡도의 정도를 나타내는 복잡도의 차수
2. 알고리즘을 실행하는데 걸리는 최대 시간을 측정.
3. 알고리즘의 실행 시간이 최악인 경우를 나타내는 방법.

 

빅 오 표기법 종류 ( 위에서부터 알고리즘 성능이 좋은 순)

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

 

재귀

재귀

1. 재귀함수 : 자기 자신을 호출하는 함수. 특정 조건을 충족할 때까지 끊임없이 동작한다. 
2. 최대 재귀 깊이(maximum recursion depth) : 컴퓨터의 가용 메모리를 한계까지 호출한 재귀함수의 횟수
3. 스택 오버플로 에러 (stack overflow error) : 최대 재귀 깊이를 초과해 발생한 에러
4. 반복과는 다르다