1. 자료구조와 알고리즘
1.1 자료구조와 알고리즘
* 프로그램 = 자료구조 + 알고리즘
ex) 최대값 탐색 프로그램 = 배열 + 순차탐색
* 자료구조
- 프로그램에서 자료들을 정리하는 여러 가지 구조
* 알고리즘
- 컴퓨터로 문제를 풀기 위한 단계적인 절차
* 자료구조의 종류
1. 스택 ex)물건을 쌓아놓는 것
2. 큐 ex) 영화관 매표소의 줄
3. 리스트 ex) 할 일 리스트
4. 트리 ex) 조직도
5. 그래프 ex) 지도
* 알고리즘의 기술 및 표현 방법
1. 자연어
- 사람이 읽기 용이
- 의미 전달 불명확성, 모호성 우려
2. 흐름도
- 직관적이고 이해하기 쉬운 알고리즘 기술 방법
- 복잡한 알고리즘은 상당히 복잡해짐
3. 유사 코드
- 알고리즘의 고수준 기술 방법
- 자연어보다는 더 구조적
- 프로그래밍 언어보다는 덜 구체적
- 알고리즘 기술에 가장 많이 이용
- 프로그램을 구현할 때는 고려해야하는 불필요한 세부사항들을 감출 수 있음
- 알고리즘의 핵심적인 내용에만 집중
- 대입 연산자로 '='가 아닌 '←'을 이용함
4. 프로그래밍 언어
- 가장 정확한 알고리즘 기술 가능
- 알고리즘을 C언어로 구현할 때 필요한 많은 세부사항들을 포함해야 함
- 알고리즘의 핵심 사항을 이해하기 쉽지 않음
1.3 알고리즘의 성능 분석
* 실행 시간 측정 방법
- 알고리즘을 실제 컴퓨터상에서 실행시킨 다음, 그 실행 시간을 측정
- 알고리즘을 구현해야 함, 고비용 발생
- 반드시 똑같은 하드웨어를 사용하여 알고리즘들의 실행 시간 측정해야 함
- 사용한 소프트웨어 환경도 중요함
* 복잡도 분석 방법
- 직접 구현하지 않고서도 대략적으로 알고리즘의 효율성을 비교할 수 있음
- 알고리즘이 수행하는 연산의 횟수를 계산하여 비교
- 일반적으로 연산의 횟수는 n의 함수
* 시간 복잡도
- 알고리즘의 실행 시간 분석
- 알고리즘을 이루고 있는 연산들이 몇 번이나 실행되는 지를 숫자로 표시
- 산술 연산, 대입 연산, 비교 연산, 이동 연산 등 기본 연산을 고려
- 알고리즘이 수행하는 연산의 개수를 계산하여 두 개의 알고리즘 비교 가능
* 공간 복잡도
- 수행에 필요한 메모리 공간 분석
* 시간 복잡도 함수 T(n)
- 연산의 실행 횟수는 고정된 숫자가 아니라 입력의 개수 n의 함수로 나타낸 것
* 빅오 표기법
- 자료의 개수가 많은 경우에는 차수가 가장 큰 항이 가장 영향을 크게 미치고 다른 항들은 상대적으로 무시될 수 있음
ex) T(n) = n^2+n=1 일 때, n = 1000 이라 하면 n^2이 약 99.9%, n이 약 0.1%를 차지
- 연산의 횟수를 대략적(점근적)으로 표기한 것
- 두 개의 함수 f(n)와 g(n)이 주어졌을 때 모든 n≥n0에 대하여 |f(n)| ≤ c|g(n)|을 만족하는 2개의 상수 c와 n0이 존재하면 f(n) = O(g(n))
- 빅오는 함수의 상한을 표시한다.
ex) n≥5이면 2n+1<10n이므로 2n+1 = O(n)
- 실행 시간이 빠른 순서의 빅오 표기법
· O(1) : 상수형
· O(logn) : 로그형
· O(n) : 선형
· O(nlongn) : 선형로그형
· O(n^2) : 2차형
· O(n^3) : 3차형
· O(2^n) : 지수형
· O(n!) : 팩토리얼형
* 최선, 평균, 최악의 경우
- 똑같은 알고리즘도 주어지는 입력의 집합에 따라 다른 실행 시간을 보일 수 있다.
1. 최선의 경우
- 실행 시간이 가장 적은 경우
- 별 의미가 없는 경우가 많음
- 찾고자 하는 숫자가 배열의 맨 처음에 있는 경우
- O(1)
2. 평균의 경우
- 평균적인 실행 시간
- 상당히 구하기 힘들 수 있음
- 모든 숫자가 균일하게 탐색된다고 가정
- (1+2+…+n)/n = (n+1)/2
- O(n)
3. 최악의 경우
- 실행 시간이 가장 오래 걸리는 경우
- 가장 널리 사용
- 계산하기 용이
- 중요한 의미를 가짐
- 찾고자 하는 숫자가 맨 마지막에 있는 경우
- O(n)