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이 주어진다. 가..

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

1. 16435. 스네이크버드 그리디 알고리즘 - 정렬 16435번: 스네이크버드 첫 번째 줄에 과일의 개수 N (1 ≤ N ≤ 1,000) 과 스네이크버드의 초기 길이 정수 L (1 ≤ L ≤ 10,000) 이 주어집니다. 두 번째 줄에는 정수 h1, h2, ..., hN (1 ≤ hi ≤ 10,000) 이 주어집니다. www.acmicpc.net 2. 2839. 설탕 배달 그리디 알고리즘 - 동전 자판기 변형 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 3. 1860. 진기의 최고급 붕어빵 시뮬레이션 SW Exp..

0. 문제 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 1. 문제 이해 그래프 BFS 2. 제출 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.Queue; import java.util.StringTokenizer; public class BOJ7576 { static int n, m, ret; static int[][] map; stati..

0. 문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1. 문제 이해 백트래킹 순열 DP 2. 제출 가. 순열 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class SWEA1247 { static int n, ret; static boolean[] vis; static Point work, home; static Point[] custs; public static void main(String[] args) throw..

0. 문제 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 1. 문제 이해 백트래킹 2. 시간 초과 n이 14일 때 10초 이내로 통과해야 함. 가. 시간 초과 import java.util.Scanner; public class BOJ9663 { static int[] map; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); // 체스판을 1차원 배열로 표현 // y행 x열 -> map[y*n ..