A-2: 배열과 문자열 — "격자 위를 걷고, 글자를 숫자로 본다"

안녕하세요! 코딩테스트와 CS의 길잡이, 홍순구 튜터입니다.

지난 시간엔 알고리즘을 평가하는 잣대, 빅오(Big-O)를 손에 쥐었습니다. "이 풀이가 시간 안에 들어올까"를 코드 제출 전에 가늠하는 눈이었죠. 그런데 잣대만으로는 문제를 못 풉니다. 잴 대상, 즉 실제로 데이터를 다루는 손이 있어야 합니다.

오늘 그 손을 만듭니다. 코딩테스트에서 가장 먼저, 가장 자주 만나는 두 가지 데이터가 바로 배열(리스트)과 문자열입니다. 입력은 거의 항상 숫자 배열이나 글자의 나열로 들어오고, 문제의 절반 가까이가 "배열을 이리저리 만지고, 격자 위를 걸어 다니고, 글자를 숫자로 바꾸는" 구현 문제예요.

"튜터님, 배열이랑 문자열은 언어 기초에서 이미 배웠는데요?"

맞습니다. 그래서 오늘은 문법을 다시 가르치지 않습니다. 우리가 배울 건 "그 배열과 문자열로 알고리즘 문제를 푸는 법"입니다. 2차원 격자를 순회하고, 문제를 그대로 코드로 옮기는 시뮬레이션을 짜고, 입력이 클 때 시간 초과를 피하는 코테 단골 기법까지. 그리고 지난 시간의 약속대로, 만드는 모든 코드마다 "이게 시간 안에 드나"를 빅오로 되짚습니다.

 오늘의 여정 — "격자 위를 걷고, 글자를 숫자로 본다"

 [1] 배열·슬라이싱     →  인덱싱은 O(1), 슬라이싱은 새 리스트라 O(k)
 [2] 2차원 격자        →  리스트의 리스트, 행×열 순회 O(행×열)
 [3] 시뮬레이션        →  방향 벡터(dx,dy) + 경계 검사로 격자 위를 이동
 [4] 문자열            →  불변·뒤집기·파싱, += 대신 join
 [5] 아스키 코드       →  ord/chr로 문자를 숫자로, 26칸 카운팅
 [6] 코테 관용구       →  컴프리헨션 · enumerate · zip
 [7] 빠른 입출력       →  sys.stdin으로 시간 초과 피하기

자, 빅오라는 눈에 이어 데이터를 주무르는 손까지 갖추러 가 봅시다. 출발합니다!

💡 오늘 수업의 핵심 — "배열·문자열·격자를 다루는 구현 기본기를 익히고, 모든 연산을 빅오로 되짚으며, 큰 입력을 빠르게 읽어 시간 초과를 피한다"

🎯 학습 목표

• 배열을 인덱싱·슬라이싱하고 2차원 격자를 순회하며, 각 연산의 시간·공간 복잡도를 짚습니다.
• 방향 벡터와 경계 검사로 격자 위 이동을 시뮬레이션하고, 문자열을 뒤집고 파싱하며 아스키 코드로 문자를 숫자처럼 다룹니다.
• 컴프리헨션·enumerate·zip 같은 코테 관용구로 풀이를 간결하게 쓰고, sys.stdin 으로 대량 입력을 빠르게 읽어 시간 초과(TLE)를 피합니다.

Step 1: "배열을 자르고 붙이기" — 인덱싱과 슬라이싱

코딩테스트에서 데이터를 담는 가장 기본 그릇은 파이썬의 리스트(list)입니다. 다른 언어에서 말하는 배열(array)에 해당하죠. 입력으로 들어온 숫자들을 리스트에 담아 두고, 인덱스로 한 칸씩 꺼내 쓰는 게 거의 모든 문제의 출발점입니다.

리스트의 한 칸을 인덱스로 꺼내는 건 O(1)입니다. 리스트는 메모리에 칸들이 나란히 붙어 있어서, "몇 번째 칸"이라는 주소를 바로 계산해 단번에 짚거든요. 길이가 100만이든 1억이든 nums[5]를 꺼내는 데 걸리는 시간은 똑같습니다.

 인덱스:     0     1     2     3     4
 nums  = [  10 ][  20 ][  30 ][  40 ][  50 ]
 음수:     -5    -4    -3    -2    -1

파이썬은 음수 인덱스도 받습니다. nums[-1]은 맨 끝, nums[-2]는 끝에서 둘째죠. 끝 원소를 꺼낼 때 nums[len(nums)-1] 대신 nums[-1]이라 쓰면 짧고 또렷합니다. 둘 다 O(1)입니다.

