SW 역량 테스트 치르기 전 숙지하면 좋을 삼성 빈출 코드 유형 정리 🕵🏼‍♀️🌀🦈

Konseo·2023년 10월 9일
64

코테풀이

목록 보기
39/59
post-thumbnail

삼성 기출에서 자주 나오는 & 숙지하면 좋을 코드 유형들을 추려보았습니다
혹시 자주 나오는 또다른 유형이 있다면 댓글로 알려주시면 감사하겠습니다 ! 🙇🏻‍♀️

1. 회전

(1) zip() 활용해서 회전

  • 정사각형, 직사각형 모두 적용 가능
arr = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]]

## zip
# 시계 방향 90 (= 반시계 방향 270)
arr_90 = list(map(list, zip(*arr[::-1])))
print(arr_90)

# 시계 방향 180 (= 반시계 방향 180)
arr_180 = [a[::-1] for a in arr[::-1]]
print(arr_180)

# 시계 방향 270 (= 반시계 방향 90)
arr_270 = [x[::-1] for x in list(map(list, zip(*arr[::-1])))[::-1]]
print(arr_270)
  • 비교적 생각하기 쉽고 빠르게 구현할 수 있다
  • (+) 정사각형이 아닌 직사각형의 경우에도 배열의 인덱스 고민없이 빠르게 처리하기 좋다
  • (-) 메모리나 시간 복잡도 면에서는 2번 방식보다 좋지 않다

(2) 인덱스 규칙 찾아서 회전

정사각형

## 인덱싱
arr = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
n = 3
# 시계 방향 90 (= 반시계 방향 270)
new_90 = [[0] * n for _ in range(n)]
for i in range(n):
    for j in range(n):
        new_90[j][n - i - 1] = arr[i][j]
print(new_90)

# 시계 180 & 반시계 180
new_180 = [[0] * n for _ in range(n)]
for i in range(n):
    for j in range(n):
        new_180[n - i - 1][n - j - 1] = arr[i][j]
print(new_180)

# 시계 270 & 반시계 90
new_270 = [[0] * n for _ in range(n)]
for i in range(n):
    for j in range(n):
        new_270[n - 1 - j][i] = arr[i][j]
print(new_270)

직사각형

def rotated_90(a):
  m= len(a)
  n = len(a[0])
  result = [[0]* m for _ in range(n)] # 배열의 가로 세로 길이가 뒤바뀌는 것 주의
  for i in range(m): # 범위 주의
    for j in range(n): # 범위 주의
      result[j][m-i-1] = a[i][j]
  return result

def rotated_180(a):
  n= len(a)
  m = len(a[0])
  result = [[0]* m for _ in range(n)] 
  for i in range(n): # 범위 주의
    for j in range(m): # 범위 주의
      result[n-i-1][m-j-1] = a[i][j]
  return result

def rotated_270(a):
  n= len(a)
  m = len(a[0])
  result = [[0]* n for _ in range(m)] # 배열의 가로 세로 길이가 뒤바뀌는 것 주의
  for i in range(n): # 범위 주의
    for j in range(m): # 범위 주의
      result[m-1-j][i] = a[i][j]
  return result

a=[[1,2,3,4],[5,6,7,8],[9,10,11,12]]
print(rotated_90(a))
print(rotated_180(a))
print(rotated_270(a))
  • 외워둔다면 해당 방식 또한 쉽고 빠르게 구현이 가능하다

2. 부분 회전

부분 회전은 말그대로 2차원배열의 특정 부분만 회전시키는 것을 말한다. 보기엔 간단해 보일 수 있어도 꼭 step 별로 구현하는 것을 추천한다. (나중에 해당 부분에서 꼬이게 되면 디버깅 하기 힘들기 때문)

# 7X7 배열
arr = [[7 * j + i for i in range(1, 8)] for j in range(7)]
new_arr = [[0] * 7 for _ in range(7)]
sy, sx = 2, 2
length = 3


# 배열의 특정 부분(정사각형)을 회전시킴
def rotate_90(sy, sx, length):
    global arr, new_arr
    # 정사각형을 시계방향으로 90도 회전
    for y in range(sy, sy + length):
        for x in range(sx, sx + length):
            # 1단계 : (0,0)으로 옮겨주는 변환을 진행함
            oy, ox = y - sy, x - sx
            # 2단계 : 90도 회전했을때의 좌표를 구함
            ry, rx = ox, length - oy - 1
            # 3단계 : 다시 (sy,sx)를 더해줌
            new_arr[sy + ry][sx + rx] = arr[y][x]

    # new_arr 값을 현재 board에 옮겨줌
    for y in range(sy, sy + length):
        for x in range(sx, sx + length):
            arr[y][x] = new_arr[y][x]
            print(arr[y][x])

rotate_90(sy, sx, length)

