앞 글에서 DP는 "앞 칸을 적어두고 다시 쓰는 것"이라고 정리했다. 거기선 답을 한 칸씩 쌓아 올렸다. 이번 두 문제는 반대였다. 답을 먼저 찍어놓고 그게 되는지 되물었다.입국심사 — 사람을 한 명씩 배치하다가 루프가 10억 번 돌았다징검다리 — 제거할 바위 조합을 재귀로 만들려다 가짓수가 12억을 넘었다두 문제의 공통 근육: 셀 수 없이 큰 값은 탐색하고, 셀 수 있는 값은 순회한다.1. 입국심사 (답 이분 탐색 기본형)문제 한 줄 요약대기 인원 n명을 여러 심사대가 나눠 볼 때, 전원이 심사를 마치는 시간의 최솟값을 구한다.n이 최대 10억, 심사 시간도 최대 10억, 심사관은 최대 10만 명.접근처음엔 우선순위 큐를 꺼냈다. 가장 빨리 비는 창구를 뽑아 다음 사람을 넣는 그림이 제일 먼저 떠올랐다..
전체 글
앞 글에서 다익스트라가 한 일은 "지금 확실해진 지점에서 이웃 지점 값을 더 좋은 걸로 고쳐 쓰기"의 반복이었다. 격자 DP도 하는 일이 똑같다. 딱 하나 다른 게 순서를 누가 정해주냐다. 다익스트라는 어디부터 볼지 몰라서 큐한테 물어봤고, 격자는 위에서 아래로 훑으면 되니까 순서가 그냥 주어진다.정수 삼각형: 한 칸으로 들어오는 화살표가 두 개다등굣길: 제한사항 마지막 한 줄을 안 읽었다두 문제의 공통 근육: 값이 정해진 칸에서, 갈 수 있는 칸의 값을 고쳐 쓰는 것.1. 정수 삼각형 (좌표 DP 기본형)문제 한 줄 요약꼭대기부터 바닥까지 대각선으로만 내려가면서, 지나온 숫자를 더한 값이 제일 큰 경우를 찾는다.높이 500 이하 — 칸이 12만 개쯤이라 다 훑어도 된다. 숫자는 0 이상 — 이 조건이 ..
앞 글에서 BFS는 "큐에 넣는 순간 최단이 확정된다"고 정리했다. 다익스트라는 그 감각이 가중치가 붙는 순간 어떻게 깨지는지를 보여주는 문제다.이 글에서 다루는 문제배달 — 다익스트라 템플릿 자체. BFS 습관 그대로 갔다가 두 번 틀렸다.합승 택시 요금 — 다익스트라는 알아도 막힌다. 막힌 이유가 알고리즘이 아니라 모델링이었다.두 문제의 공통 근육: 꺼내는 순서를 통제해야 확정할 수 있다 + 모르는 값은 유도 말고 열거.1. 배달 (다익스트라 기본형)문제 한 줄 요약무방향 가중 그래프에서 1번 마을로부터 최단 거리가 K 이하인 마을의 개수를 반환. N ≤ 50, 간선 비용 1 ≤ c ≤ 10,000.접근"최단 거리"인데 간선마다 비용이 다르다. BFS는 여기서 못 쓴다. 다익스트라를 쓰는데, 그 근거..
그래프 탐색 문제는 알고리즘이 어려워서 틀리는 게 아니다. 어떤 도구를 고르느냐, 그리고 상태를 언제 확정하느냐에서 갈린다.이 글은 내가 실제로 풀며 틀렸던 두 문제를 근거로, "왜 이 도구인가"를 중심으로 정리한 것이다.이 글에서 다루는 문제게임 맵 최단거리 — 상대 진영까지 최소 칸 수 → visited를 꺼낼 때 켜서 시간 초과가 난 함정네트워크 — 연결된 컴퓨터 묶음의 개수 → 거리가 필요 없으니 DFS로 "시작 횟수"를 세는 아이디어두 문제의 공통 근육: 최단이면 BFS, 몇 덩어리면 DFS라는 판단 + 중간 상태를 최종으로 착각하지 않기. 이게 흔들리면 다익스트라·위상정렬 같은 상위 유형에서도 똑같이 무너진다.1. 게임 맵 최단거리 (BFS)문제 한 줄 요약0(벽)/1(길)로 된 n×m 맵에서..
격자 위에서 좌표를 규칙대로 움직이는 구현 문제는 알고리즘이 어려워서 틀리는 게 아니다. 딱 한 칸 차이를 안 틀리는 정확성에서 갈린다.이 글은 내가 실제로 풀며 틀렸던(또는 헷갈렸던) 두 문제를 근거로, "어디서 한 칸이 어긋나는가"를 중심으로 정리한 것이다. 이 글에서 다루는 문제거리두기 확인하기 — 5×5 대기실에서 응시자 간 맨해튼 거리 2 이하 배치를 판별 → 시작점을 이중으로 걸러 정상 케이스까지 막은 함정행렬 테두리 회전하기 — 테두리를 시계방향으로 한 칸씩 회전 → 큐를 "딜레이 버퍼"로 쓰는 아이디어두 문제의 공통 근육: 격자 좌표를 규칙대로 훑기 + 경계 조건 정확성. 이게 흔들리면 다익스트라·BFS 같은 상위 유형에서도 똑같이 무너진다.1. 거리두기 확인하기 (BFS)문제 한 줄 요약..
문자열 관련 문제는 여러 코딩테스트에서 빈번하게 등장한다.이 글은 내가 실제로 풀고 틀린 문제들을 근거로 정리한 것이다. 문제를 "유형"으로 나열하는 대신, 어떤 도구로 푸는지 + 어디서 자주 틀리는지를 중심으로 묶었다. 이 글에서 다루는 문제 (전부 직접 풀며 틀렸던 것)문자열 다루기 기본 — 문자열이 길이 4 또는 6이고 전부 숫자인지 판별 → 길이·문자 조건을 정규식으로 묶기중요한 단어를 스포 방지 — 스포 처리된 단어 중 '중요한 단어' 수 세기 → 공백 파싱 함정[3차] n진수 게임 — n진수로 이어붙인 문자열에서 특정 위치의 숫자 뽑기 → += 누적 함정1. 문자열 도구 상자언제 String 메서드, 언제 Pattern + Matcher?이게 문자열 문제에서 가장 먼저 하는 판단이다. 기준은 ..
FastAPI를 이용해 ML serving을 실습하면서 pydantic를 이용한 fail-fast 설계에 대해 공부했다.핵심은 Settings를 trust boundart로 만들어 외부 입력을 부팅 시점에 한 번에 검증하고 그 후로는 코드 어디서나 신뢰하는 것이다.이 글은 그 원리와 pydantic_settings의 세 가지 도구가 어떻게 이 원리를 구현하는지 정리한다. 앱은 환경마다 다르게 동작해야 한다. - 개발 환경: localhost:5432 DB - 스테이징: staging-db.internal:5432 - 프로덕션: prod-db.internal:5432 이것을 하드코딩하지 않고 외부에서 주입받기 위한 가장 흔한 방법은 환경변수다. 👀 하지만 만약 config 검증이 입력 시점에 이뤄..
프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 2025 카카오 하반기 2차 - 선인장 숨기기주제: 2차원 슬라이딩 윈도우문제: 선인장 구역이 가능한 늦게 비를 맞도록 하기 변수: - 세로 m, 가로 n - 선인장 구역 세로 h, 가로 w - 빗방울이 떨어지는 순서대로 좌표를 담은 2차원 정수 배열 drops동일 조건 처리: - 가장 왼쪽 위칸의 좌표시간복잡도: - 완전탐색시 (m-h+1)*(n-w+1)*h*w - 최악의 경우(h=m/2, w=n/2): 연산량 약 156억 번 -> 1초(1억 번) 기준 - 슬라이딩 윈도우 최적화 시: O(m * n) -> 50만 번으로 0.01초 내 해결 [단조 큐(Mon..