notepad by Oxix

트리란 ? 모두가 연결되어 있는 그래프 -> 어떤 두 점을 골라도 간선을 타고 사이를 이동 가능 사이클이 존재하지 않음 정점 개수 V = 간선 개수 E + 1 위의 조건 중 2개 이상을 만족해야 한다. 알고리즘 문제를 풀게 되면 Rooted Tree가 대부분이다. Rooted Tree? Node -> 정점 Root -> 최상단에 있는 정점 Depth -> 상대적 값이다. Root depth == 0 (1부터 시작해도 무관하다.) Parent, Child, Ancestor, Sibling - Parent : 현재 위치 노드와 연결되어 있으며 바로 한단계 위의 노드 - Child : 현재 위치 노드와 연결되어 있으며 바로 한단계 아래의 노드 - Ancestor : 자신의 루트 노트 사이의 관계 - Sibli..

문제 풀이 직선 위에 점은 위치와 색깔을 나타낸다. (위치,색깔) 위치는 최대 10만까지 색깔은 300개까지 최대 가능하다. 점을 지나칠때 마다 모두 검사를 한다면 제한 시간 2초 (약 2억번)에는 불가능하다. 이유는 O(n) * n 이기 때문에 2억번을 넘는다. 그렇기 때문에 색상 별로 나누고 정렬한다. 가장 가까운 원소는 양 옆에 있기 때문에 하나를 고르면 된다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.lang.reflect.Array; import java.util.ArrayList; import java.util.Collections; import j..

문제 풀이 해당 문제는 정렬 문제이다. 숫자 카드에 쓰이는 정수는 int형을 벗어나므로 long형을 쓰거나 BigInteger를 사용해야하며, 길이가 최대 10만인 배열을 순차적으로 비교할때 제한 시간 1초 약 1억번의 연산으로 충분해 보인다. 카드에 적힌 숫자가 가장 많은 것을 찾아야하고 동률인 경우 더 작은 수를 출력해야 하기 때문에 내림차순으로 정렬한 뒤 기본값으로 지정한 count보다 많은 경우 값을 변경해주면 된다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; public class 카드_11652 { static StringBui..

문제 풀이 해당 문제는 제목과 같이 정렬 문제이다. 배열 크기 N은 최대 50이며 50개의 배열을 일반 정렬로 구현해도 제한 시간안에 충분히 구현 가능하다. 자료형은 Int형 범위안에 들기 때문에 Int를 쓰도록 하겠다. 원본 배열을 정렬된 배열과 비교하여 index값을 정렬된 배열에 몇번째 위치하는지 나타내는 배열을 출력하는 문제 이다. 구조체를 사용하여 index, value을 갖게한 다음 value기준으로 정렬하여 값을 비교 이후, 결과를 도출했다.(value가 같으면 index를 이용하여 알아서 정렬해준다.) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.u..

문제 유형 완전 탐색을 하여 하나씩 결과를 비교해야 하기 때문에 브루트 포스 알고리즘 유형이다. N의 최대는 20이기 때문에 2의 20제곱 만큼 경우의 수가 나온다 완전탐색의 경우 2초안에 가능한 범위이며 정수 S의 최대치는 정수형이기 때문에 변수는 int형을 쓰도록 하겠다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class 부분수열의합_1182 { static int N, S, ans; static int[] arr; static BufferedReader br = new BufferedReader(new..

최단 경로 알고리즘 최단 경로란 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. 그래서 "길 찾기" 문제라고도 불린다. 해당 알고리즘 유형에는 다양한 종류가 있는데, 상황에 맞는 효율적인 알고리즘이 이미 정립되어 있다. 다양한 사례가 존재하며 이런 사례에 맞는 알고리즘을 알고 있다면 문제를 좀 더 쉽게 풀 수 있다. 최단 경로 알고리즘 유형에서 다익스트라 최단 경로와 플로이드 워셜 알고리즘 2가지가 코딩 테스트에서 가장 많이 등장하는 유형이다. 앞서 그리디 알고리즘 + 다이나믹 프로그래밍 알고리즘에 그대로 적용되는 특징을 가지고 있다. 다익스트라 최단 경로 알고리즘 다익스트라 최단 경로 알고리즘은 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주..

해당 문제는 브루트 포스 문제로 모든 경우를 다 탐색한 다음 합산한 값을 비교하여 출력하기로 하였다. public class 퇴사_14501 { static int N; static Work[] arr; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; N = Integer.parseInt(br.readLine()); arr = new Work[N + 1]; for (int i = 1; i

다이나믹 프로그래밍? 최적의 해를 구하기에 시간이 매우 많이 필요하거나 메모리 공간이 매우 많이 필요한 문제 등이 컴퓨터로도 해결하기 어려운 문제이다. 연산 속도에 한계가 있고, 메모리 공간을 최대한 활용 할 수 있는 효율적인 알고리즘을 작성해야 한다. 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가 시킬 수 있는 방법이 있는데 해당 방법 중에 하나가 다이나믹 프로그래밍이다. 다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예시로 피보나치 수열이 있다. 피보나치 수열을 해석하면 다음과 같다. n번째 피보나치 수 = ( n - 1 )번째 피보나치 수 + ( n - 2 )번째 피보나치 수 단, 1번째 피보나치 수 = 1 , 2번째 피보나치 수 = 1 public int fibo(int x){ i..

순차 탐색 N개의 데이터가 있을 때, 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법이다. 리스트 내에 데이터가 아무리 많아도 시간만 충분하다면 항상 찾을 수 있는 장점이 있다. 코드로 작성하면 다음과 같다. public class 순차탐색 { public static void main(String[] args) { int[] arr = {1, 2, 3, 4, 5}; int value = 3; boolean isTrue = sequentialSearch(arr, value); System.out.println(isTrue); } private static boolean sequentialSearch(int[] arr, int value) { for (int ..

정렬이란 데이터를 특정한 기준에 따라 순서대로 나열하는 것을 의미한다. 데이터를 가공할 때 내림차순, 오름차순으로 정렬해서 사용하는 경우가 많기에 프로그램을 작성할 때 가장 많이 사용되는 알고리줌 중 하나이다. 정렬 알고리즘은 버블 정렬, 선택 정렬, 삽입 정렬, 병합 정렬, 퀵 정렬 등이 있다. 정렬을 공부하면 알고리즘의 효율성을 쉽게 이해할 수 있고 적절한 정렬 알고리즘이 공식처럼 사용된다. 선택 정렬 데이터가 무작위로 여러 개 있는 경우 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두번째 데이터와 바꾸는 과정을 반복한다. 이 방법은 가장 원시적인 방법으로 매번 가장 작은 것을 선택하는 의미에서 선택 정렬 알고리즘이라고 한다. void selecti..