0. 한 줄 요약 가능한 모든 경우를 재귀로 하나씩 만들어 조건에 맞는 것을 고른다. 조합은 start로 앞 번호를 막고, 순열은 used로 중복만 막고, 부분집합은 포함/미포함으로 가른다. 세 가지 모두 "넣고 → 재귀 → 뺀다(원복)" 구조다. 1. 완전탐색(Brute Force)완전탐색이란?완전탐색(Brute Force)은 가능한 모든 경우를 하나씩 만들어 보고 조건에 맞는 것을 고르는 방식이다. 규칙을 찾는 대신 컴퓨터의 속도에 맡긴다. 왜 필요한가DP나 그리디는 규칙을 찾아야 하는데, 처음엔 규칙이 안 보이는 문제가 많다. 입력이 작으면(N ≤ 10~20) 모든 경우를 직접 세어도 시간 안에 끝난다. 완전탐색은 가장 먼저 시도하는 기본기이고, 백트래킹과 DP로 가는 출발점이다. 핵심 아이디..
0. 한 줄 요약 격자(map)의 칸을 정점으로, 상하좌우 이동을 간선으로 보면 격자 문제도 그래프 탐색이다. 이웃은 인접 리스트 대신 dy/dx 배열로 계산한다. 1. 격자 탐색격자 탐색이란?격자 탐색은 2차원 배열로 주어진 지도에서 칸 단위로 이동하며 탐색하는 방식이다. 각 칸이 정점이고, 상하좌우로 이웃한 칸 사이가 간선이다. 이 그래프는 인접 행렬이나 인접 리스트로 따로 만들지 않고, 좌표 계산으로 이웃을 바로 구한다. 왜 필요한가미로, 지도, 섬 같은 문제는 입력이 이미 격자 모양이다. 이걸 인접 리스트로 바꾸면 코드만 길어진다. 좌표에 dy/dx를 더하는 방식이면 이웃 탐색이 for문 하나로 끝나고, 7일차 DFS와 8일차 BFS를 그대로 가져다 쓸 수 있다. 핵심 아이디어이웃 좌표는 ny..
0. 한 줄 요약 시작점에서 가까운 정점부터 한 겹씩 넓혀 가는 탐색이다. 간선 비용이 모두 같으면 정점을 처음 발견한 순간의 거리가 곧 최단 거리다. 1. BFSBFS란?BFS(Breadth-First Search, 너비 우선 탐색)는 시작 정점에서 거리 1인 정점을 모두 방문하고, 그다음 거리 2인 정점을 모두 방문하는 식으로 거리 순서대로 탐색하는 알고리즘이다. 이 순서를 지키기 위해 큐(queue)를 쓴다. 왜 필요한가DFS는 "연결되어 있는가", "덩어리가 몇 개인가"에는 충분하지만, 한 갈래를 끝까지 파고드는 탐색이라 먼저 도착한 경로가 가장 짧은 경로라는 보장이 없다. “1번에서 5번까지 최소 몇 칸에 가는가”처럼 간선 비용이 같은 최단 거리 문제에는 BFS가 필요하다. 핵심 아이디어큐..
0. 들어가기지도서비스에서 특정 주소의 지도보기를 클릭하면 지도 팝업이 열리면서 해당 필지로 지도 이동과 함께 지적 테두리를 하이라이트 해 주는 기능이 있었다.이 기능을 기존에 lx map의 지도 데이터로 서비스했는데, lx에서 데이터 갱신 시 연속지적도 필지가 누락되는 경우가 많았다.그리하여 수많은 민원을 쳐내다가 lx map필지가 없으면 연속지적도 필지를 대신 조회해 이후 로직이 진행되도록 변경하기로 했다. 개선한 기능은 로컬 및 개발서버에서 문제가 없었고, 운영 반영 이후 테스트에도 문제가 없었다.하지만 다음날 오전, 민원이 계속 들어오는 것이다! 내용은 지도가 켜지고 필지 이동하던 것이 작동하지 않아 기본 위치인 세종시 필지로 화면이 이동한다는 것이었다. 0.1 역시나 캐시냐..아무것도 적용되지..
0. 한 줄 요약DFS는 한 방향으로 끝까지 깊이 들어가고 막히면 되돌아오는 탐색이다. visited로 한 번 간 곳을 표시해서 전체를 **O(V + E)**에 훑는다. "연결되어 있는가", "덩어리가 몇 개인가"를 묻는 문제의 기본 도구다. 1. 그래프그래프란?그래프(graph)는 정점(vertex)과 간선(edge)으로 이루어진 구조다. 정점은 점(사람, 도시, 칸)이고 간선은 정점을 잇는 선(친구 관계, 도로)이다. 간선에 방향이 있으면 방향 그래프, 없으면 무방향 그래프다. 정점을 노드(node)라고도 부른다. 1 / \ 2 3 / \ \ 4 5 6코테에서는 인접리스트로 표현한다. 정점마다 "이 정점에서 갈 수 있는 이웃 목록"을 vector로 들고 있다...
