(2장-1) 역량 테스트 출제 유형

안녕하세요. 지칸입니다.

2장에서는 자주 출제되는 유형에 대해 간단히 살펴보겠습니다.

1장에서 처럼 기본적으로 자주 사용하는 템플릿이 있고 문제에서 요구하는 사항을 반영하여 약간의 수정이 필요합니다.

문제 분석 과정에서 어떤 알고리즘을 써야겠다고 생각이 든다면 기계적으로 외웠던 템플릿을 먼저 작성합니다.

 

2-1) DFS, BFS 유형

2-2) 경우의 수, 순열, 조합 유형

2-3) 시뮬레이션 유형

2-4)1~3 혼합 유형

---

2-1) DFS, BFS 유형

그래프 탐색으로쓰이는 DFS, BFS는 자주 출제되는 유형입니다. 각 알고리즘에 대한 설명은 추후 설명하도록 하겠습니다. 자주 사용하는 코드를 보여드리겠습니다.

그림1은 DFS 코드입니다. DFS는 재귀함수로 구현하는 경우가 대부분인데 저는 stack를 사용하여 구현하였습니다.

(재귀함수보다 이해하기가 편했습니다.)

그림2

그림2는 BFS 코드입니다. BFS는 queue를 사용하여 구현하였습니다.

 

각 알고리즘은 방문하는 정점의 순서만 다를 뿐 시작 정점으로부터 연결된든 정점을 방문합니다.

두 알고리즘의 장단점이 존재하고 어떤 문제냐에 따라 두 알고리즘의 성능에 큰 차이가 있을 수 있습니다.

하지만 신입 공채 역량 테스트 레벨에서는 계산량 자체가 큰 편이 아니므로 어떤 알고리즘을 사용해도 상관없다고 생각합니다. 이해하기 쉽고 외우기 쉬운 알고리즘 1개만 익혀도 성공입니다.

 

 

문제에 따라 어디를 수정해야 하는지는 다를 수 있습니다. 방문하는 정점 값이 필요하면 printV 배열처럼 저장하거나 정점과 간선으로 연결된 모든 정점을 찾을 때 2차원 맵이고 4 방향으로만 주어진다면 정점 기준 4곳의 정점만 조건을 확인할 수 있습니다. 혹은 방문하지 않은 정점이 필요하면 visit배열을 전체 검색하면서 찾을 수 있습니다.

이렇듯 알고리즘을 어떻게 쓸 것인가는 문제 분석 단계에서 고민해봐야 합니다.

(이 부분은 많은 문제를 풀어보며 응용하는 방법을 익히는 편이 좋다고 생각합니다.)

 

다양한 DFS/BFS문제를 풀어보면서 템플릿을 어떻게 수정하는지 보여드리겠습니다.

2021.04.08 - [알고리즘/SW역량테스트 기출문제] - [백준 17142번] 연구소 3 (조합, BFS)

2021.04.08 - [알고리즘/SW역량테스트 기출문제] - [백준 14502번] 연구소 (조합, BFS)

 

역량테스트 유사 문제 기준으로는 백준사이트에서 제공하고 있습니다.

(https://www.acmicpc.net/workbook/view/1152)