내가 정리하는 코딩테스트 문제 유형 별 풀이 방법

 

하반기 채용 공고가 점차 뜨기 시작하면서 코딩테스트를 준비하고 있는 분들이 늘고 있는 것 같아 글을 쓰게 되었습니다.

 

물론 저도 많이 부족하지만, 상반기 코딩테스트 준비하면서 참 힘들었고, 취준생분들 불안한 마음을 누구보다 잘 알기에,,,, 조금이나마 도움이 될 수 있지 않을까 해서 포스팅 하게 되었습니다.

(고수분들 스루해주세요!!....)

 

일단 코딩테스트에서 자주 출제되는 유형을 정리해보면,

 

브루트 포스

DFS

BFS

시뮬레이션/구현

DP

그리디

이분탐색

투포인터

 

이정도이다. 그 중에서 가장 많이 출제되는 유형을 꼽아보면, 

 

브루트 포스

DFS

BFS

시뮬레이션/구현

DP

그리디

이분탐색

투포인터

 

해당 유형이다. 그렇기 때문에, 해당 4가지 유형만 깊게 파고 공부하면, 웬만한 코딩테스트 합격선에는 들 수 있다고 생각한다.

 

이 외에, 혹시 라인/카카오/네이버와 같은 IT 서비스 기업 코딩테스트를 준비하고 있는 분들이라면 위 유형 외에

 

우선순위 큐

해시 맵

trie 알고리즘

유니온 파인드

크루스칼 알고리즘

트리의 지름 구하기

 

정도는 추가적으로 공부해두는 편이 좋다고 생각한다.

 

내가 주로 문제를 맞딱뜨렸을 때 제일 먼저 시도하는 방법은 완전 탐색(브루트 포스)이다. 80%의 문제가 완전 탐색으로 해결되었고, 효율성을 따지는 문제 같은 경우는 시간 초과를 대비해 DP, 그리디, 투포인터, 이분 탐색(파라메트릭 서치) 순으로 풀이법을 고민해보았던 것 같다.

 

1. 브루트 포스(완전 탐색)

 

모든 경우를 다 탐색해보는 경우이다. 백준의 숫자 야구(www.acmicpc.net/problem/2503)와 같이 주어진 범위 내에 모든 수를 탐색해보면서 조건에 해당하는지 탐색하는 경우이다.

2503번: 숫자 야구

 

2. DFS(깊이 우선 탐색)

 

DFS 같은 경우는 삼성 역량테스트에 가장 많이 출제되는 유형이다. 나의 경우엔 DFS 알고리즘을 이용해서 풀어야 하는 문제의 경우에는 3가지 유형이 있었던 것 같다.

 

• 한 가지 정점과 연결된 모든 정점을 탐색해야 하는 경우
• 경로를 찾아야 되는 경우
• 사이클이 존재하는 경로 찾는 경우

먼저, 첫 번째의 경우에는 일반적인 DFS 알고리즘을 사용하면 된다. 해당 지점을 방문 여부를 체크할 수 있는 배열을 선언한 뒤, 한 정점씩 방문 후 그 정점과 인접한 정점들 중 아직 방문하지 않은 정점을 다시 재귀 호출하는 방식을 이용하면 된다.

 

//간단한 dfs 알고리즘 메소드

void dfs(int v, int [] c){
	c[v] = 1;
    
    for(int a : adlist[v]){
    	if(c[a] == 0)
        	dfs(a, c);
    }
}

 

두 번째의 경우에는 연결 요소를 찾는 것이 아닌 경로를 찾아야 하는 경우이다. 그렇기 때문에, dfs 알고리즘을 약간 변형하여 이용하면 된다. (순열과 조합 구하는 것들이 익숙하지 않은 분들은 백준에 N과 M 문제집을 쭉 풀어보시는 것을 추천합니다!)

 

//경로 찾는 문제

