coding test - python/SAMSUNG SWT(SW역량 테스트)
[삼성 SW 역량테스트 대비] 빈출 개념 6가지 (배열 회문, 조합, 순열 등)
sillon
2024. 9. 12. 20:07
728x90
반응형
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])- 원본
- !https://velog.velcdn.com/images/rhdmstj17/post/a6d76525-e2a9-4f21-a67d-1f29a9da2e0f/image.png
- 회전 후
- !https://velog.velcdn.com/images/rhdmstj17/post/ce6231eb-b35d-474c-a569-39d9c418d4f0/image.png
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. 특정 블럭에 닿을 때까지 하강한다 (=특정 블럭은 움직이지 않는다)
- !https://velog.velcdn.com/images/rhdmstj17/post/0106aa54-0e6b-4bf9-abee-1edd7b89d72d/image.png
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])!https://velog.velcdn.com/images/rhdmstj17/post/ce47c190-ff73-4b08-881e-0048ebd99c2a/image.png
- 돌아가는 순서는 문제마다 다를 수 있다 (위 코드는 좌->하->우->상 방향)
밖에서 안으로
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
reference
728x90
반응형