Coding Story

https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net package DAY06.P1922; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; class Computer implements Comparable{ int start, end, cost; public Computer(int start, int end, int cost) { this.start = start; this.end = e..

https://yeoncoding.tistory.com/573 [자료구조] 우선순위 큐(Priority Queue)와 힙(Heap) 우선순위 큐(Priority Queue) 1. 우선순위 큐란? 보통의 큐는 선입 선출(FIFO)의 원칙에 의하여 먼저 들어온 데이터가 먼저 나가게 된다. 그러나 우선순위 큐는 데이터들이 우선 순위를 가지고 있고 우 yeoncoding.tistory.com 힙의 개념은 위의 링크에 정리해두었다. 아래는 최대힙의 삽입, 삭제를 리스트로 구현한 것이다. class MaxHeap{ List list; public MaxHeap(){ list = new ArrayList(100001); list.add(0); } public void insert(int val){ // 1. 마지막에..

https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.StringTokenizer; public class Main{ public static void main(String[] args) th..

이분 탐색이란? 이분 탐색은 이진 탐색, Binary Search 라고도 한다. 순차적 탐색보다 빠른 탐색을 위해 나온 탐색 방법으로 실제로 이분 탐색의 시간복잡도가 순차적 탐색보다 낮다. 순차 탐색: 리스트 안에 있는 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법이분 탐색: 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정한다. 이분 탐색 방법 처음 범위는 인덱스 0부터 끝까지이다. 이 때 중간 인덱스를 mid로 한다. mid의 값와 찾는 원소를 비교한다. 2-1) 찾는 원소와 mid의 값이 같다면 탐색 종료한다. 2-2) mid의 값 < 찾는 원소 일 때 left는 mid + 1로 하여 2)를 다시 반복한다. ..

StringBuilder reverse() 사용 public static ArrayList solution(String[] str){ ArrayList answer = new ArrayList(); for(String x : str){ String tmp = new StringBuilder(x).reverse().toString(); answer.add(tmp); } return answer; } toCharArray로 배열로 바꿔 풀이 public static ArrayList solution2(String[] str){ ArrayList answer = new ArrayList(); for(String x :str){ char[] s = x.toCharArray(); int left = 0, righ..

https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.StringTokenizer; public class Main{ static int n, m; static ArrayList list; static boolean[] visit; static int answer = 0; public static void dfs..

https://www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net Set 사용 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new ..

https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main{ public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parse..

Dijkstra 최단 경로 알고리즘 하나의 시작 정점으로부터 모든 다른 정점까지의 최단 경로를 찾는 알고리즘 n개의 정점이 있다면 O(n^2)의 시간복잡도를 가진다. #include #include #define TRUE 1 #define FALSE 0 #define MAX_VERTICES 100 #define INF 1000L typedef struct GraphType { int n; // 정점의 개수 int weight[MAX_VERTICES][MAX_VERTICES]; }GraphType; int distance[MAX_VERTICES]; // 시작 정점으로부터의 최단경로 거리 int found[MAX_VERTICES]; // 방문한 정점 표시 // 선택되지 않은 정점 중 distance 값이 가..

신장 트리(Spanning Tree) 그래프 내의 모든 정점을 포함하는 트리 모든 정점들이 연결되어 있고 사이클을 포함하면 안된다. 그래프의 최소(간선의 수가 가장 작은) 연결 부분 그래프 n개의 가지는 그래프는 최소한 (n-1)개의 간선을 가진다. 간선에 비용을 붙여 링크의 구축 비용까지를 고려해 최소 비용의 신장 트리를 선택해야함 통신 네트워크 구축에 많이 사용 최소 비용 신장 트리(MST) 네트워크에 있는 모든 정점들을 가장 적은 수의 간선과 비용으로 연결 신장 트리 중에서 사용된 간선들이 가중치 합이 최소인 신장 트리 Kruskal, Prim 알고리즘이 대표적 반드시 n-1 개의 간선만 사용하고, 사이클이 포함되어서는 안된다. Kruskal 의 MST 알고리즘 탐욕적인 방법(greedy metho..