3월 15일, 4월 12일 이틀을 끊어서 코딩 테스트 특강이 진행되었다.
목적
특강에 앞서 코딩 테스트의 필요성에 대해 알아보았다.
회사 입장에서는 코딩 테스트를 통해 기본적인 문제해결능력을 함양하고 있는지, 자료구조 알고리즘 및 코드 구현 능력이 있는지 효율적으로 판단할 수 있다.
또 회사마다 원하는 인재상이 다르기 때문에 목표로 하는 회사에 따라 전략을 달리 해야 한다.
- 네이버, 카카오 등은 고난이도의 코딩 테스트 실력을 요구하며, CS 전공지식을 깊게 물어본다.
- 당근마켓, 토스 등은 코딩 테스트보다는 과제를 해결하는 데에 중점을 두며, 실제 개발 실력이 있는지 면접단계에서 철저히 검증한다. 또, 프로젝트 및 언어와 관련하여 깊은 지식을 테스트하는 편이다.
- 그 외의 작은 회사들은 간단한 코딩테스트를 통과하는지를 본다.
코딩 테스트에서 효율적으로 공부하기 위해서는
- 시간 복잡도부터 공부해야 하며,
- 자주 나오는 필수 자료구조 및 알고리즘 위주로 공부하고,
- 이론을 제대로 이해하고 문제를 풀어야 한다.
- 구현 능력이 중요하므로, 주력 언어를 정하고 체화해야 한다.
특별히 한 언어를 고집해야 하는 경우가 아니고, 어느 정도 여유가 있다면 파이썬으로 준비하는 것을 추천하는 편이라고 한다.
그래프
이 날은 그래프 문제 풀이법인 BFS, DFS를 주제로 진행되었다.
그래프는 객체 간의 연결 관계를 표현하는 자료구조로, 정점(vertex, node)과 이를 연결하는 간선(edge)으로 구성된다. 현실적으로 가장 많이 쓰이는 자료구조이기 때문에 이를 잘 사용하는 것이 관건이다.
(ex) 지하철 노선도
그래프 종류
- 방향 그래프
- 무방향 그래프(주로 양방향)
- 다중그래프(정점과의 연결관계가 여러 개. 코딩 테스트에는 나오지 않음)
- 단순 그래프(중복된 연관관계 x)
- 가중치 그래프(연결관계마다 가중치를 가진 그래프) “다익스트라 알고리즘”
- 비가중치 그래프
- 순환 그래프(왔던 길을 돌아가지 않고도 시작했던 정점으로 다시 돌아올 수 있는 그래프)
- 비순환 그래프
코딩 테스트에서는 무방향, 단순, 비가중치, 순환 그래프가 자주 출제된다.
(가중치는 dijkstra, 비순환그래프는 DAG, Tree의 별개의 주제로 따로 출제된다.)
그래프 표현 방법
그래프 표현 방법에는 총 3개가지가 있다.
-
인접행렬 adjacency matrix
노드의 개수만큼 2차원 배열을 만들어서 위치를 정하는 방식이다. 장점은 표현하기 쉽다는 점이나, 연결이 되지 않은 경우를 표기할 때 불필요한 메모리를 사용하게 된다는 단점이 있다. -
인접리스트 adjacency list
그래프를 해시맵이나 해시테이블로 구현하는 방법이다. 주로 이 방법을 사용하게 된다. -
암시적 그래프 implicit graph
문제에서 정한 규칙과 주어진 조건대로 그리드를 형성하여 그래프로 해석하는 방식이다. 그 예시로, 1은 벽, 0은 길 식으로 문제에서 조건을 제공하는 것을 들 수 있다.
그래프 순회 Graph Traversal
체계적으로 모든 노드를 방문하는 과정을 말한다. 이 과정에서 각 노드는 최소 한 번 이상 방문된다. 대표적인 알고리즘으로 BFS와 DFS가 있다.
그래프 탐색 Graph Search
특정 조건을 만족하는 노드를 찾는 과정으로, 이 과정에서 모든 노드를 방문할 수도, 목표 노드를 찾으면 탐색을 중단할 수도 있다. 마찬가지로 BFS, DFS를 사용하여 구현할 수 있다.
BFS Breadth First Search
너비우선탐색으로, 시작점에 가까운 순서부터 탐색하는 알고리즘이다. 큐를 사용하며(FIFO), 이 큐에는 아직 방문하지 않은 노드들이 저장된다. 이름 그대로 같은 계층에 있는 노드를 전부 다 방문한 후에 다음 계층으로 넘어간다. 중복 예약을 피하기 위해 노드에 방문하기 전에 해당 노드를 방문한 노드 맵에 저장하며, 이 큐가 다 빌 때까지 while문을 사용해 방문을 예약해 체계적으로 모든 노드를 방문한다.
DFS Depth First Search
깊이우선탐색으로, 시작 노드에서 더 이상 연결된 노드가 없을 때까지 탐색을 반복한다. 먼저 현재 방문한 노드에서, 연결되어 있고 아직 방문하지 않은 노드를 찾고, 그 노드를 방문하여 이를 반복한다. BFS와는 반대로 노드 방문 시점에 해당 노드를 이미 방문한 노드 목록에 추가한다. 또, 재귀를 사용하여 연결된 노드를 다 뚫을 때까지 dfs를 호출하도록 짤 수도 있다.
예시문항: LeetCode 200. Number of Islands
class Solution {
static int rowLength, colLength;
static boolean[][] visited;
static int[] dr = {0,1,0,-1};
static int[] dc = {1,0,-1,0};
public static boolean isValid(int r, int c, char[][] grid){
return (r>=0&&r<rowLength) && (c>=0&&c<colLength)&&(grid[r][c] == '1');
}
public static void bfs(int r, int c, char[][] grid){
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{r,c});
visited[r][c] = true;
while (!queue.isEmpty()){
int[] curPos = queue.poll();
int curRow = curPos[0];
int curCol = curPos[1];
for (int i = 0; i <4 ; i++){
int nextRow = curRow + dr[i];
int nextCol = curCol+dc[i];
if (isValid(nextRow, nextCol, grid)){
if (!(visited[nextRow][nextCol])){
queue.offer(new int[]{nextRow, nextCol});
visited[nextRow][nextCol] = true;
}
}
}
}
}
public int numIslands(char[][] grid) {
int count = 0;
rowLength = grid.length;
colLength = grid[0].length;
visited = new boolean[rowLength][colLength];
for (int i=0; i<rowLength;i++){
for (int j = 0; j<colLength;j++){
if ((grid[i][j] == '1')&&(!visited[i][j])){
bfs(i,j,grid);
count++;
}
}
}
return count;
}
}