2차원 배열 유형 문제

삼성역량테스트에서 출제되는 코테문제들의 경우 2차원 배열을 특정한 기준을 통해 회전시키는 문제가 자주 출제됩니다.

그래서 이번 포스트에서는 관련된 유사한 유형의 문제들로 코테에 자주 등장하는 2차원 배열을 능숙하게 다루는 유형을 대비하여 봅시다.

관련 문제)


백준) 배열 돌리기 3(16935번)

배열돌리기 3_백준

  • 문제 설명: N*M 크기의 2차원 배열에 대하여 6가지의 연산을 구현하는 문제입니다.

  • 1번 연산


1번 연산

1번 연산을 두가지의 방법으로 풀이해보려고 합니다.
우선 첫번째 방법은, 파이썬의 리스트 컴프리핸션 방식을 잘 활용해주는 방법입니다.

첫번째 방법, 구현 과정

기존의 배열을 가장 아래 열에서부터 읽으면서 새롭게 저장한다.

def op1(a):
    n = len(a)
    a = [a[i][:] for i in range(n-1, -1, -1)]
    return a

처음 위의 표현을 볼 때는, 세번째 줄에 대해서 조금 설명을 덧붙이자면,
“내가 a 2차원 배열을 다시 새롭게 만들건데! a[i]번째 row를 싹다 긁어서 덮어씌울꺼야! 근데 i는 역순으로 가장 밑(idx:n-1)에서부터 시작해서 가장 위에(idx: 0) 순서로 정했어” 라고 할 수가 있습니다.

리스트 컴프리헨션 문법에 대해 궁금하다면, 파이썬 요약 포스트를 참고해 주시기 바랍니다.
Introducing Python 정리(1) 컴프리헨션 부분

두번째 방법, 구현 과정

문제에서 주어진 연산1 정의를 그대로 구현한다.

def op1(a):
    n = len(a)
    m = len(a[0])
    # 새롭게 저장할 tmp 2차원 배열을 선언합니다.
    tmp=[[0]*m for _ in range(n)]
    for i in range(n):
      for j in range(m):
        tmp[i][j]=a[m-i-1][j]
    return tmp

새로운 tmp 2차원 배열을 선언하여, a 2차원 배열을 아래에서 부터 읽어서 저장합니다.
새로운 2차원 배열이 필요한 이유는, 기존의 2차원 배열에 덮어씌우는 방식으로 한다면 반복문이 진행되는 과정에서 읽어들어오는 배열이 이미 새로운 값으로 바뀌어 있는 경우가 발생하기 때문입니다.

  • 2번 연산


2번 연산

2번 연산도 1번 연산과 마찬가지로 전체적인 구현은 비슷합니다.
아래 row에서 부터 읽던 방식 대신 오른쪽 col에서부터 읽어오면 됩니다.

구현 과정

기존의 배열을 가장 오른쪽 행에서부터 읽으면서 새롭게 저장한다.

def op2(a):
    n = len(a)
    m = len(a[0])
    for i in range(n):
        tmp = []
        for j in range(m-1, -1, -1):
            tmp.append(a[i][j])
        # 아래의 방법도 마찬가지 입니다.
        # for j in range(m):
        #     tmp.append(a[i][m-j-1])
        a[i] = tmp
    return a
  • 3번 연산, 4번 연산


3번 연산


4번 연산

3번 연산은, 2차원 배열에 왼쪽에서부터 아래에서 위로 선을 그으면서 읽고, 가로로 선을 그으면서 저장하면 됩니다.
4번 연산도 비슷한 방식으로 오른쪽에서 부터 위에서 아래로 선을 그으면서 읽고, 가로로 선을 그으면서 저장하면 됩니다.

def op3(a):
    n = len(a)
    m = len(a[0])
    ans = []
    for i in range(m):
        tmp = []
        for j in range(n):
            tmp.append((a[n-j-1][i]))
        ans.append(tmp)
    return ans

def op4(a):
    n = len(a)
    m = len(a[0])
    ans = []
    for i in range(m):
        tmp = []
        for j in range(n):
            tmp.append((a[j][m-i-1]))
        ans.append(tmp)
    return ans
  • 5번 연산, 6번 연산


5번 연산


6번 연산