이번엔 슬라이싱(slicing), 즉 nums[a:b]로 일부 구간을 잘라내는 연산을 봅시다. 여기엔 빅오 함정이 하나 숨어 있습니다. 슬라이싱은 잘라낸 길이만큼 새 리스트를 복사해 만든다는 점입니다. nums[1:4]처럼 3칸을 자르면 3칸짜리 새 리스트가 생기죠. 그래서 길이 k를 잘라내면 시간도 공간도 O(k)입니다.

이 성질을 이용해 리스트를 왼쪽으로 k칸 회전하는 함수를 슬라이싱 두 조각으로 짜 봅시다.

# patterns/array_basics.py

def rotate_left(nums, k):
    """리스트를 왼쪽으로 k칸 회전한다. 슬라이싱 두 조각을 이어 붙인다.

    예: rotate_left([1, 2, 3, 4, 5], 2) -> [3, 4, 5, 1, 2]
    시간 O(n) · 공간 O(n)  — 길이 n짜리 새 리스트가 만들어진다.
    """
    if not nums:
        return []
    k %= len(nums)                       # k가 길이보다 커도 한 바퀴로 접는다
    return nums[k:] + nums[:k]

[1, 2, 3, 4, 5]를 2칸 왼쪽으로 돌리면 [3, 4, 5, 1, 2]가 나옵니다. nums[2:](=[3,4,5])와 nums[:2](=[1,2])를 이어 붙인 거죠. 두 슬라이스를 합쳐 길이 n짜리 새 리스트를 만드니 O(n)입니다.

한 가지 더, "앞에서부터 지금까지의 최댓값"을 차례로 기록하는 함수도 봅시다. 입력을 딱 한 번만 훑는 전형적인 O(n) 패턴입니다.

def running_max(nums):
    """앞에서부터 '지금까지의 최댓값'을 차례로 기록한다.

    예: running_max([3, 1, 4, 1, 5]) -> [3, 3, 4, 4, 5]
    한 번만 훑으니 시간 O(n) · 공간 O(n).
    """
    result = []
    best = None
    for x in nums:
        best = x if best is None else max(best, x)
        result.append(best)
    return result

[3, 1, 4, 1, 5]를 넣으면 [3, 3, 4, 4, 5]가 나옵니다. 첫 칸 3, 다음은 max(3,1)=3, 다음은 max(3,4)=4... 이렇게 진행 중인 최댓값이 한 칸씩 쌓이죠. 입력을 한 번 훑으니 O(n)입니다.

💡 한 줄 정리

인덱싱은 O(1)이지만 슬라이싱은 잘라낸 길이만큼 새 리스트를 복사하므로 O(k)다. "한 칸 꺼내기"와 "구간 잘라 복사하기"의 비용은 다르다.

Step 2: "표를 코드로 — 2차원 격자" (만들기와 순회)

이제 한 줄짜리 리스트에서 표(격자)로 넘어갑니다. 미로, 지도, 게임 보드, 픽셀 이미지 — 코딩테스트의 단골 무대가 전부 격자(grid)입니다. 격자는 별게 아니라 리스트를 원소로 가지는 리스트, 즉 "리스트의 리스트"입니다.

         c0   c1   c2   c3
   r0  [  0    0    0    0  ]
   r1  [  0    1    1    0  ]
   r2  [  0    0    0    0  ]

위는 3행 4열 격자입니다. r은 행(row), c는 열(column)이라고 부를게요. grid[1][2]는 "1행 2열" 칸, 즉 값 1이 든 칸입니다. 바깥 인덱스가 행, 안쪽 인덱스가 열이라는 순서를 헷갈리지 않는 게 핵심입니다.

격자를 만들 때 초보자가 거의 반드시 한 번은 밟는 함정이 있습니다. 바로 [[0] * w] * h입니다.

# patterns/grid_simulation.py

def make_grid(h, w, fill=0):
    """h행 w열 격자를 fill로 채워 만든다.

    ⚠️ [[fill] * w] * h 는 '같은 행' 하나를 h번 참조해서, 한 칸만 바꿔도
       모든 행이 함께 바뀌는 버그를 부른다. 컴프리헨션으로 행마다 새로 만든다.
    시간 O(h*w) · 공간 O(h*w)
    """
    return [[fill] * w for _ in range(h)]

⚠️ [[0] * w] * h는 "같은 행 하나"를 h번 참조해 늘어놓을 뿐입니다. 그래서 grid[0][0] = 9처럼 한 칸만 바꿔도 모든 행이 동시에 9로 바뀌는, 잡기 까다로운 버그가 납니다. 반드시 컴프리헨션 [[0] * w for _ in range(h)]으로 행마다 새 리스트를 만들어야 합니다. (이 참조와 복사의 차이는 오늘 생각해볼 주제로도 던지겠습니다.)

