[취업 준비] 신입 개발자 알고리즘 팁 정리 및 문제 추천

이번에는 취업 준비를 하면서 풀었던 백준 알고리즘 문제 중에서 개인적으로 괜찮았던 문제들을 추천해보고자 합니다. 예전에 풀었던 기록들을 보고 정리한거라 빠진 좋은 문제들도 많이 있을텐데, 댓글 많이 남겨주세요:)

 

 

1. 코딩 테스트(알고리즘) 준비 및 간단한 팁

---

요즘 거의 모든 기업에서 코딩 테스트 전형을 진행하고 있는데, 이번에는 코딩 테스트와 관련된 부분에 대해 이야기해보도록 하겠습니다.

 

 

[ 빈출 유형 파악 ]

수능에도 자주 출제되는 영역이 있듯이 코딩 테스트도 당연히 자주 출제되는 유형이 있습니다. 그렇기 때문에 전략적으로 빈출 유형을 집중적으로 준비하는 것이 도움이 됩니다. 알고리즘 코딩 테스트에서 자주 출제되는 유형은 크게 다음의 4가지가 있습니다.

1. 구현/시뮬레이션: 문제의 요구사항을 주고 이를 구현하거나 시뮬레이션하도록 함
2. 그래프 이론: DFS/BFS와 관련된 알고리즘으로 문제 해결
3. 자료구조: 다양한 자료구조를 사용하여 문제 해결
4. 완전탐색(부르트 포스): 모든 경우를 탐색하여 해결

그 외에도 동적 계획법(Dynamic Programming, 다이나믹 프로그래밍)이나 이진트리, 다른 그래프 알고리즘 등 다른 부분도 충분히 나올 수 있고, 실제로 나오기도 합니다. 하지만 결국 가장 자주 나오고, 많이 준비해야 하는 영역은 위의 4가지 입니다. 우선 위의 4가지 유형은 반드시 준비하고, 회사의 기출에 따라 나왔던 영역을 준비하는 것이 코딩 테스트 전형을 준비하는 가장 효과적인 방법이라고 생각합니다.

그래서 위의 4가지 유형과 그 외에 몇가지를 더해 추천할만한 좋은 문제들을 선별해보고자 합니다.

 

 

[ 준비 방법 ]

저의 경우에는 처음에 기본적인 문제들을 풀면서 알고리즘이라는 전형에 적응을 하기 시작했고, 적응이 끝난 이후에는 빈출되는 유형들 중에서 좋은 문제들을 선별하면서 문제를 풀어나갔습니다. 위의 4가지 알고리즘 유형들 중에서는 구현/시뮬레이션을 먼저 준비할 것을 권장드립니다. 구현/시뮬레이션은 특별한 알고리즘적인 개념이 필요하지 않기 때문에 알고리즘이라는 영역에 적응하기에 쉬우며, 이 부분을 잘 준비해두면 다른 영역을 준비해도 수월합니다.

그리고 문제를 해결한 후에 다른 사람의 문제 풀이를 보는 것도 많은 도움이 됩니다.

 

 

[ Java 알고리즘 최적화 팁 ]

이 내용은 Java로 알고리즘을 준비하시는 분들을 위한 내용이므로 다른 언어를 사용하시는 분들은 건너뛰셔도 됩니다.

일부 회사에서는 알고리즘의 통과 여부에 더해 성능까지 측정하기도 하는데, 물론 기본적으로는 구현을 잘 해야겠지만 공통적으로 다음을 적용하면 조금이나마 성능을 높일 수 있습니다.

1. 입력을 받기 위해서는 Scanner보다 BufferedReader를 사용하는 것이 좋다.
2. 한 줄 입력이 여러번 들어오는 경우에는 split보다 StringTokenizer를 사용하여 파싱하는 것이 좋다.
3. 여러 번 출력해야 하는 경우에는 StringBuilder를 사용해 한번에 출력하는 것이 것이 좋다.
4. Array를 사용하는 것보다 ArrayList를 사용하는 것이 좋다.
5. ArrayList를 정렬하기 위해서는 Collections.sort()를 사용한다.
6. 배열을 초기화하기 위해서는 java.util.Arrays의 Arrays.fill(배열, 초기화값)을 사용한다.
7. 연속으로 있는 숫자를 입력받기 위해서는 1번 대신에 2번을 사용하자 ex) 10111010101
   1. String[] inputs = br.readLine().split(""); 
   2. br.read() - '0';

 

Java로 알고리즘 문제를 풀면 일반적으로 다음과 같이 입력을 받고 이후의 로직을 작성하게 됩니다.

public class Quiz1062 {