void go(int v, int [] c){
	for(int a : adlist[v]){
    	if(c[a] == 1) continue;
        c[a] = 1;
        go(a, c);
        c[a] = 0;
    }
}

 

마지막 세번째의 경우는 사이클이 존재하는 경로를 찾는 문제다. 사이클이 존재한다는 것은 어떤 의미일까? 이전에 방문했던 곳을 다시 방문해 일종의 원형 반복 cycle이 생겼다는 것을 의미한다. 일반적인 dfs와 같은 경우에는 방문했던 곳을 다시 방문하지 않는다. 그렇기 때문에, 기존의 dfs 알고리즘에 약간 변형을 주어 문제를 해결해야한다.

해당 유형의 문제는 백준 텀 프로젝트 문제를 풀어보시면 됩니다.(www.acmicpc.net/problem/9466)

 

기존에 사용하던 방문여부 체크 배열 외에 경로가 시작된 정점을 저장하기 위해 cycle[i] 배열을 하나 추가로 생성한다. 그리고 나서 dfs 탐색을 하되 이번에는 기존에 방문했던 정점들에 대해서도 조건 체크를 해주어야 한다.

 

//사이클이 존재하는 경로 찾기

int dfs(int start, int v, int [] c, int [] cycle){
	c[v] = 1;
    cycle[v] = start;
    
    if(c[adlist[v]] == 1 && cycle[adlist[v]] == start)
    	return 사이클!
    else if(c[adlist[v]] == 1 && cycle[adlist[v]] != start)
    	return;
        
    return dfs(start, adlist[v], c, cycle);
}

 

 

3. BFS(넓이 우선 탐색)

 

BFS 알고리즘 같은 경우도 삼성 역량테스트에서 가장 많이 출제되는 유형 중의 하나다. 단계별 탐색이 가능하기 때문에 최단 거리를 구할 수 있다는 특징이 있어 많이 사용되는 알고리즘이다. BFS를 사용해야하는 문제를 분류해보면 크게 두 가지로 나눠볼 수 있다.

 

• 최단 거리를 구해야하는 경우
• 최단 거리를 구하되 조건이 여러 개 존재하는 경우(방문한 지점도 다시 방문 가능)

첫 번째 경우에는 일반적인 BFS 알고리즘을 이용해서 구해주면된다. 큐(Queue)를 이용하여 단계별로 정점들을 탐색해주면 된다.

 

//일반적인 BFS 구현 코드

void bfs(){
	Queue<Integer> q = new LinkedList<Integer>();
    int [] c = new int[N];
    
    q.offer(1);
    c[1] = 1;
    
    while(!q.isEmpty()){
    	int a = q.poll();
        
        for(int v : adlist[a]){
        	if(c[v] == 0){
            	q.offer(v);
                c[v] = 1;
            }
        }
    }
}

 

두 번째의 경우가 살짝 복잡하고 응용이 필요한 경우다. 최단 거리를 찾되 주어진 조건이 여러 개라 고려해야할 사항이 많은 경우는 큐에 해당 조건을 모두 저장하기 위해 custom class를 하나 선언해준 뒤, 큐에 모든 정보를 저장하면서 bfs 알고리즘을 수행한다. 단, 기존의 bfs와 달리 기존에 방문했던 정점이라도 최소 비용으로 업데이트가 가능한 경우에는 큐에 새로 추가한다.

해당 경우를 연습해볼 수 있는 문제로는 지난 2020 카카오 인턴십 기출문제인 경주로 건설이 있다. 개인적으로 아주 좋은 문제라고 생각한다.(programmers.co.kr/learn/courses/30/lessons/67259)

코딩테스트 연습 - 경주로 건설

//bfs(조건이 여러 개 있는)
import java.util.*;

class Solution {
    static class Point{
        int i;
        int j;
        int cost;
        int dir;
        
        Point(int i, int j, int cost, int dir){
            this.i = i;
            this.j = j;
            this.cost = cost;
            this.dir = dir;
        }
    
    }    
    static class Visit{
        int visited;
        int cost;
        
