- DFS는 출력해주는 위치에 따라 전위 / 중위 / 후위를 표현할 수 있다. 💻 코드 package org.kyhslam.algorithm; public class d58 { public static void dfs(int v) { if(v > 7) return; else{ System.out.print(v + " "); // 전위 : 1 2 4 5 3 6 7 dfs(v*2); //System.out.print(v + " "); // 중위 : 4 2 5 1 6 3 7 dfs((v*2)+1); //System.out.print(v + " "); // 후위 : 4 5 2 6 7 3 1 } } public static void main(String[] args) { dfs(1); } }
하나의 정점에서 다른 모든 정점들의 경로를 구하는 알고리즘이다. 간선들은 모두 양의 간선들을 가져야 한다. Dijkstra의 알고리즘에서는 시작 정점에서 집합S에 있는 정점만을 겨처서 다른 정점으로 가는 최단 거리를 기록하는 배열이 있어야 하는데 이 배열을 우선순위 큐로 구현하여 해당 큐에 들어간 Node중에 가중치가 젤 작은 정점을 가져오도록 구현해야 한다. 시작 정점을 0으로 잡고, 각 지점까지의 거리를 표시한다. 여기서 각 정점까지의 정보와 거리를 우선순위 큐에 넣는다. 그리고 우선순위 큐에서 가장 짧은 거리인 4정점까지의 거리인 3이므로 4정점에서 시작을 한다. 나는 해당 배열을 우선순위 큐로 구현하였다. 우선수위 큐 구현(가장 작은 값 순서로) package org.kyhslam.cps.sect..
문제 https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 참고 : m.blog.naver.com/PostView.nhn?blogId=tlstjd436&logNo=221568959948&proxyReferer=https:%2F%2Fwww.google.com%2F 백준(BOJ) 1182 - 부분수열의 합 (부분집합 구하기) //[java]- 재귀 부분수열의 합문제N개의 정수로 이루어진 수열이 있을 때, 길이가 양수인..
Student 클래스의 age 나이를 기준으로 나이가 많은, 적은 순으로 우선순위 큐를 사용하는 방법 나이가 많은 순 import java.util.PriorityQueue; // 우선순위 큐 // 객체의 특정 값을 기준으로 정렬 public class priorityQueu_Test { public static class Student implements Comparable { String name; int age; public Student(String name, int age){ this.name = name; this.age = age; } @Override public int compareTo(Student o) { return this.age
유니온 파인드 (Union-Find) 대표적 그래프 알고리즘으로 '합집합 찾기'라는 의미 상호 배타적 집합(Disjoint-set)이라고도 한다 여러 노드가 존재할 때, 두 개의 노드를 선택해서 현재 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘 Find : x가 어떤 집합에 포함되는지 찾는 연산 Union : x와 y가 포함되어 있는 집합을 합치는 연산 그림으로 이해하기 노드의 개수만큼 아래와 같이 모든 값이 자기 자신을 가리키도록 한다. i : 노드번호, P[i] : 부모노드 번호 를 의미하며, 즉 자기자신이 어떤 부모에 포함되어 있는지를 의미한다 간단히 Parent[i] = i 로 표현한다 Union(1,2) 를 하면 2번째 인덱스에 "1" 값이 들어간다. 부모를 합칠 때는 일반적으로 더 작은..
우선순위 큐(Priority Queue) 일반적인 큐는 제일 먼저 들어간 데이터가 가장 먼저 나오게 되는 자료구조이다. 이와 달리 우선순위 큐(Priority Queue)는 들어간 순서에 상관없이 일정한 규칙에 따라 우선순위를 선정하고, 우선순위가 가장 높은 데이터가 가장 먼저 나오게 된다. 최대힙 PriorityQueue의 생성자에 Collections.reverseOrder() 을 주어야 한다. import java.util.*; // 최대힙 (priority_queue : 우선순위 큐) public class cp73 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); PriorityQueue queue = ..
{33, 36, -73, 15, 43, -17, 36, -28, -1, 21} 1단계 : 배열 초기화 //초기화 public static void calculate_max(int[] s, int n){ for(int i=1; i < n; i++){ System.out.println("c[" + i + "] = max( s["+i+"], (s[" + i + "] + c[" + (i-1) + "] ) )"); c[i] = max( s[i] , (s[i] + c[i-1]) ); } System.out.println(); System.out.printf("a[] : "); view1(a); System.out.printf("c[] : "); view1(c); } c[1] = max( s[1], c[0] ) c[..
투자액 기업0 기업1 기업2 1 2 3 1 2 4 5 3 3 6 6 7 4 9 8 9 참고로 해당 이익표의 내용들을 아래와 같이 저장하였다. A[0,2] = 4 는 0기업에 2만원 투자했을 때의 이익이 4라는 것이다. static int[][] r = { {0,2,4,6,9}, {0,3,5,6,8}, {0,1,3,7,9} }; 쉽게 생각해서 max_return이라는 새로운 배열을 선언한고 해당 배열에는 최대값을 넣는다. 즉, max_return[1][2] = 3 이라고하면 0~1번 기업까지 2만원을 투자했을 때 얻을수있는 최대이익이 3 이라는 것이다. max_return[1][2] 값을 구하기 위해서는 아래와 같은 과정이 필요하다. 1) max_return[0][0] + r[1][2] 2) max_ret..
길찾기 알고리즘 지금까지 동적프로그래밍이란 재귀 + 메모제이션 이라고 알고 있었다. 재귀의 단점을 발전시킨 것이 메모제이션이고 이는 Top-Down 방식으로 진행된다. 동적프로그래밍은 초기화 된 처음 값을 쌓아가는 방식으로 Bottom-Up 방식으로 진행된다. 둘다 아이디어는 같다. 부분 문제들의 값을 다른 메모리 배열에 저장하여 반복계산하지 않는다. 주로 선호되는 방식은 메모제이션이다. 점화식 # 점화식 if ( map[i][j] == 0 ) MEMO[i][j] = 0; if ( map[i][j] == 1 ){ i==0, j==0 이면 MEMO[0][0] = 1; i > 0, j==0 이면 MEMO[i][j] = MEMO[i-1][j]; i==0, j > 0 이면 MEMO[i][j] = MEMO[i][..
소스 구현 (정렬된 수에서 32를 찾기) package org.kyhslam.algo; public class binarySearch { static int a[] = {12,23,32,57,65,81,89,99}; public static void main(String[] args) { viewArray(a); int target = 32; System.out.println(); binary(target); } //반복문 static public void binary(int target){ int left = 0; int right= a.length-1; // 7 while(left target){ right = mid -1; }else if(a[mid] < target){ left = mid +1; ..
선택정렬 개념 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘 최솟값 또는 최댓값을 찾고 남은 정렬 부분의 가장 앞에 있는 데이터와 swap하는 것이 선택정렬의 핵심이다. 첫번째 순서에는 첫번째 위치에 가장 최솟값을 넣는다. 두번째 순서에는 두번째 위치에 남은 값 중에서의 최솟값을 넣는다. 선택정렬 특징 장점 자료의 이동횟수가 미리 결정된다. 단점 시간 복잡도가 n제곱이라 효율적이지 않아코딩 테스트에서는 많이 사용하지 않는다. 안정성을 만족하지 않는다. 즉, 값이 같은 레코드가 있는 경우에 상대적인 위치가 변경될 수 있다. 선택정렬 예제 선택정렬 구현 코드 package org.kyhslam.algo; public class selectSort { public s..
| 병합정렬(Merge Sort) 대표적인 분할정복 방법을 채택한 알고리즘 이다. 퀵 정렬과 동일하게 O(N * logN)의 시간 복잡도를 가진다. 병합정렬은 정확히 반씩 나눈다는 점에서 최악의 경우에도 O(N * logN)을 보장한다. 하나씩 나누고 합쳐지면서 정렬을 수행한다. 즉, 합쳐지는 순간에 정렬을 수행한다. 왼쪽 집합의 i와 두번째 집합의 j를 증가시키면서 비교연산을 통해 비어있는 새로운 배열에 넣어준다. 병합정렬을 구현할 때 중요한 부분은 반드시 정렬에 사용되는 배열을 전역변수로 선언해야 한다는 것이다. 기존의 데이터를 담을 추가적인 배열공간이 필요하다는 점에서 메모리 활용이 비효율적이라는 문제가 있다. 구현 소스 package org.kyh.algorithm; public class mer..