격자를 다 훑는 순회는 행을 바깥 반복, 열을 안쪽 반복으로 두 겹 돌립니다. 모든 칸을 한 번씩 보니, 칸 수만큼 일하죠.

for r in range(h):
    for c in range(w):
        ...   # grid[r][c] 한 칸 처리

격자가 h행 w열이면 칸은 모두 h×w개입니다. 그래서 격자 전체 순회는 O(h × w)입니다. 정사각형처럼 한 변이 n이면 O(n²)가 되죠. "격자 문제에서 한 변이 1,000을 넘으면 전체 순회만 100만 번이니, 그 안에서 또 무거운 일을 하면 시간 초과를 의심하라"는 감각, 이게 지난 시간 빅오의 첫 실전 적용입니다.

💡 한 줄 정리

격자는 "리스트의 리스트"이고 grid[행][열]로 짚는다. 생성은 반드시 컴프리헨션으로([[0]*w]*h 참조 함정 금지), 전체 순회는 O(행 × 열).

Step 3: "문제를 그대로 옮긴다 — 시뮬레이션" (방향 벡터와 경계)

코딩테스트 유형 중 구현·시뮬레이션(implementation/simulation)이라는 큰 갈래가 있습니다. 화려한 알고리즘 없이, 문제에 적힌 규칙을 그대로 코드로 옮겨 한 단계씩 흉내 내면 풀리는 유형이죠. "로봇이 명령대로 격자 위를 움직인다", "조건대로 보드를 갱신한다" 같은 문제가 전부 여기 속합니다. 알고리즘은 단순하지만, 규칙을 빠뜨리지 않고 코드로 옮기는 꼼꼼함이 승부를 가릅니다.

격자 위 이동 시뮬레이션의 두 기둥은 방향 벡터와 경계 검사입니다. 상하좌우로 한 칸 움직인다는 건, 현재 좌표 (r, c)에 "행 변화량과 열 변화량"을 더하는 일입니다. 그 변화량을 미리 묶어 둔 게 방향 벡터죠.

              위(U) = (-1, 0)
                    │
   왼(L)=(0,-1) ──── ● ──── 오른(R)=(0, 1)
                    │
              아래(D) = (1, 0)

위로 가면 행이 1 줄고(-1) 열은 그대로(0), 오른쪽으로 가면 행은 그대로 열이 1 늘죠(+1). 이걸 사전(dict)에 담아 둡니다.

# patterns/grid_simulation.py

# 상·하·좌·우 네 방향. (행 변화, 열 변화)
DIRECTIONS = {"U": (-1, 0), "D": (1, 0), "L": (0, -1), "R": (0, 1)}

움직이기 전에 반드시 경계 검사를 합니다. 다음 좌표가 격자 안인지 확인하지 않으면, 격자 밖으로 나가 엉뚱한 칸을 짚거나 음수 인덱스로 반대편을 짚는 버그가 납니다.

def in_bounds(r, c, h, w):
    """좌표 (r, c)가 h×w 격자 안에 있는지. 비교 두 번이라 O(1)."""
    return 0 <= r < h and 0 <= c < w

0 <= r < h and 0 <= c < w — 행도 열도 0 이상이고 한계 미만이어야 통과입니다. 비교 몇 번이면 끝이니 O(1)이죠. 이 두 기둥을 합쳐, 명령대로 걷되 벽에 막히면 제자리에 머무는 이동을 시뮬레이션합니다.

def simulate_walk(h, w, start, moves):
    """start에서 moves(방향 글자들)대로 한 칸씩 움직인다.

    격자 밖으로 나가는 이동은 무시하고 제자리에 머문다(경계 검사).
    예: simulate_walk(3, 3, (0, 0), "DDRR") -> (2, 2)
    이동 횟수 m에 비례 → 시간 O(m) · 공간 O(1).
    """
    r, c = start
    for move in moves:
        dr, dc = DIRECTIONS[move]
        nr, nc = r + dr, c + dc
        if in_bounds(nr, nc, h, w):
            r, c = nr, nc
    return (r, c)

3행 4열 격자의 왼쪽 위 (0, 0)에서 "DDRR"(아래·아래·오른쪽·오른쪽)대로 걸으면 (2, 2)에 도착합니다. 만약 (0, 0)에서 "UULL"처럼 벽 쪽으로 명령하면, 매번 경계 검사에 걸려 제자리 (0, 0)에 머뭅니다. 이동 횟수 m번을 한 번씩 처리하니 시간은 O(m), 좌표 두 개만 들고 다니니 추가 공간은 O(1)입니다.