    // 입력으로 받는 값들을 저장하기 위한 변수
    private static int N, M;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());


        // 단어 목록을 입력으로 받아서 리스트에 추가한다.
        while(N-->0){
            ... 입력을 받음
        }
        
    }

}

 

 

 

2. 유형별 알고리즘 문제 추천

---

[ 구현 및 시뮬레이션 문제 추천 ]

 

브론즈/실버 난이도

• https://www.acmicpc.net/problem/10798
• https://www.acmicpc.net/problem/2490
• https://www.acmicpc.net/problem/2884
• https://www.acmicpc.net/problem/3048
• https://www.acmicpc.net/problem/2980
• https://www.acmicpc.net/problem/1063
• https://www.acmicpc.net/problem/8979
• https://www.acmicpc.net/problem/2563

 

골드 난이도

• https://www.acmicpc.net/problem/14500
• https://www.acmicpc.net/problem/14890
• https://www.acmicpc.net/problem/17837
• https://www.acmicpc.net/problem/15683
• https://www.acmicpc.net/problem/17144
• https://www.acmicpc.net/problem/15685
• https://www.acmicpc.net/problem/14499
• https://www.acmicpc.net/problem/14891
• https://www.acmicpc.net/problem/15686
• https://www.acmicpc.net/problem/2563
• https://www.acmicpc.net/problem/15686
• https://www.acmicpc.net/problem/14503
• https://www.acmicpc.net/problem/16235
• https://www.acmicpc.net/problem/16236

 

 

 

[ 브루트포스 문제 추천 ]

• https://www.acmicpc.net/problem/1527
• https://www.acmicpc.net/problem/1107
• https://www.acmicpc.net/problem/16943
• https://www.acmicpc.net/problem/1051

 

 

 

[ 자료구조 문제 추천 ]

• https://www.acmicpc.net/problem/1021
• https://www.acmicpc.net/problem/11866
• https://www.acmicpc.net/problem/3190
• https://programmers.co.kr/learn/courses/30/lessons/42583
• https://programmers.co.kr/learn/courses/30/lessons/42746
• https://programmers.co.kr/learn/courses/30/lessons/42587

 

 

 

[ 그래프(넓이 우선 탐색, BFS/ 깊이 우선 탐색, DFS) 문제 추천 ]

 

 

브론즈/실버 난이도

• https://www.acmicpc.net/problem/16236
• https://www.acmicpc.net/problem/2606
• https://www.acmicpc.net/problem/11403
• https://www.acmicpc.net/problem/1325
• https://www.acmicpc.net/problem/1260
• https://www.acmicpc.net/problem/10451
• https://www.acmicpc.net/problem/7569
• https://www.acmicpc.net/problem/7576
• https://www.acmicpc.net/problem/2178
• https://www.acmicpc.net/problem/11403
• https://www.acmicpc.net/problem/2667
• https://www.acmicpc.net/problem/2468
• https://www.acmicpc.net/problem/9205
• https://www.acmicpc.net/problem/2644
• https://www.acmicpc.net/problem/5567

 

골드 난이도

• https://www.acmicpc.net/problem/14502
• https://www.acmicpc.net/problem/16988
• https://www.acmicpc.net/problem/13460
• https://www.acmicpc.net/problem/16234

 

 

[ 백트래킹 문제 추천 ]

• https://www.acmicpc.net/problem/14888
• https://www.acmicpc.net/problem/9663
• https://www.acmicpc.net/problem/14889
• https://www.acmicpc.net/problem/2580
• https://www.acmicpc.net/problem/12100
• https://www.acmicpc.net/problem/1062

 

 

 

[ 동적 계획법(다이나믹 프로그래밍) 문제 추천 ]

• https://www.acmicpc.net/problem/9095
• https://www.acmicpc.net/problem/1932
• https://www.acmicpc.net/problem/1890
• https://www.acmicpc.net/problem/2293
• https://www.acmicpc.net/problem/14501

 

 

 

 

상대적으로 중요한 구현/시뮬레이션과 그래프는 추천 문제가 많아서 난이도 별로 분류하였습니다. 그리고 개인적으로 삼성 기출 문제들 중에서 괜찮은 문제들이 상당히 많이 있었던 것 같습니다. 그렇기 때문에 삼성 기출 문제들 많이 살펴보시는 것도 추천드립니다.

 

막상 정리 해보니 예전에 풀었던 좋은 문제들이 많이 빠진 것 같네요ㅜㅜ 혹시 추천해주실 괜찮은 문제들 있으면 댓글로 남겨주세요! 검토해보고 내용에 추가하겠습니다:)