1753 최단경로
https://www.acmicpc.net/problem/1753
문제설명
주어진 방향 그래프에서 특정 출발 정점에서 모든 다른 정점까지의 최단 경로를 계산한다. 이 문제는 가중치가 있는 간선이 있는 방향 그래프를 대상으로 하며, 그래프의 정점 수와 간선 수가 주어진다. 또한, 출발 정점에서 각 정점까지의 최단 경로를 출력한다.
코드 설명
- 입력 처리:
- 정점의 개수 v와 간선의 개수 e, 출발 정점 k를 입력받는다.
- 각 정점에 대한 인접 리스트를 초기화하고, 간선 정보를 읽어 인접 리스트를 구성한다.
- 다익스트라 알고리즘:
- 우선순위 큐를 사용하여 현재까지 발견된 최단 경로를 기반으로 다음 노드를 결정한다.
- 시작 정점의 거리를 0으로 설정하고, 그 외 정점의 거리는 무한대로 초기화한다.
- 큐에서 가중치가 가장 작은 노드를 꺼내어, 해당 노드와 연결된 다른 노드의 거리를 업데이트한다. 새로운 거리가 더 짧으면 큐에 추가한다.
- 결과 출력:
- 각 정점까지의 최단 거리를 출력한다. 도달할 수 없는 경우는 "INF"로 표시한다.
접근방식
O(N ^ 2) 시간복잡도.
- 우선순위 큐를 사용한 경우:
- 우선순위 큐를 사용하면, 다익스트라 알고리즘의 시간복잡도는
- 여기서 V는 정점의 개수, E는 간선의 개수이다.
- 우선순위 큐에서의 삽입과 삭제 연산이 로그 시간 복잡도를 가지기 때문에, 모든 정점과 간선에 대해 이 연산을 수행한다.
- 간선 수가 정점 수보다 많은 경우:
- 그래프가 조밀하여 간선 수가 정점 수보다 많은 경우, 시간복잡도는 O(ElogV)가 된다.
- 우선순위 큐를 사용하여 간선을 처리하기 때문에, 간선 수에 따라 시간 복잡도가 결정된다.
문제 조건 분석 과정
- 입력 처리:
-
- 정점의 개수 v와 간선의 개수 e, 출발 정점 k를 입력받는다.
- 각 정점에 대한 인접 리스트를 초기화하고, 간선 정보를 읽어 인접 리스트를 구성한다.
- 다익스트라 알고리즘:
- 우선순위 큐를 사용하여 현재까지 발견된 최단 경로를 기반으로 다음 노드를 결정한다.
- 시작 정점의 거리를 0으로 설정하고, 그 외 정점의 거리는 무한대로 초기화한다.
- 큐에서 가중치가 가장 작은 노드를 꺼내어, 해당 노드와 연결된 다른 노드의 거리를 업데이트한다. 새로운 거리가 더 짧으면 큐에 추가한다.
- 결과 출력:
- 각 정점까지의 최단 거리를 출력합니다. 도달할 수 없는 경우는 "INF"로 표시다.
-
전체코드
import java.io.*;
import java.util.*;
class Node implements Comparable<Node> {
int end, weight;
// 생성자: Node 객체를 초기화합니다.
public Node(int end, int weight) {
this.end = end; // 끝 노드
this.weight = weight; // 가중치
}
// 노드를 가중치에 따라 정렬하기 위해 Comparable 인터페이스를 구현합니다.
@Override
public int compareTo(Node o) {
return Integer.compare(this.weight, o.weight); // 가중치가 작은 순서로 정렬
}
}
public class Main_1753최단경로 {
private static final int INF = 100_000_000; // 무한대를 나타내는 값
static int v, e, k; // 정점 개수, 간선 개수, 시작 정점
static List<Node>[] list; // 인접 리스트
static int[] dist; // 최단 경로를 저장할 배열
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
v = Integer.parseInt(st.nextToken()); // 정점 개수
e = Integer.parseInt(st.nextToken()); // 간선 개수
k = Integer.parseInt(br.readLine()); // 시작 정점
// 인접 리스트
list = new ArrayList[v + 1];
dist = new int[v + 1];
Arrays.fill(dist, INF); // 모든 정점까지의 거리 초기화 (무한대)
for (int i = 1; i <= v; i++) {
list[i] = new ArrayList<>(); // 각 정점에 대한 인접 리스트를 초기화
}
for (int i = 0; i < e; i++) {
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken()); // 간선의 시작 정점
int end = Integer.parseInt(st.nextToken()); // 간선의 끝 정점
int weight = Integer.parseInt(st.nextToken()); // 간선의 가중치
list[start].add(new Node(end, weight)); // 인접 리스트에 간선 추가
}
dijkstra(k); // 다익스트라 알고리즘을 실행하여 시작 정점 k에서 최단 경로 계산
StringBuilder sb = new StringBuilder();
for (int i = 1; i <= v; i++) {
if (dist[i] == INF) sb.append("INF\n"); // 무한대인 경우 "INF" 출력
else sb.append(dist[i]).append("\n"); // 최단 거리 출력
}
System.out.print(sb.toString());
br.close();
}
private static void dijkstra(int start) {
PriorityQueue<Node> queue = new PriorityQueue<>(); // 우선순위 큐를 사용하여 노드를 가중치에 따라 처리
boolean[] check = new boolean[v + 1]; // 방문 여부를 체크하는 배열
queue.add(new Node(start, 0)); // 시작 정점을 큐에 추가
dist[start] = 0; // 시작 정점까지의 거리는 0
while (!queue.isEmpty()) {
Node curNode = queue.poll(); // 큐에서 가중치가 가장 작은 노드를 꺼낸다
int cur = curNode.end; // 현재 노드
if (check[cur]) continue; // 이미 방문한 노드인 경우 무시
check[cur] = true; // 현재 노드를 방문한 것으로 표시
for (Node node : list[cur]) {
// 현재 노드의 인접 노드를 검사
if (dist[node.end] > dist[cur] + node.weight) {
// 현재 노드를 거쳐 가는 것이 더 짧은 경우
dist[node.end] = dist[cur] + node.weight; // 최단 거리 업데이트
queue.add(new Node(node.end, dist[node.end])); // 큐에 새로운 노드를 추가
}
}
}
}
}
1238 파티
https://www.acmicpc.net/problem/1238
문제설명
- N개의 정점과 M개의 간선으로 이루어진 방향 그래프가 주어진다.
- X 정점에서 파티가 열리며, 모든 정점에서 X로 가는 경로와 X에서 모든 정점으로 가는 경로의 최단 거리를 구하여 각 정점에서 X로 가는 거리와 X에서 그 정점으로 가는 거리의 합이 최대가 되는 정점을 찾고 그 합의 최대값을 출력한다.
- 첫 번째 줄: 정점의 수 N, 간선의 수 M, 파티가 열리는 정점 X이 주어진다.
- 다음 M줄: 간선의 정보가 주어지며, 각 줄은 시작 정점, 끝 정점 end, 가중치 weight로 구성된다
- 각 정점에서 X까지의 거리와 X에서 각 정점까지의 거리의 합이 최대가 되는 값을 출력한다.
접근방식
O((N+M)logN) 시간복잡도
- 다익스트라 알고리즘:
- 다익스트라 알고리즘의 시간복잡도는 O((N+M)logN)이다.
- 여기서 N은 정점의 수, M은 간선의 수 이다. 우선순위 큐를 사용하여, 각 정점에 대해 간선을 검사하고 업데이트하는데 O(logN) 시간이 소요된다.
- 전체 복잡도:
- 두 번의 다익스트라 알고리즘을 수행하므로 전체 시간복잡도는 2로, 이 경우 O((N+M)logN)으로 표현된다
문제 조건 분석 과정
- 그래프와 역방향 그래프 준비:
-
- 입력으로 주어진 방향 그래프와 역방향 그래프를 만든다.
- 방향 그래프는 각 정점에서 다른 정점으로 가는 간선 정보를 저장한다.
- 역방향 그래프는 각 정점에서 다른 정점으로 가는 간선 정보를 반대로 저장한다.
- 다익스트라 알고리즘 실행:
- X에서 모든 정점으로의 최단 거리: 원래 방향 그래프를 사용하여 X에서 각 정점으로의 최단 거리를 계산한다.
- 모든 정점에서 X로의 최단 거리: 역방향 그래프를 사용하여 각 정점에서 X까지의 최단 거리를 계산한다.
- 최대값 계산:
- 각 정점에 대해, X에서 그 정점까지의 거리와 그 정점에서 X까지의 거리의 합을 계산하고, 이 값의 최대값을 찾는다.
- 결과 출력:
- 최댓값을 출력한다.
-
전체코드
import java.util.*;
import java.io.*;
// Town 클래스는 다익스트라 알고리즘에서 사용하는 노드 정보를 저장
class Town implements Comparable<Town> {
int end; // 도착 정점
int weight; // 간선의 가중치
Town(int end, int weight) {
this.end = end;
this.weight = weight;
}
@Override
public int compareTo(Town arg0) {
// 가중치에 따라 우선순위 큐에서 정렬
return weight - arg0.weight;
}
}
public class Main_1238파티 {
static final int INF = 987654321; // 무한대 값을 나타내기 위한 큰 값
static ArrayList<ArrayList<Town>> arrList, reverse_arrList; // 그래프 및 역방향 그래프
static int N, X; // 정점의 수(N) 및 파티가 열리는 정점(X)
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken()); // 정점의 수 입력
int M = Integer.parseInt(st.nextToken()); // 간선의 수 입력
X = Integer.parseInt(st.nextToken()); // 파티가 열리는 정점 입력
arrList = new ArrayList<>();
reverse_arrList = new ArrayList<>();
// 각 정점에 대해 인접 리스트 초기화
for (int i = 0; i <= N; i++) {
arrList.add(new ArrayList<>());
reverse_arrList.add(new ArrayList<>());
}
// 간선 정보 입력
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken()); // 시작 정점
int end = Integer.parseInt(st.nextToken()); // 끝 정점
int weight = Integer.parseInt(st.nextToken()); // 간선의 가중치
// 양방향 그래프이므로 양방향 모두 추가
arrList.get(start).add(new Town(end, weight));
reverse_arrList.get(end).add(new Town(start, weight));
}
// 다익스트라 알고리즘을 이용하여 두 가지 그래프에서 최단 거리 계산
int[] dist1 = dijkstra(arrList); // X에서 각 정점까지의 최단 거리
int[] dist2 = dijkstra(reverse_arrList); // 각 정점에서 X까지의 최단 거리
// 각 정점까지의 최단 거리와 X까지의 최단 거리의 합 중 최대값 계산
int ans = 0;
for (int i = 1; i <= N; i++) {
ans = Math.max(ans, dist1[i] + dist2[i]);
}
// 결과 출력
System.out.println(ans);
br.close(); // 입력 스트림 닫기
}
// 다익스트라 알고리즘을 이용하여 주어진 그래프에서 최단 거리 계산
public static int[] dijkstra(ArrayList<ArrayList<Town>> a) {
PriorityQueue<Town> pq = new PriorityQueue<>(); // 우선순위 큐 초기화
pq.offer(new Town(X, 0)); // 시작 정점과 거리를 큐에 추가
boolean[] check = new boolean[N + 1]; // 방문 여부 체크 배열
int[] dist = new int[N + 1]; // 최단 거리 저장 배열
Arrays.fill(dist, INF); // 거리 배열을 무한대로 초기화
dist[X] = 0; // 시작 정점의 거리는 0으로 초기화
while (!pq.isEmpty()) {
Town curTown = pq.poll(); // 현재 노드를 큐에서 꺼내기
int cur = curTown.end; // 현재 정점
if (!check[cur]) {
check[cur] = true; // 현재 정점을 방문 처리
for (Town town : a.get(cur)) { // 현재 정점과 연결된 모든 정점 탐색
if (!check[town.end] && dist[town.end] > dist[cur] + town.weight) {
dist[town.end] = dist[cur] + town.weight; // 최단 거리 업데이트
pq.add(new Town(town.end, dist[town.end])); // 큐에 추가
}
}
}
}
return dist; // 최단 거리 배열 반환
}
}1504 특정한 최단거리
https://www.acmicpc.net/problem/1504
문제설명
그래프에서 특정 경로를 통해 이동하는 최단 거리를 계산한다.
주어진 그래프는 N개의 정점과 E개의 간선으로 이루어져 있으며, 간선은 양방향이다.
두 개의 정점 v1과 v2가 주어졌을 때, 다음 두 가지 경로 중 더 짧은 경로를 찾는다,
- 경로 1: 1 -> v1 -> v2 -> N
- 경로 2: 1 -> v2 -> v1 -> N
여기서 1과 N은 시작점과 끝점, v1과 v2는 반드시 거쳐야 할 정점이다. 이 경로들 중 최단 거리를 구하고
만약 두 경로 모두 도달할 수 없다면 -1을 출력한다
접근방식
- 다익스트라 알고리즘의 시간 복잡도: O((N + E) * log N)
-
- N은 정점의 수
- E는 간선의 수
- 우선순위 큐를 사용하여 각 정점에 대해 로그 N 시간의 복잡도로 거리 갱신을 수행한다
-
- (한 번은 1 -> v1 / v2, 두 번째는 v1 / v2 -> v2 / v1, 세 번째는 v2 / v1 -> N)
- 전체 시간 복잡도: O(3 * (N + E) * log N) = O((N + E) * log N)
문제 조건 분석 과정
- 주어진 문제는 다익스트라 알고리즘을 여러 번 호출하여 두 가지 경로의 거리를 비교하는 방식으로 해결할 수 있다.
- 그래프 초기화: 정점과 간선 정보를 입력받아 그래프를 인접 리스트로 저장한다.
- 다익스트라 알고리즘:
- 특정 정점에서 출발하여 다른 정점까지의 최단 거리를 계산한다.
- 다익스트라 알고리즘을 구현하기 위해 우선순위 큐를 사용하여 최단 거리 갱신을 수행한다.
- 경로 계산:
- 주어진 두 경로(1 -> v1 -> v2 -> N, 1 -> v2 -> v1 -> N)의 거리 계산 후, 두 경로 중 최단 경로를 선택한다.
- 만약 두 경로 모두 무한대(도달 불가능)인 경우 -1을 출력한다.
전체코드
import java.util.*;
import java.io.*;
public class Main_1504특정한 {
static int N, E; // 정점의 수(N)와 간선의 수(E)
static ArrayList<ArrayList<Node>> a; // 그래프를 저장할 인접 리스트
static int[] dist; // 최단 거리를 저장할 배열
static boolean[] check; // 각 정점의 방문 여부를 기록할 배열
static final int INF = 200000000; // 무한대 값을 표현하기 위한 상수
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken()); // 정점의 수
E = Integer.parseInt(st.nextToken()); // 간선의 수
a = new ArrayList<>();
dist = new int[N + 1];
check = new boolean[N + 1];
// 거리 배열을 무한대로 초기화
Arrays.fill(dist, INF);
// 그래프 초기화
for (int i = 0; i <= N; i++) {
a.add(new ArrayList<>());
}
// 간선 정보를 입력받아 그래프에 추가
for (int i = 0; i < E; i++) {
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
int weight = Integer.parseInt(st.nextToken());
a.get(start).add(new Node(end, weight));
a.get(end).add(new Node(start, weight));
}
// 거쳐야 하는 두 정점(v1, v2)을 입력받음
st = new StringTokenizer(br.readLine());
int v1 = Integer.parseInt(st.nextToken());
int v2 = Integer.parseInt(st.nextToken());
// 경로 1: 1 -> v1 -> v2 -> N
int res1 = 0;
res1 += dijkstra(1, v1);
res1 += dijkstra(v1, v2);
res1 += dijkstra(v2, N);
// 경로 2: 1 -> v2 -> v1 -> N
int res2 = 0;
res2 += dijkstra(1, v2);
res2 += dijkstra(v2, v1);
res2 += dijkstra(v1, N);
// 최단 거리 중 유효한 값을 선택
int ans = (res1 >= INF && res2 >= INF) ? -1 : Math.min(res1, res2);
System.out.println(ans); // 결과 출력
br.close();
}
// 다익스트라 알고리즘을 사용하여 start부터 end까지의 최단 거리를 계산
public static int dijkstra(int start, int end) {
Arrays.fill(dist, INF); // 거리 배열 초기화
Arrays.fill(check, false); // 방문 배열 초기화
PriorityQueue<Node> pq = new PriorityQueue<>(); // 우선순위 큐 초기화
pq.offer(new Node(start, 0)); // 시작 정점을 큐에 추가
dist[start] = 0; // 시작 정점까지의 거리 0으로 설정
while (!pq.isEmpty()) {
Node curNode = pq.poll(); // 큐에서 현재 정점 꺼내기
int cur = curNode.end;
if (!check[cur]) { // 현재 정점이 방문되지 않았다면
check[cur] = true; // 방문 처리
// 현재 정점과 연결된 모든 정점에 대해
for (Node node : a.get(cur)) {
// 해당 정점으로 가는 거리 업데이트
if (!check[node.end] && dist[node.end] > dist[cur] + node.weight) {
dist[node.end] = dist[cur] + node.weight;
pq.add(new Node(node.end, dist[node.end])); // 우선순위 큐에 추가
}
}
}
}
return dist[end]; // 최단 거리 반환
}
// 정점과 가중치를 저장하는 내부 클래스
static class Node implements Comparable<Node> {
int end;
int weight;
Node(int end, int weight) {
this.end = end;
this.weight = weight;
}
@Override
public int compareTo(Node o) {
return weight - o.weight; // 우선순위 큐에서 가중치 기준으로 정렬
}
}
}14888 연산자 끼워넣기
https://www.acmicpc.net/problem/14888
문제설명
주어진 숫자와 연산자들을 사용하여 가능한 모든 수식의 결과를 계산한 후, 그 결과들 중에서 최대값과 최소값을 찾는다
접근방식
DFS의 깊이: 숫자의 개수 N 만큼 깊이 탐색을 진행한다.
가지 수: 각 단계에서 사용할 수 있는 연산자는 4개 (+, -, *, /)이므로, 각 단계에서 4가지 연산자를 선택한다.
연산자 배열을 사용하여 가능한 모든 연산을 시도하는데
숫자의 개수가 N일 때, 각 단계에서 4가지 연산을 시도하므로 DFS의 가지 수는 최대 4(N−1)이 된다.
따라서 DFS 탐색의 시간복잡도는 O(4(n-1) 이 된다.
문제 조건 분석 과정
주어진 숫자와 연산자들을 조합하여 가능한 모든 결과를 탐색하는 문제로, DFS(깊이 우선 탐색)를 사용한다.
초기 숫자를 시작으로 모든 가능한 연산자 조합을 시도하면서 결과를 계산하여각 연산 결과를 계산할 때마다
최대값과 최소값을 갱신한다.
DFS(깊이 우선 탐색)
- 현재 상태: 현재까지 계산된 결과와 사용된 숫자의 인덱스
- 종료 조건: 모든 숫자를 사용한 경우, 결과를 최대값과 최소값을 갱신
- 재귀 호출: 각 연산자를 사용하여 다음 단계로 넘어간
전체코드
import java.util.*;
import java.io.*;
public class Main {
// 최대값과 최소값을 저장하기 위한 변수
public static int MAX = Integer.MIN_VALUE;
public static int MIN = Integer.MAX_VALUE;
// 연산자의 개수를 저장하기 위한 배열
public static int[] operator = new int[4];
// 입력된 숫자들을 저장하기 위한 배열
public static int[] number;
// 숫자의 개수
public static int N;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 숫자의 개수 입력
N = Integer.parseInt(br.readLine());
number = new int[N];
// 숫자 배열 입력
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
for (int i = 0; i < N; i++) {
number[i] = Integer.parseInt(st.nextToken());
}
// 연산자 배열 입력
st = new StringTokenizer(br.readLine(), " ");
for (int i = 0; i < 4; i++) {
operator[i] = Integer.parseInt(st.nextToken());
}
// DFS를 사용하여 가능한 모든 계산 결과를 탐색
dfs(number[0], 1);
// 결과 출력
System.out.println(MAX);
System.out.println(MIN);
}
// DFS를 통한 연산 결과 탐색
public static void dfs(int num, int idx) {
// 모든 숫자를 사용했을 때 최대값과 최소값 갱신
if (idx == N) {
MAX = Math.max(MAX, num);
MIN = Math.min(MIN, num);
return;
}
// 연산자 배열을 순회하며 가능한 모든 연산을 시도
for (int i = 0; i < 4; i++) {
if (operator[i] > 0) {
// 현재 연산자 사용
operator[i]--;
// 해당 연산 수행
switch (i) {
case 0: dfs(num + number[idx], idx + 1); break; // 더하기
case 1: dfs(num - number[idx], idx + 1); break; // 빼기
case 2: dfs(num * number[idx], idx + 1); break; // 곱하기
case 3: dfs(num / number[idx], idx + 1); break; // 나누기
}
// 연산자 배열 복구
operator[i]++;
}
}
}
}1927 최소 힙
https://www.acmicpc.net/problem/1927
문제설명
최소 힙을 사용하여 특정 명령어를 처리한다.
주어진 명령어에 따라 숫자를 힙에 추가하거나, 힙에서 가장 작은 숫자를 제거하고 출력하는 작업을 수행한다.
접근방식
- 삽입 연산 (pq.add(num)):
- PriorityQueue에 원소를 삽입할 때, 내부적으로 힙의 성질을 유지하기 위해 O(log N)의 시간이 소요된다.
- 삭제 연산 (pq.poll()):
- 힙에서 가장 작은 원소를 제거할 때도 O(log N)의 시간이 소요된다.
- 각 명령어를 처리하는데 O(log N) 시간이 걸리며, 전체 N개의 명령어를 처리하는 시간 복잡도는 O(N log N)이다.
문제 조건 분석 과정
- 데이터 구조:
- PriorityQueue<Integer>를 사용하여 최소 힙을 구현한다.
- Java의 PriorityQueue는 기본적으로 최소 힙으로 동작하기 때문에 역순으로 정렬해주는 collection을 사용해야한다
- 명령어 처리:
- 각 명령어를 읽어 num에 저장한다.
- num이 0이면:
- 힙이 비어있는 경우 0을 출력한다.
- 그렇지 않으면 힙에서 가장 작은 값을 제거하고 출력한다.
- num이 0이 아닌 경우, 해당 숫자를 힙에 추가한다.
전체코드
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 최소 힙을 구현하기 위해 PriorityQueue 사용
PriorityQueue<Integer> pq = new PriorityQueue<>();
int N = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
// N개의 명령 처리하는 반복문
for (int i = 0; i < N; i++) {
// 각 명령 입력
int num = Integer.parseInt(br.readLine());
// 명령이 0인 경우
if (num == 0) {
// 힙이 비어있는 경우 0 출력
if (pq.isEmpty()) {
sb.append("0\n");
} else {
// 힙에서 가장 작은 값을 제거하고 출력
sb.append(pq.poll()).append("\n");
}
} else {
// 명령이 0이 아닌 경우, 해당 숫자를 힙에 추가
pq.add(num);
}
}
// 모든 명령을 처리한 후 결과를 출력
System.out.print(sb.toString());
}
}2075 N번째 큰 수
https://www.acmicpc.net/problem/2075
문제설명
n x n 크기의 행렬이 주어질 때, 이 행렬의 모든 숫자 중에서 n번째로 큰 숫자를 찾는다.
접근방식
- 입력 크기: n x n의 행렬에서 총 n^2개의 숫자를 처리한다.
- 힙 연산: 힙의 크기가 n으로 제한되며, 각 숫자를 추가하거나 삭제하는 연산의 시간 복잡도는 O(log n)이다.
-
- 따라서, 전체 시간 복잡도는 O(n^2 log n)입니다. 이는 행렬의 모든 숫자에 대해 힙 연산을 수행해야 하기 때문이다.
문제 조건 분석 과정
- 최소 힙 (Min-Heap)을 활용하여 상위 n개의 큰 숫자 중에서 가장 작은 값을 출력한다.
-
- 행렬을 순회하며 힙에 숫자 추가: 각 숫자를 힙에 추가한다. 힙의 크기가 n이 되면 힙의 최상단(최소값)을 제거하고 새로운 숫자를 추가하여 상위 n개의 큰 숫자만을 유지한다.
- 결과 출력: 마지막으로, 모든 숫자를 힙에 추가한 후 힙의 최상단을 출력하면 이는 전체 숫자 중 n번째로 큰 값이 된다.
- 우선순위 큐 (PriorityQueue) 활용: Java의 PriorityQueue는 기본적으로 최소 힙을 구현한다. 이를 이용해 최솟값을 찾는다. 행렬의 각 숫자를 읽고, PriorityQueue에 추가하다가 힙의 크기가 n에 도달하면, 현재 힙의 최소값과 비교하여 더 큰 값을 유지한다.
-
전체코드
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 입력으로 주어지는 배열의 크기(n)
int n = Integer.parseInt(br.readLine());
// 최소 힙을 사용하기 위한 PriorityQueue
Queue<Integer> q = new PriorityQueue<>();
// StringTokenizer를 사용하여 각 줄의 숫자를 분리
StringTokenizer st = null;
// n개의 행
for(int i = 0; i < n; i++) {
// 각 행의 숫자
st = new StringTokenizer(br.readLine());
for(int j = 0; j < n; j++) {
// 숫자를 정수로 변환
int num = Integer.parseInt(st.nextToken());
// 힙의 크기가 n일 때
if(q.size() == n) {
// 현재 숫자가 힙의 최소값보다 클 경우
if(q.peek() < num) {
// 힙에서 최소값을 제거하고 현재 숫자를 추가
q.poll();
q.add(num);
}
} else {
// 힙의 크기가 n보다 작으면 현재 숫자를 추가
q.add(num);
}
}
}
// 힙에서 n번째로 큰 수(최소 힙에서의 최상단)를 출력
System.out.println(q.poll());
}
}11279 최대 힙
https://www.acmicpc.net/problem/11279
문제설명
최대 힙을 구현한다.
- 정수 삽입: 정수를 힙에 삽입한다.
- 최대값 제거 및 출력: 힙에서 최대값을 제거하고 출력한다.
- 힙이 비어있는 상태에서 최대값을 제거하려고 하면 0을 출력한다.
접근방식
- 삽입 연산:
- 힙에 요소를 삽입하는 연산은 O(log N)의 시간 복잡도를 가진다. 여기서 N는 현재 힙에 있는 요소의 개수이다.
- 제거 연산:
- 힙에서 최대값을 제거하는 연산도 O(log N)의 시간 복잡도를 가진다
- 전체 시간 복잡도:
- 주어진 N개의 작업을 모두 처리하는 최악의 시간 복잡도는 O(N log N)이다. 이는 각각의 삽입 및 제거 연산이 최악의 경우 O(log N)시간이 걸리기 때문이다.
문제 조건 분석 과정
PriorityQueue를 사용하여 힙을 구현한다.
기본적으로 PriorityQueue는 최소 힙(min-heap)으로 동작하지만,
Collections.reverseOrder()를 사용하여 최대 힙(max-heap)으로 만든다.
- 0이 아닌 정수는 힙에 추가한다.
- 정수가 0이면 힙에서 최대값을 제거하고 결과를 출력한다. 힙이 비어 있으면 0을 출력한다.
전체코드
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 첫 번째 줄에서 입력 받을 정수의 개수 N
int N = Integer.parseInt(br.readLine());
// 최대 힙을 구현하기 위해 PriorityQueue를 생성
// PriorityQueue는 최소 힙(min-heap)을 사용하므로,
// 최대 힙(max-heap)을 구현하기 위해 Collections.reverseOrder()를 사용
PriorityQueue<Integer> que = new PriorityQueue<>(Collections.reverseOrder());
StringBuilder sb = new StringBuilder();
// N개의 정수
for (int i = 0; i < N; i++) {
// 한 줄에 있는 정수 입력
int num = Integer.parseInt(br.readLine());
if (num == 0) {
// num이 0인 경우, 힙에서 최대값을 제거하고 출력
// 힙이 비어있으면 0을 출력
sb.append(que.size() == 0 ? 0 : que.poll()).append('\n');
} else {
// num이 0이 아닌 경우, 힙에 num을 추가
que.add(num);
}
}
System.out.println(sb.toString());
}
}9663 N-Queen
https://www.acmicpc.net/problem/9663
문제설명
N x N 체스판 위에 N개의 퀸을 서로 공격하지 않도록 배치한다.
두 퀸이 서로 공격하지 않으려면 같은 행, 같은 열, 또는 같은 대각선에 있어서는 안되며
가능한 유효한 배치의 수를 찾는다.
접근방식
-
- 모든 가능한 배치를 시도해야 하므로 O(N!) 의 팩토리얼 시간 복잡도를 가진다.
문제 조건 분석 과정
- 백트래킹(Backtracking) 알고리을 사용한다
- 재귀적 탐색 (DFS): 체스판의 각 행마다 퀸을 배치하고, 유효한 배치인지 확인하며 다음 행으로 넘어가는 방식으로 탐색을 진행한다
- 유효성 검사: 각 배치가 유효한지 확인하기 위해, 현재까지 배치된 퀸들과 충돌하지 않는지를 검사한다
전체코드
import java.util.*;
import java.io.*;
public class Main {
// 퀸의 위치를 저장할 배열
public static int[] arr;
// 체스판의 크기
public static int N;
// 유효한 퀸 배치의 수
public static int count = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 체스판의 크기 N을 입력받음
N = Integer.parseInt(br.readLine());
// 퀸의 위치를 저장할 배열 초기화
arr = new int[N];
// N-Queen 문제 해결을 위한 함수 호출
nQueen(0);
// 가능한 퀸 배치의 수를 출력
System.out.println(count);
}
/**
* N-Queen 문제를 해결하기 위한 재귀 함수
* @param depth 현재 행을 나타내는 변수
*/
public static void nQueen(int depth) {
// 모든 행에 퀸을 배치한 경우
if (depth == N) {
// 유효한 배치가 하나 추가됨
count++;
return;
}
// 현재 행에 퀸을 배치할 수 있는 모든 열을 시도
for (int i = 0; i < N; i++) {
// 현재 행의 열에 퀸을 배치
arr[depth] = i;
// 배치가 유효한지 검사
if (Possibility(depth)) {
// 다음 행으로 이동
nQueen(depth + 1);
}
}
}
/**
* 현재까지 배치된 퀸들이 유효한지 검사하는 함수
* @param col 현재 검사할 열
* @return 유효한 배치인지 여부
*/
public static boolean Possibility(int col) {
// 현재 행(col)까지 배치된 모든 퀸들과 비교
for (int i = 0; i < col; i++) {
// 같은 열에 퀸이 배치된 경우
if (arr[col] == arr[i]) {
return false;
}
// 대각선에 퀸이 배치된 경우
else if (Math.abs(col - i) == Math.abs(arr[col] - arr[i])) {
return false;
}
}
// 유효한 배치
return true;
}
}15652 N과 M (4)
https://www.acmicpc.net/problem/15652
문제설명
1부터 N까지의 숫자 중에서 M개의 숫자를 선택하여 만들 수 있는 모든 순열을 생성하고 출력한다.
숫자는 중복해서 사용될 수 있으며, 순서도 여러개가 있다. 길이가 M인 순열의 모든 조합의 경우의 수를 출력해야 한다.
접근방식
- 총 조합의 수는 N^M이다. 이는 M개의 위치 각각에 대해 N개의 선택지가 있기 때문이다.
- 모든 가능한 길이의 M의 순열을 생성하고 처리할때 걸리는 시간복잡도는 O(N^M)이다.
문제 조건 분석 과정
- 깊이 우선 탐색(DFS) 알고리즘을 사용하여 순열을 만들 수 있는 모든 경우의 수를 탐색한다.
전체코드
import java.util.*;
import java.io.*;
public class Main {
public static int[] arr; // 조합을 저장할 배열
public static boolean[] visit; // 방문 여부를 기록할 배열
public static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
// N과 M을 입력받음
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
arr = new int[M]; // 길이 M의 배열 초기화
visit = new boolean[N]; // 길이 N의 방문 여부 배열 초기화
dfs(N, M, 0); // 깊이 우선 탐색 시작
System.out.println(sb); // 결과 출력
}
// 깊이 우선 탐색 (DFS) 함수
public static void dfs(int N, int M, int depth) {
if (depth == M) { // 배열이 M개의 요소로 채워지면
for (int val : arr) { // 배열의 모든 요소를 출력
sb.append(val).append(' ');
}
sb.append('\n'); // 줄 바꿈 추가
return;
}
for (int i = 0; i < N; i++) { // 1부터 N까지 반복
if (!visit[i]) { // 현재 숫자가 방문되지 않았다면
visit[i] = true; // 방문 표시
arr[depth] = i + 1; // 현재 깊이에 숫자 추가 (i + 1)
dfs(N, M, depth + 1); // 다음 깊이로 탐색
visit[i] = false; // 방문 표시 초기화 (백트래킹)
}
}
}
}15649 N과 M (1)
https://www.acmicpc.net/problem/15649
문제설명
- 수열의 길이는 M이다.
- 수열의 각 원소는 1부터 N까지의 정수 중 하나이다.
- 수열은 오름차순으로 정렬되어야 한다
주어진 N과 M에 대해, 가능한 모든 수열을 출력한다.
접근방식
깊이 M까지 탐색: 각 깊이에서 N개의 선택이 가능하므로, M 깊이까지 탐색하면 N^M개의 수열을 생성한다.
각 수열의 처리: 각 수열을 저장하는 데 걸리는 시간은 O(M)이다.
DFS를 사용하여 모든 가능한 수열을 탐색하는 경우 O(N ^ M) 의 시간복잡도가 소요된다.
문제 조건 분석 과정
- 깊이 우선 탐색(DFS) 알고리즘을 활용하여 모든 가능한 수열을 탐색하고, 유효한 수열을 찾을 때마다 결과를 저장한다.
전체코드
import java.util.*;
import java.io.*;
public class Main {
public static int N, M; // N과 M을 저장할 변수
public static int[] arr; // 결과를 저장할 배열
public static StringBuilder sb = new StringBuilder(); // 결과를 문자열로 저장할 StringBuilder
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " "); // 입력 문자열을 공백으로 나누기 위한 StringTokenizer
N = Integer.parseInt(st.nextToken()); // N 값을 파싱
M = Integer.parseInt(st.nextToken()); // M 값을 파싱
arr = new int[M]; // 길이가 M인 배열 생성
dfs(1, 0); // DFS 호출 (시작 인덱스 1, 깊이 0)
System.out.println(sb); // 결과 출력
}
public static void dfs(int at, int depth) {
if (depth == M) { // 깊이가 M에 도달하면
for (int val : arr) { // 배열의 각 값 출력
sb.append(val).append(' ');
}
sb.append('\n'); // 줄바꿈 추가
return; // 종료
}
for (int i = at; i <= N; i++) { // 현재 인덱스 at부터 N까지 반복
arr[depth] = i; // 배열의 현재 깊이에 i 값을 저장
dfs(i, depth + 1); // 다음 깊이로 재귀 호출
}
}
}1941 소문난 칠공주
https://www.acmicpc.net/problem/1941
문제설명
- 선택된 7개의 셀 중에서 'Y'가 4개 이상 없어야 한다.
- 선택된 7개의 셀은 모두 서로 연결되어 있다. 연결은 상하좌우로만 가능하며, 대각선 연결은 안된다.
5x5 격자판에서 특정 규칙을 만족하는 7개의 셀 조합을 찾는다.
접근방식
백트래킹
- 25개의 셀 중 7개를 선택하는 조합의 수는 (25 7 ) 이다.
- 이 조합의 수는 480,700정도 된다. 각 조합에 대해 BFS를 호출하므로, 모든 조합을 검사한다.
BFS
- BFS는 각 셀에 대해 상하좌우로 이동하며 탐색하므로 시간복잡도는 O(4 * 7) = O(28)이다.
- BFS는 각 조합에 대해 선형적으로 실행되므로 백트래킹의 조합 수와 BFS의 선형 시간복잡도가 곱해진 형태이다.
- 전체 시간복잡도는
문제 조건 분석 과정
- 백트래킹을 이용하여 7개의 셀 조합을 생성한다.
- backTracking 함수로 7개의 셀을 선택하는 모든 가능한 조합을 생성한다.
- 각 조합을 선택할 때 'Y'의 개수가 4개 이상이 되면 해당 조합은 더 이상 고려하지 않는다.
- 7개의 셀 조합을 완성하면 BFS를 호출하여 셀들이 모두 연결되어 있는지 확인한다
- BFS (너비 우선 탐색)를 사용하여 선택된 7개의 셀이 모두 연결되어 있는지 검사한다.
- 연결된 셀을 탐색하면서, 선택된 셀들 중에서 인접한 셀을 찾아서 큐에 추가한다.
- 연결된 셀의 수가 7이 되면, 이 조합은 유효한 조합으로 간주하고 카운트를 증가시킨다.
- 격자판의 범위를 벗어나지 않는지 확인한다.
전체코드
import java.util.*;
import java.io.*;
public class Main {
static char[][] map; // 5x5 격자판
static int answer = 0; // 유효한 조합의 개수를 저장
static boolean[] visited; // BFS에서 방문 여부를 체크
static int[] selected = new int[7]; // 선택된 7개의 셀의 인덱스를 저장
static int[] dr = {-1, 1, 0, 0}; // 상하좌우 이동을 위한 행 변화 배열
static int[] dc = {0, 0, -1, 1}; // 상하좌우 이동을 위한 열 변화 배열
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
map = new char[5][5]; // 5x5 격자판 초기화
// 격자판의 각 행을 읽어들여서 map 배열에 저장
for(int r = 0; r < 5; r++) {
map[r] = br.readLine().toCharArray();
}
// 백트래킹을 통해 모든 조합을 생성
backTracking(0, 0, 0);
// 결과 출력
System.out.println(answer);
}
// 백트래킹을 통해 7개의 셀 조합을 생성
static void backTracking(int depth, int numY, int start) {
// 'Y'의 개수가 4개 이상일 경우 더 이상 진행할 필요 없음
if(numY >= 4) return;
// 7개의 셀을 모두 선택한 경우
if(depth == 7) {
visited = new boolean[7]; // BFS를 위한 방문 배열 초기화
BFS(); // 선택된 셀들이 연결되어 있는지 확인
return;
}
// 가능한 모든 셀을 선택
for(int i = start; i < 25; i++) {
selected[depth] = i; // 현재 깊이(depth)에 해당하는 셀 선택
// 현재 셀이 'Y'일 경우와 'S'일 경우 분기
if(map[i / 5][i % 5] == 'Y') {
backTracking(depth + 1, numY + 1, i + 1);
} else {
backTracking(depth + 1, numY, i + 1);
}
}
}
// BFS를 통해 선택된 7개의 셀이 모두 연결되어 있는지 확인
static void BFS() {
Queue<int[]> q = new LinkedList<>();
q.add(new int[] {selected[0] / 5, selected[0] % 5}); // 시작 셀 추가
visited[0] = true; // 시작 셀 방문 처리
int conn = 1; // 연결된 셀의 수
// BFS를 통해 모든 연결된 셀 탐색
while(!q.isEmpty()) {
int[] cur = q.poll();
int r = cur[0];
int c = cur[1];
// 상하좌우로 이동하며 인접 셀 탐색
for(int i = 0; i < 4; i++) {
int nr = r + dr[i];
int nc = c + dc[i];
int ni = nr * 5 + nc; // 2D 인덱스를 1D 인덱스로 변환
// 셀이 유효한 범위에 있는지 확인
if(!isValid(nr, nc)) continue;
// 선택된 셀 중 방문하지 않았고 인접한 셀 찾기
for(int j = 0; j < 7; j++) {
if(!visited[j] && selected[j] == ni) {
q.add(new int[] {nr, nc}); // 큐에 추가
visited[j] = true; // 방문 처리
conn++; // 연결된 셀 수 증가
}
}
}
}
// 7개의 셀이 모두 연결된 경우 카운트 증가
if(conn == 7) answer++;
}
// 유효한 셀인지 확인
static boolean isValid(int r, int c) {
return r >= 0 && r < 5 && c >= 0 && c < 5;
}
}16987 계란으로 계란치기
https://www.acmicpc.net/problem/16987
문제설명
여러 개의 계란이 주어졌을 때, 각 계란의 내구도와 무게를 이용하여 최대 몇 개의 계란을 깨뜨릴 수 있는지를 구한다.
접근방식
- 다익스트라 알고리즘의 시간 복잡도: O((N + E) * log N)
-
- N은 정점의 수
- E는 간선의 수
- 우선순위 큐를 사용하여 각 정점에 대해 로그 N 시간의 복잡도로 거리 갱신을 수행한다
-
- (한 번은 1 -> v1 / v2, 두 번째는 v1 / v2 -> v2 / v1, 세 번째는 v2 / v1 -> N)
- 전체 시간 복잡도: O(3 * (N + E) * log N) = O((N + E) * log N)
문제 조건 분석 과정
- 백트래킹은 가능한 모든 경우의 수를 탐색하는 방법으로, 최적해를 찾기 위해 모든 경우를 시도하는 문제에 자주 사용된다.
- 백트래킹:
- 모든 계란을 처리했을 때, 최대 깨진 계란의 개수를 업데이트한다.
- 현재 계란이 이미 깨졌거나, 다른 계란이 모두 깨졌을 경우, 다음 계란으로 넘어간다.
- 현재 계란을 기준으로 다른 모든 계란과의 충돌을 시뮬레이션한다.
- 충돌 후, 깨진 계란의 수를 계산하고, 다음 단계로 넘어간다.
- 충돌 후에는 계란의 상태를 원래대로 복구한다.
- 충돌 및 복구:
- 두 계란이 충돌하여 내구도를 감소시키는 작업을 수행한다.
- 충돌로 인해 감소된 내구도를 원래 상태로 복구한다.
- 백트래킹:
전체코드
import java.util.*;
import java.io.*;
public class Main {
static int N;
static int[] dura; // 각 계란의 내구도를 저장하는 배열
static int[] weight; // 각 계란의 무게를 저장하는 배열
static int max = Integer.MIN_VALUE; // 최대 깨진 계란의 개수를 저장하는 변수
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine()); // 계란의 개수
dura = new int[N];
weight = new int[N];
// 각 계란의 내구도와 무게 입력
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine(), " ");
dura[i] = Integer.parseInt(st.nextToken());
weight[i] = Integer.parseInt(st.nextToken());
}
// 백트래킹을 통해 최대 깨진 계란의 개수를 찾음
bt(0, 0);
// 결과 출력
System.out.println(max);
}
// 백트래킹 함수
static void bt(int idx, int cnt) {
// 모든 계란을 처리했을 때
if (idx == N) {
max = Math.max(max, cnt); // 최대 깨진 계란의 개수 업데이트
return;
}
// 현재 계란이 이미 깨졌거나, 다른 계란이 N-1개 깨졌을 때
if (dura[idx] <= 0 || cnt == N - 1) {
bt(idx + 1, cnt); // 다음 계란으로 넘어감
return;
}
int nCnt = cnt; // 현재 깨진 계란의 개수 저장
// 다른 모든 계란과 부딪히는 경우 시도
for (int i = 0; i < N; i++) {
if (i == idx) continue; // 자기 자신과 부딪히지 않음
if (dura[i] <= 0) continue; // 이미 깨진 계란과 부딪히지 않음
// 계란 i와 계란 idx를 부딪힘
hitEgg(idx, i);
// 현재 계란이 깨졌는지 확인
if (dura[idx] <= 0) {
cnt++;
}
// 계란 i가 깨졌는지 확인
if (dura[i] <= 0) {
cnt++;
}
// 다음 계란으로 넘어감
bt(idx + 1, cnt);
// 계란을 원래 상태로 복구
recoveryEgg(idx, i);
cnt = nCnt; // 깨진 계란의 개수 복구
}
}
// 계란을 부딪혀서 내구도를 감소시키는 함수
static void hitEgg(int handEgg, int targetEgg) {
dura[targetEgg] -= weight[handEgg];
dura[handEgg] -= weight[targetEgg];
}
// 계란의 내구도를 원래대로 복구하는 함수
static void recoveryEgg(int handEgg, int targetEgg) {
dura[targetEgg] += weight[handEgg];
dura[handEgg] += weight[targetEgg];
}
}'자료구조 > 문제풀이' 카테고리의 다른 글
| [백준 JAVA] 12100 2048 (Easy) (1) | 2024.09.21 |
|---|---|
| [백준 JAVA] 15685 드래곤 커브 (0) | 2024.09.21 |
| [백준 JAVA] 16987 계란으로 계란치기 (1) | 2024.09.13 |
| [백준 JAVA] 1941 소문난 칠공주 (0) | 2024.09.13 |
| [백준 JAVA] 15649 N과 M (1) (0) | 2024.09.13 |