알고리즘(1) - 알고리즘 문제를 풀기 위한 스텝

알고리즘은 총 4단계의 프로세스를 거친다고 볼 수 있다.

 

알고리즘을 오랫동안 공부하고 인공지능도 어쩌다 만나게되면

둘이 동일한 프로세스로 진행된다는 것을 미연중에 알게된다.

전처리 - 정답을 출력하는 알고리즘(머신러닝은 높은 정확도) - 출력 - 최적화

 

이 순서만 기억하고 전처리를 어떻게 할지

그리고 전처리에 맞춘 어떤 알고리즘을 사용할지

어떻게 정답에 맞춘 출력을 할지

마지막으로 보다 빠른 시간안에 출력하는 방법은 없을지를 고민하게된다.

 

여기에서 최적화는 반드시 필요한 부분은 아니다.

 

그럼 시작해보도록 하자.

 

1. Data Preprocessing

데이터 전처리이다. 알고리즘을 구현하기 위해서 어떻게 데이터를 알고리즘에 맞춘 형태로 만들지에 대한 고민을 하게된다. 이게 바로 자료구조라는 명목으로 사용되는 부분이다.

 

선형 자료구조 : STL Vector로 모두 구현 가능하다

배열(Array, Vector 사용)

연결 리스트(Vector 사용)

스택(Vector 사용)

큐(Vector 사용)

힙(Vector 사용)

 

추상적 자료구조 : STL 이 나뉘어 있다.

트리

트라이

이진 탐색 트리

그래프

 

딕셔너리 자료구조

연관 배열

연관 리스트

해시 테이블

 

부가

정렬 알고리즘(병합 정렬, 퀵 정렬)

 

까지가 기본적인 자료구조이다. 이 자료구조를 기반으로 알고리즘들이 생기는 것이기 때문에 문제의 데이터를 먼저 어떻게 정재할 것이고 그 다음 어떻게 활용할 것인지로 넘어가야 한다.

 

그래서 문제를 보아서도 먼저 입력부분을 보고 데이터를 어떻게 정재하고 어떻게 활용할 것인지를 고민해야 한다.

 

2. 알고리즘

어떤 문제들은 앞의 Data Preprocessing 만으로 끝나는 경우가 허다하다. 보통 실버 이하에서 많이 볼 수 있고

골드 문제부터는 알고리즘이 추가된다고 보면된다.

 

탐색 알고리즘

DFS

BFS

이진 탐색

 

트리 탐색 알고리즘

우선법

힙 트리

트라이

 

그래프 알고리즘

다익스트라 알고리즘

밸먼-포드 알고르짐

A* 알고리즘

 

패러다임

백트래킹

동적 계획법

분할 정복 알고리즘

분기 한정법

그리디 알고리즘

최소 신장 트리

 

수학

 

3. 출력

출력도 중요하다. 하지만 먼저 문제를 맞추어야 출력을 할 수 있다는 것을 명심하자.

 

 

4. 최적화

만약 앞에서 정답을 맞추었지만 문제가 풀리지 않은 경우 시간을 줄이기 위한 방법론을 고민해야 한다.