알고리즘의 기본

알고리즘이란?

알고리즘이란 뭔가를 수행하는 방식의 집합이다. 알고리즘은 문제나 과제를 해결하기 위한 절차다. 문제 해결은 예를 들자면 사용설명서, 요리 레시피, 악보 같은 것이다.

대부분의 경우 문제 해결은 그저 우리가 가지고 있는 직관이나 생각들을 기계나 다른 사람들이 이해할 수 있는 방식으로 번역하는 것에 불과하다. 알고리즘을 기계가 이해할 수 있도록 프로그래밍 언어로 작성한 것이 프로그램이다. 예를 들어 로봇청소기는 사람이 미리 만들어 둔 알고리즘에 따라 움직이는 것이다. 방 청소라는 일을 하나씩 분해하여 순서대로 실행하도록 절차를 지시한 것이다.

절차가 알고리즘이기 위한 조건

1. 정확한 결과를 얻을 수 있어야 한다.
   • 문제 해결 = 올바른 답 출력 or 원하는 결과를 얻을 수 있다.
   • 얻어진 결과가 틀리다면 알고리즘이라고 할 수 없다.
2. 반드시 종료되어야 한다.
   • 끝나지 않는다면 ‘무한 루프’가 되어버린다.

프로그램 진행 단계

기획 → 설계 → 프로그래밍 → 디버깅(테스트) → 문서작성

1. 기획
   • 프로그래밍은 요구(Needs)에서 출발한다
2. 알고리즘은 설계 단계에서 필요하다.
   • 프로그램의 품질은 알고리즘의 좋고 나쁨에 달렸다.
   • 조건을 만족하는 알고리즘은 반드시 하나뿐인 건 아니다.
3. 코딩은 프로그래밍 언어를 사용하여 알고리즘을 프로그램으로 만들어 나가는 것을 말한다.
4. 설계 단계에서 알고리즘을 확실히 고려했다면 버그를 약간 수정하면 된다.
   • 그러나 동작 불량의 원인이 알고리즘의 설계에 있는 경우에는 다시 한 번 알고리즘을 검토하여 프로그래밍 전체를 수정해야 하는 불상사가 발생할 수도 있다.
5. 문서document는 자료 또는 서류라고 한다.
   • 프로그래머를 위한 문서 : 유지보수를 위한 것
   • 사용자를 위한 문서 : 사용설명서

좋은 알고리즘이란

• 알기 쉽다
• 속도가 빠르다
• 효율적이다 = 프로그램을 실행할 때 사용하는 메모리의 영역이 작다
• 재이용하기 쉽다

왜 알고리즘을 공부해야 하는가?

• 속도가 빠르고, 효율적이고, 범용성이 높은 좋은 프로그램을 만들기 위해
• 프로그램의 좋고 나쁨을 판단하기 위해
  • 하나의 문제나 과제를 해결하기 위한 알고리즘은 반드시 하나가 아닐 수도 있다
  • 알고리즘을 제대로 공부하면 프로그램 소스 코드만 보고도 좋은 알고리즘인지 판단할 수 있다.
• 프로그램 작성 과정 전체를 효율화하기 위해
  • 설계 단계에서 제대로 해 놓는 편이 좋다
• 프로그래밍 기술을 향상시키기 위해
  • = 더 빠르고, 효율적이고, 더 범용적인 프로그램을 만든다
  • 이를 위해 알고리즘을 스스로 만들어 보는 것이 중요하다.
  • 잘 알려진 알고리즘을 활용하는 것이 제대로 이해하는 방법.
    • 유명 알고리즘은 알고리즘의 표본
    • 또한 좋은 프로그램을 만들기 위한 힌트가 많이 포함되어 있다.
    • 선인들의 시행착오와 프로그램 작성 요령이 담겨 있다.

알고리즘의 기본형 세 가지

이 세 가지 절차만 기억해 두면 대부분의 알고리즘을 작성할 수 있다.

1. 순차구조

처음부터 순서대로 처리하는 절차

실행해 주길 원하는 처리를 위해서부터 순서대로 작성한다.

가장 많이 사용된다.

2. 선택 구조

조건식으로 판단해 실행할 처리를 전환하는 절차

