문제 https://www.acmicpc.net/problem/1068알고리즘1. bfs풀이1. 트리 구조 생성각 노드에 대해 빈 리스트를 생성합니다.  부모가 -1인 경우는 루트 노드로 처리하고, -1이 아니면 해당 부모의 자식 리스트에 현재 노드 번호를 추가합니다.2. 삭제할 노드 처리삭제할 노드를 선택하면 그 노드와 그 아래의 모든 노드들은 트리에서 제거되어야 합니다.단순히 DFS로 방문하면서 삭제할 노드를 만나면 무시하게 되면, 부모 노드의 자식 리스트에는 여전히 삭제된 노드 번호가 남게 됩니다. 부모 노드가 자식 리스트에 삭제된 노드를 가지고 있다면, 실제로는 삭제되었지만 리스트가 비어있지 않아 리프 노드가 아니라고 잘못 판단할 수 있습니다.3. 트리 탐색BFS활용해 남은 트리를 탐색합니다.삭제..

문제 https://www.acmicpc.net/status?user_id=rudals9901&problem_id=13549&from_mine=1알고리즘1. bfs2. 다익스트라풀이가중치가 다른 경로 탐색:이동 비용이 0초와 1초로 다르므로 가중치가 있는 그래프라고 생각하고 다익스트라알고리즘을 사용합니다.0-1 BFS의 원리:비용이 0인 이동은 덱의 앞쪽에, 비용이 1인 이동은 덱의 뒤쪽에 추가하여 탐색 순서를 관리해 시간 소요가 없는 순간이동 경로가 우선적으로 처리 합니다.최소 비용 갱신:각 위치까지 도달하는 최소 시간을 저장하는 distance 배열을 사용해야 합니다. 새 경로의 비용이 기존에 기록된 최소 비용보다 작을 때만 업데이트합니다.코드public class Main { static List>..

문제https://www.acmicpc.net/problem/1707알고리즘1. bfs2. 이분 그래프풀이이분 그래프란 두 그룹 분할:그래프의 모든 정점을 두 그룹으로 나눌 수 있다고 생각할 수 있습니다. 이때 한 그룹에 속한 정점들끼리는 서로 연결되어 있지 않아야 합니다.간선의 특성:만약 어떤 두 정점이 같은 그룹에 속한다면 이 둘 사이에 간선이 존재해서는 안 됩니다. 모든 간선은 항상 서로 다른 그룹의 정점들을 연결해야 합니다  각 연결 요소 별로 처리그래프가 여러 개의 연결 요소로 이루어져 있을 수 있으므로, 방문하지 않은 모든 정점에 대해 각각 이분 탐색을 수행하여 색칠 과정을 진행합니다.색칠 방법아직 방문하지 않은 한 정점을 선택하고 임의의 색을 할당합니다.선택한 정점과 인접한 모든 정점에는 반..

문제https://www.acmicpc.net/problem/1504알고리즘1. 최단경로2. 다익스트라풀이경로를 여러 구간으로 나누어 각각의 최단 경로를 구한 후 합산하는 해야합니다.1. 필수 정점을 포함한 경로 분할1번 정점에서 시작해서 N번 정점으로 가야 하는데, 그 사이에 반드시 두 개의 정점(v1​와 v2​)을 지나야 합니다.따라서 전체 경로를 두 개의 경우로 나눌 수 있습니다.경우 1: 1→v1→v2→N1 경우 2: 1→v2→v1→N12. 각 구간별 최단 거리 계산다익스트라 알고리즘과 같은 최단 경로 알고리즘을 사용하여,1번 정점에서 모든 정점까지의 최단 경로,v1​에서 모든 정점까지의 최단 경로,v2​에서 모든 정점까지의 최단 경로를 각각 구합니다.3. 경로의 합산과 비교각 경우에 대해 경로 ..

문제https://www.acmicpc.net/problem/1197알고리즘1. 그래프 이론2. 최소 스패닝 트리3. 그리디 알고리즘풀이스패닝 트리(Spanning Tree)란?정의스패닝 트리(Spanning Tree) 는 연결된 무방향 그래프에서 모든 정점을 포함하면서, 사이클이 없는 트리 구조를 말합니다.한 그래프의 스패닝 트리는 그래프에 있는 모든 정점을 최소한의 간선(V-1개) 으로 연결하여 완전 연결을 이루는 부분 그래프입니다.특징모든 정점을 포함: 스패닝 트리는 원래 그래프의 모든 정점을 포함합니다.간선의 수: 정점의 개수가 V라면 스패닝 트리는 정확히 V-1개의 간선을 가집니다.사이클 없음: 스패닝 트리는 트리이므로, 사이클(순환 경로)이 존재하지 않습니다.연결성: 스패닝 트리에 포함된 모든..

