2. 알고리즘 정의

출처: https://cdn.inflearn.com/wp-content/uploads/algorith.png

---

알고리즘이란?

문제를 해결하기 위한 절차나 방법.

algorithm의 발음 기호는 [|ӕlgərɪðəm]이며 ð는 this [ðɪs]의 ð 발음이다.

즉, algorithm을 알고리즘으로 읽는 건 this를 "지스"로 읽는 것과 마찬가지이다.

이 단어는 영어식으로 앨거리듬으로 표기하거나 좀 더 한국식 발음으로 표기하더라도 알고리듬으로 표기해야 한다.

rhythm [|rɪðəm]을 "리즘"이 아닌 "리듬"으로 표기하는 것과 마찬가지이다.

algorism이라는 "아라비아 숫자식 기수법"이라는 뜻을 가진 유사한 단어가 있으며 이 단어의 발음기호는 [ǽlɡərìzm]이므로

오히려 이 단어를 앨거리즘이나 알고리즘이라고 읽어야 한다.

 

알고리즘이라는 용어는 문제를 해결하기 위한 절차나 방법을 의미하는 단어로 넒은 범위에서 사용된다.

조금 더 정확한 의미를 따져보자면 알고리즘은
어떠한 행동을 하기 위해서 만들어진 명령어들의 유한 집합(finite set)이다.

컴퓨터 프로그램은 정교한 알고리즘들의 집합이라고 간주할 수 있다.

---

알고리즘의 조건

알고리즘은 이하의 요건을 만족해야만 한다.

• 입력 - 알고리즘은 0 또는 그 이상의 외부에서 제공된 자료가 존재한다.

• 출력 - 알고리즘은 최소 1개 이상의 결과를 가진다.

• 명확성 - 알고리즘의 각 단계는 명확하여 애매함이 없어야 한다.

• 유한성 - 알고리즘은 단계들을 유한한 횟수로 거친 후 문제를 해결하고 종료해야 한다. 알고리즘의 한 단계 이후 m의 값은 n 보다 작으며, m!=0이면 n의 값은 다음 번 단계에서 줄어든다.

• 효과성 - 알고리즘의 모든 연산들은 사람이 종이와 연필을 이용하여 유한한 시간 안에 정확하게 수행할 수 있을 정도로 충분히 단순해야 한다.

---

프로그래밍에서 사용하는 알고리즘들

• 자료구조

  • 정렬

    • 정렬 예제

  • 탐색

    • 탐색 알고리즘: DFS (Depth-First Search), BFS (Breadth-First Search), 이진 탐색 등.

      • 트리 탐색 알고리즘: 우선법, 힙 트리(heap), 트라이(Trie)

        • 그래프 알고리즘 기반의 최단 경로 탐색: 다익스트라 알고리즘, 벨먼-포드 알고리즘, A* 알고리즘

• 알고리즘 패러다임: 백트래킹, 동적 계획법, 분할 정복법, 분기 한정법, 그리디 알고리즘

  • 동적 계획법: 메모이제이션 문서도 참조.

  • 최소 신장 트리: 크러스컬 알고리즘

• 그래프 알고리즘: 경로 탐색, Union Find, 네트워크 흐름(network flow) 알고리즘

• 기계학습: 서포트 벡터 머신(SVM) 등.

• 문자열 알고리즘: KMP 등

• 기타 Pollard's rho 등의 정수론 알고리즘, 선형합동법등의 난수발생 알고리즘, 해석기하/그래픽 알고리즘, 유전 알고리즘 기법 등.

• 응용 분야에 따른 구분

  • 미로탐색 알고리즘: 트리 탐색 알고리즘 예제로 많이 나오는 문제.

  • 알고리즘 트레이딩

  • 암호 알고리즘: AES, DES, SEED, 아리아, LEA, MD5, ROT13, 공개키 암호화 방식, 대칭 열쇠 암호, RSA 암호화, 복호화, SHA

---

알고리즘 공부 사이트

온라인 DB를 이용하여 평가하는 자발 트레이닝 시스템.

1. 더블릿

http://59.23.150.58/

천천히 흘러도 흘러가야 합니다 --- 더블릿

2. Baekjoon OJ

https://www.acmicpc.net/

Baekjoon Online Judge

3. CodeUp

https://codeup.kr/

CodeUp

4. JUNGOL

http://www.jungol.co.kr/

JUNGOL

5. KOISTUDY

http://koistudy.net/

KOISTUDY

6. Alcall OJ

https://www.a2oj.com/

A2 Online Judge

7. Codeground

https://www.codeground.org/

codeground

8. URI Online Judge

https://www.urionlinejudge.com.br/judge/login?redirect=%2Fen

URI Online Judge

9. 프로그래머스

https://programmers.co.kr/learn/challenges

프로그래밍 강의 | 프로그래머스

 

---

 2012년 구글 검색결과 수 "알고리듬" 290,000건, "알고리즘" 4,510,000건임을 봤을때 모두 알고리즘이라 알고 있다.

출처: https://namu.wiki/w/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

알고리즘 - 나무위키