        Visit(){
            this.visited = 0;
            this.cost = 0;
        }
    }
        
    static int [] dx = {0, 0, -1, 1};
    static int [] dy = {-1, 1, 0, 0};
        
    public int solution(int[][] board) {
        int answer = Integer.MAX_VALUE;
        
        Queue<Point> q = new LinkedList<Point>();
        Visit [][] c = new Visit[board.length][board[0].length];
        for(int i=0;i<board.length;i++){
            for(int j=0;j<board[0].length;j++)
                c[i][j] = new Visit();
        }
        
        q.offer(new Point(0, 0, 0, -1));
        c[0][0].visited = 1;
        
        while(!q.isEmpty()){
            Point p = q.poll();
            
            for(int i=0;i<dx.length;i++){
                if(p.i+dx[i] >= 0 && p.i+dx[i] < board.length && p.j+dy[i] >= 0 && p.j+dy[i] < board[0].length && board[p.i+dx[i]][p.j+dy[i]] == 0){
                    int newCost = 0;
                    if(p.dir == -1 || p.dir == i)
                        newCost = p.cost + 100;
                    else
                        newCost = p.cost + 600;
                    
                    if(c[p.i+dx[i]][p.j+dy[i]].visited == 0){
                        q.offer(new Point(p.i+dx[i], p.j+dy[i], newCost, i));
                        c[p.i+dx[i]][p.j+dy[i]].cost = newCost;
                        c[p.i+dx[i]][p.j+dy[i]].visited = 1;
                    }else if(c[p.i+dx[i]][p.j+dy[i]].visited == 1 && c[p.i+dx[i]][p.j+dy[i]].cost >= newCost){
                        q.offer(new Point(p.i+dx[i], p.j+dy[i], newCost, i));
                        c[p.i+dx[i]][p.j+dy[i]].cost = newCost;

                    }
                }
            }
        }
        
        answer = c[board.length - 1][board[0].length - 1].cost;
        return answer;
    }
}

 

4. 시뮬레이션

 

시뮬레이션 유형은 말그대로 문제에 나와 있는 상황과 조건을 토대로 구현하면 되는 문제이다. 따라서, 특별히 알아야 하는 알고리즘은 없지만 다양한 문제를 경험해보는 것이 중요하다. 구현에 종종 필요한 팁들은 제가 작성한 다른 포스팅(myeongmy.tistory.com/9)을 참고하면 좋을 것 같습니다.

알고리즘 구현 시 자주 등장하는 유형(개념) - JAVA

 

5. DP(동적 프로그래밍)

 

DP 문제는 사실 많이 풀어서 익숙해지는 게 중요하기 보다는 기본적인 수학적 사고에 영향을 많이 받는 것 같다....ㅋㅋ 그렇기 때문에 코딩테스트에 자주 등장하는 유형은 아닌데 완전 탐색으로 풀었을 때 시간 초과가 나는 경우(N이 큰 경우) DP를 주로 이용하게 된다. 내가 DP 문제를 맞딱뜨렸을 때의 사고 방식은 다음과 같다.

• long 형으로 배열을 선언한다.
• 문제에서 구하라고 하는 부분을 배열로 선언한다.
• 조건이 여러 개인 경우에는 2차원 배열을 선언한다.

그리고, 구간을 구하는 문제 같은 경우는 A[i]를 끝 점으로 하는 수열의 최장 길이, A[i]를 시작으로 하는 수열의 최장 길이! 이런 식으로 배열을 선언하는 편이다.

(참고: 백준 11054번 가장 긴 바이토닉 부분 수열 www.acmicpc.net/problem/11054)