• 조건에 따라 그 이후의 처리가 나누어진다(=분기한다)
  • 따라서 분기 구조라고 하기도 한다
• 조건식
  • 조건 판단을 실시하는 문장

3. 반복 구조

조건을 만족하는 동안 같은 처리를 반복하는 절차

• 속도가 빠르고 효율적인 알고리즘을 만들기 위해서는 반복 구조를 얼마나 잘 활용하는지가 중요하다.

알고리즘 기술방법

1. 순서도 = flow chart

도형 기호로 표현한다. 시각적이어서 직관적이다.

• 유의사항
  • 처리 기호나 판단 기호 옆에 흐름선을 사용하면 안 된다
    • 반드시 위에서!
  • 판단 기호로부터 나오는 흐름선에는 Yes No를 확실하게 써야 한다 (True False도 OK)
  • 입력선이나 출력선을 빼먹지 않는다
  • 처리 기호의 입력선이나 출력선은 1개 뿐이다.
    • 2개가 나와야 한다면? 판단 기호를 써야 할 상황인 것이다.

2. 프로그래밍 언어

3. 의사 언어 = Psudo Code

• 의사 = ~와 같은 것
  • 즉 프로그래밍 언어와 같은 언어 라는 뜻이다.
  • 순서도와 같은 기호 사용. 도형이 아니라 직선과 문자를 사용하여 list 같은 느낌으로 작성한다.
• 알고리즘을 사람이 알아듣기 쉽도록 쓴 것으로 아래와 같다.

1. 전화번호부를 본다
2. 가운데를 편다
3. 페이지를 본다
4. 만약 스미스가 페이지에 있는 게 참이라면
5. 마이크에게 전화를 건다
6. 스미스가 더 앞에 있으면
    1. 왼쪽 책의 절반을 연다
    2. 이제 다시 3번으로 간다
7. 만약 스미스가 책 뒷쪽에 있으면
    1. 오른쪽 책의 절반을 연다
    2. 이제 다시 3번으로 간다
8. 만약 그가 어느 페이지에도 없다면
    1. 탐색을 그만둬라

알고리즘에 필요한 것

• 정당성 : 주어진 과제에 대해 올바른 결과를 반환해야 한다.
• 정지성 : 반드시 처리를 완료하고 정지해야만 한다.

알고리즘의 다양한 종류

기술 계산

기술 계산을 위한 알고리즘

• 유클리드 호제법(최대공약수)
• 가우스 소거법(방정식)
• 사다리꼴의 법칙(정적분)
• 데이크스트라 알고리즘(최적 경로)
• 에라토스테네스의 체(소수)

정렬 Sort

오름차순(작은 순서) 또는 내림차순(큰 순서)로 정렬하는 알고리즘

• 단순 선택 정렬
• 단순 교환 정렬(버블 정렬)
• 단순 삽입 정렬
• 셀 정렬
• 병합 정렬
• 퀵 정렬

검색 Search

많은 양의 데이터 중 원하는 데이터를 찾아내기 위한 알고리즘

• 선형 검색(리니어 서치)
• 이진 검색(바이너리 서치)

문자열 패턴 매칭

문자열 중에서 지정한 문자열의 패턴(부분 문자열)과 일치하는 부분을 찾아내기 위한 알고리즘

• 단순 문자열 일치
• KMP 알고리즘
• BM 알고리즘

알고리즘의 기초가 되는 구조적 프로그래밍의 개념

효율화, 오류 최소화의 방법론.

모든 프로세스의 흐름은 다음 3가지 구조를 조합해서 설명할 수 있어야 한다.

1. 순차 구조 : 작성된 순서대로 순차 실행한다
2. 선택 구조 : 조건에 따라 수행할 작업의 흐름을 바꾼다.
3. 반복 구조 : 조건이 일치하는 동안 일정 과정을 반복해서 실행한다.

 

Reference

• <처음 만나는 알고리즘>, 이토 시즈카
• <그림으로 배우는 알고리즘 Basic>, 스기우라 켄
• <알고리즘 도감>, 이시다 모리테루, 미야자키 쇼이치
• 모두를 위한 컴퓨터 과학 CS50 2019