Algorithm

프로그래밍 = 자료구조 + 알고리즘

컴퓨터가 효율적으로 문제를 처리하기 위해서는 문제를 정의하고 분석하여 최적의 프로그램을 작성해야한다.

• 자료(Data) : 프로그램의 처리 대상이 되는 값들

• 자료형(Data Type) : 처리할 자료의 집합과 자료에 대해 적용할 수 있는 연산자의 집합

  • 연산(operation) : 어떤 일을 처리하는 과정

• 자료구조(Data Structure) : 자료를 효율적으로 표현하고 저장하고 처리할 수 있도록 정리하는 것

  • 스택(Stack), 큐(Queue)

  • Array List, Node List, Sequence

  • Map, Dictionary

  • Priority Queue

  • Tree, Binary Tree, Heap, Search Tree

  • Graph

자료의 추상화(Data Abstraction)

• 크고 복잡하고 어려운 문제를 처리할 때

  • 큰 문제는 작게 나누어 단순히 생각하기(단순화)

  • 핵심적인 것에 집중하기(추상화)

  • 중요정보부터 강조하기(정보은닉)

추상 데이터 타입(ADT : Abstract Data Type)

자료와 연산자의 특성을 논리적으로 추상화하여 정의한 자료형

• 추상화 : "무엇(what)"인가를 논리적으로 정의 : 알고리즘 정의

• 구체화 : "어떻게(how)"할 것인가를 실제적으로 표현 : 프로그램 구현

알고리즘(Algorithm)

주어진 문제를 해결하기 위한 단계적인 절차이다.

이 절차에는 입력값과 출력값이 존재해야하며, 유한한 단계를 거쳐서 반드시 종료되어야 한다.

조건

• 입력 : 0개 이상의 입력 존재

• 출력 : 1개 이상의 출력 존재

• 명백성 : 각 명령어의 의미는 모호하지 않고 명확해야함

• 유한성 : 한정된 수의 단계 후에는 반드시 종료한다.

• 유효성 : 각 명령어들은 실행 가능한 연산이어야한다.

표현방법

알고리즘은 주로 자연어, 의사코드, 프로그래밍언어 등의 방법으로 기술할 수 있다.

자연어

알고리즘 A
(1단계) 원소의 인덱스를 id로 정의한다.
(2단계) 집합 S에 대하여 1<=id<=n까지의 합을 구하고 이를 s라 한다.
(3단계) s를 출력하고 종료한다.

의사코드(shudo code)

알고리즘 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);
}

순서도(Flow chart)를 이용한 도식화 표현

계산 문제

수학적으로 계산 가능하며, 컴퓨터를 이용해 풀 수 있는 모든 문제들을 의미한다.

• 결정 문제(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;
}

import time
start_time = time.time() # 시간측정 시작

# program code

end_time = time.time() #시간측정 종료
print("time : ", end_time - start_time) # 수행시간 출력

수행시간을 측정하는 전형적인 프로그램이다. 하지만 소프트웨어 환경에 따른 실행속도의 차이와 데이터에 따른 전혀 다른 결과 등등의 문제점도 있다.

복잡도 분석

알고리즘 효율성을 계산량으로 표현할 것이며, 계산량은 입력크기 n에 대한 실행시간을 나타낸다.

• 어느 알고리즘이 가장 빠른가, 비용이 적게 드는가, 최적이라 볼 수 있는가

• 실행과 관계없이 효율성을 평가하자

• 직접 구현하지 않고서도 대략적인 수행 시간을 분석하는 방법

• 시간 복잡도(time complexity) : 알고리즘의 수행 시간 분석

  • 알고리즘을 이루고 있는 기본 연산들이 몇 번이나 수행되는지를 숫자로 표시(산술, 대입, 비교, 이동 등의 기본적인 연산)

  • 입력의 개수가 n일 때, 연산의 실행횟수는 n에 따라 변한다

  • 시간복잡도 T(n) → 입력의 개수 n에 대한 함수

  • 실제 실행시간 보다는 명령문의 실행 빈도수에 따라 계산

• 공간 복잡도(space complexity) : 알고리즘 수행시 필요로하는 메모리 공간 분석

  • 파이썬 공간 복잡도 주의 : 파이썬은 다른 언어에 비해서 구현상의 복잡함이 적은 편이지만 데이터 처리량이 많은 때는 꼭 메모리 제한을 고려하도록 해야한다. 리스트를 여러개 선언하고, 그중에서 크기가 1,000만 이상인 리스트가 있는 경우에는 메모리 제한을 고려해야한다.

  • int 자료형 데이터의 개수에 따른 메모리 사용량

    데이터의 개수	메모리 사용량
    1,000	약 4KB
    1,000,000	약 4MB
    1,000,000,000	약 40MB

성능 분석 표기법

• 빅오(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))

프로그래밍 대회를 위한 여섯 단계 문제 해결 알고리즘

1. 문제를 읽고 이해한다.

2. 재정의와 추상화 문제를 익숙한 용어로 재정의한다.

3. 어떻게 해결할지 계획을 세운다.

4. 계획을 검증한다.

5. 프로그램으로 구현한다.

6. 어떻게 풀었는지 돌아보고, 개선할 방법이 있는지 찾아본다.

실습

C++

입력을 모르는 경우

입력이 몇 개인지 주어지지 않은 경우가 있다.

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사이에 숫자를 넣으면 그 길이만큼 입력을 받는다.

typedef

C언어에서 사용자 정의 데이터 타입을 만드는 경우에 쓰이는 키워드이다. 타입을 새롭게 정의하는 것이 아닌, 이미 정의되어 있는 타입에 다른 타입을 부여하는 것이다.

//typedef <type정의> <새로운 type 이름>

typedef int element;
typedef struct ListNode{
  element data;
  struct ListNode *link;
} ListNode;

python

입력받기

input()

파이썬은 input() 으로 간단하게 입력 받을 수 있다. 이때 받는 값이 int여야한다면,

int(input())

받는 값을 리스트로 매핑해야한다면

list(map(int, input().split()))

다음과 같이 입력값을 다양하게 받아 올 수 있다.

빠르게 입력받기

입력 데이터의 수가 많은 문제에 input() 핫무를 사용하면, 동작 속도가 느려 시간 초과로 오답 판정을 받을 수 있다.

import sys

# 하나의 문자열 데이터 입력받기
# rstrip()은 줄바꿈 기호로 입력되는 것을 제거
input_data = sys.stdin.readline().rstrip()

다음과 같이 sys 라이브러리의 readline() 을 사용하는 것을 권장한다.

알고리즘 문제 풀이 사이트

• https://codeup.kr/ : 난이도가 낮은 기본문제 풀이

• https://programmers.co.kr/