11054번: 가장 긴 바이토닉 부분 수열

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class N_11054_v2 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		try {
			int N = Integer.parseInt(br.readLine());
			int[] A = new int[N];

			String[] arr = br.readLine().split(" ");
			for (int i = 0; i < N; i++)
				A[i] = Integer.parseInt(arr[i]);

			long[] d = new long[N]; // d[i]: A[i]를 끝 원소로 하는 증가 수열의 최장 길이
			long[] e = new long[N]; // e[i]: A[i]를 시작 원소로 하는 감소 수열의 최장 길이

			for (int i = 0; i < N; i++) {
				d[i] = 1;
				e[i] = 1;
			}

			// d배열 채우기
			for (int i = 1; i < N; i++) {
				for (int j = i - 1; j >= 0; j--) {
					if (A[i] > A[j]) {
						d[i] = Math.max(d[i], d[j] + 1);
					}
				}
			}
			// e배열 채우기
			for (int i = N - 2; i >= 0; i--) {
				for (int j = i + 1; j < N; j++) {
					if (A[i] > A[j]) {
						e[i] = Math.max(e[i], e[j] + 1);
					}
				}
			}
			long max_length = Integer.MIN_VALUE;
			for (int i = 0; i < N; i++) {
				if (max_length < d[i] + e[i])
					max_length = d[i] + e[i];
			}

			System.out.println(max_length - 1);
		} catch (IOException e) {
			e.printStackTrace();
		}
	}

}

 

6. 그리디(Greedy)

 

그리디 알고리즘은 욕심쟁이 방법이라고도 불리는데, 그 때 그 때 상황에서의 최적해가 전체 최적해가 된다는 원리를 이용한 방식이다. 그리디를 이해하기 위해서는 백준 1931번 회의실 배정(www.acmicpc.net/problem/1931) 문제를 풀어보면 좋을 것 같다.

1931번: 회의실배정

 

최대한 많은 회의를 잡기 위해서 끝나는 시간을 기준으로 회의를 오름차순 정렬한다. 그 뒤 끝나는 시간이 제일 빠른 것을 선택하면서 겹치지 않는 최대 회의 수를 선택한다. 겹치는 경우에는 최대한 일찍 끝나는 회의를 선택하는 것이 좋다.

 

 

7. 이분탐색(파라메트릭 서치)

 

이분탐색은 내 개인적인 생각으로는 카카오에서 많이 출제되는 것 같다. 완전 탐색으로 해결하는 경우 시간 초과가 날 때 대부분의 문제가 이분탐색, 즉 파라메트릭 서치를 이용하면 해결되는 경우가 많았다. 이분 탐색이란 정렬된 배열이 있을 때 중간부터 탐색을 시작하여 탐색할 문제를 점차 반씩 줄여나가는 방식을 이용한다. 

 

이분 탐색에서 가장 중요한 것은!

• 먼저 정렬되어 있는지 확인하고 정렬되어 있지 않다면 정렬을 먼저 수행
• 문제에서 구하라고 하는 값의 범위를 고려해서 이분 탐색의 범위로 할당

참고하면 좋은 문제는 2019 카카오 겨울 인턴십 기출 징검다리 문제다.(programmers.co.kr/learn/courses/30/lessons/64062)

코딩테스트 연습 - 징검다리 건너기

 

//이분탐색(파라메트릭 서치)
//이분탐색의 대상 : 징검다리를 건널 수 있는 친구들의 수(1 ~ stones 배열 최대값)

class Solution {
    static int max_result = Integer.MIN_VALUE;
    
