내일의 나는 오늘보다 나을까?

# 문제17408번 : 수열과 쿼리 17408https://www.acmicpc.net/problem/17408 세그먼트 트리로 가장 큰 수와 두번재로 큰 수의 합을 구하는 문제이다. 세그먼트 트리로 범위안에서 가장 큰 수를 구하는 문제에서 두번재로 큰 수까지 구하는 로직을 넣으면 된다. 세그먼트 트리를 2차원 배열로 만들어서 가장 큰 값과 두번재 값을 구한 코드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 IOEx..

# 문제27968번 - 사사의 사차원 사탕 봉지https://www.acmicpc.net/problem/27968 누적합 + 이진탐색 문제이다.입력의 개수가 많기 때문에 순차탐색으로는 해결할수 없다.. import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new Input..

# 문제5619번 : 세 번째https://www.acmicpc.net/problem/5619  두 수를 조합해서 만들수 있는 수 중에 3번째로 작은 수를 구하는 문제이다.문제를 잘 읽어보면 전체를 고려할 필요가 없고 앞에있는 몇개의 수만 고려하면 된다.작성한 코드에서는 모든 수를 입력받고 정렬한 후에 인덱스 10번까지만 고려해서 문제를 풀었다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.HashSet;import java.util.PriorityQueue;import java.util.Set;public class ..

# 문제14438번 : 수들의 합 7https://www.acmicpc.net/problem/14438제시된 범위에서 가장 작은 값을 출력하는 문제이다.세그먼트트리로 풀수있다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer;public class Main { static int[] tree; static int startIndex; static BufferedReader br; static StringTokenizer st; public static void main(String[] arg..

# 문제2268번 : 수들의 합 7https://www.acmicpc.net/problem/2268  세그먼트 트리를 이용해야 제한시간에 맞게 풀수 있는 문제이다. 내용자체는 복잡하지 않아서 세그먼트 트리를 알면 충분히 풀수 있는 문제이지만 자바에서는 index 가 0에서 부터 시작되는데 반해 문제에서는 index 가 1부터 시작하기 때문에 혼란이 올수 있다.또 세그먼트 트리에 저장되는 값이 int 가 넘을 수 있기 때문에 반드시 long 자료형으로 배열을 선언해 주어야 올바른 답을 구할 수 있다.그리고 입력되는 인자가 반드시 처음값보다 나중값이 크다는 보장이 없어서 이 부분도 처리해 주어야 한다. 우선 만약에 문제에서 인덱스가 1번부터 시작하는 경우 배열의 크기를 세그먼트 트리의 형태에 맞게 선언해주고..

세그먼트 트리는 데이터들의 구간 합이나 구간에서 가장 큰수, 가장 작은수등을 빠르게 계산하기 위해 고안된 자료구조이다. 세그먼트 트리가 어떻게 구성되는지 예를 통해 알아보자  길이가 8인 배열 {1, 2, 3, 4, 5, 6, 7, 8} 이 있을 때 만약 누적합을 세그먼트 트리를 이용해 계산하면 우선 트리에 가장 아래 부분에 순서대로 수열의 값을 저장한다 트리의 부모노드에 자식노드의 합을 저장한다. 여기에 1 부터 인덱스를 부여하면길이가 16인 배열에 { 0, 26, 10, 26, 3, 5, 7 ,11, 15, 1, 2, 3, 4, 5, 6, 7, 8} 순서대로 값이 저장되어 있다. 세그먼트 트리를 만드는 방법을 그림을 통해 유추해 보면세그먼트 트리 배열의 길이는 기존의 배열의 길이보다 크거나 같은 2의..

# 문제13549번 : 숨바꼭질 3https://www.acmicpc.net/problem/13549 백준 문제를 풀다 보면 글을 잘 읽어야 할때가 많다...순간이동을 할때는 말그대로 순간이동이라 걸리는 시간이 0초인점.동생과 수빈이의 위치가 0에서 100000이고 동생이 수빈이보다 앞에 있다는 말이 없다. 코드자체는 단순한데 문제의 조건에 맞게 다익스트라 알고리즘을 작성해주면 된다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.PriorityQueue;import java.util.StringTokenizer;clas..

노드사이의 거리를 구하는 문제이다.# 문제1240번 : 노드사이의 거리https://www.acmicpc.net/problem/1240문제 분류는 트리로 되어 있는데 이게 왜 트리 문제인지 사실 잘 모르겠다.트리로는 이 문제를 어떻게 해결하는지 잘 모르겠어서 다익스트라 알고리즘을 사용해 해결했다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.List;import java.util.PriorityQueue;import java.util.StringTokenizer;// 노드 클래스 정의 (우선순위 큐에서 사용할 Co..

플로이드 워셜 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘이다. 기능장점단점모든 노드 간에 최단 경로를 탐색음수 가중치 에지가 있어도 수행할 수 있음속도가 느림 O(n3) 플로이드 워셜 알고리즘을 사용할 때는 시간 복잡도를 반드시 고려해야 한다. 플로이드 워셜 알고리즘의 가장 핵심적인 원리는 A 노드 에서 B 노드를 거쳐 C노드로 갈때  ( A -> B -> C)A 노드와 C노드의 경로가 최단 경로일때 (A -> B -> C) 중간 경로들인 A노드 에서 B (A -> B -> C)노드 까지 가는 경로도 최단 경로인 것이다. D[A][C] = Math.min(D[A][C], D[A][B] + D[B][C])A 에서 C까지의 최단 거리는A 에서 C까지의 기존 거리, A에서 B까지의 거리 + B 에서 C..

트리의를 순회하는 방법은 3가지가 있다1. 전위 순회 : Root -> Left -> Right2. 중위 순회 : Left -> Root -> Right3. 후위 순회 : Left -> Root -> Right외우는 방법전위순회는 root 가 앞에중위는 root 가 중간에후위는 root 가 뒤에전위순회한 결과 : ABDCEFG중위순회한 결과 : DBAECFG후위순회한 결과 : DBEGFCA # 문제1991번 : 트리 순회하기https://www.acmicpc.net/problem/1991설명 : 단순히 트리를 순회하는 코드를 작성하는 문제이다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;i..