cedis 님의 블로그

이 문제는 DFS로 정점을 번갈아 색칠하면서 판별하는 대표적인 이분 그래프 문제다. 핵심은 인접한 두 정점은 반드시 서로 다른 색이어야 한다는 조건 하나다. [Source](https://www.acmicpc.net/problem/1707)문제 요약그래프의 정점들을 두 그룹으로 나누되, 같은 그룹 안의 정점끼리는 서로 인접하지 않게 분할할 수 있으면 그 그래프를 이분 그래프라고 한다. 입력으로 여러 그래프가 주어질 때, 각각이 이분 그래프인지 판별하면 된다. 항목내용입력테스트케이스 K, 정점 수 V, 간선 수 E, 그리고 E개의 간선 정보출력이분 그래프이면 YES, 아니면 NO핵심 판별 기준인접한 두 정점의 색이 항상 달라야 함이분 그래프를 쉽게 말하면정점들을 두 팀으로 나눌 수 있고, 같은 팀끼리는 간..

이 문제의 핵심은 “그래프 전체의 성질”을 보는 것이 아니라, 1번 컴퓨터에서 시작했을 때 실제로 도달 가능한 컴퓨터가 몇 대인가를 구하는 것이다. 즉, 1번과 연결된 컴포넌트의 크기를 구한 뒤 자기 자신을 빼면 된다. [Source](https://www.acmicpc.net/problem/2606)문제 요약웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 감염되면, 그 컴퓨터와 네트워크 상에서 연결된 모든 컴퓨터도 감염된다. 여기서 1번 컴퓨터가 감염되었을 때, 최종적으로 몇 대의 컴퓨터가 추가로 감염되는지를 구하면 된다.항목내용정점컴퓨터간선네트워크 연결 정보시작 노드1번 컴퓨터구해야 하는 값1번에서 출발해 도달 가능한 모든 컴퓨터 수 - 1문제를 한 줄로 바꾸면이 문제는 결국 “1번 노드와 연결..

이 문제는 코드보다 먼저 문제 상황을 정확히 해석하는 것이 더 중요하다. 현재 칸에 적힌 숫자만큼 오른쪽 또는 아래로 점프하면서, 오른쪽 아래 끝 칸에 도달할 수 있는지를 판단하는 문제다. [Source](https://www.acmicpc.net/problem/16173)문제 요약N × N 게임판이 주어지고, 시작 위치는 항상 왼쪽 위 칸이다. 현재 밟고 있는 칸의 숫자를 보고 그 수만큼 오른쪽 또는 아래로 이동할 수 있다. 마지막 칸에는 -1이 적혀 있고, 그곳에 도달하면 성공이다. 항목내용시작 위치(0, 0)이동 방향오른쪽, 아래만 가능이동 거리현재 칸 숫자만큼 정확히 이동목표오른쪽 아래 끝 칸(-1)에 도달 가능하면 HaruHaru, 아니면 Hing이 문제에서 제일 중요한 해석많은 사람이 처음에 ..

이 문제는 그래프를 직접 탐색해야 할 것처럼 보이지만, 실제 핵심은 훨씬 단순하다. 모든 국가를 여행할 수 있도록 하되, 비행기 종류 수를 최소로 만들어야 한다는 점만 정확히 이해하면 정답은 바로 나온다. [Source]문제 요약상근이는 N개의 국가를 여행하려고 하고, 주어진 비행 스케줄 안에서 가능한 한 적은 종류의 비행기를 타고 모든 국가를 방문하고 싶다. 한 국가에서 다른 국가로 갈 때 중간에 다른 국가를 거쳐 가도 된다. 항목내용입력테스트케이스 수 T, 각 테스트케이스마다 국가 수 N, 비행기 종류 수 M, 그리고 M개의 간선 정보출력모든 국가를 방문하기 위한 최소 비행기 종류 수핵심 해석모든 국가를 연결하기만 하면 되고, 최소 간선 수를 묻는 문제처음 보면 이렇게 접근하기 쉽다문제를 처음 읽으면..

이 문제는 복잡한 트리 알고리즘을 묻는 문제가 아니라, 리프 노드 개수를 정확히 맞추는 트리 구조를 직접 구성하는 문제다. 핵심은 “어떤 모양으로 연결하면 리프가 몇 개 생기는가”를 먼저 감각적으로 이해하는 것이다. 문제 요약항목내용입력정점 개수 n, 원하는 리프 노드 개수 m출력조건을 만족하는 트리의 간선 n-1개문제 핵심트리를 직접 “구성”해서 리프 개수를 맞추는 것중요 조건트리는 연결되어 있어야 하고, 사이클이 없어야 하며, 간선 수는 정확히 n-1개여야 함먼저 리프 노드부터 다시 확인하기리프 노드는 연결된 간선이 정확히 1개인 정점이다. 즉, 트리의 끝점이라고 생각하면 된다.예시: 일렬로 연결한 트리0 - 1 - 2 - 3이 경우 리프는 양 끝점인 0, 3 두 개다.이 문제의 핵심 아이디어이 문제..

위상 정렬은 방향 그래프에서 "무엇을 먼저 해야 하는가"를 정하는 대표 알고리즘입니다. 선수 과목, 작업 순서, 빌드 순서, 업무 의존성 같은 문제에서 자주 등장합니다.위상 정렬이란?위상 정렬은 방향 그래프에서, 간선의 방향을 거스르지 않도록 정점을 순서대로 나열하는 것입니다.쉽게 말하면 먼저 해야 하는 일을 먼저 배치하는 정렬입니다.예시 1. 선수 과목기초 과목을 먼저 듣고, 그 다음 중급 과목을 들어야 함예시 2. 작업 순서설계가 끝나야 구현을 시작할 수 있음예시 3. 빌드 순서라이브러리가 준비되어야 메인 프로젝트를 빌드 가능핵심 개념: 진입 차수(in-degree)진입 차수는 어떤 정점으로 들어오는 간선의 개수입니다.A → B이 경우 B는 A로부터 들어오는 간선 1개를 가지므로, B의 진입 차수는 ..

DFS는 그래프를 깊게 탐색하는 방식입니다. 재귀 함수와 함께 이해하면 훨씬 쉽게 익힐 수 있습니다.DFS란?DFS(Depth-First Search)는 현재 갈 수 있는 길이 있다면 한 방향으로 끝까지 내려간 뒤, 더 이상 갈 곳이 없을 때 되돌아오면서 탐색하는 방식입니다.깊이 우선 탐색재귀 또는 스택 사용예제 그래프0 ─── 1│ │└ 2 ── 3시작 정점0에서 시작합니다.DFS의 느낌을 그림처럼 이해하기예를 들어 인접 리스트 순서가 그대로 유지된다면 다음과 같이 진행될 수 있습니다.0 → 1 → 2 → 3물론 DFS는 인접 정점의 저장 순서에 따라 방문 결과가 달라질 수 있습니다. 그래서 문제에 따라 DFS 결과가 여러 개 나올 수도 있습니다.재귀 호출 흐름1단계dfs(0)을 호출하고 0..

BFS는 그래프 탐색의 가장 기본이 되는 방법 중 하나입니다. 시작점에서 가까운 정점부터 층별로 방문한다는 점이 핵심입니다.BFS란?BFS(Breadth-First Search)는 가까운 정점부터 차례대로 탐색하는 방식입니다. 그래서 흔히 "너비 우선 탐색"이라고 부릅니다.핵심 자료구조큐(Queue)예제 그래프0 ─── 1│ │└ 2 ── 3시작 정점0에서 시작한다고 가정합니다.BFS가 큐를 쓰는 이유큐는 먼저 들어온 데이터가 먼저 나가는 구조입니다. 따라서 시작점 근처에서 발견한 정점들을 순서대로 처리할 수 있어, 자연스럽게 가까운 정점부터 탐색하게 됩니다.탐색 과정을 단계별로 보기초기 상태visited = [0]queue = [0]0을 꺼냄0과 연결된 정점은 1, 2입니다.visited =..

그래프 기초그래프 기본 - 인접 리스트 표현 완전 정리그래프 문제를 풀기 위해서는 먼저 그래프를 코드로 표현할 수 있어야 합니다. 그중 가장 자주 쓰는 방식이 바로 인접 리스트입니다.그래프란?그래프는 정점(Vertex)과 간선(Edge)으로 이루어진 자료구조입니다. 트리와 달리 일반적인 연결 관계를 자유롭게 표현할 수 있습니다.정점: 연결의 대상이 되는 점간선: 정점과 정점을 이어주는 선인접 리스트란?인접 리스트는 각 정점마다 연결된 다른 정점들의 목록을 저장하는 방식입니다.예시 형태{정점: [연결된 정점들]}왜 많이 쓸까?간선 수가 많지 않은 그래프에서 메모리 효율이 좋고, BFS/DFS 구현과도 잘 어울립니다.예제 그래프0 ─── 1│ │└ 2 ── 3간선이 [(0,1), (0,2), (1..

BST는 이진 트리에 정렬 규칙이 추가된 구조입니다. 이 규칙 덕분에 원하는 값을 훨씬 빠르게 찾을 수 있습니다.BST란?BST(Binary Search Tree)는 각 노드에 대해 다음 규칙을 만족하는 트리입니다.왼쪽 서브트리의 모든 값현재 노드 값보다 작다.현재 노드 값비교의 기준이 되는 값오른쪽 서브트리의 모든 값현재 노드 값보다 크다.예제 BST 구조5／ ＼3／ ＼247이 구조를 BST라고 부를 수 있는 이유5의 왼쪽에는 3, 2, 4처럼 5보다 작은 값들만 있습니다.5의 오른쪽에는 7처럼 5보다 큰 값만 있습니다.노드 3을 기준으로 봐도 왼쪽은 2, 오른쪽은 4로 같은 규칙을 만족합니다.검색 아이디어BST 검색은 현재 노드 값과 target을 비교하면서 진행합니다.비교 결과동작target == ..