SSAFY 7기 기자단이 알려주는 코딩테스트 필수 알고리즘

이것만은 알고 가자!
코테 필수 알고리즘
SSAFY 7기 김혜린 기자

1. 정렬

정렬 알고리즘은 어떤 데이터들이 주어졌을 때,
이를 순서대로 나열하는 알고리즘입니다.

정렬이 프로그래밍에서 중요한 이유는,
컴퓨터는 셀 수 없이 많은 데이터를 탐색해야 할 때가 많은데, 그 과정에서 데이터를 효율적으로
다루어야 자원이 낭비되지 않기 때문입니다.

예) 선택 정렬, 버블 정렬, 삽입 정렬

2. 완전 탐색

완전탐색 알고리즘은 가능한 경우의 수를 모두
탐색하여 답을 찾는 알고리즘입니다.

얼핏 보면 간단하지만, 완전탐색 기법을 사용한
다양한 종류의 알고리즘 유형을 숙지하는 것이
포인트 입니다. 코딩 테스트에 빠지지 않고
등장하는 유형이니 꼭 알아두어야겠죠!

예) 백트래킹, 재귀함수, 순열

3. BFS/DFS

BFS(너비 우선 탐색)/DFS(깊이 우선 탐색)
알고리즘은 코딩 테스트의 단골 주제로, 주로
자료구조의 하나인 '그래프'나 배열을 탐색하는
대표적인 방법입니다.

따라서 '완전 탐색'과 결합돼 문제에서 주어진
전체 범위를 탐색해야 하는 문제들이 다양하게
출제되고 있습니다.

예) 미로 탈출, 집 방문, 전염

4. 스택(Stack), 큐(Queue)

스택(Stack)과 큐(Queue)는 각각 마지막에 들어간
자료가 먼저 나오는 구조, 그리고 처음 들어간 자료가
먼저 나오는 구조를 의미합니다.

핵심 자료구조 중 하나인 만큼 코딩 테스트에서
이를 활용한 문제들이 다양하게 등장하니 꼭
알아둬야 합니다. (특히 큐의 경우 BFS에서
활용됩니다)

5. 동적 계획법(Dynamic Programming)

동적 계획법(Dynamic Programming)은 쉽게
말하면 '답을 재활용'하는 알고리즘 풀이
방식입니다.

풀이 과정에서 반복적으로 등장하는 값이 있다면,
그것을 미리 저장해놓고 재사용함으로써

불필요한 반복 계산을 막고,
더욱 효율적인 코드를
만들 수 있습니다.

6. 우선순위 큐와 힙(Heap)

우선순위 큐(Priority Queue)는 기존의 큐 개념과 다르게, '들어간 순서에 상관없이, 우선순위가 높은 데이터가 먼저 나가는 형태'의 자료구조입니다.

우선순위 큐는 힙(Heap)이라고 하는 방식으로
구현하는 것이 가장 효율적인데요,

* '최대 힙' 으로 정정합니다. 죄송합니다.

힙은 트리 자료구조 중 완전 이진 트리이면서
부모 노드가 자식 노드보다 큰 트리입니다.
따라서 우선 순위가 높은 것을 맨 위로 보내는 데
유리한 자료구조가 됩니다.

*완전 이진 트리: 마지막을 제외하고 모든 부분이 꽉 차있는 이진 트리

오늘은 많은 기업의 코딩 테스트 전형에서
자주 출제되는 알고리즘/자료구조 유형을
알아 보았는데요.

생소한 용어와 개념들도 많지만, 개념 학습을
진행한 뒤 문제 풀이로 연습하면

알고리즘을 처음 접해본 분들도
금방 익숙해 질 수 있는 내용이니,

오늘부터 차근차근 공부해 보시면 어떨까요?
여러분의 코딩 테스트 통과까지! 응원하겠습니다:)