알고리즘
-
[알고리즘-JAVA] 백준 알고리즘 2579번 - 계단 오르기알고리즘 2019. 8. 16. 03:23
처음 실패했던 코드. import java.util.Scanner; import java.lang.Math; public class Main { public static int d[]; public static int arr[]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int count = sc.nextInt(); d = new int[count]; arr = new int[count]; for (int i = 0; i < count; i++) { arr[i] = sc.nextInt(); } if (count == 1) { System.out.println(arr[0]); } else if (count =..
-
[알고리즘-JAVA] 백준 알고리즘 1912번 - 연속합알고리즘 2019. 8. 15. 17:48
접근 과정 1. 어떤 문제로 이해 했는가? 그리고 문제의 제약 조건은? 주어진 임의의 수열에서 연속합의 최대값 구하기 2. 나의 방식대로 문제를 재정의 하자. d[i] = i번째 수를 마지막으로 했을 때의 최대 연속합 3. 어떤 알고리즘과 자료구조를 사용할 것인가? bottom-up을 이용한 dp 4. 어떻게 계산할 것인가? 1) 입력 Scanner사용 2) 시간 복잡도 계산 n만큼만 돌면 되고 하나의 n을 구할때의 연산은 O(1)이므로 O(N)이다. 5. 주의할 점은 무엇인가? 최대값을 구할때 마이너스가 나올수도 있다는 점. 6. 풀이 과정 a[i]로 끝나는 최대 연속합 경우 1. A[i-1]로 끝나는 연속합을 포함하는 경우 = D[i-1]+A[i] 경우 2. 새로운 연속합 A[i] [전체 소스 코드]..
-
[알고리즘-JAVA] 백준 알고리즘 11053번 - 가장 긴 증가하는 부분수열알고리즘 2019. 8. 15. 17:04
접근 과정 1. 어떤 문제로 이해 했는가? 그리고 문제의 제약 조건은? 수열 A가 주어지면, 가장 긴 증가하는 부분 수열(LIS)를 구하는 문제 2. 나의 방식대로 문제를 재정의 하자. d[i] = a[i]를 마지막으로 하는 가장 긴 증가하는 수열의 개수. 3. 어떤 알고리즘과 자료구조를 사용할 것인가? Bottom-up, dp 4. 어떻게 계산할 것인가? 1) 입력 Scanner 2) 시간 복잡도 계산 N개 탐색 * N번째 값을 구할때 N만큼의 비교가 필요하므로 O(N^2) 5. 주의할 점은 무엇인가? d[i]를 채우기 위한 d[j]를 찾는 과정, 그리고 마지막 답은 d[]배열 중 가장 큰 값을 출력하는 것. 6. 풀이 과정 d[i] = a[i]를 마지막으로 하는 가장 긴 증가하는 부분수열의 수 d[i..
-
[알고리즘-JAVA] 백준 알고리즘 2156번 - 포도주 시식알고리즘 2019. 8. 15. 16:03
접근 과정 1. 어떤 문제로 이해 했는가? 그리고 문제의 제약 조건은? 조건에 따라 최대로 마실 수 있는 포도주의 양을 구하는 문제이다. 2. 나의 방식대로 문제를 재정의 하자. d[n][k] = n번째 포도주가 k연속일 경우의 최대값. 3. 어떤 알고리즘과 자료구조를 사용할 것인가? 배열, Bottom-up 4. 어떻게 계산할 것인가? 1) 입력 Scanner이용 2) 시간 복잡도 계산 O(N) - n번째 배열까지 만들고 탐색 5. 주의할 점은 무엇인가? count가 1일때를 고려하지 않아서 에러가 났다. 6. 풀이 과정 d[n][k] = n번째 포도주잔을 마실 때 연속 k인 경우 d[n][0] = n번째 포도잔이 연속 0번째인 경우 = max(d[n-1][0], d[n-1][1], d[n-1][2] ..
-
[알고리즘-JAVA] 머지소트(Merge Sort)구현알고리즘 2019. 8. 11. 23:02
public class temp { public static int sorted[] = new int[30]; public static void Msort(int[] arr, int left, int right) { int center = (left + right) / 2; Msort(arr, left, center); Msort(arr, center + 1, right); Merge(arr, left, center, right); } public static void Merge(int[] arr, int lpos, int rpos, int rightend) { int leftend = rpos - 1; int sortedindex = lpos; int start = lpos; int end = righ..
-
[알고리즘-JAVA] 백준 알고리즘 1991번 - 트리의 순회[미완]알고리즘 2019. 8. 11. 22:31
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.StringTokenizer; import java.util.ArrayList; public class Main { public static ArrayList array; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int nCount = Integer.parseInt(br.readLine()); array = new ..
-
[알고리즘-JAVA] 백준 알고리즘 11724번 - 연결 요소의 개수알고리즘 2019. 8. 8. 00:14
접근 과정 1. 어떤 문제로 이해 했는가? 그리고 문제의 제약 조건은? 그래프 연결 요소의 개수를 구하는 문제이다. 2. 나의 방식대로 문제를 재정의 하자. 각 연결요소별로 dfs나 bfs를 돌려서 전부 탐색하게 한 뒤에, 총 연결요소의 개수를 구해내면 되는 문제이다. 3. 어떤 알고리즘과 자료구조를 사용할 것인가? dfs, ArrayList 4. 어떻게 계산할 것인가? 1) 입력 BufferedReader, InputStreamReader를 이용 2) 시간 복잡도 계산 O(N) 5. 주의할 점은 무엇인가? 연결 요소의 개수를 구하는 문제이기 때문에, check[]가 false인 모든 구간에서 dfs를 한번씩 다 해줘야 한다. 6. 풀이 과정 dfs/bfs 둘다 사용해서 풀이가 가능한데, 나는 dfs/ ..