격자 문제에 자주 끼는 또 하나는 "내 칸의 상하좌우 이웃을 살피는" 동작입니다. 같은 방향 벡터를 그대로 재사용해, 네 이웃 중 특정 값이 몇 개인지 셉니다.

def count_adjacent(grid, r, c, target):
    """(r, c)의 상하좌우 네 칸 중 값이 target인 칸 수를 센다.

    방향이 네 개로 고정이라, 격자가 아무리 커도 한 칸당 O(1).
    """
    h, w = len(grid), len(grid[0])
    count = 0
    for dr, dc in DIRECTIONS.values():
        nr, nc = r + dr, c + dc
        if in_bounds(nr, nc, h, w) and grid[nr][nc] == target:
            count += 1
    return count

방향이 네 개뿐이라, 격자가 100만 칸이어도 한 칸의 이웃을 세는 비용은 O(1)입니다. 이 "방향 벡터 + 경계 검사" 한 쌍은 오늘 시뮬레이션에서 처음 만나지만, 뒤에 격자를 큐로 훑는 탐색에서도 똑같이 등장합니다. 그 큐 이야기는 다음 시간 예고에서 살짝 꺼내겠습니다.

💡 한 줄 정리

시뮬레이션은 "문제 규칙을 그대로 코드로 옮기는" 유형이다. 격자 이동의 두 기둥은 방향 벡터(dr, dc)와 경계 검사(in_bounds) — 이동은 O(이동 횟수), 이웃 살피기는 O(1).

Step 4: "글자의 나열, 문자열" (불변성·뒤집기·파싱)

배열을 다뤘으니 이제 문자열(string)입니다. 문자열은 사실 "글자들의 나열"이라 리스트와 닮았지만, 결정적인 차이가 하나 있습니다. 파이썬 문자열은 불변(immutable), 즉 한 번 만들면 내용을 바꿀 수 없다는 점입니다. s[0] = 'x' 같은 칸 수정이 아예 안 됩니다. 그래서 문자열을 "바꾸는" 모든 연산은 사실 새 문자열을 만드는 일입니다.

먼저 뒤집기. 슬라이싱 [::-1]이면 한 방에 끝납니다.

# patterns/string_ops.py

def reverse(s):
    """문자열을 뒤집는다. 슬라이싱 한 번. 시간 O(n) · 공간 O(n)."""
    return s[::-1]


def is_palindrome(s):
    """앞뒤가 같은 회문(palindrome)인지. 뒤집어 비교하니 O(n)."""
    return s == s[::-1]

reverse("hello")는 "olleh"를, is_palindrome("level")은 True를 돌려줍니다. 뒤집힌 새 문자열을 만들고 한 번 비교하니 둘 다 길이에 비례한 O(n)입니다. 회문(앞뒤가 똑같이 읽히는 단어) 판별은 코테 기초 단골이죠.

다음은 파싱(parsing)입니다. 입력은 보통 "10 20 30"처럼 한 줄에 공백으로 구분된 글자로 들어옵니다. 이걸 숫자 리스트로 바꾸는 게 거의 모든 문제의 첫 줄이에요. split()으로 공백 기준으로 자르고, 각 토막을 int로 바꿉니다.

def parse_ints(line):
    """'10 20 30' 같은 한 줄을 정수 리스트로 바꾼다.

    split()으로 공백 기준으로 자르고 각 토큰을 int로. 시간 O(n).
    예: parse_ints("10 20 30") -> [10, 20, 30]
    """
    return [int(token) for token in line.split()]

parse_ints("10 20 30")은 [10, 20, 30]이 됩니다. 글자 수에 비례해 한 번 훑으니 O(n)이죠.

자, 이제 문자열 불변성이 빅오와 맞물리는 중요한 대목입니다. 글자들을 하나씩 이어 붙여 긴 문자열을 만들 때, +=로 이어 붙이면 안 됩니다. 문자열이 불변이라 s += ch는 매번 "기존 전체 + 새 글자"를 통째로 복사한 새 문자열을 만들거든요. n개를 이렇게 붙이면 1+2+...+n번 복사가 일어나 O(n²)로 폭발합니다.

# ❌ 매번 전체를 복사 → O(n^2)
result = ""
for ch in chars:
    result += ch

# 🌟 조각을 리스트에 모았다가 한 번에 잇기 → O(n)
parts = []
for ch in chars:
    parts.append(ch)
result = "".join(parts)