5번 연산6번 연산을 하기 위해서는 우선 배열을 N/2*M/2인 작은 4개의 부분 배열로 나누는 과정이 필요합니다.
그 후 4개로 나뉘어진 덩어리 배열 전체를 한 번에 시계방향/반시계방향으로 회전시킵니다.

구현 과정

  1. N/2*M/2인 작은 4개의 부분 배열을 나눌때, 왼쪽 위의 꼭짓점을 기준으로 4개의 점을 저장합니다.
  2. 각 꼭짓점을 기준 인덱스로 하여 4개의 배열 덩어리를 회전시킵니다.
def op5(a):
    n=len(a)
    m=len(a[0])
    block_n=n//2
    block_m=m//2
    ans=[[0]*m for _ in range(n)]
    for i in range(block_n):
      for  j in range(block_m):
        # 각 덩어리 블록의 왼쪽 위 모서리 좌표가 기준점 입니다.
        # 1번 덩어리 블록
        ans[i][j]=a[i][block_m+j]
        # 2번 덩어리 블록
        ans[i][block_m+j]=a[block_n+i][block_m+j]
        # 3번 덩어리 블록
        ans[block_n+i][block_m+j]=a[block_n+i][j]
        # 4번 덩어리 블록
        ans[block_n+i][j]=a[i][j]
    return ans

def op6(a):
    n=len(a)
    m=len(a[0])
    block_n=n//2
    block_m=m//2
    ans=[[0]*m for _ in range(n)]
    for i in range(block_n):
      for  j in range(block_m):
        # 각 덩어리 블록의 왼쪽 위 모서리 좌표가 기준점 입니다.
        # 1번 덩어리 블록
        ans[i][j]=a[block_n+i][j]
        # 2번 덩어리 블록
        ans[i][block_m+j]=a[i][j]
        # 3번 덩어리 블록
        ans[block_n+i][block_m+j]=a[i][block_m+j]
        # 4번 덩어리 블록
        ans[block_n+i][j]=a[block_n+i][block_m+j]
    return ans

백준) 배열 돌리기 1(16926)

배열돌리기 1_백준

  • 문제 설명: N*M 크기의 2차원 배열의 둘레 한층 한층을 기준으로, R만큼 회전시키는 문제입니다.


배열돌리기 1

배열을 Column 혹은 Row를 기준으로 정렬시키는 유형이 아니라 배열의 둘레를 회전시키는 것이기 때문에, 풀이의 접근이 난감하게 느껴질 수가 있습니다. 하지만 2차원 배열의 둘레를 1차원 리스트로 변환하여 생각한다면 문제가 간단하게 바뀝니다.

파이썬 코드와 함께 차근 차근 생각하여 봅시다.

전체 구현 과정

  1. 가장 바깥쪽의 첫 번째 둘레를, Lv1 둘레라고 하고, Lv1의 요소들을 우선은 1차원 배열에 담습니다.
  2. 1번의 과정을 모든 Lv에 대해서 수행합니다.
  3. 각각의 Lv 배열들을 R번 회전시키고, 1번의 과정과 같은 방법으로 다시 2차원 배열에 담아줍니다.
  • 가장 바깥쪽의 첫 번째 둘레를, Lv1 둘레라고 하고, Lv1의 요소들을 우선은 1차원 배열에 담습니다.
  • 1번의 과정을 모든 Lv에 대해서 수행합니다.
# 입력을 받는 부분
n, m, r = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
# 최대 Lv
max_lv = min(n, m)//2
# 임시로 1차원 배열로 변환한 Lv을 저장할 리스트
tmp_set = []

for i in range(max_lv):
    tmp = [] # 각 Lv의 둘레를 1차원 배열의 형태로 바꾸어 저장할 곳
    # 왼쪽 위 꼭짓점에서 부터 시작하여 시계방향으로 오른쪽, 아래, 왼쪽, 위의 순서로 1차원 배열에 저장합니다.
    for y in range(i, m-i-1):
        tmp.append((a[i][y]))
    for x in range(i, n-i-1):
        tmp.append(a[x][m-i-1])
    for y in range(m-i-1, i, -1):
        tmp.append(a[n-i-1][y])
    for x in range(n-i-1, i, -1):
        tmp.append(a[x][i])
    tmp_set.append(tmp)
  • 각각의 Lv 배열들을 R번 회전시키고, 1번의 과정과 같은 방법으로 다시 2차원 배열에 담아줍니다.