for i in range(len(arr)):
    print(arr[i])
  • 원본

  • 회전 후

3. 순열, 중복 순열, 조합, 중복 조합

삼성 코테는 itertools 라이브러리 사용 불가하다. 백트래킹으로 직접 구현해서 써야한다.

순열 (permutations)

arr = [1, 2, 3, 4]
visited = [0] * len(arr)  # visited도 전역으로 둬도 됨


def permutations(n, new_arr):
    global arr
    # 순서 상관 0, 중복 X
    if len(new_arr) == n:
        print(new_arr)
        return
    for i in range(len(arr)):
        if not visited[i]:
            visited[i] = 1
            permutations(n, new_arr + [arr[i]])
            visited[i] = 0


permutations(2, [])
  • 순서 0, 중복 X
  • 유일하게 visited 배열이 있음 -> 순서를 고려해야하기 때문
  • parameter : 뽑을 개수, 뽑힌 값을 담는 배열
  • 전역변수 : visited 배열

중복 순열 (product)

arr = [1, 2, 3, 4]
def product(n, new_arr):
    global arr
    # 순서 상관 0, 중복 0
    if len(new_arr) == n:
        print(new_arr)
        return
    for i in range(len(arr)):
        product(n, new_arr + [arr[i]])

product(2, [])
  • 순서 0, 중복 0
  • 부가 조건이 없는 가장 라이트한 코드라고 생각하기
  • parameter : 뽑을 개수, 뽑힌 값을 담는 배열

조합 (combinations)

arr = [1, 2, 3, 4]

# 현재 인덱스 +1 만큼을 매개변수로 계속 넘겨주어야함
# 순서가 상관없고 중복 불가이기 때문에 현재 인덱스보다 같거나 작은 인덱스는 볼 필요가 없기 때문
def combinations(n, new_arr, c):
    # 순서 상관 X, 중복 X
    if len(new_arr) == n:
        print(new_arr)
        return
    for i in range(c, len(arr)):
        combinations(n, new_arr + [arr[i]], i + 1)


combinations(2, [], 0)
  • 순서 X, 중복 X
  • 현재 인덱스를 의미하는 매개변수가 추가됨
    • 순서가 상관없고 중복 불가이기 때문에 현재 인덱스보다 같거나 작은 인덱스는 볼 필요가 없기 때문임. 따라서 재귀돌릴때 현재 인덱스+1 값을 넘김
  • parameter : 뽑을 개수, 뽑힌 값을 담는 배열, 현재 인덱스

중복 조합 (combinations_with_replacement)

arr = [1, 2, 3, 4]

def combinations_with_replacement(n, new_arr, c):
    # 순서 상관 X, 중복
    if len(new_arr) == n:
        print(new_arr)
        return
    for i in range(c, len(arr)):
        combinations(n, new_arr + [arr[i]], i)


combinations_with_replacement(2, [], 0)
  • 순서 X, 중복 0
  • 조합과 동일하게 현재 인덱스를 의미하는 매개변수가 추가됨
    • 중복 가능하므로 재귀 돌릴때 현재 인덱스+1가 아닌 현재 인덱스 값을 그대로 넘김
  • parameter : (뽑을 개수, 뽑힌 값을 담는 배열, 현재 인덱스)

4. 중력

바닥까지 하강

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

print("기존")
for i in range(len(arr)):
    print(arr[i])


def gravity():
    n = len(arr)
    m = len(arr[0])
    for i in range(n - 1):
        for j in range(m):
            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("변화")
for i in range(len(arr)):
    print(arr[i])
  • 윗줄부터 차례로 중력을 가한다고 생각하기
  • 현재칸이 아래칸으로 내려갈 수 있다면 현재칸으로부터 윗줄에 있는 모든 칸이 한 칸 씩 연쇄적으로 내려와야하므로 while문 로직이 존재함
  • 위 코드 기반에서 특정 조건들이 붙는 경우가 많음
    • ex. 특정 블럭에 닿을 때까지 하강한다 (=특정 블럭은 움직이지 않는다)

5. 달팽이(나선형) 배열 🐌

2차원 배열에서 시작 지점을 기준으로 나선형으로 값에 접근하는 코드 유형이다
어딘가에선 토네이도 🌪 코드라고도 불리는 듯 하다

안에서 밖으로

arr = [[0] * 5 for _ in range(5)]


def tornado():
    global arr
    d = [(0, -1), (1, 0), (0, 1), (-1, 0)]
    y = len(arr) // 2
    x = len(arr) // 2
    num = 0  # 칸에 채워넣을 값
    dist = 1
    d_idx = 0  # 서 남 동 북 순서
    move_count = 0  # 2가 되면 dist 길이가 1 늘어나고 move_count는 다시 0으로 초기화
    while True:
        for _ in range(dist):
            dy, dx = d[d_idx]
            Y = dy + y
            X = dx + x
            if (Y, X) == (0, -1):  # 0행 -1열이 토네이도가 모두 끝나고 나서의 위치임
                return
            num += 1
            arr[Y][X] = num
            y = Y
            x = X
        move_count += 1
        d_idx = (d_idx + 1) % 4
        if move_count == 2:
            dist += 1
            move_count = 0