    static void binarySearch(int start, int end, int [] stones, int k){
        if(start > end) return;
        int mid = (start + end) / 2;
        
        int [] arr = new int[stones.length];
        arr = stones.clone();
        
        for(int i=0;i<arr.length;i++)
            arr[i] -= (mid-1);
        
        int cnt = 0;
        int flag = 0;
        
        for(int i=0;i<arr.length;i++){    //mid 번째 니니즈 친구가 건널 수 있는지 확인
            if(arr[i] <= 0)
                cnt++;
            else{
                if(cnt >= k)
                    flag = 1;
                cnt = 0;
            }
        }
        if(cnt >= k) flag = 1;
        
        if(flag == 1)
            binarySearch(start, mid-1, stones, k);
        else{
            if(max_result < mid)
                max_result = mid;
            binarySearch(mid+1, end, stones, k);
        }
    }
    public int solution(int[] stones, int k) {
        int answer = 0;
        
        int max = stones[0];
        for(int i=1;i<stones.length;i++){
            if(max < stones[i])
                max = stones[i];
        }
        
        binarySearch(1, max, stones, k);
        answer = max_result;
        return answer;
    }
}

 

8. 투포인터(Two Pointer)

 

투포인터 알고리즘은 나도 코딩테스트를 준비하며 처음 알게된 알고리즘이었다.(학교에서 배운 기억이 없는데,,, 내가 기억을 못하는 건가,,ㅋㅋ)

투포인터 알고리즘은 구간을 구하기 위해 사용하는 알고리즘이다. 역시 완전 탐색으로 구간을 구할 수는 있지만 효율성(시간 초과) 측면에서 투포인터를 사용하는 것이 좋다.

 

알고리즘 이름 그대로 2개의 포인터를 사용한다. 배열의 인덱스를 가리키는 start와 end 포인터 두 가지를 두고 조건에 맞춰 end 포인터를 ++1, start 포인터를 ++1 해나가는 방식이다.

 

투 포인터 알고리즘 유형은 크게 두가지이다.

• 대상이 되는 배열이 1개인 경우
• 대상이 되는 배열이 2개인 경우

첫 번째의 경우에는 백준 1806번 부분합(www.acmicpc.net/problem/1806)문제를 참고하면 된다.

1806번: 부분합

1. start와 end 포인터를 모두 0으로 초기화한다.
2. start 포인터가 배열의 범위를 벗어날 때 까지 반복한다.
3. -> sum < M, end++;
4. -> sum >= M, start ++;
5. -> end 포인터가 배열의 범위를 벗어나면, start++;

두 번째의 경우는 백준 1208번 부분수열의 합2(www.acmicpc.net/problem/1208) 문제를 참고하면 된다.

1208번: 부분수열의 합 2

부분수열은 일반적으로 조합(완전 탐색)을 이용해서 풀이하게 된다. 다만, 해당 문제는 N의 범위가 크기 때문에 완전 탐색으로 풀게 되면 시간 초과가 나기에 N/2 단위로 완전 탐색을 한 뒤, 각각 두 배열을 하나는 오름차순, 하나는 내림차순 정렬을 하여 두 개의 포인터를 이용하여 답을 구해야 한다.

 

9. 우선순위 큐(PriorityQueue)

 

자바를 기준으로 PriorityQueue는 java.util 패키지 내장 클래스로 기본 반환 순서는 최소 힙(min heap) 형태이다.

• N번째 요소 구하기 (큐의 크기를 N으로 유지한 뒤 N+1개가 들어올 때 가장 작은 요소와 비교)
• 중앙값 구하기(두 개의 우선순위 큐를 이용해서)
• 2, 5, 8, 11 ..... (2, 5, 8 초기값을 큐에 넣고 하나씩 뽑으면서 연산을 진행한 뒤 N번째 요소 구하기)

 

10. 해시 맵(HashMap)

 

해시 맵은 꼭!꼭! 기억해야하는 자료구조이다. 개인적으로 코딩테스트 문제 풀이 시 가장 많이 이용하게 되는 자료구조인 것 같다.

• 배열 내 빈도 수 구하기
• 배열 내 중복된 요소 구하기
• HashMap<Integer, LinkedList<Integer>>....
• 등등....

정말 많이 이용되니 꼭 기억해두고 활용하는 법을 알아두자. (TreeMap의 .ceilingKey() 메소드도 추가적으로 알면 좋을듯)

 

 