"순진한 방법(+=)"과 "코테 표준(join)"이 빅오부터 갈립니다. join은 전체 길이를 먼저 계산해 딱 한 번에 이어 붙이므로 O(n)입니다. 위 reverse나 caesar(다음 Step) 같은 함수가 "".join(...)을 쓰는 이유가 바로 이거예요. 문자열을 많이 이어 붙일 땐 리스트에 모았다가 마지막에 한 번 join — 이게 코테의 기본기입니다.

💡 한 줄 정리

문자열은 불변이라 바꾸는 연산은 늘 새 문자열을 만든다. 뒤집기·파싱은 O(n)이고, 많이 이어 붙일 땐 +=(O(n²))가 아니라 리스트에 모아 join(O(n))을 쓴다.

Step 5: "문자를 숫자로 본다 — 아스키 코드" (ord·chr·카운팅 배열)

컴퓨터는 글자도 결국 숫자로 저장합니다. 각 글자에 매겨진 번호가 아스키 코드(ASCII code)예요. 'a'는 97, 'b'는 98... 'z'는 122이고, 'A'는 65, '0'은 48입니다. 파이썬에선 ord(문자)로 글자를 번호로, chr(번호)로 번호를 글자로 바꿉니다.

표의 마지막 줄이 핵심입니다. 어떤 소문자든 ord(ch) - ord('a')를 하면 0부터 25까지의 인덱스로 바뀝니다. 'a'→0, 'b'→1... 'z'→25. 이걸 알면 두 가지 단골 기법이 열립니다.

첫째, 시저 암호(Caesar cipher) 같은 글자 밀기입니다. 글자를 숫자로 당겨 더하고, 26으로 나눈 나머지를 취한 뒤 다시 글자로 되돌립니다. 'z'를 넘으면 'a'로 돌아오게 하는 게 나머지 연산(% 26)의 역할이죠.

# patterns/string_ops.py

def caesar(s, shift):
    """소문자를 shift칸 뒤로 미는 시저 암호. 문자를 숫자로 바꿔 계산한다.

    'a'(아스키 97)을 0으로 당겨, shift를 더하고 26으로 나눈 나머지를 다시
    'a'부터 매긴다. 소문자가 아닌 글자는 그대로 둔다. 시간 O(n).
    예: caesar("abc", 2) -> "cde",  caesar("xyz", 3) -> "abc"
    """
    result = []
    for ch in s:
        if "a" <= ch <= "z":
            shifted = (ord(ch) - ord("a") + shift) % 26
            result.append(chr(shifted + ord("a")))
        else:
            result.append(ch)
    return "".join(result)

caesar("abcxyz", 3)은 "defabc"가 됩니다. x, y, z가 끝을 넘어 a, b, c로 돌아온 게 보이시죠? 글자 수만큼 한 번 훑으니 O(n)이고, 조각을 리스트에 모아 join한 건 Step 4에서 본 그대로입니다.

둘째, 카운팅 배열(counting array)입니다. "각 알파벳이 몇 번 나왔나"를 셀 때, 26칸짜리 리스트를 만들어 ord(ch) - ord('a')를 인덱스로 쓰면 됩니다.

def char_count(s):
    """소문자 a~z의 빈도를 26칸 배열로 센다. 인덱스 = ord(ch) - ord('a').

    글자 종류가 26개로 고정이라 공간은 입력과 무관한 O(1)(항상 26칸).
    시간 O(n). (키가 알파벳이 아니라 임의의 값이면 B에서 배울 해시로 넘어간다.)
    예: char_count("banana")[ord('a') - ord('a')] -> 3  ('a'가 3개)
    """
    counts = [0] * 26
    for ch in s:
        if "a" <= ch <= "z":
            counts[ord(ch) - ord("a")] += 1
    return counts

char_count("banana")를 하면 a는 3, b는 1, n은 2로 세어집니다. 글자 수만큼 한 번 훑으니 시간은 O(n), 칸은 늘 26개로 고정이라 추가 공간은 입력 크기와 무관한 O(1)입니다.

여기서 자연스러운 한계가 보입니다. 카운팅 배열은 "셀 대상이 a~z처럼 작고 고정된 범위"일 때만 통합니다. 만약 키가 임의의 정수나 단어, 사람 이름이라면? 26칸 배열로는 감당이 안 되죠. 그때 등장하는 게 해시(hash)입니다. "무엇이든 키로 세는" 도구인데, B-3 모듈에서 dict와 Counter로 직접 다룹니다. 오늘은 "범위가 좁고 고정이면 카운팅 배열, 넓고 임의면 해시"라는 갈림길만 기억해 두세요.