문제https://www.acmicpc.net/problem/1697알고리즘1. BFS2. 그래프 이론풀이  1. 상태 정의: 수빈이의 현재 위치와 현재까지 걸린 시간을 상태로 정의2. 탐색 공간 제한: 위치는 0부터 100,000까지로 이 범위 안에서만 처리.3. 방문 체크: 이미 방문한 위치를 다시 방문하지 않도록 관리4. 이동 규칙: 수빈이가 이동할 수 있는 경우는 걷기와 순간이동 이 규칙을 적용해 다음 상태를 계산 1. 수빈이의 시작 위치에서 탐색을 시작합니다.2. 한 번 이동할 때마다 새로운 상태를 큐에 추가하고, 방문 여부를 체크합니다.3. 동생의 위치에 도달하면 그 시점의 시간을 출력하고 탐색을 종료합니다.  왜 BFS인가?BFS는 모든 경로를 동일한 "단계"에서 탐색하므로 가장 먼저 목표에..

문제https://www.acmicpc.net/problem/13164알고리즘1. 그리디 알고리즘2. 정렬풀이티셔츠 제작 비용은 "각 조의 최대 키와 최소 키의 차이"이므로 이 차이를 최소화하는 것이 목표이다.조를 나누는 위치 중요조를 나누는 위치마다 새로운 그룹이 시작되고 그룹 간의 비용 합계에 영향을 준다.두 키의 차이 핵심인접한 두 원생의 키 차이를 구하고 큰 차이가 발생하는 곳에서 조를 나누면 전체 비용을 줄일 수 있다.1. 차이 배열 생성원생들의 키 배열에서 인접한 원생들 간의 키 차이를 계산한다.예를 들어 키 배열이 [1, 3, 5, 6, 10]이라면 차이 배열은 [2, 2, 1, 4]가 된다. 2. 조 나누기 (K개의 그룹 만들기)K개의 조로 나누기 위해서는 K-1번의 구분점을 선택해야 한다..

문제https://www.acmicpc.net/problem/2812알고리즘1. 그리디 알고리즘2. 스택풀이처음에 숫자를 앞에서부터 하나씩 비교하며 다음 숫자가 더 크면 현재 숫자를 지우는 방식으로 접근 했다. 예를 들어 4177252841에서:처음 두 숫자 4와 1을 비교 → 1 삭제 → 477252841다시 4와 7을 비교 → 4 삭제 → 77252841... 이런 식으로  반복해 답을 구하려 했습니다.숫자를 지운 후에도 다시 앞의 숫자와 비교해야 할 경우를 놓치게 되는 상황이 발생하고 시작 복잡도가 높아서 복잡도로는 숫자가 50만 자리일 때 시간 초과가 발생했다. 스택 자료구조를 사용하면 O(N)으로 해결할 수 있다.숫자를 왼쪽에서부터 차례로 처리하면서 큰 숫자를 앞쪽에 남기고 작은 숫자는 제거하는..

문제https://www.acmicpc.net/problem/11000알고리즘1. 그리디 알고리즘2. 우선순위 큐풀이문제 풀이의 핵심수업의 겹침 여부 판단:    두 수업이 동시에 진행될 수 없는 경우는 한 수업의 종료 시간이 다른 수업의 시작 시간보다 늦을 때강의실 재사용 조건:    기존 강의실을 재사용하려면 새로운 수업의 시작 시간이 현재 강의실에서 가장 빨리 끝나는 수업의 종료 시간보다 크거나 같아야 한다.  시작 시간 기준 정렬:    특정 수업이 시작되기 전에 어떤 수업이 끝났는지를 명확히 판단하기위해 시작 시간을 기준으로 정렬 우선순위 큐:    우선순위 큐를 사용하여 현재 진행 중인 강의실에서 가장 빨리 끝나는 수업의 종료 시간을 관리새로운 수업을 배정할 때:    새로운 수업의 시작 시간..