11. 유니온 파인드(Union-Find)

 

유니온 파인드 알고리즘은 특정 두 노드가 어느 집합에 속하는지 판별하고, 두 노드를 하나의 집합으로 합칠 때 사용하는 알고리즘이다. 크루스칼 알고리즘과 더불어서 같이 많이 사용되기도 하고 독립적으로 사용되는 경우도 많다.

 

//Union-Find

//find 메소드(최상위 부모를 찾는 메소드)
int find(int v){
	if(v == parent[v]) return v;
    
	return find(parent[v]);
}

//union 메소드(두 노드를 하나의 집합으로 합치는 메소드)
void union(int v1, int v2){
	int parent1 = find(v1);
    int parent2 = find(v2);
    
    parent[parent1] = parent2;
}

 

12. Trie 알고리즘

 

Trie 알고리즘은 문자열 검색 및 처리를 위한 알고리즘이다. 문자열을 일반적인 String 클래스를 이용해 선형적으로 저장하지 않고, Tree 형태로 저장하여 검색 속도의 향상을 추구하는 알고리즘이다.

 

각 트리의 노드 멤버 변수는 다음과 같다.

static class TrieNode{
	int val;    //알파벳 값
    TrieNode [] next = new TrieNode[26];   //다음 노드
    boolean isEnd = false;    //문자열의 마지막 위치인지 여부
}

trie를 이용해서 접두어, 접미어 처리를 할 수 있다. 다만, trie 트리를 구성할 때 길이가 짧은 문자열부터 trienode를 생성해야함을 주의해야한다.

 

13. 크루스칼 알고리즘(Kruskal Algorithm)

 

크루스칼 알고리즘은 MST(Minimum Spanning Tree)를 구하기 위한 알고리즘이다. N개의 노드로 이루어진 그래프가 주어졌을 때, N-1개의 간선을 이용한 최소 가중치의 트리를 구할 때 사용한다.

 

방식은 다음과 같다.

1. 간선들을 모두 오름차순 정렬한다.
2. 가중치가 가장 작은 간선부터 선택하면서 사이클이 생기지 않는 경우 해당 간선을 선택한다.
3. N-1개의 간선이 선택될 때까지 반복

문제 유형은 크게 간선이 모두 주어지는 경우, 간선이 주어지지 않는 경우가 있는데, 후자의 경우 모든 간선을 직접 구해야한다면 시간 초과가 나는 경우가 있다. 그럴 때는 조건을 정렬하여 최소 간선만 선택할 수 있도록 해야한다.

 

14. 트리의 지름 구하기

 

트리의 지름 구하기(?)라고 하면 생소하게 들릴 수도 있는데 어렵지 않다. N개의 노드와 N-1개의 간선으로 이루어진 트리가 있을 때, 가장 멀리 떨어져 있는 두 노드 사이의 depth를 구하라는 의미이다.

 

해당 문제는 두 번 dfs 알고리즘을 수행하면 된다.

1. 임의의 정점에서 dfs 알고리즘을 수행해 가장 멀리 떨어져 있는 노드 구하기
2. 1번에서 구한 노드를 대상으로 다시 한 번 dfs를 수행해 가장 멀리 떨어져 있는 노드 구하기 -> 정답!

관련해서 풀어보면 좋은 문제는 백준 14657번 준오는 최종인재야!!!(www.acmicpc.net/problem/14657)이다.

14657번: 준오는 최종인재야!!

해당 문제는 위에서 말한 방식으로 두 번 dfs를 수행하되 가장 멀리 떨어져 있는 것 외에 가중치가 최소가 되는 정점이라는 조건을 추가적으로 고려해서 풀어야한다는 점이 있다.

 

15. 문자열 처리

 

주어진 문자열을 파싱하여 원하는 형태로 만들어 조건대로 문제를 풀이하는 유형이다. 문자열 처리에 자주 사용되는 메소드로는 .split() 메소드, StringTokenizer 클래스, .substring() 메소드 등이 있다.

 

