코딩테스트를 위한 알고리즘

0. 개요

C++의 기본적인 컨테이너의 사용법과 for문 if문 만으로 프로그래머스 2단계까지 풀며
주먹구구로 푸는 것에 한계에 부딛혔다. 코딩테스트를 풀기위해 기본적인 알고리즘과 주변개념들에 대해 알아보자.

1. 알고리즘, Alorithm

• 알고리즘: 문제를 해결하기 위한 절차나 방법
• 컴퓨터 프로그램은 정교한 알고리즘들의 집합
• 수학이나 컴퓨터과학에서 말하는 알고리즘은, 보통 반복되는 문제를 풀기위한 작은 프로시저(진행철차)

2. 알고리즘의 조건

• 입력: 알고리즘은 0 또는 그 이상의 외부에서 제공된 자료가 존재해야 한다.
• 출력: 알고리즘은 최소 1개 이상의 결과를 가져야 한다.
• 명확성: 알고리즘의 각 단계는 명확하여 애매함이 없어야 한다.
• 유한성: 알고리즘은 단계들을 유한한 횟수로 거친 후 문제를 해결하고 종료
• 효과성(수행가능성): 알고리즘의 모든 연산들은 사람이 종이와 연필을 이용하여 유한한 시간 안에 정확하게 수행할 수 있을 정도로 충분히 단순해야 한다.

3. 알고리즘의 표현방법

• 의사코드: 자연어를 이용해 만든 문장을 프로그래밍 언어와 유사한 형식으로 배치한 코드를 뜻한다.
• 순서도: 어떤 일을 처리하는 과정을 간단한 기호와 화살표로 도식화한 그림
• 프로그래밍 언어: 기계에게 명령이나 연산을 시킬 목적으로 설계되어 기계와 의사소통을 할 수 있게 해주는 언어

4. 알고리즘의 평가

• 컴퓨터에서는 시간과 메모리라는 두 자원을 얼마나 소모하는지가 효율성의 중점이 된다.

5. 시간복잡도, Time Complexity

• 자료의 수 n이 증가할 때 시간이 증가하는 대략적인 패턴을 시간 복잡도라는 이름으로 나타낸다.
• 주로 Big-O표기법(Big O notation)으로 주로 나타낸다.
• 검색 알고리즘의 경우 O(1) 이나 O(log n)의 시간복잡도를 선호
• 정렬 알고리즘의 경우 O(n log n)의 시간복잡도를 선호

  시간복잡도는 괴랄하게 증가할 수도 있다. 하지만 그 방법이 최선인 경우도 있다.

6. 공간 복잡도, Space Complexity

• 시간 복잡도와 같이 Big-O표기법을 주로 사용
• 시간이 적으면서 메모리까지 지수적으로 증가하는 경우는 없기 때문에, 중요도는 떨어진다.
• 동적 계획법의 경우에는 메모리가 상당히 많이 필요하기 때문에 입력 값의 범위가 넓으면 사용하지 못하는 경우가 많다.
• 임베디드, 펌웨어 등 하드웨어 환경이 극도로 한정되어 있을 경우 공간 복잡도도 상당히 중요하게 취급된다.

7. 주요 알고리즘 종류

1) 자료구조

• 스택, 큐, 환형 큐, 힙, 트리, 그래프
• 정렬
• 탐색: 탐색 알고리즘(DFS, Depth-First Search), BFS(Breadth-First Search), 이진 탐색 등
  - 트리 검색 알고리즘: 힙트리
  - 그래프 알고리즘 기반의 최단 경로 알고리즘, 벨먼-포드 알고리즘

2) 알고리즘 패러다임

-백트래킹, 동적계획법
- 그리디
- 동적계획법(메모리제이션)
- 최소 신장 트리: 크루스칼 알고리즘
- 분할 정복 알고리즘, 분기 한정법(짧은 시간에 학습 불가능)

3) 그래프 알고리즘

경로 탐색, Union Find, 네트워크 흐름 알고리즘

8. 코딩테스를 위해

• 이 이외에드 운영체제, 네트워크, 인공지능 분야를 위한 알고리즘, 문자열 알고리즘, 암호 알고리즘 등 기타 여러 알고리즘이 있다.
• 위의 주요 알고리즘이란 코딩테스트를 풀기 위해 추려 놓은 것이다.
• 순서대로 알아보자