💡 한 줄 정리

ord/chr로 문자와 숫자를 오간다. ord(ch) - ord('a')로 소문자를 0~25 인덱스로 바꾸면 26칸 카운팅 배열(시간 O(n)·공간 O(1))로 빈도를 센다. 범위가 넓어지면 해시(B-3)로 넘어간다.

Step 6: "짧고 또렷하게 — 파이썬 코테 관용구" (컴프리헨션·enumerate·zip)

같은 알고리즘도 파이썬으론 훨씬 짧게 쓸 수 있습니다. 코딩테스트에서 자주 쓰는 세 관용구, 컴프리헨션·enumerate·zip을 정리합니다. 시작 전에 미리 분명히 해 둘 게 하나 있어요. 이 셋은 빅오를 바꾸지 않습니다. 셋 다 입력을 한 번 훑는 O(n)이에요. 다만 의도가 한눈에 보이고, 파이썬에선 보통 손으로 푼 반복문보다 약간 빠릅니다. "문법 자랑"이 아니라 "풀이를 또렷하게 쓰는 도구"로 보겠습니다.

컴프리헨션(comprehension)은 "거르고 변형해 새 리스트를 만드는" 반복문을 한 줄로 압축합니다.

# patterns/idioms_demo.py

def evens_squared(nums):
    """짝수만 골라 제곱한 리스트. 컴프리헨션 = 필터 + 변환 한 줄. 시간 O(n).

    예: evens_squared([1, 2, 3, 4]) -> [4, 16]
    """
    return [x * x for x in nums if x % 2 == 0]

[x * x for x in nums if x % 2 == 0] 한 줄이 "nums를 돌며(for), 짝수만 골라(if), 제곱해서(x*x) 새 리스트에 담아라"입니다. evens_squared([1, 2, 3, 4])는 [4, 16]이죠.

enumerate는 반복하면서 인덱스와 값을 함께 줍니다. "몇 번째 원소인지"가 필요할 때, range(len(...))로 인덱스를 따로 굴리는 대신 깔끔하게 풀어 줍니다.

def find_positions(nums, target):
    """target이 있는 모든 인덱스. enumerate로 (인덱스, 값)을 함께 본다. 시간 O(n).

    예: find_positions([5, 3, 5, 1, 5], 5) -> [0, 2, 4]
    """
    return [i for i, x in enumerate(nums) if x == target]

enumerate(nums)는 (0, 첫값), (1, 둘째값)...을 차례로 내놓습니다. find_positions([5, 3, 5, 1, 5], 5)는 5가 있는 위치 [0, 2, 4]를 돌려주죠.

zip은 길이가 같은 여러 리스트의 짝을 맞춰 동시에 훑습니다. 두 배열을 나란히 비교하거나 더할 때 제격입니다.

def dot_product(a, b):
    """같은 길이 두 벡터의 내적. zip으로 두 리스트의 짝을 맞춰 동시에 훑는다.

    예: dot_product([1, 2, 3], [4, 5, 6]) -> 32   (1*4 + 2*5 + 3*6)
    시간 O(n).
    """
    return sum(x * y for x, y in zip(a, b))

zip([1,2,3], [4,5,6])은 (1,4), (2,5), (3,6)을 내놓고, 각 짝을 곱해 더하면 내적 32가 나옵니다. 세 관용구 모두 입력을 한 번 훑는 O(n)이라는 점, 다시 한번 짚어 둡니다.

💡 한 줄 정리

컴프리헨션(거르고 변형)·enumerate(인덱스+값)·zip(여러 리스트 짝)은 풀이를 또렷하게 쓰는 코테 관용구다. 셋 다 한 번 훑는 O(n)으로, 빅오는 그대로 두고 코드만 간결해진다.

Step 7: "입력이 크면 읽는 것도 일이다 — 빠른 입출력" (sys.stdin)

마지막은 코테에서 의외로 많은 사람을 떨어뜨리는 함정, 입력 속도입니다. 풀이 로직은 완벽한데 시간 초과가 나는 경우, 범인이 입력을 읽는 input()일 때가 있습니다.

왜일까요? input()은 한 줄을 읽을 때마다 줄 끝을 다듬고 안내 처리를 하는 등 부가 작업을 합니다. 한두 줄이면 티가 안 나지만, 입력이 수십만 줄이면 그 자잘한 부담이 쌓여 시간을 까먹죠. 코테 표준 해법은 sys.stdin.readline으로 읽는 것입니다. 군더더기 없이 한 줄을 그대로 가져와 훨씬 빠릅니다.

import sys

input = sys.stdin.readline   # 이후 input()이 빠른 읽기로 바뀐다

