[Algorithm] 삼성 SW 역량 테스트(코딩 테스트) 자주 나오는 알고리즘 유형 정리(유형별 Python Code 및 문제)

 

본 포스팅에서 삼성 SW 역량 테스트를 준비하며 자주 출제되는 문제를 알고리즘 별로 정리하고 Python 예시 코드를 살펴보겠습니다.

삼성 SW 역량 테스트 기출 문제는 Baekjoon Online Judge 문제를 기준으로 하였습니다. 또한 각 알고리즘을 푸는 방식은 여러 방법이 존재할 수 있습니다.

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

문제집: 삼성 SW 역량 테스트 기출 문제 (baekjoon)

---

1. 기본 알고리즘

---

삼성 기출 문제는 보통 2차원 배열을 이용한 구현, 시뮬레이션 문제를 주로 다룹니다. 비교적 최근 문제인 컨베이어 벨트 위의 로봇(https://www.acmicpc.net/problem/20055) 문제는 1차원 배열로 풀 수 있었으나, 대부분은 2차원 배열을 이용한 문제가 많이 나옵니다.

대부분의 문제에 기본으로 사용되는 알고리즘은 완전 탐색(브루트 포스), BFS(Breadth First Search), DFS(Depth First Search), 순열, 조합 입니다. 각 알고리즘의 차이를 이해하고 상황에 맞게 코드를 작성할 수 있어야합니다. 

1.1 BFS

보통 2차원 배열 문제가 나오는 삼성 코딩테스트에서 BFS는 거의 대부분의 문제에 사용되는 알고리즘입니다.
예를 들어 배열의 (r, c) 위치에서 동서남북 4방향(가끔 대각선 포함 8방향)으로 값을 탐색하는 경우에 자주 사용됩니다.

저는 대부분 deque를 이용하여 문제를 해결합니다. Python 예시 코드는 다음과 같습니다.

from collections import deque
 
#      ↑   ←   ↓   →
dy = (-1,  0,  1,  0)
dx = ( 0, -1,  0,  1)
 
def out_ot_range(y, x): # 격자에서 벗어났는지 확인하는 함수
    return y < 0 or x < 0 or y >= N or x >= N
 
 
def bfs(y, x):
    q = deque() # queue
    # 시작 좌표(y, x) 삽입 및 visited 표시
    q.append((y, x))
    visited = [[False] * N for _ in range(N)] # NxN 격자의 경우
    visited[y][x] = True
 
    while q: #queue에 값이 존재하는 동안 반복
        sy, sx = q.popleft() 
        for d in range(4): # pop한 좌표의 4방향 탐색
            ny = sy + dy[d]
            nx = sx + dx[d]
 
            if out_ot_range(ny, nx) or visited[ny][nx]: # 격자에서 벗어났거나, 방문한 좌표의 경우 continue
                continue
            else: # 아닌 경우 (상황에 따라 다른 예외가 있는 경우 처리해야합니다.)
                do_something() # 이후 동작 호출(혹은 코드를 바로 작성하여도 무방)
                q.append((ny, nx)) # queue에 탐색한 좌표 추가 및 방문 기록
                visited[ny][nx] = True
 

추천 문제

- 골드5 로봇청소기(https://www.acmicpc.net/problem/14503)
- 골드2 상어 중학교 (https://www.acmicpc.net/source/41094409)

1.2 DFS를 이용한 조합 구현

조합 + DFS 알고리즘은 OO 중 M개를 골랐을 때 최소(최대)가 되는 값을 찾으세요(순서가 없는 경우). 와 같은 형식의 문제가 있을 때 사용할 수 있습니다.

이 때 itertools.combinations() 와 같은 기본 라이브러리 함수를 사용하면 편하게 구현할 수 있지만 삼성 코딩테스트에서는 해당 라이브러리의 사용이 불가합니다. (이외에도 sys 등 사용 불가한 라이브러리들이 존재합니다.)

저는 보통 재귀함수를 이용합니다. 파이썬에서 재귀 호출의 제한이 꽤 엄격한 편이지만 M개를 선택하는 조합 문제에서 재귀 제한(기본 1000번)이 걸릴 정도로 재귀가 깊어지는 경우는 잘 없었으며, 그런 경우에는 다른 알고리즘을 사용하는게 맞을 것 같습니다.

위의 예시에서 comb 변수는 deque를 사용하였는데, list로 구현하여도 무방합니다.

파이썬 예시 코드는 다음과 같습니다.

from collections import deque
 
def do_something(comb):
    print(comb)
 
M = 3
some_list = [1, 2, 3, 4]
 
 
def dfs(comb: deque, depth: int):
    if len(comb) == M:  # 종료 조건 1 : M개를 모두 선택했을 때
        do_something(comb)  # 선택 후의 알고리즘 호출
        return
    elif depth == len(some_list):  # 종료 조건 2: 리스트의 마지막 까지 탐색했을 때
        return
 
    # 현재 depth의 값 포함 재귀 호출
    comb.append(some_list[depth])
    dfs(comb, depth + 1)
 
    # 현재 depth의 값 미포함 재귀 호출
    comb.pop()
    dfs(comb, depth + 1)
 
dfs(deque(), 0)
 

 

위의 코드 출력 결과 (4C3 이므로 결과는 4개) : (1, 2, 3) ~ (2, 3, 4)까지

deque([1, 2, 3])
deque([1, 2, 4])
deque([1, 3, 4])
deque([2, 3, 4])

추천 문제

- 골드5 치킨 배달(https://www.acmicpc.net/problem/15686)
- 골드4 연구소 3(https://www.acmicpc.net/problem/17142)

1.3 DFS를 이용한 순열 구현

순열 + DFS 알고리즘은 OO 중 M개를 골랐을 때 최소(혹은 최대)가 되는 값을 찾으세요(순서가 있는 경우). 와 같은 형식의 문제가 있을 때 사용할 수 있습니다.

이 또한 재귀함수를 이용하며 1.1 DFS를 이용한 조합 구현과 비슷하지만 depth가 아닌 visited 변수를 이용하여 방문 기록을 확인하며 재귀를 호출한다는 점이 다른 점입니다.

중복을 허용하므로 재귀가 호출될 때마다 리스트의 모든 값을 탐색한 후 방문하지 않은 노드를 포함하여 재귀함수를 호출합니다. 중복을 허용하지 않는 조합과 비교하여 보면 더 좋을 것 같습니다.

from collections import deque
 
def do_something(perm):
    print(perm)
 
M = 3
some_list = [1, 2, 3, 4]
 
visited = [False] * len(some_list)
result = []
def dfs(perm: deque):
    if len(perm) == M:  # 종료 조건 : M개를 모두 선택했을 때
        result.append(list(perm))
        do_something(perm)
        return
 
    for i, val in enumerate(some_list):
        if visited[i]: # 방문한 노드인 경우 제외
            continue
        # i번째 노드를 포함하여 재귀 호출
        perm.append(val)
        visited[i] = True
        dfs(perm)
        # i번째 노드 삭제
        perm.pop()
        visited[i] = False
 
dfs(deque())
 

 

위의 코드 출력 결과(4P3 이므로 24개) : (1,2,3) ~ (4,3,2) 까지

deque([1, 2, 3]) deque([1, 2, 4]) deque([1, 3, 2]) deque([1, 3, 4]) deque([1, 4, 2]) deque([1, 4, 3]) deque([2, 1, 3]) deque([2, 1, 4]) deque([2, 3, 1]) deque([2, 3, 4]) deque([2, 4, 1]) deque([2, 4, 3]) deque([3, 1, 2]) deque([3, 1, 4]) deque([3, 2, 1]) deque([3, 2, 4]) deque([3, 4, 1]) deque([3, 4, 2]) deque([4, 1, 2]) deque([4, 1, 3]) deque([4, 2, 1]) deque([4, 2, 3]) deque([4, 3, 1]) deque([4, 3, 2])

추천 문제

- 골드1 마법사 상어와 복제 (https://www.acmicpc.net/problem/23290)

 

2. 특수 알고리즘

---

삼성 코딩테스트에서 선호(?)하는 특수한 알고리즘의 유형들이 있습니다. 매번 등장하는 문제의 유형들은 아니지만 꽤나 반복적으로 등장하므로 미리 알아두면 좋을것 같습니다.

특히 전혀 모른 상태로 시험장에서 문제를 만나면 멘붕이 오기 쉬운 문제 유형들입니다.

2.1 2차원 배열의 나선형 알고리즘

이름을 어떻게 지어야할지 몰라 위와 같이 지었습니다. 2차원 배열의 나선형 알고리즘은 다음 그림과 같이 2차원 배열을 처리하는 방식의 알고리즘입니다.

[백준 20057번] 마법사 상어와 토네이도에서 토네이도의 이동

기본적으로는 홀수길이의 2차원 배열의 중심에서 시작하여 방향을 바꾸며 이동(혹은 탐색)을 하는데, 방향을 2번 바꿀 때마다 이동 거리가 1씩 증가하는 형식의 알고리즘입니다.

5x5 격자에 중앙에서부터 번호를 붙이는 파이썬 코드는 다음과 같습니다.

N = 5
board = [[0] * N for _ in range(N)]
 
#      ←   ↓   →   ↑ (4방향, 시작방향: 서쪽)
dy = ( 0,  1,  0, -1)
dx = (-1,  0,  1,  0)
 
 
def init_grid():
    y = x = int(N / 2) # 배열의 중앙 좌표
    direction = move_count = number = 0
    dist = 1
 
    while True:
        move_count += 1 # 움직인 횟수
        for _ in range(dist): # dist만큼 direction 방향으로 이동
            ny = y + dy[direction]
            nx = x + dx[direction]
 
            # 종료 조건 : 이동한 좌표가 (0, -1)인 경우(배열의 길이가 홀수면 항상 마지막 좌표는 (0, -1), 방향은 서쪽
            if (ny, nx) == (0, -1):
                return
            # 번호 증가 및 기록
            number += 1
            board[ny][nx] = number
 
            # (y, x) 갱신
            y = ny
            x = nx
 
        if move_count == 2: # 어떠한 방향으로든 2번 이동한 경우
            dist += 1 # 이동거리 1 증가
            move_count = 0 # 초기화
        direction = (direction + 1) % 4 # 방향 변경
 
init_grid()
for row in board:
    print(row)
 

 

위의 코드 출력 결과(나선형 형태를 따라서 번호가 0~24번까지 기록됨)

[24, 23, 22, 21, 20]
[9, 8, 7, 6, 19]
[10, 1, 0, 5, 18]
[11, 2, 3, 4, 17]
[12, 13, 14, 15, 16]

추천 문제

- 골드3 마법사 상어와 토네이도(https://www.acmicpc.net/problem/20057)
- 골드1 마법사 상어와 블리자드(https://www.acmicpc.net/problem/21611)

2.2 배열 돌리기

2차원 배열을 45도 90도 180도 등 다양한 형태로 회전시키는 유형의 문제도 자주 등장합니다. 특히 난이도가 높은 문제에 속하는 어항정리(https://www.acmicpc.net/problem/23291) 문제의 경우에는 직사각형의 배열을 회전시키기도 합니다.

특히 단순히 2차원 배열을 회전시키는것 보단 2차원 배열 내에서 사각형 형태로 배열을 잘라 해당 배열만 회전시키는 방식으로 회전시키는 문제들이 있습니다. 생각만해도 머리가 복잡하니 연습을 해두면 좋을것 같습니다.

N = 5
board = [[i * N + j for j in range(N)] for i in range(N)]
 
 
def rotate45():
    # 시계방향으로 배열을 45도 회전하는 함수
    new_board = [[0] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            new_board[i][j] = board[N - j - 1][i]
    return new_board
 
 
print("원본")
for row in board:
    print(row)
print()
 
print("시계방향 45도 회전")
rotated = rotate45()
for row in rotated:
    print(row)
 

 

위의 코드 출력 결과

원본
[0, 1, 2, 3, 4]
[5, 6, 7, 8, 9]
[10, 11, 12, 13, 14]
[15, 16, 17, 18, 19]
[20, 21, 22, 23, 24]

시계방향 45도 회전
[20, 15, 10, 5, 0]
[21, 16, 11, 6, 1]
[22, 17, 12, 7, 2]
[23, 18, 13, 8, 3]
[24, 19, 14, 9, 4]

추천 문제

- 골드4 마법사 상어와 파이어스톰(https://www.acmicpc.net/problem/20058)
- 플래티넘5 어항 정리(https://www.acmicpc.net/problem/23291) - (어려움)
- 배열 돌리기 시리즈(https://www.acmicpc.net/problem/16926)

---

삼성 SW 역량 테스트를 준비하며 자주 출제되는 문제를 알고리즘 별로 정리하고 Python 예시 코드를 살펴았습니다. 

위의 알고리즘을 모두 숙지했다고 해서 삼성 코딩테스트에 통과할 수 있는 것은 아닙니다. 문제를 읽고 문제에서 요구하는 바를 코드로서 구현할 수 있어야합니다. 삼성 코딩테스트에서는 보통 복잡한 구현 및 시뮬레이션 문제가 등장하므로 코드를 작성하는 것도 중요하지만, 문제를 제대로 읽는것이 중요하다고 생각합니다.

문제를 풀어보며 더 다양한 유형의 문제들이 있다면 업데이트하도록 하겠습니다.