Gyu&een

14501은 DP를 공부할 때 꼭 한 번 정리해둘 만한 문제였다.코드 길이도 길지 않고, 상태 정의와 점화식이 분명해서 기본기를 익히기에 좋다.앞으로 비슷한 유형의 문제를 만났을 때 떠올리기 쉬운 형태이기도 하다.왜 기억해둘 만한 문제인가이 문제는 매 날짜마다 선택이 하나씩 주어진다.오늘 상담을 한다오늘 상담을 하지 않는다그리고 이 두 선택 중 더 좋은 결과를 고르면 된다.문제 구조가 단순해서 DP의 핵심이 잘 보인다.현재 위치에서 어떤 선택을 할 수 있는지, 그 선택이 다음 상태에 어떤 영향을 주는지를 그대로 식으로 만들 수 있다.이런 형태는 다른 문제에서도 자주 나온다.어떤 일을 수행할지 말지 고르는 경우특정 구간을 사용할지 건너뛸지 정하는 경우현재 선택 때문에 다음에 가능한 날짜나 위치가 달라지는 ..

이 문제는 단순히 정답을 맞히는 것보다, 구현 문제를 어떤 식으로 바라봐야 하는지 다시 생각하게 해 준 문제였다.구현, 조합, 시뮬레이션, 탐색이 함께 섞여 있는 문제여서 더 좋았고, 동시에 더 배울 점이 많았다.왜 좋은 문제라고 느꼈는가이 문제의 좋은 점은 여러 개념이 따로 노는 것이 아니라, 문제 안에서 자연스럽게 연결된다는 점이다.벽을 3개 세워야 하니 빈 칸 중 3개를 고르는 조합이 필요하고,벽을 세운 뒤 바이러스가 퍼지는 과정을 표현하려면 BFS가 필요하다.그리고 그 모든 과정을 반복해서 최대 안전영역을 구해야 하니 결국 시뮬레이션 문제의 성격도 갖는다. 이런 문제는 단순히 한 알고리즘을 외워서 푸는 문제보다 훨씬 좋은 연습이 된다.실제로 코딩테스트에서는 “이건 무조건 BFS”, “이건 무조건 ..

코딩 테스트를 준비하면서 가장 헷갈렸던 지점 중 하나는“이 문제를 DFS로 풀어야 하는지, 아니면 combinations 같은 라이브러리를 써도 되는지”였다.특히 BOJ 14889 (스타트와 링크) 문제를 풀면서 이 고민이 명확해졌다.1. 처음 접근: 문제를 어떻게 해석했는가문제를 처음 보면 핵심은 두 가지다.N명 중 N/2명을 선택해서 두 팀으로 나눈다각 팀의 능력치를 계산해서 차이의 최솟값을 구한다여기서 중요한 포인트는 “선택”이다.N명 중 절반을 뽑는 순간, 이 문제는 자연스럽게 조합 문제로 바뀐다.2. 막혔던 지점: 선택 이후의 계산절반을 뽑는 것까지는 이해가 되는데,그 다음 “능력치를 어떻게 계산해야 하는지”에서 막혔다.정리해보면 규칙은 이렇다.한 팀이 주어지면, 그 팀 내부에서 2명씩 묶는다각..

Step 1. 무조건 손으로 설계 먼저바로 코딩하지 말 것예시1. 현재 위치는?2. 다음 상태는?3. 언제 멈추지? Step 2. 상태를 명확히 정의 # 예x, ydirectionvisited Step 3. 규칙 하나씩 코드로 옮기기한 번에 짜지 말고이동 → 구현조건 → 구현예외 → 구현 Step 4. 쓰면서 시뮬레이션 구현 실력 빨리 늘리기1: 같은 문제 2번 풀기👉 첫 번째: 이해👉 두 번째: 속도 + 정확성2: 디버깅 연습👉 틀린 이유 찾는 게 핵심3: 유형 반복 꼭 해야 할 유형격자 이동시뮬레이션BFS + 상태회전 / 이동

