문제 링크 : https://www.acmicpc.net/problem/9663문제 요약N×N 체스판 위에 N개의 퀸을 서로 공격하지 않도록 배치하는 문제다.퀸은 가로, 세로, 대각선 방향으로 모두 공격할 수 있다.결국 조건은 이거다.같은 행에 두 개 있으면 안 되고같은 열에 두 개 있으면 안 되고같은 대각선 위에 있어도 안 된다풀이 사고 과정이 문제는 조금만 생각해보면 형태가 단순해진다.각 행에는 어차피 퀸을 하나씩만 놓으면 된다.그렇다면 문제는 이렇게 바뀐다.각 행에 하나씩 퀸을 두되,열과 대각선이 겹치지 않도록 배치하라. 이제 “행”은 깊이(depth)로 보고,각 depth마다 “어느 열에 둘 것인가”를 결정하면 된다.그래서 자연스럽게 백트래킹을 떠올렸다.첫 번째 행에서 가능한 열에 하나 놓고,두 ..

문제 링크: https://www.acmicpc.net/problem/15686문제 요약도시에는 집과 치킨집이 있고, 치킨집 중에서 M개만 남겨야 한다. 각 집에서 가장 가까운 치킨집까지의 거리(치킨 거리)를 구하고, 그 합이 최소가 되도록 M개의 치킨집을 선택하는 문제다. 결국 핵심은 치킨집을 어떻게 고를 것인가이다.풀이 사고 과정처음에 든 생각은 단순했다.만약 M이 치킨집 개수와 같다면 그냥 전부 사용하면 된다.그런데 M이 더 작다면, 일부를 골라야 한다.결국 “치킨집 중에서 M개를 고르는 문제”이고, 이건 조합 문제다.그래서 백트래킹으로 조합을 만들기로 했다.치킨집의 위치들을 pair 형태로 저장하고, 그 인덱스를 기준으로 조합을 생성한다. 조합이 하나 완성되면 그 조합을 기준으로 도시 치킨 거리를..

https://www.acmicpc.net/problem/1707 문제를 처음 보고 한 착각처음 이 문제를 접근했을 때는이분 그래프가 정확히 뭔지 몰라서 연결 요소의 숫자를 구했었다.로직은 맞는데 정답이 이상하게 나와 이상하다고 여겨이분 그래프가 정확히 뭔지 구글링을 했다.... 구글링을 한 결과 문제를 완전히 잘못 이해했다는 것을 깨달았다. 이분 그래프란 :모든 정점을 두 개의 그룹으로 나누었을 때,같은 그룹에 속한 정점끼리는 서로 연결된 간선이 없느 그래프즉, 한 정점이 그룹 A라면 그 이웃들은 전부 그룹 B여야 한다. 개념만 이해하고 나니까, 로직은 오히려 단순했다.정점을 두 그룹으로 나눌 수 있는가?모든 간선이 서로 다른 그룹을 연결하는가?이 규칙만 지키면 이분 그래프다. 구현 아이디어핵심 아이디..

https://www.acmicpc.net/problem/7576 문제 요약2차원 격자에서 토마토가 익어간다.1: 익은 토마토, 0: 안 익은 토마토, -1: 빈 칸하루가 지나면 익은 토마토의 상하좌우 토마토가 익는다.모든 토마토가 익기까지 걸리는 최소 일수를 구하라.끝까지 익지 못하는 토마토가 있다면 -1 출력문제를 보고 처음 든 생각들문제를 딱 읽고 나서 정리한 생각은 이랬다.0이 고립되어 있으면 → 이건 무조건 fail입력 받을 때 1이 있는 위치는 전부 시작점이 될 수 있음하루 단위로 퍼져나가니까 DFS는 아니고 BFSBFS를 다 돌고 나서 가장 깊은 depth가 정답일 듯? ❌ 처음에 시도한 방법 (실패)내가 처음에 생각한 방식은 이거였다.시작점(1)이 여러 개니까각 시작점마다 BFS를 각각 실..

배경프로젝트 초기에는 개발 속도를 우선시해JPA의 ddl-auto: update와 Java 기반 데이터 초기화 방식을 사용했다.이 방식은 빠른 개발에는 유리했지만,서비스 출시를 고려하면서 다음과 같은 한계를 명확히 인식하게 되었다.스키마 변경이 언제, 왜 발생했는지 추적하기 어려움애플리케이션 재기동 시 DB 상태가 달라질 수 있음개발 환경과 운영 환경의 데이터 경계가 흐려짐이 시점부터 데이터베이스를“프레임워크가 대신 관리해주는 영역”이 아니라“서비스 안정성을 좌우하는 핵심 시스템”으로 보게 되었다.문제 정의겉으로 드러난 문제는 ddl-auto 설정이었지만,본질적인 문제는 다음 질문으로 정리되었다.“DB 스키마 변경에 대한 책임은 어디에 있어야 하는가?”JPA의 자동 스키마 생성에 위임할 것인가아니면 애플..

https://www.acmicpc.net/problem/2667 이 문제는2차원 격자에서 연결된 컴포넌트(Connected Component)를 찾는 전형적인 문제다.겉으로 보면 단순한 BFS 문제처럼 보이지만,막상 구현하려고 하면 다음 지점에서 많이 막히게 된다.BFS를 어떻게 여러 번 호출하지?각 단지가 몇 개의 집으로 이루어졌는지는 어디서 세야 하지?나 역시 이 아이디어를 떠올리는 데 꽤 시간이 걸렸다.문제 핵심 요약1 → 집이 있는 곳0 → 집이 없는 곳상하좌우로 연결된 1들의 묶음이 하나의 단지구해야 할 것전체 단지 개수각 단지에 포함된 집의 수 (오름차순 출력)즉, 이 문제는👉 “BFS 한 번 = 단지 하나” 라는 관점으로 접근해야 한다.접근하면서 가장 어려웠던 점처음에는 이런 생각까지는 ..

문제 핵심 요약무방향 그래프정점 번호가 작은 것부터 방문같은 시작점에서DFS 결과 출력BFS 결과 출력즉, 탐색 알고리즘 + 순서 제어가 핵심입니다. 이 문제를 DFS/BFS 템플릿 문제로 두고,이 구조를 기반으로 다른 그래프 문제들을 풀고 있습니다.DFS / BFS 수도코드 정리DFS 수도코드 (재귀 기반)DFS(node): node 방문 처리 node 출력 for 인접한 정점 next: if 방문하지 않았다면: DFS(next)BFS 수도코드 (큐 기반)queue 생성시작 노드 push시작 노드 방문 처리while queue가 비어있지 않다면: 현재 노드 pop 현재 노드 출력 for 인접한 정점 next: if 방문하지 않..

BFS와 DFS는 그래프·트리·격자(Grid) 문제의 출발점이 되는 핵심 탐색 알고리즘입니다. 1. BFS (Breadth-First Search, 너비 우선 탐색)“최단 거리”가 보이면 → BFS부터 의심하자BFS는 가까운 노드부터 차례대로 탐색합니다.그래서 처음 도달한 순간의 거리 = 최단 거리가 됩니다(단, 모든 간선 가중치가 동일할 때).🔹 핵심 특징탐색 방식: 레벨(Depth) 순 탐색대표 문제 유형최단 거리 / 최소 이동 횟수미로 탈출시작점에서 퍼져나가는 전염/확산 문제🔹 핵심 도구std::queue🔹 C++에서 반드시 지켜야 할 포인트push와 동시에 방문 처리큐에 넣을 때 visited = true꺼낼 때 방문 처리 ❌ → 중복 push → 메모리 초과 위험q.push({x, y});..