for i in range(max_lv):
    # 각 Lv 마다 1차원 배열의 전체 길이를 저장합니다.
    size = len(tmp_set[i])
    # r번 회전을 size만큼 한다면 회전을 안한 결과와 같으므로 mod size를 합니다.
    # idx 위치를 기준으로 tmp배열의 값을 원래 a 2차원배열에 저장합니다.
    idx = r % size
    tmp = tmp_set[i]
    # 1번 과정과 같은 방법으로 오른쪽, 아래, 왼쪽, 위의 순서로 수행합니다.
    for y in range(i, m-i-1):
        a[i][y] = tmp[idx]
        idx = (idx+1) % size
    for x in range(i, n-i-1):
        a[x][m-i-1] = tmp[idx]
        idx = (idx+1) % size
    for y in range(m-i-1, i, -1):
        a[n-i-1][y] = tmp[idx]
        idx = (idx+1) % size
    for x in range(n-i-1, i, -1):
        a[x][i] = tmp[idx]
        idx = (idx+1) % size


Post의 참고자료와 이미지의 출처는 아래와 같습니다.

처음 시작하는 파이썬[2판], 한빛미디어, 빌루바노빅




2021 의 게시글

NMF

NMF 음수미포함 행렬분해

PCA, EVD

PCA 주성분 분석(차원 축소)

15989번 1,2,3 더하기 4(다이내믹 프로그래밍)

다이내믹 프로그래밍 방법이 필요한 문제들은 처음엔 접근 방법이 막막하게 느껴지곤 합니다. DP 접근 풀이가 필요한 관련 유형의 문제들을 많이 다뤄보도록 합시다.

10942번 펠린드롬(다이내믹 프로그래밍)

다이내믹 프로그래밍 방법이 필요한 문제들은 처음엔 접근 방법이 막막하게 느껴지곤 합니다. DP 접근 풀이가 필요한 관련 유형의 문제들을 많이 다뤄보도록 합시다.

12865번 평범한 배낭(다이내믹 프로그래밍)

다이내믹 프로그래밍 방법이 필요한 문제들은 처음엔 접근 방법이 막막하게 느껴지곤 합니다. DP 접근 풀이가 필요한 관련 유형의 문제들을 많이 다뤄 보도록 합시다.

11066번 파일 합치기(다이내믹 프로그래밍)

다이내믹 프로그래밍 방법이 필요한 문제들은 처음엔 접근 방법이 막막하게 느껴지곤 합니다. DP 접근 풀이가 필요한 관련 유형의 문제들을 많이 다뤄보도록 합시다.

2차원 배열 유형 문제

삼성역량테스트에서 출제되는 코테문제들의 경우 2차원 배열을 특정한 기준을 통해 회전시키는 문제가 자주 출제됩니다.

Introducing Python 파이썬 정리(2)

Introducing Python 처음 시작하는 파이썬[2판] 을 읽으면서, 몇 가지 헷갈리거나 새롭게 알게된 문법, 함수, 메소드들을 정리하려고 합니다.

Introducing Python 파이썬 정리(1)

Introducing Python 처음 시작하는 파이썬[2판] 을 읽으면서, 몇 가지 헷갈리거나 새롭게 알게된 문법, 함수, 메소드들을 정리하려고 합니다.

Pipeline CPU(5)- Control Hazard

Pipeline-CPU 목차 Pipeline CPU(1) : Single-Cycle vs Multi-Cycle CPU Pipeline CPU(2) : Pipeline-CPU의 간략한 이해 Pipeline CPU(3) : Data Hazard(RAW...

Pipeline CPU(4)- Data Forwarding

Pipeline-CPU 목차 Pipeline CPU(1) : Single-Cycle vs Multi-Cycle CPU Pipeline CPU(2) : Pipeline-CPU의 간략한 이해 Pipeline CPU(3) : Data Hazard(RAW...

Pipeline CPU(3)- Data Hazard

Pipeline-CPU 목차 Pipeline CPU(1) : Single-Cycle vs Multi-Cycle CPU Pipeline CPU(2) : Pipeline-CPU의 간략한 이해 Pipeline CPU(3) : Data Hazard(RAW...

맨 위로 이동 ↑