이 문제를 풀면서 가장 크게 느낀 점은단순히 DFS를 쓰는 문제가 아니라,“DFS를 어떻게 바라보느냐”에 대한 문제였다. 1. 처음 느낀 위화감쉬운 난이도의(내가 알던) DFS그래프를 한 번 탐색해서 끝미로 탐색특정 노드까지 도달 가능 여부👉 DFS = 문제 해결 자체그런데 이 문제는DFS를 계속 여러 번 돌림+ 조건까지 붙음 (높이 > rain)👉 뭔가 DFS가 아닌 다른 알고리즘처럼 느껴짐 -> DP인가? 생각함2. 핵심 깨달음 ❗ DFS는 알고리즘이 아니라 “탐색 도구”다 DFS = “연결된 것들을 한 번에 처리하는 도구”3 . 안전 영역 문제에서 DFS의 역할이 문제에서 DFS는 이렇게 사용된다.🔍 DFS의 실제 역할1. 안 잠긴 칸 발견2. DFS로 연결된 칸 전부 방문 처리3. → 영역..

알고리즘 문제를 풀다 보면,단순한 완전탐색으로는 시간초과가 나는 경우를 자주 마주하게 된다.이럴 때 사용하는 대표적인 방법이 바로 DP (Dynamic Programming)이다.📌 1. DP란 무엇인가?DP는 이미 계산한 결과를 저장해두고, 다시 사용하는 알고리즘이다.즉,“같은 계산을 여러 번 하지 않기 위해 결과를 저장하는 방식”이다.✔️ DP가 적용되는 조건DP는 아무 문제에나 쓸 수 있는 게 아니다.아래 두 가지 조건을 만족해야 한다.1. 중복되는 부분 문제 (Overlapping Subproblem)같은 계산이 여러 번 반복됨2. 최적 부분 구조 (Optimal Substructure)작은 문제의 답으로 큰 문제를 해결할 수 있음 2. DP 구현 방식: Top-Down vs Bottom-UpD..

BFS/DFS 문제를 처음 풀 때 많은 사람들이 막히는 지점이 있다.문제를 보고 어디서부터 시작해야 할지 모르겠다.특히 문제마다 그래프를 표현하는 방식이 달라서 더 헷갈린다.현재까지는 BFS/DFS 문제는 대부분 딱 3가지 패턴으로 나뉜다고 생각한다. 1️⃣ 좌표 그래프 (격자 BFS/DFS)대표 문제미로 탐색 (2178)벽 부수고 이동하기 (2206)토마토 (7576)섬의 개수 (4963)문제 특징문제에서 이런 단어가 등장한다.N x M맵격자상하좌우 이동이런 표현이 나오면 거의 격자 BFS/DFS 문제다.기본 입력 구조N, M = map(int, input().split())graph = [list(map(int, input().strip())) for _ in range(N)]이동 방향 정의격자 문제..

백준 1697 숨바꼭질은 BFS의 대표적인 입문 문제다.하지만 단순히 “최단거리니까 BFS”라고 외우기보다는 왜 BFS가 맞는지를 스스로 납득하는 과정이 중요하다.이 글에서는 문제를 보고 어떤 사고 과정을 통해 BFS로 접근하게 되었는지 정리해보았다.1. 문제 요약수빈이는 현재 위치 N에 있고, 동생은 K에 있다.수빈이는 다음 세 가지 방법으로 이동할 수 있다.X → X - 1X → X + 1X → 2 * X모든 이동은 1초가 걸린다.목표는동생을 찾는 최소 시간을 구하는 것이다.2. 처음 들었던 의문 — 그리디 아닌가?처음 문제를 보면 이런 생각이 들 수 있다.K보다 작으면 *2가 빠르지 않을까?K보다 크면 -1 하면 되지 않을까?즉 현재 목표에 가까워지는 선택을 계속 하면 되지 않을까?라는 생각이 자연..

이 문제는 단순한 BFS처럼 보이지만, 실제로는 상태(state)를 확장해야 하는 BFS 문제이다.처음 문제를 읽고 바로 구현하기보다는 다음과 같은 사고 과정을 통해 접근하였다.1. 문제 유형 판단문제의 핵심 조건은 다음과 같다.(1,1) → (N,M)으로 이동상하좌우 이동최단 경로벽을 한 번만 부술 수 있음여기서 가장 먼저 확인한 것은 다음 질문이었다.이 문제는 최단거리 문제인가?답은 YES였다.이동 비용은 모두 동일하고, 목표는 가장 적은 칸을 지나가는 경로이다.이 경우 그래프 이론에서 가중치가 동일한 최단거리 문제 → BFS로 해결할 수 있다. 2. 일반적인 BFS 설계일반적인 격자 BFS는 다음과 같은 상태를 가진다.(y, x)그리고 방문 배열은visited[y][x]형태로 관리한다.기본 구조는 ..