tornado()
for i in range(5):
    print(arr[i])

  • 돌아가는 순서는 문제마다 다를 수 있다 (위 코드는 좌->하->우->상 방향)

밖에서 안으로

def solution(n):
    if n == 1:
        return [[1]]

    answer = [[0 for j in range(n)] for i in range(n)]  # 배열 초기화

    x = 0
    y = 0
    d_idx=0

    for i in range(n * n):
        answer[x][y] = i + 1
        if d_idx == 0:
            y += 1
            if y == n - 1 or answer[x][y + 1] != 0:  # 맨 끝에 도달했거나 가려는 곳에 이미 값이 있으면 방향 전환
                d_idx = 1
        elif d_idx == 1:
            x += 1
            if x == n - 1 or answer[x + 1][y] != 0:
                d_idx = 2
        elif d_idx == 2:
            y -= 1
            if y == 0 or answer[x][y - 1] != 0:
                d_idx = 3
        elif d_idx == 3:
            x -= 1
            if x == n - 1 or answer[x - 1][y] != 0:
                d_idx = 0

    return answer


arr=solution(5)
for i in range(len(arr)):
    print(arr[i])
  • 밖에서 안으로 들어가는 것은 더욱 쉽다. 별도의 move_count나 dist를 두지 않아도 되기 때문이다.
  • 프로그래머스에 정수를 (0,0)에서부터 나선형으로 배치하는 문제와 같은 문제라고 생각하면 된다.

6. 이동 중 벽에 부딪혀서 방향이 전환되는 경우

낚시왕 문제는 아래 방식대로 코드를 짜지 않으면 시간초과가 난다. 아래 코드의 경우 한 번에 코드를 이해하기 힘들 수 있는데 해당 영상이 이해하는 데 도움이 될 수 있으니 참고해 보면 좋을 듯 하다

def get_next_loc(i, j, speed, dir):

    if dir == UP or dir == DOWN:  # i
        cycle = R * 2 - 2
        if dir == UP:
            speed += 2 * (R - 1) - i
        else:
            speed += i

        speed %= cycle
        if speed >= R:
            return (2 * R - 2 - speed, j, UP)
        return (speed, j, DOWN)

    else:  # j
        cycle = C * 2 - 2
        if dir == LEFT:
            speed += 2 * (C - 1) - j
        else:
            speed += j

        speed %= cycle
        if speed >= C:
            return (i, 2 * C - 2 - speed, LEFT)
        return (i, speed, RIGHT)

7. 배열 한 칸씩 돌리기

백준의 배열돌리기1 문제 풀이이다 !

from collections import deque

N, M, R = map(int, input.split())

arr = []
new_arr = [[0]*M for _ in range(N)]
q = deque()

for i in range(N):
    arr.append(list(input().split()))

loops = min(N, M) // 2
for i in range(loops):
    q.clear()
    q.extend(arr[i][i:M-i])
    q.extend([row[M-i-1] for row in arr[i+1:N-i-1]])
    q.extend(arr[N-i-1][i:M-i][::-1])
    q.extend([row[i] for row in arr[i+1:N-i-1]][::-1])
    
    q.rotate(-R)
    
    for j in range(i, M-i):                 # 상
        new_arr[i][j] = q.popleft()
    for j in range(i+1, N-i-1):             # 우
        new_arr[j][M-i-1] = q.popleft()
    for j in range(M-i-1, i-1, -1):           # 하
        new_arr[N-i-1][j] = q.popleft()  
    for j in range(N-i-2, i, -1):           # 좌
        new_arr[j][i] = q.popleft()    

return new_arr
profile
둔한 붓이 총명함을 이긴다

8개의 댓글

comment-user-thumbnail
2023년 10월 14일

좋은 글 감사합니다 :)

1개의 답글
comment-user-thumbnail
2023년 10월 14일

삼성 코딩테스트 전날에 정말 도움되는 글입니다. 감사합니다~~

1개의 답글
comment-user-thumbnail
2024년 1월 23일

많은도움되었습니다 !!

답글 달기
comment-user-thumbnail
2024년 4월 5일

270도 회전 이렇게는 어떤가요
arr_270 = list(map(list, zip(*arr)))[::-1]

답글 달기
comment-user-thumbnail
2024년 4월 6일

참고해요! 감사합니다!

답글 달기
comment-user-thumbnail
2024년 9월 19일

공부하는데 많은 도움 되었습니다. 감사합니다!

답글 달기