문자열 처리 문제로 종종 등장하는 유형이 연산식 형태의 문자열이 주어진 후 조건대로 식을 계산하여 결과값을 구하는 유형이다. 이런 경우에는 문자열을 파싱하여 피연산자에 해당하는 숫자들과 연산자에 해당하는 부분을 각각 따로 덱(Deque)에 저장한다. 덱(Deque)을 이용하는 이유는 리스트를 이용하는 것보다 효율성 측면에서 좋은 자료구조이기 때문이다.

 

 

16. 다익스트라 알고리즘

 

다익스트라 알고리즘은 최단 경로를 구하기 위한 알고리즘이다. 한 시작 지점에서 모든 노드까지의 최단 거리를 구하고자 할 때 사용하는 방법이다.

먼저, 시작점과 각 노드 사이의 최단 거리를 저장할 배열을 하나 선언해준 뒤, 거리가 가장 짧은 노드를 선택하여 해당 노드와 연결된 노드들을 대상으로 업데이트를 진행한다. (d[i] = d[a] + 간선 가중치)

코드로 구현할 때는 거리가 가장 짧은 노드를 선택하기 위해서 우선순위 큐를 이용하면 된다.

 

시간복잡도를 분석해본다면,

다익스트라에서 요구되는 연산은 크케 두 가지이다. 첫 째는 모든 간선을 탐색하는 과정, 둘 째는 그 과정 속에서 우선 순위 큐를 조작하는 연산이다. 최단 거리를 구하기 위해 그래프 내 모든 간선을 탐색하게 되므로 해당 시간 복잡도는 O(|E|)에 해당한다. 우선순위 큐는 우선순위 큐에 들어갈 수 있는 후보의 최대 갯수는 간선 수이고, 우선순위 큐에서 요소를 삭제하는 연산은 O(log|E|)의 시간을 필요로 하므로 총 O(Elog|E|)의 시간이 걸린다.

 

따라서, 시간 복잡도는 O(|E|) + O(Elog|E|) = O(Elog|E|)에 해당한다.

 

 

16. 위상정렬(Topology Sort)

 

위상정렬 알고리즘은 주어진 수를 나열하되 순서가 정해져 있는 요소가 있는 경우에 정렬할 때 사용하는 알고리즘이다. 따라서, 순서가 정해져 있는 요소 조건에 따라 그래프를 그려보고 각 노드들에 대한 진입 차수(inDegree)를 구하고, 진입 차수가 0인 지점부터 차례대로 탐색하면 된다. 자세한 구현 방법은 큐(Queue)를 이용한 방법이 있다.

 

큐를 하나 선언해준 뒤,진입 차수가 0인 노드를 모두 큐에 넣어준다.

 

큐에서 하나씩 노드를 빼내면서!   1. 해당 노드가 가리키고 있는 노드들의 진입 차수를 1-- 해준다   2. 이 과정에서 진입 차수가 0이 된 노드는 큐에 삽입한다.   3. 해당 과정을 큐에 아무 요소가 없어질 때까지 반복한다.

 

참고하면 좋은 문제는 다음 문제다! 백준에 있는 문제인데, 위상 정렬과 우선순위 큐를 종합해서 풀어야 하는 문제니 풀어보면 위상 정렬에 대한 감을 잡기 좋은 문제다.www.acmicpc.net/problem/1766

1766번: 문제집

 

 

 

후,,, 이렇게 코딩테스트에 등장할 수 있는 모든 유형에 대해서는 언급한 것 같다.

글을 쓰다보니 중요한 알고리즘이 계속 떠오르는 바람에 주저리주저리 글이 너무 길어진 감이 없지 않아 있지만,,, 위 내용들만 어느 정도 숙지하면 웬만한 코딩테스트는 충분히 합격하고도 남을 것이라 생각한다.

 

 

그럼 끝!