앞서 포스팅했던 claude의 추천문제 구현 1단계 풀이한 내용입니다
"대피소" 같은 격자 위 시뮬레이션 문제가 손에 안 붙어서, 결이 비슷한 문제들을 난이도순으로 풀어보기로 했다.
이 글은 그 1단계 — 격자/좌표·거리·상태 추적 감각을 잡는 Lv.2 문제 4개 풀이 정리다.
좌표 채우기, 거리 판정, 상태 추적, 좌표↔인덱스 변환
| 문제 | 왜 푸는가 | 링크 |
|---|---|---|
| 삼각 달팽이 | 방향 바꿔가며 격자 채우기 | 바로가기 |
| 거리두기 확인하기 | 격자 거리(BFS/맨해튼) 판정 | 바로가기 |
| 롤케이크 자르기 | 배열 순회하며 상태(개수) 추적 | 바로가기 |
| n² 배열 자르기 | 좌표 ↔ 인덱스 변환 | 바로가기 |
1. 삼각 달팽이
💡 핵심: ① 아래 → ② 오른쪽 → ③ 대각선 위 를 반복하며 격자를 채운다.
담을 곳 / 좌표 / 방향 이동 세 가지만 정하면 끝나는 전형적인 "방향 바꿔가며 채우기" 문제.
흐름 정리
숫자 = 1
방향 = 0 (①부터)
현재위치 r, c = 0, 0
1부터 (총개수)까지 반복:
지금 칸에 숫자 적기
숫자 += 1
다음칸 = 현재위치 + 지금방향
만약 다음칸이 (밖이거나 / 이미 찼으면):
방향을 다음 것으로 바꾸기 ← (방향+1) % 3
다음칸을 새 방향으로 다시 계산
현재위치 = 다음칸풀이
def solution(n):
# 1) 삼각형(이중 리스트) 만들기
tri = [[0] * (i + 1) for i in range(n)]
# 2) 방향: 아래 → 오른쪽 → 대각선 왼위
directions = [(1, 0), (0, 1), (-1, -1)]
# 3) 초기 상태
r, c = 0, 0 # 좌표
d = 0 # 방향
total = n * (n + 1) // 2 # 총 채울 개수
# 4) 1 ~ total 채우기
for num in range(1, total + 1):
tri[r][c] = num
# 다음 칸 위치 계산
nr = r + directions[d][0]
nc = c + directions[d][1]
# 다음 칸이 삼각형 밖 or 이미 채워졌으면 방향 전환
if nr < 0 or nr >= n or nc < 0 or nc > nr or tri[nr][nc] != 0:
d = (d + 1) % 3 # 다음 방향
nr = r + directions[d][0]
nc = c + directions[d][1]
r, c = nr, nc # 다음 칸 이동
return [num for row in tri for num in row]좌표·방향 감각 정리
① 방향 벡터 (row, col)
(1, 0)→ 아래(0, 1)→ 오른쪽(-1, -1)→ 대각선 왼위
② r / c 의미
r= 몇 번째 줄 (위→아래, 내려갈수록 커짐)c= 그 줄 안에서 몇 번째 칸 (왼→오른, 오른쪽 갈수록 커짐)
c=0 c=1 c=2 c=3
r=0 → [ ]
r=1 → [ ] [ ]
r=2 → [ ] [ ] [ ]
r=3 → [ ] [ ] [ ] [ ]③ 다음 칸 = 지금 위치 + 변화량
nr = r + directions[d][0]→ 지금 줄r+r변화량nc = c + directions[d][1]→ 지금 칸c+c변화량
④ 이중 리스트 → 1차원 리스트
- 이중 for문으로 돌면서 새
[]에append(또는 위 코드처럼 컴프리헨션).
🤖 다음 날 다시 풀어봤는데, 방향 전환 조건(
if) 이 제일 헷갈렸다.
nc > nr(그 줄의 칸 수를 넘어감) 조건을 빼먹기 쉬우니 주의. 삼각형은 줄마다 칸 개수가 달라서nc >= n이 아니라nc > nr로 막아야 한다.
2. 거리두기 확인하기
⚠️ 위반 규칙 3가지
- 거리 1: 딱 붙어 있음 →
PP- 거리 2 일직선: 한 칸 띄고 가운데가
O→POP- 거리 2 대각선: 사이 두 칸 중 하나라도
O→P O/O P(4칸 중 하나라도O면 막힘)
방법 1 — BFS (거리 2 이내 사람 탐색)
P마다 BFS를 돌려서 거리 2 이내에 다른 P가 닿는지 확인한다. X(파티션)를 만나면 그 방향은 막히므로 더 안 퍼진다. 이게 규칙 3개를 따로 안 나눠도 되는 이유다.
from collections import deque
def is_safe(place):
# P 위치마다 BFS
for r in range(5):
for c in range(5):
if place[r][c] != 'P':
continue
# 이 P에서 출발
visited = [[False] * 5 for _ in range(5)]
visited[r][c] = True
q = deque([(r, c, 0)]) # (행, 열, 거리)
while q:
cr, cc, dist = q.popleft()
if dist == 2: # 거리 2까지만 보면 됨
continue
for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
nr, nc = cr + dr, cc + dc
if not (0 <= nr < 5 and 0 <= nc < 5):
continue
if visited[nr][nc]:
continue
if place[nr][nc] == 'P':
return 0 # 거리 2 이내 다른 사람 만남 → 위반
if place[nr][nc] == 'O':
visited[nr][nc] = True
q.append((nr, nc, dist + 1))
# 'X'면 아무것도 안 함 = 막힘
return 1 # 끝까지 위반 없으면 안전
def solution(places):
return [is_safe(place) for place in places]방법 2 — if로 위반 3경우 직접 판정
BFS가 부담되면, 위반 3가지를 방향 벡터로 그대로 나눠서 검사해도 된다.
def is_safe(place):
# 먼저 P들의 좌표를 다 모은다
persons = [(r, c) for r in range(5) for c in range(5)
if place[r][c] == 'P']
for r, c in persons:
# ① 거리 1: 상하좌우에 P 있으면 위반
for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
nr, nc = r + dr, c + dc
if 0 <= nr < 5 and 0 <= nc < 5 and place[nr][nc] == 'P':
return 0
# ② 거리 2 일직선: 가운데가 O면 위반
for dr, dc in [(-2, 0), (2, 0), (0, -2), (0, 2)]:
nr, nc = r + dr, c + dc
mr, mc = r + dr // 2, c + dc // 2 # 가운데 칸
if 0 <= nr < 5 and 0 <= nc < 5 and place[nr][nc] == 'P' and place[mr][mc] == 'O':
return 0
# ③ 거리 2 대각선: 사이 두 칸 중 하나라도 O면 위반
for dr, dc in [(-1, -1), (-1, 1), (1, -1), (1, 1)]:
nr, nc = r + dr, c + dc
if 0 <= nr < 5 and 0 <= nc < 5 and place[nr][nc] == 'P':
if place[r + dr][c] == 'O' or place[r][c + dc] == 'O': # 사이 두 칸
return 0
return 1
def solution(places):
return [is_safe(p) for p in places]🤖 처음엔 "BFS로 풀면 되지 않을까?"만 생각하고 방법 2(
if나열)로 먼저 통과시켰다.
BFS 버전은 규칙을 따로 안 나눠도 거리 개념 하나로 통합된다는 게 장점. 대피소류로 넘어가면 결국 BFS 감각이 필요하니, 방법 1로도 꼭 다시 풀어볼 것.
3. 롤케이크 자르기
💡 배열을 한 번 순회하면서 왼쪽/오른쪽 토핑 종류 수가 같아지는 지점을 센다.
관건은 "매번 새로 세지 말고, 하나씩 옮기며 갱신"하는 것.
❌ 내 풀이 (매번 복사해서 비교 → O(n²), 비효율)
from collections import Counter
def solution(topping):
answer = 0
for i in range(len(topping)):
dong = topping[:i + 1]
chul = topping[i + 1:]
d = Counter(dong)
c = Counter(chul)
if len(d) == len(c):
answer += 1
return answer✅ 좋은 풀이 (하나씩 옮기며 갱신 → O(n))
from collections import Counter
def solution(topping):
right = Counter(topping) # 처음엔 전부 오른쪽
left = set()
answer = 0
for t in topping:
left.add(t) # 한 조각 왼쪽으로 이동
right[t] -= 1
if right[t] == 0:
del right[t] # 오른쪽에서 종류 사라지면 제거
if len(left) == len(right):
answer += 1
return answer🤖 나는 왜 이렇게 풀었을까? 고찰
세인은 "일단 돌아가게" 짜는데, N이 얼마인지(제약조건)를 먼저 안 본다.
롤케이크는 토핑이 최대 100만 개. 이걸 먼저 봤다면 "O(n²)는 1조 번이라 안 되겠네 → O(n)이어야겠네"가 코딩 전에 나왔을 것.
제약조건(N 범위) 먼저 확인 → 목표 복잡도 정하기
| N 범위 | 허용 복잡도 |
|---|---|
| ~1,000 | O(n²) 괜찮음 |
| ~100,000 | O(n log n) |
| ~1,000,000+ | O(n) 이어야 함 |
🤖 해결법
- 반복문 안에서 뭔가 새로 만들려고 할 때 → "이거 이전 거에서 조금만 바꾸면 안 되나?" 자문하기.
- "재계산(rebuild) → 갱신(update)" 으로 바꾸는 게 효율성 문제의 90%. 슬라이딩 윈도우, 누적합 다 같은 원리.
4. n² 배열 자르기
⚠️
n이 커지면n×n배열은 최대 10¹⁴(100조) 칸. 배열을 통째로 만들면 무조건 터진다.
→ 표를 만들지 말고, 위치(인덱스)만으로 값을 역산해야 한다.
❌ 내 풀이 (방향 벡터 + DFS로 칸 채우기 → 메모리 터짐)
import sys
def solution(n, left, right):
sys.setrecursionlimit(n * n + 10) # 재귀 깊이 늘리기
arr = [[0] * n for _ in range(n)]
visited = [[False] * n for _ in range(n)]
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
def dfs(i, j):
visited[i][j] = True
arr[i][j] = max(i, j) + 1 # 방문한 칸에 값 적기
for di, dj in directions:
ni, nj = i + di, j + dj
if 0 <= ni < n and 0 <= nj < n and not visited[ni][nj]:
dfs(ni, nj)
dfs(0, 0) # 모든 칸 방문
flat = [x for row in arr for x in row]
return flat[left:right + 1]- 애초에
n×n배열을 만드는 순간10¹⁴→ 절대 못 만든다. - 값의 규칙이
max(i, j) + 1인 걸 알았으면, 배열을 만들 이유가 없었다.
✅ 좋은 풀이 (배열 없이 위치로 값 역산 → O(right - left))
def solution(n, left, right):
answer = []
for k in range(left, right + 1):
i = k // n # 몇 번째 행
j = k % n # 몇 번째 열
answer.append(max(i, j) + 1)
return answer🤖 롤케이크와 똑같은 실수. "전체를 만들어놓고 자른다" → "필요한 부분만 계산한다" 로 사고를 바꾸는 게 핵심.
left ~ right만 필요한데n×n을 전부 만든 게 문제였다. 1차원 인덱스k를k // n(행),k % n(열)로 바꾸는 좌표 ↔ 인덱스 변환이 이 문제의 진짜 주제.
✅ 한 장 요약
| 문제 | 얻어가는 감각 | 실수 포인트 |
|---|---|---|
| 삼각 달팽이 | 방향 벡터로 격자 채우기 | 삼각형은 nc > nr로 경계 막기 |
| 거리두기 확인하기 | 격자 거리 판정 (BFS / if) | X 막힘 처리, 대각선 사이 칸 검사 |
| 롤케이크 자르기 | 상태 갱신(update) | 제약조건(N=100만) 먼저 보기 |
| n² 배열 자르기 | 좌표 ↔ 인덱스 역산 | 전체 배열 만들지 말기 (10¹⁴) |
🤖 1단계 두 문제(롤케이크·n²)에서 같은 실수가 반복됐다:
① 제약조건(N)을 안 보고 짠다 → ② "전체를 만들고 자른다" 는 사고.
앞으로 문제 읽자마자 N 범위 → 목표 복잡도 → "재계산 대신 갱신 / 필요한 것만 계산" 순서를 습관으로.
다음은 2단계 — 조건 많은 카카오 기출 시뮬레이션([1차] 캐시 · [3차] 압축 · 주차 요금 계산 · k진수 소수)으로 이어집니다. 💪