코테에서 가장 흔한 한 줄이 위입니다. input이라는 이름에 sys.stdin.readline을 얹어, 기존 input() 호출을 그대로 빠른 읽기로 바꾸는 관용구죠. 실제 읽고 합산하는 골격을 봅시다. 읽는 통로만 read_line이라는 인자로 떼어 두면, 로직을 그대로 둔 채 입력원만 갈아 끼울 수 있습니다.

# patterns/fast_io.py

def sum_of_line(read_line):
    """두 줄을 읽는다: 첫 줄 n, 둘째 줄 n개의 정수. 그 정수들의 합을 돌려준다.

    read_line은 '한 줄을 돌려주는 함수'다. 실전: sum_of_line(sys.stdin.readline).
    입력 길이에 비례 → 시간 O(n).
    """
    n = int(read_line())
    nums = list(map(int, read_line().split()))
    return sum(nums[:n])

첫 줄에서 개수 n을, 둘째 줄에서 n개의 정수를 읽어 합을 냅니다. 입력으로 3 / 10 20 30을 주면 60이 나오죠. 실전에선 sum_of_line(sys.stdin.readline)처럼 빠른 읽기 함수를 넘깁니다. map(int, ...)은 각 토막을 정수로 바꾸는 관용구이고, 입력 길이에 비례하니 O(n)입니다.

여기서 지난 시간 빅오와 다시 만납니다. 빠른 입출력은 빅오를 바꾸지 않습니다. input()이든 sys.stdin.readline이든 입력을 읽는 일 자체는 똑같이 O(n)이에요. 바뀌는 건 그 앞에 붙는 상수배입니다. 지난 시간 "빅오는 상수를 버린다"고 했는데, 바로 그 버려진 상수가 실전에서 통과와 시간 초과를 가르는 게 여기예요. n이 충분히 크면 상수배 차이만으로도 1초 한도를 넘길 수 있거든요.

⚠️ 한 가지 주의. sys.stdin.readline은 줄 끝의 줄바꿈 문자(\n)까지 딸려 옵니다. 숫자로 바꿀 땐 int()가 알아서 공백을 무시해 괜찮지만, 문자열을 그대로 비교할 땐 .rstrip()으로 줄바꿈을 떼고 써야 엉뚱한 비교를 피합니다.

💡 한 줄 정리

입력이 수십만 줄이면 input()은 느려 시간 초과를 부른다. sys.stdin.readline은 빅오는 그대로 두고 상수배를 줄여 통과시킨다 — 지난 시간 "버린 상수"가 실전에서 승부를 가른다.

마무리

오늘은 빅오라는 눈에 더해, 배열·문자열·격자를 직접 주무르는 손을 만들었습니다. 코딩테스트 문제의 입력을 받아 격자 위를 걷고, 글자를 숫자로 바꾸고, 큰 입력을 빠르게 읽는 — 구현의 기본기를 한 바퀴 돌았어요.

오늘 배운 핵심 세 가지

• 💡 하나 — 배열과 격자, 비용을 빅오로 본다. 인덱싱은 O(1)이지만 슬라이싱은 O(k)로 새 리스트를 복사한다. 격자는 "리스트의 리스트"이고 전체 순회는 O(행 × 열). 격자 생성은 반드시 컴프리헨션으로([[0]*w]*h 참조 함정 금지).
• 💡 둘 — 시뮬레이션과 문자열, 규칙을 코드로 옮긴다. 격자 이동은 방향 벡터(dr, dc)와 경계 검사(in_bounds)로. 문자열은 불변이라 바꾸면 새 문자열이 생기니, 많이 이어 붙일 땐 +=(O(n²)) 대신 join(O(n))을 쓴다. ord/chr로 문자를 숫자로 보면 26칸 카운팅 배열이 열린다.
• 💡 셋 — 관용구로 또렷하게, sys.stdin으로 빠르게. 컴프리헨션·enumerate·zip은 빅오를 그대로 둔 채 풀이를 간결하게 한다. 입력이 크면 sys.stdin.readline으로 상수배를 줄여 시간 초과를 피한다 — 지난 시간 "버린 상수"가 실전에서 승부를 가른다.

다음 시간 예고

오늘까지 카테고리 A(기초와 복잡도)를 마쳤습니다. 다음 시간(B-1)부터는 선형 자료구조로 들어갑니다. 데이터를 한 줄로 늘어놓는 세 그릇 — 스택·큐·덱이 첫 주자예요.

