0. 문제 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 1. 문제 이해 인접 리스트의 완전 탐색 DFS 2. 제출 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.StringTokenizer; public class BOJ13023 { static int N, M, flag; static List[] list; static boolean[] vis; public static void..

0. 문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1. 문제 이해 서로소 집합 2. 제출 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class SWEA3289 { static int N, M; // 노드 수, 연산 수 static int[] p; // 부모 노드 저장 public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputSt..

1. 최소 신장 트리 (MST) 신장 트리 n개의 정점으로 이루어진 무향 그래프에서 n개 정점과 n-1개의 간선으로 이루어진 트리 최소 신장 트리 (Minimum Spanning Tree) 모든 정점을 연결하는 간선들의 가중치의 합이 최소가 되는 트리 두 정점 사이의 최소 비용의 경로 찾기 알고리즘 방식 시간 복잡도 유리한 상황 자료구조 Kruskal 일반적 O(ElogE + V) 간선이 많지 않은 그래프 간선 리스트 Prim (PQ 구현) 우선순위 큐(PQ) 사용 O(ElogV) 또는 O(ElogE) 간선이 많지 않은 그래프 인접 행렬, 인접 리스트 Prim (반복문 구현) 반복문 사용 O(V^2) 간선이 많은 밀집 그래프 인접 행렬, 인접 리스트 (E : 간선의 수, V : 정점의 수) But! PQ..

1. 서로소 집합 Disjoint-set 상호 배타 집합 서로 중복되는 원소가 없는 집합들. 표현 연결 리스트 트리 연산 집합들을 식별하기 위해서 특정 멤버를 대표자로 사용한다. make-set(x) : 집합을 생성한다. 전처리 과정에서 단 한번 실행된다. find-set(x) : x가 속한 집합을 찾아서 대표자를 반환한다. Union(x, y) : x가 속한 집합과 y가 속한 집합을 합친다. Union-Find 연산이 핵심이다. 가. 연결 리스트로 구현 같은 집합의 원소들은 하나의 연결리스트로 관리 가장 앞의 원소를 대표자로 사용 각각의 원소는 자신의 대표자와 다음 원소를 가리키는 2개의 링크를 가진다. 연산의 편의성을 위해서 tail을 사용한다. Make-Set(a) : a를 대표자(rep)이자 ta..

2636. 치즈 Flood Fill DFS BFS 2636번: 치즈 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진 www.acmicpc.net 1987. 알파벳 그래프 DFS 비트마스킹 1987번: 알파벳 세로 $R$칸, 가로 $C$칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 ($1$행 $1$열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 www.acmicpc.net 2623. 음악프로그램 위상 정렬 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가..

0. 문제 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 1. 문제 이해 BFS DFS 정렬 2. 제출 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Collections; import java.util.List; import java.util.Queue; import j..

0. 문제 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 1. 문제 이해 위상 정렬 BFS 2. 제출 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Queue; import java.util.StringTokenizer; public class BOJ2252 { st..

1. 그래프 정점 간의 관계를 간선으로 표현한 것. 간선의 방향에 따라서 무향 그래프(양방향 그래프), 유향 그래프로 나뉠 수 있다. 밀집도에 따라서 완전 그래프, 밀집 그래프 그리고 희소 그래프로 나뉜다. 이 외에도 가중치 그래프, 사이클 없는 그래프 등 다양한 그래프가 존재한다. 그래프를 표현하는 방식은 크게 3가지 있다. 그래프 표현 방식 설명 시간 복잡도 (연결 여부 확인) 공간 복잡도 특징 인접 행렬 그래프의 노드들을 2차원 배열에 저장. 배열의 행과 열은 각각 그래프의 노드를 의미하며, 배열의 값은 두 노드 간의 간선 유무(또는 가중치)를 의미함. O(1) O(V^2) -구현이 쉽다. -진입 차수를 구하기 쉽다. -밀집 그래프에 유리한다. 인접 리스트 각 노드에 연결된 노드들을 리스트로 저장...