프로그래밍 = 자료구조 + 알고리즘
컴퓨터가 효율적으로 문제를 처리하기 위해서는 문제를 정의하고 분석하여 최적의 프로그램을 작성해야한다.
- 자료(Data) : 프로그램의 처리 대상이 되는 값들
- 자료형(Data Type) : 처리할 자료의 집합과 자료에 대해 적용할 수 있는 연산자의 집합
- 연산(operation) : 어떤 일을 처리하는 과정
- 자료구조(Data Structure) : 자료를 효율적으로 표현하고 저장하고 처리할 수 있도록 정리하는 것
- 스택(Stack), 큐(Queue)
- Array List, Node List, Sequence
- Map, Dictionary
- Priority Queue
- Tree, Binary Tree, Heap, Search Tree
- Graph
- 크고 복잡하고 어려운 문제를 처리할 때
- 큰 문제는 작게 나누어 단순히 생각하기(단순화)
- 핵심적인 것에 집중하기(추상화)
- 중요정보부터 강조하기(정보은닉)
자료와 연산자의 특성을 논리적으로 추상화하여 정의한 자료형
- 추상화 : "무엇(what)"인가를 논리적으로 정의 : 알고리즘 정의
- 구체화 : "어떻게(how)"할 것인가를 실제적으로 표현 : 프로그램 구현
주어진 문제를 해결하기 위한 단계적인 절차이다.
이 절차에는 입력값과 출력값이 존재해야하며, 유한한 단계를 거쳐서 반드시 종료되어야 한다.
- 입력 : 0개 이상의 입력 존재
- 출력 : 1개 이상의 출력 존재
- 명백성 : 각 명령어의 의미는 모호하지 않고 명확해야함
- 유한성 : 한정된 수의 단계 후에는 반드시 종료한다.
- 유효성 : 각 명령어들은 실행 가능한 연산이어야한다.
알고리즘은 주로 자연어, 의사코드, 프로그래밍언어 등의 방법으로 기술할 수 있다.
알고리즘 A
(1단계) 원소의 인덱스를 id로 정의한다.
(2단계) 집합 S에 대하여 1<=id<=n까지의 합을 구하고 이를 s라 한다.
(3단계) s를 출력하고 종료한다.
알고리즘 A
(1단계) id←1,s←0
(2단계) s = s + Sid, id ← id + 1
(3단계) id <= n goto 2단계
(4단계) print s
void A(int S, int n){
int s = 0;
for(int id = 1;id<=n;id++){
s = s + S[id];
}
printf("%d\n",s);
}수학적으로 계산 가능하며, 컴퓨터를 이용해 풀 수 있는 모든 문제들을 의미한다.
- 결정 문제(decision problem)
- 탐색 문제(search problem)
- 카운팅 문제(counting problem)
- 최적화 문제(optimization problem)
- 함수형 문제(function problem)
계산 문제들 중 그 결과를 'YES' or 'NO'로 답할 수 있는 문제를 의미한다.
계산결과 얻은 후보 해들 중 가장 적절한 해를 찾는 형태의 문제를 말한다.
- 평가기준
- 정확성 : 올바른 자료 입력 시 유한한 시간 내에 올바른 결과 출력 여부
- 명확성 : 알고리즘이 얼마나 이해하기 쉽고 명확하게 작성되었는가
- 수행량 : 일반적인 연산 제외, 알고리즘 특성상 나타내는 중요 연산 모두 분석
- 실행시간, 메모리 사용량 => 측정가능
- 최적성 : 가장중요
- 자료구조로 알고리즘을 완료하는데 얼마나 많은 시간과 공간이 필요한지에 따라 이 자료구조가 좋은지 나쁜지 평가할 수 있다.
- 실행시간이 짧으면서 메모리 자원을 덜 사용하는 것이 효율적
- 일반적으로 실행시간이 메모리 공간보다 더 중요시
#include <time.h>
void main(){
clock_t start, end;
double duration;
start = clock();
// 코드
end = clock();
duration = (double)(start - end) / CLOCKS_PER_SEC;
}수행시간을 측정하는 전형적인 프로그램이다. 하지만 소프트웨어 환경에 따른 실행속도의 차이와 데이터에 따른 전혀 다른 결과 등등의 문제점도 있다.
알고리즘 효율성을 계산량으로 표현할 것이며, 계산량은 입력크기 n에 대한 실행시간을 나타낸다.
-
어느 알고리즘이 가장 빠른가, 비용이 적게 드는가, 최적이라 볼 수 있는가
-
실행과 관계없이 효율성을 평가하자
-
직접 구현하지 않고서도 대략적인 수행 시간을 분석하는 방법
-
시간 복잡도(time complexity) : 알고리즘의 수행 시간 분석
- 알고리즘을 이루고 있는 기본 연산들이 몇 번이나 수행되는지를 숫자로 표시(산술, 대입, 비교, 이동 등의 기본적인 연산)
- 입력의 개수가 n일 때, 연산의 실행횟수는 n에 따라 변한다
- 시간복잡도 T(n) → 입력의 개수 n에 대한 함수
- 실제 실행시간 보다는 명령문의 실행 빈도수에 따라 계산
-
공간 복잡도(space complexity) : 알고리즘 수행시 필요로하는 메모리 공간 분석
- 빅오(O)표기법 : 연산의 횟수를 대략적(점근적)으로 표기하여 함수의 상한을 표시하기 위한 방법
- 궁극적으로 다항식의 최고차항의 차수만 사용한다.
f(n) = 5 //=> O(1)
f(n) = 2n+1 //=> O(n)
f(n) = 3n^2 +100 //=> O(n^2)
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(n^k) < O(2^n) < O(n!)
사실상 지수형이나 팩토리얼의 복잡도를 가지면 사용하는 것이 무의미하다.
- 빅오메가 : 함수의 하한을 표시하기 위한 방법
- 빅세타 : 함수의 하하인 동시에 상한을 표시
- 최선의 경우 : 수행 시간이 가장 빠른 경우
- 찾고자 하는 숫자가 맨 앞에 있음(O(1))
- 최악의 경우 : 수행 시간이 가장 늦은 경우
- 찾고자 하는 숫자가 맨 뒤에 있는 경우(O(n))
- 평균의 경우 : 수행시간이 평균적인 경우
- 각 요소들이 균일하게 탐색 (O(n))
- 문제를 읽고 이해한다.
- 재정의와 추상화 문제를 익숙한 용어로 재정의한다.
- 어떻게 해결할지 계획을 세운다.
- 계획을 검증한다.
- 프로그램으로 구현한다.
- 어떻게 풀었는지 돌아보고, 개선할 방법이 있는지 찾아본다.
입력이 몇 개인지 주어지지 않은 경우가 있다.
while(scanf("%d %d",&a,&b)==2)
// scanf의 리턴값은 성공적으로 입력받은 변수의 개수이다.
while(cin >> a >>b)이렇게 입력을 EOF까지 받으면 된다.
fgets(s, 100, stdin);
//줄바꿈까지 입력 받는다.
scanf("%[^\n]\n", s);
// 줄바꿈을 입력받지 않기때문에 편리하다. 하지만 공백을 인식하지 않는다.#include <cstdio>
int main() {
char c;
while ((c = getchar()) && c != EOF) {
printf("%c",c);
}
return 0;
}while을 이용해서 입력을 받아 공백까지 그대로 출력할 수 있다.
scanf("%1d",a);%d사이에 숫자를 넣으면 그 길이만큼 입력을 받는다.
C언어에서 사용자 정의 데이터 타입을 만드는 경우에 쓰이는 키워드이다. 타입을 새롭게 정의하는 것이 아닌, 이미 정의되어 있는 타입에 다른 타입을 부여하는 것이다.
//typedef <type정의> <새로운 type 이름>
typedef int element;
typedef struct ListNode{
element data;
struct ListNode *link;
} ListNode;