read

프로그래밍은 컴퓨터로 문제를 해결하는 것이다. 그렇다면 프로그래밍 능력은 “컴퓨터를 이용하여 얼마나 주어진 문제를 잘 해결하는가”에 달렸을 것이다. 프로그래밍을 잘하기 위한 요소는 무엇일까?

알고리즘은 컴퓨터 프로그래밍에서 가장 중요한 요소 중에 하나이다. 이는 프로그램의 성능 및 품질에 영향을 미치고, 좋은 알고리즘은 좀 더 빠른 시간 혹은 몇배는 빠른 시간안에 작동한다. 그렇다면 알고리즘은 무엇이고, 좋은 알고리즘은 어떻게 구분하는가?

이 글에서는 기본적인 알고리즘의 개념과 알고리즘 복잡도 분석 관련 내용을 정리해보았다.

Algorithm

컴퓨터로 주어진 문제를 풀기 위한 절차.

정의

• 입력 : 0개 이상의 입력이 존재하여야 한다.
• 출력 : 1개 이상의 출력이 존재하여야 한다.
• 명백성 : 각 명령어의 의미는 모호하지 않고 명확해야 한다.
• 유한성 : 한정된 수의 단계 후에는 반드시 종료되어야 한다.
• 유효성 : 각 명령어들은 실행 가능한 연산이여야 한다.

기술 방법

1. 자연어(영어, 한국어 등등)
2. 흐름도(Flow Chart)
3. 유사 코드(pseudo-doce)

알고리즘 풀이 절차

파인만 알고리즘

1. 칠판에 문제를 적는다.
2. 골똘히 생각한다.
3. 칠판에 답안을 적는다.

2번과 3번 사이에 대체 무슨일이 생겼는지 본인만 알듯하다..

일반적인 풀이 절차

1. 문제를 읽고 이해한다.
2. 문제를 익숙한 용어로 재정의한다.
3. 어떻게 해결할지 계획을 세운다.
4. 계획을 검증한다.
5. 프로그램으로 구현한다.
6. 어떻게 풀었는지 돌아보고, 개선할 방법이 있는지 찾아본다.

문제풀이를 위한 질문들

1. 비슷한 문제를 풀어본 적이 있던가?
2. 단순한 방법에서 시작할 수 있을까?
3. 내가 문제를 푸는 과정을 수식화할 수 있을까?
4. 문제를 단순화할 수 없을까?
5. 그림으로 그려볼 수 있을까?
6. 수식으로 표현할 수 있을까?
7. 문제를 분해할 수 있을까?
8. 뒤에서부터 생각해서 문제를 풀 수 있을까?
9. 순서를 강제할 수 있을까?
10. 특정 형태의 답만을 고려할 수 있을까?

자주하는 실수

1. 산술 오버플로우
2. 배열 범위 밖 원소에 접근
3. 일관되지 않은 범위 표현 방식 사용
4. Off-by-one 오류
5. 컴파일러가 잡아주지 못하는 상수 오타
6. 스택 오버플로우
7. 다차원 배열 인덱스 순서 바꿔 쓰기
8. 잘못된 비교 함수 작성
9. 최소,최대 예외 잘못 다루기
10. 연산자 우선순위 잘못 쓰기
11. 너무 느린 입출력 방식 선택
12. 변수 초기화 문제
13. 실수값 처리

디버깅과 테스팅

디버깅

1. 작은 입력으로 테스트
2. 단정문 사용
3. 계산 중간 결과 출력

테스팅

스캐폴딩 샘플 입력을 자동 생성하는 코드를 통하여 알고리즘 테스트

성능분석

필요성

• 처리할 데이터의 규모의 증가.
• 상용 프로그램의 메모리 사용량 증가.

측정방법

• 실행 시간 측정 방법(시간 복잡도)
  • 동일한 조건에서 다른 알고리즘의 연산 시간 비교
  • 사용 소프트웨어 환경, 똑같은 하드웨어 등 제약조건이 많음.
  • T(N)을 비교 [입력값 $N$에 대한 시간 복잡도 함수]
• 기억 공간 분석(공간 복잡도)
  • 알고리즘이 사용하는 기억 공간 분석.
  • 보통 시간 복잡도 분석을 사용
  • 특정 알고리즘이 수행하는 연산의 개수를 계산하여 알고리즘을 비교.

대부분 알고리즘이 차지하는 공간보다는 실행 시간에 더 관심이 많다.

빅오 표기법

• 일반적으로 입력의 개수 n과 시간 복잡도 함수 T(n)의 관계는 상당히 복잡함.
• 하지만, 자료의 개수가 많을 경우에는 차수가 가장 큰 항이 가장 영향을 크게 미치고 다른 항들은 상대적으로 무시될 수 있음.

증명

두개의 함수 $f(n)$과 $g(n)$이 주어졌을 때, 모든 $n>=n_0$에 대하여 $|f(n)|<=c|g(n)|$을 만족하는 2개의 상수 $C$와 $n_0$가 존재하면, $f(N)=O(g(N))$이다.

빅오 표기법에 따른 알고리즘의 실행 시간 비교

$O(1)< O(logN) < O(N) < O(NlogN) < O(N^2) < O (2^N) < O(N!)$

기타

• 빅 오메가 표기법, 빅 세타 표기법 등이 있지만, 빅 오 표기법을 주로 사용.

최선, 평균, 최악의 경우

• 최선 : 실행 시간의 가장 적은 경우를 고려
• 평균 : 평균 실행 시간을 고려
• 최악 : 실행 시간이 가장 오래 걸리는 경우를 고려

  보통 최악의 경우를 알고리즘의 시간 복잡도 척도로 잡음. 계산이나 경우를 계산하였을 때 최악의 경우가 가장 합리적.

시간복잡도 분석

시간 복잡도(Time complexity)는 가정 널리 사용되는 알고리즘의 수행 시간 기준으로, 알고리즘이 실행되는 동안 수행하는 기본적인 연산의 수를 입력의 크기에 대한 함수로 표현한 것.

선형 시간 알고리즘

$O(N)$

선형 이하 시간 알고리즘

이진 탐색

지수 시간 알고리즘

다항 시간 알고리즘

$O(N^k)$

$O(2^N)$

Problem	Number of iteration	Big $O$
Moving average	$N$	$O(N)$
Binary search	$logN$	$O(logN)$
Set cover	$N \cdot M \cdot 2^M$	$O(N \cdot M \cdot 2^M)$