정사각형 암호 해독: 90도 회전 변환의 원리와 구현

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

문제 개요

정사각형 암호(Square Cipher)는 평문을 정사각형 격자에 배치한 후 90도 회전시켜 암호문을 만드는 방식입니다. 이 글에서는 암호문을 복호화하는 과정을 다룹니다.

예제:

입력: RSTEEOTCP
출력: TOPSECRET

핵심 원리

1. 변환 과정 시각화

길이 9인 문자열 "TOPSECRET"을 3×3 격자로 배치:

0 1 2     T O P
3 4 5  =  S E C
6 7 8     R E T

90도 시계방향 회전 후:

R S T
E E O
T C P

1차원으로 읽기: "RSTEEOTCP"

2. 수학적 공식 (0-based 인덱싱)

2차원 위치를 1차원 인덱스로 표현할 수 있습니다. 나이브한 방법은 "1차원 → 2차원 → 회전 → 1차원" 순서로 변환하는 것이지만, $n$개의 원소가 일정한 기하학적 규칙으로 1:1 대응하므로 직접 인덱스 매핑 수식을 찾으면 변환 없이 구현할 수 있습니다.

인덱스 이동 규칙 찾기:

한 변의 길이를 $q$라고 할 때, 평문의 첫 번째 행(인덱스 0, 1, 2, ...)이 암호문에서 어디로 이동하는지 관찰하면:

• $0 \rightarrow 4 = q - 1$
• $1 \rightarrow 9 = 2q - 1$
• $2 \rightarrow 14 = 3q - 1$

패턴을 일반화하면, 인덱스 $i$에 대해:

• $0 \rightarrow (0 \bmod q) \times q + (q - 1 - \lfloor 0 / q \rfloor) = 0 \times q + 4 = 4$
• $1 \rightarrow (1 \bmod q) \times q + (q - 1 - \lfloor 1 / q \rfloor) = 1 \times q + 4 = 9$
• $2 \rightarrow (2 \bmod q) \times q + (q - 1 - \lfloor 2 / q \rfloor) = 2 \times q + 4 = 14$

따라서 일반식은:

인코딩 (평문 → 암호문):

$$j = (i \bmod q) \times q + (q - 1 - \lfloor i / q \rfloor)$$

# i: 평문 인덱스 → j: 암호문 인덱스
j = (i % q) * q + (q - 1 - i // q)

디코딩 (암호문 → 평문):

# j: 암호문에서 읽을 위치
# i: 평문에서 쓸 위치
r[i] = c[j]  # 여기서 j = (i % q) * q + (q - 1 - i // q)

여기서 $q = \lfloor\sqrt{\text{문자열 길이}}\rfloor$ (정사각형 한 변의 길이)

3. 좌표 변환 상세

python

# 1차원 → 2차원
row = i // q
col = i % q

# 90도 시계방향 회전
new_row = col
new_col = q - 1 - row

# 2차원 → 1차원
j = new_row * q + new_col
  = (i % q) * q + (q - 1 - i // q)

구현 방법

최종 최적화 코드

python

def s():
    n, *a = open(0, 'rb').read().split()
    res = bytearray()

    for c in a:
        l = len(c)
        q = int(l**0.5)
        r = bytearray(l)

        for i in range(l):
            r[i] = c[(i % q) * q + (q - 1 - i // q)]

        res.extend(r)
        res.append(10)  # '\n'

    open(1, 'wb').write(res)

s()

더 간결한 버전

python

for _ in range(int(input())):
    s = input()
    n = int(len(s)**.5)
    print(''.join(s[i::n] for i in range(n-1,-1,-1)))

작동 원리:

• s[i::n]: i번째 열 추출 (i, i+n, i+2n, ...)
• range(n-1,-1,-1): 열을 역순으로 순회 (오른쪽→왼쪽)
• 각 열을 위→아래로 읽는 것이 90도 회전의 역변환

성능 비교

방법코드 길이실행 속도가독성

인덱스 계산	중간	느림	⭐⭐
슬라이싱	짧음	빠름	⭐⭐⭐⭐⭐

슬라이싱이 빠른 이유:

• C 레벨에서 최적화됨
• %, //, * 연산 반복 없음
• Python 인터프리터 오버헤드 최소화

결론

정사각형 암호 해독의 핵심은:

1. 수식 이해: (i % q) * q + (q - 1 - i // q)가 90도 회전 매핑
2. 방향 구분: 인코딩 vs 디코딩에서 인덱스 사용 방향 주의
3. 최적화: 가능하면 슬라이싱 활용

백준 같은 온라인 저지에서는 간결한 슬라이싱 버전을 추천하지만, 바이트 레벨 처리가 필요하거나 성능이 중요한 경우 인덱스 계산 방식도 충분히 효율적입니다.