오늘 격자 시뮬레이션에서 "방향 벡터로 이웃 칸을 살핀다"를 봤죠? 격자를 한 칸씩 퍼져 나가며 탐색할 때, "다음에 갈 칸들"을 줄 세워 두는 그릇이 바로 큐(queue)입니다. 그리고 리스트는 맨 끝에 추가·삭제는 빠르지만 중간에 끼워 넣거나 빼는 건 O(n)이라는 한계가 있는데, 이걸 O(1)로 푸는 연결 리스트도 곧 만납니다. 지난 시간 예고한 그림 ② 자료구조 지도(선형 B와 비선형 C)를, 다음 시간 B 카테고리를 열며 펼치겠습니다.

과제

오늘 배운 격자 시뮬레이션·문자열·아스키·빠른 입출력을 직접 손으로 짜 보는 문제들입니다. 풀어 본 뒤 예시 답안과 맞춰 보세요. 각 풀이의 시간·공간 복잡도를 빅오로 적는 것도 잊지 마세요.

[기초] 격자에서 이웃 세기

h행 w열 격자(0과 1로 채워진 2차원 리스트)가 주어집니다. 값이 1인 칸들 각각에 대해, 상하좌우 네 이웃 중 1인 칸의 개수를 모두 더한 값을 돌려주는 함수를 작성하세요. 격자 순회와 이웃 살피기를 결합하는 문제입니다. 전체 시간 복잡도를 빅오로 적고, 왜 그렇게 나오는지 설명하세요.

[응용] 애너그램 판별

두 문자열 a, b가 애너그램(anagram)인지 판별하는 함수를 작성하세요. 애너그램이란 글자 구성은 같고 순서만 다른 두 단어입니다(예: "listen"과 "silent"). 두 문자열은 소문자로만 이루어졌다고 가정합니다. 오늘 배운 26칸 카운팅 배열을 활용해 O(n)에 푸세요. (정렬해서 비교하는 방법도 있지만, 그건 O(n log n)입니다. 왜 카운팅 배열이 더 빠른지도 한 줄 적어 보세요.)

[심화] 지뢰찾기 숫자 채우기 + 빠른 입력

지뢰찾기 판을 완성하는 문제입니다. h행 w열 격자에서 지뢰는 '*', 빈 칸은 '.'로 주어집니다. 각 빈 칸을 그 칸의 상하좌우·대각선 여덟 이웃 중 지뢰의 개수(0~8)를 나타내는 숫자로 바꾼 격자를 돌려주세요(지뢰 칸은 '*' 그대로). 여덟 방향 벡터를 다뤄야 합니다.

추가로, 입력이 h, w가 각각 최대 1,000이라고 합시다. 표준 입력에서 격자를 읽는 부분을 sys.stdin으로 빠르게 처리하세요. 전체 시간 복잡도를 빅오로 판정하고, "1초 1억 연산" 잣대로 통과 가능한지 진단하세요.

생각해볼 주제

정답이 하나가 아닌 질문들입니다. 혼자 고민해도 좋고, 스터디에서 토론해도 좋아요.

1. 슬라이싱은 편한데, O(k) 비용이 숨어 있다

nums[a:b] 슬라이싱은 한 줄로 깔끔하지만 잘라낸 길이만큼 새 리스트를 복사합니다. 평소엔 신경 안 써도 되지만, 어떤 상황에서 이 숨은 비용이 시간 초과로 이어질까요? 반대로, "복사가 일어나도 괜찮은" 경우는 언제일까요? 슬라이싱을 마음껏 써도 될 때와 조심해야 할 때를 가르는 기준을 생각해 보세요.

2. [[0]*w]*h는 왜 버그를 부를까?

격자를 만들 때 [[0]*w]*h로 쓰면 한 칸만 바꿔도 모든 행이 함께 바뀝니다. 반면 [[0]*w for _ in range(h)]는 멀쩡하죠. 빅오는 둘 다 같은데 동작이 갈립니다. 왜 이런 차이가 생기는지, "복사(copy)"와 "참조(reference)"라는 말로 설명해 보세요. 그리고 1차원 [0]*w는 왜 같은 함정이 없는지도 생각해 보세요.

3. 빠른 입출력은 빅오를 안 바꾸는데, 왜 통과/실패를 가를까?

input()이든 sys.stdin.readline이든 입력을 읽는 일은 똑같이 O(n)입니다. 빅오가 같은데 한쪽은 시간 초과, 한쪽은 통과가 됩니다. 지난 시간 "빅오는 상수를 버린다"고 배웠는데, 그 버려진 상수가 여기선 왜 승부를 가를까요? "빅오로 충분한 경우"와 "상수까지 봐야 하는 경우"의 경계를 따져 보세요.