11.19 알고리즘 문제풀이

코테 연습

 

구현

첫 번째

import sys
input = lambda: sys.stdin.readline().rstrip()

result = []
for _ in range(int(input())):
    n, d = map(int, input().split())
    d = d // 45 % 8
    n_2 = n//2

    grid = [list(map(int, input().split())) for _ in range(n)]
    moved_grid = [[0] * n for _ in range(n)]

    for _ in range(d):
        for r in range(n):
            for c in range(n):
                # 주 대각선
                if r == c:
                    moved_grid[r][n_2] = grid[r][c]
                    continue
                # 가운데 열
                if c == n_2:
                    moved_grid[r][n-r-1] = grid[r][c]
                    continue
                # 부 대각선
                if r + c == n-1:
                    moved_grid[n_2][c] = grid[r][c]
                # 가운데 행
                if r == n_2:
                    moved_grid[c][c] = grid[r][c]
        for r in range(n):
            for c in range(n):
                if not moved_grid[r][c]:
                    moved_grid[r][c] = grid[r][c]
        grid = moved_grid
        moved_grid = [[0] * n for _ in range(n)]
    result.append(grid)

for res in result:
    for row in res:
        print(*row, sep=" ")

import sys
from collections import deque

input = sys.stdin.readline
answer = []

for _ in range(int(input())):
    n, d = map(int, input().split())
    board = [list(input().split()) for _ in range(n)]
    lines = [list() for _ in range(8)]

    for i in range(n // 2):
        lines[0].append(board[i][i])

    for i in range(n // 2):
        lines[1].append(board[i][n // 2])

    for i in range(n // 2):
        lines[2].append(board[i][n - i - 1])

    for i in range(n // 2):
        lines[3].append(board[n // 2][n - i - 1])

    for i in range(n // 2):
        lines[4].append(board[n - i - 1][n - i - 1])

    for i in range(n // 2):
        lines[5].append(board[n - i - 1][n // 2])

    for i in range(n // 2):
        lines[6].append(board[n - i - 1][i])

    for i in range(n // 2):
        lines[7].append(board[n // 2][i])

    lines = deque(lines)

    count = d // 45

    if count >= 0:
        for _ in range(count):
            lines.appendleft(lines.pop())
    else:
        for _ in range(-count):
            lines.append(lines.popleft())

    for i in range(n // 2):
        board[i][i] = lines[0][i]

    for i in range(n // 2):
        board[i][n // 2] = lines[1][i]

    for i in range(n // 2):
        board[i][n - i - 1] = lines[2][i]

    for i in range(n // 2):
        board[n // 2][n - i - 1] = lines[3][i]

    for i in range(n // 2):
        board[n - i - 1][n - i - 1] = lines[4][i]

    for i in range(n // 2):
        board[n - i - 1][n // 2] = lines[5][i]

    for i in range(n // 2):
        board[n - i - 1][i] = lines[6][i]

    for i in range(n // 2):
        board[n // 2][i] = lines[7][i]

    for row in board:
        answer.append(' '.join(row))

print("\n".join(answer))

 

위 코드가 내가 작성한 코드이고 아래 코드가 우수한 공개 코드이다.

나는 45도 회전할 때마다 원소를 바꿔가며 진행했지만

우수한 코드는 8개의 line을 리스트에 저장해놓고

회전할 때는 자료구조 queue를 이용해서 line을 popleft and append로 진행했다.

배울 것이 있는 풀이였다.

 

그래프

첫 번째

https://www.acmicpc.net/problem/1043

1043번: 거짓말

 

다이나믹 프로그래밍

첫 번째

https://www.acmicpc.net/problem/2407

2407번: 조합

import sys
input = lambda: sys.stdin.readline().rstrip()

n, m = map(int, input().split())

def solve():
    dp = [[0] * (n+1) for _ in range(n+1)]
    for i in range(1, n+1):
        for j in [0, i]:
            dp[i][j] = 1
    
    for i in range(2, n+1):
        for j in range(1, n):
            dp[i][j] = dp[i-1][j] + dp[i-1][j-1]
    return dp[n][m]

print(solve())

 

조합의 파스칼 삼각형 특징을 이용한 문제 풀이이다.

조합의 공식을 사용해도 되지만 그러면 의미가 없으니깐 dp로 풀이했다.

핵심 계산식은 아래와 같다.

dp[i][j] = dp[i-1][j] + dp[i-1][j-1]