[코딩테스트] 단기간에 잘해질 수 있을까..?

코딩테스트는 코딩 실력과 별개로 체계적으로 접근해야 빠르게 성장할 수 있다고 생각한다. 하지만 공부 범위가 너무 방대해서 어떻게 공부해야 할 지 체계적으로 접근하기 쉽지 않다고 생각했다. 그래서 확실한 로드맵으로 효율적인 코딩테스트 공부법을 작성해보고자 한다.

학습 범위 이것은 코딩테스트를 위한 학습 범위인데 내가 1년동안 학습과 경험을 통해서 코딩테스트를 처음 시작할 때 도움이 많이 되었던 것을 소개드릴려고 한다. (구현과 그래프)

이 내용은 코딩테스트 공부를 시작하거나, 자신만의 공부하는 방법이 없는 취업준비생에게 추천한다.

N과M

https://www.acmicpc.net/workbook/view/2052

첫번째는 바로 N과M 시리즈를 다 푸는 것이다. 이때 그냥 푸는 것이 아니라 하나의 코드를 외운다.

이 코드는 N과M 시리즈 1번 문제의 정답이다.

import java.util.*;
import java.io.*;

public class Main {
    static int n, m;
    static int[] p,r,visited;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        p = new int[m+1];
        visited = new int[n+1];

        perm(0);

    }
    public static void perm(int depth) {
        if(depth >= m){
            for(int i=0;i<m;i++){
                System.out.print(p[i] + " ");
            }
            System.out.println();
            return;
        }
        // 외워야 할 부분 
        for(int i=1;i<=n;i++){
            if(visited[i] == 1) continue;
            visited[i] = 1;
            p[depth] = i;
            perm(depth+1);
            visited[i] = 0;
        }
    }
}

일단 이 코드를 밥 먹으면서도 적을 수 있도록 완벽하게 외운다. 질문은 받지 않는다.

다 외웠다면 조합을 하는 방법까지 알려줄테니 외운다. (N과M-2)

1. 메서드 파라미터에 int start를 추가한다.
2. 재귀 for문을 start부터 돌린다.

	public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        p = new int[m+1];
		// start 값 추가
        combi(0, 1);

    }
    static public void combi(int depth, int start) {
        if(depth >= m){
            for(int i=0;i<m;i++){
                System.out.print(p[i] + " ");
            }
            System.out.println();
            return;
        }
        // visited 없이 start부터 출발 (왜 visited가 필요 없을까?)
        for(int i=start;i<=n;i++){
            p[depth] = i;
            combi(depth+1, i+1);
        }
    }

여기까지 완벽히 외웠다면 이제 여기에 있는 값들을 하나씩 변경시켜 보면서 다른 시리즈를 모두 풀면 된다. 이 두개의 틀에서 조금씩 변형시켜 보고 값을 출력해보면 이 코드가 어떻게 돌아가는 지 감이 잡히게 된다. (안잡히면 그려보는 것을 추천한다)

여기까지 한다면 이제 재귀와 백트래킹에 대해서 이해할 수 있고, 대부분의 문제를 완전탐색으로 접근할 수 있게 된다! (이제부터 코테가 재밌어짐)

빵집 (DFS)

https://www.acmicpc.net/problem/3109

DFS의 대표 문제이다. 풀었더라도 다시한번 풀고, 모르겠다면 오래 고민하지 말아야 한다.

DFS의 특징을 사용해서 그리디하게 문제를 풀어야 한다.

이 그림을 보고 왜 되는 지 파악하면서 코드를 작성한다. 다시한번 말하지만 너무 시간 쏟지 말고 AI한테 코드를 부탁하고 외운다.

벽부수기 시리즈 (BFS)

https://www.acmicpc.net/search#q=%EB%B2%BD%20%EB%B6%80%EC%88%98%EA%B3%A0&c=Problems

이 시리즈는 단순한 BFS는 아니다. 다차원 BFS이고 벽을 부쉈을 때 안 부쉈을 때 다른 평면에서 움직인다는 것이 핵심 아이디어이다.

		map = new int[n][m];
		visited = new int[n][m][2];

이렇게 3차원 visited 배열을 사용해서 벽이 있다면 부쉈을 때의 세계선, 안부수고 지나갔을 때의 세계선을 다 기록하면서 도착지까지 가는 것이다.

여기까지 문제를 다 풀고 코드를 외웠다면 간단한 구현 문제들은 다 풀 수 있을 것이다!

최소비용 구하기 (다익스트라)

https://www.acmicpc.net/problem/1916

이 문제를 추천하는 이유는 그래프를 구현하는 방법을 배우기 위함이다. 그래프를 배열로 만드는 방식과 연결리스트로 만드는 방식 두가지를 다 시도해보길 바란다.

	static class Rode implements Comparable<Rode> {
        int to;
        int weight;
        public Rode(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }

        @Override
        public int compareTo(Rode o) {
            return this.weight - o.weight;
        }
    }
    ...
    ...
    ...
    private static void bfs(int start) {
        // 초기값 설정
        visited = new int[n+1];
        dist = new int[n+1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        // 탐색 시작
        PriorityQueue<Rode> pq = new PriorityQueue<>();
        pq.add(new Rode(start, 0));
        dist[start] = 0;
        while(!pq.isEmpty()) {
            Rode curRode = pq.poll();
            int cur = curRode.to;
            if(visited[cur] == 1) continue;
            visited[cur] = 1;
            for(Rode next : pList[cur]) {
                if(next.weight + dist[cur] >= dist[next.to]) continue;
                dist[next.to] = next.weight + dist[cur];
                pq.add(new Rode(next.to, dist[next.to]));
            }
        }
    }
    

Class를 사용해서 길(Road)를 객체화 하고 PriorityQueue를 통해서 weight가 가장 작은 것부터 나오게 하는 것이 왜 속도가 빠르게 되는 지를 이해하면 된다!

여기까지 문제를 풀고 코드를 외웠다면 기본적인 문제를 도전할 수 있게되고, 구현은 되는데 시간 복잡도와 공간복잡도에서 막히게 되는 실력까지 생길 수 있을 것이다.

그때가 되면 알고리즘을 학습해야 한다. 알고리즘 리스트 여기서 하나씩 알고리즘을 골라서 대표 문제를 도전하고 AI에게 정석 코드를 받아서 외우고 다른 대표 문제를 풀면서 알고리즘을 학습한다.

사실 이걸 적으면서 느낀 건데 이 문제들만 푼다고 바로 코딩테스트의 고수가 될 수는 없을 것이다. 나도 아직 너무 못하기 때문에..

하지만 코딩테스트 초보가 알고리즘을 사용하는 문제에 도달하기 전까지 코딩테스트가 재미없고, 벽이 존재한다고 생각한다. 그 벽을 깨고 알고리즘 문제에 도달할 수 있는 구현 능력을 가지게 되었을 때 코딩테스트를 재밌게 느끼고, 실력이 빠르게 늘 수 있다고 생각하기에 이 4가지 종류의 문제를 충분히 익히는 것을 추천한다!