SW 역량 테스트 전, 삼성 빈출 코드 유형 정리

삼성 코테는 구현 및 시뮬레이션 유형이 자주 나오는데 빈출 유형을 확실히 숙지하고 가면 좋을거 같다

1. 회전

회전하는 유형은 정말 자주 나오는데 뇌지컬만 구현하려고 할때 틀리기 쉽상이다. 꼭 외워두자.

정사각형 회전

arr = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]

n = len(arr)
# 시계방향 90도 회전
arr_90 = [[0] * n for _ in range(n)]
for i in range(n):
    for j in range(n):
        arr_90[j][n-i-1] = arr[i][j]
print(arr_90)

# 시계방향 180도 회전
arr_180 = [[0]*n for _ in range(n)]
for i in range(n):
    for j in range(n):
        arr_180[n-i-1][n-j-1] = arr[i][j]
print(arr_180)

# 시계방향 270도 (반시계 90도) 회전
arr_270 = [[0]*n for _ in range(n)]
for i in range(n):
    for j in range(n):
        arr_270[n-j-1][i] = arr[i][j]
print(arr_270)

• 90° 회전 (시계): (i, j) → (j, n-1-i)
• 180° 회전: (i, j) → (n-1-i, n-1-j)
• 270° 회전 (시계): (i, j) → (n-1-j, i)

직사각형 회전

arr = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]

def rotate_90(arr):
    r = len(arr)
    c = len(arr[0])
    res = [[0]*r for _ in range(c)] # 배열의 row, col 뒤바뀌는것 주의
    for i in range(r):
        for j in range(c):
            res[j][r-i-1] = arr[i][j]
    return res


def rotate_180(arr):
    r = len(arr)          
    c = len(arr[0])       
    res = [[0]*c for _ in range(r)]  # 결과 배열: r x c (원래 크기 유지)
    for i in range(r):
        for j in range(c):
            res[r-1-i][c-1-j] = arr[i][j]  # 180도 회전
    return res

def rotate_270(arr):
    r = len(arr)          
    c = len(arr[0])       
    res = [[0]*r for _ in range(c)]  # 결과 배열: c x r (90도와 동일)
    for i in range(r):
        for j in range(c):
            res[c-1-j][i] = arr[i][j]  # 270도 회전
    return res

• 90° 회전 (시계): (i, j) → (j, r-1-i)
• 180° 회전: (i, j) → (r-1-i, c-1-j)
• 270° 회전 (시계): (i, j) → (c-1-j, i)

2. 부분 회전

부분 회전은 2차원 배열의 특정 부분만 회전시키는 것이다. 

2차원 배열을 다룰 때의 행 우선 순회(row-major order)를 기억하자.

arr = [[7 * j + i for i in range(1, 8)] for j in range(7)]

start_x, start_y = 2, 2
length = 3

#정사각형 배열의 특정 부분만 회전시키는 함수
def partial_rotate(arr, start_x, start_y, length):
    n = len(arr)
    new_arr = [row[:] for row in arr]  # 깊은 복사

    for y in range(start_y, start_y + length):
        for x in range(start_x, start_x + length):
            oy, ox = y - start_y, x - start_x
            ry, rx = ox, length - 1 - oy
            new_arr[start_y + ry][start_x + rx] = arr[y][x]

    return new_arr

 

회전 전

회전 후

3. 순열 조합

삼성 코테는 itertools 라이브러리 사용이 불가해서, 백트래킹으로 직접 구현해야 한다. DFS와 같이 재귀적으로 모든 경우의 수를 탐색해야 한다. 

순열 (permutations)

def permutations(arr, n, new_arr):
    if len(new_arr) == n:
        print(new_arr)
        return # 해당 지점에서 더 이상 탐색하지 않고 재귀 호출 종료
    for i in range(len(arr)):
        if not visited[i]: # 순서를 고려해야 되서
            visited[i] = True
            permutations(arr, n, new_arr + [arr[i]])
            visited[i] = False # 백트래킹

arr = [1, 2, 3, 4]
visited = [False]*len(arr)
permutations(arr, 2, [])

 

조합 (combinations)

현재 인덱스를 의미하는 변수가 추가된다. 순서가 상관없고 중복 불가여서 현재 인덱스보다 같거나 작은 인덱스는 볼 필요가 없기 때문이다. 따라서 재귀 돌릴때 현재 인덱스+1 값을 넘긴다. 

def combinations(arr, n, new_arr, c):
    # 순서 상관 X, 중복 X
    if len(new_arr) == n:
        print(new_arr)
        return # 현재 호출 종료 
    for i in range(c, len(arr)):  # 순서 상관 없으므로 c부터 시작
        combinations(arr, n, new_arr+[arr[i]], i+1)


arr = [1, 2, 3, 4]
combinations(arr, 2, [], 0)

 

4. 중복 순열조합

중복 순열

def product(arr, n, new_arr):
    if len(new_arr) == n:
        print(new_arr)
        return
    for i in range(len(arr)):
        product(arr, n, new_arr+[arr[i]])
        
arr = [1, 2, 3, 4]
product(2, [])

 

중복 조합

def combination_dupli(arr, n, new_arr, c):
    if len(new_arr) == n:
        print(new_arr)
        return 
    for i in range(c, len(arr)):
        combination_dupli(arr, n, new_arr+[arr[i]],i)

combination_dupli(arr, 2, [], 0)

 

5. 중력

바닥까지 하강하는 매커니즘이다.

arr = [[0, 1, 0], [1, 0, 1], [0, 1, 0], [0, 0, 1], [0, 1, 0]]

print(arr)

def gravity():
    r = len(arr)
    c = len(arr[0])
    for i in range(r - 1):
        for j in range(c):
            p = i
            # 현재칸이 아래로 내려갈 수 있다면 그 윗줄도 한 칸 씩 연쇄적으로 내려와야함
            while 0 <= p and arr[p][j] == 1 and arr[p + 1][j] == 0:
                arr[p][j], arr[p + 1][j] = arr[p + 1][j], arr[p][j]
                p -= 1

gravity()
print(arr)