반응형 Algorithm/이론9 DP 동적 프로그래밍은 Dynamic Programming이며 짧게 DP라고 줄여서 부릅니다. 이름 자체가 "동적" " 역동성" 이어서 난이도가 높아보이고 용어가 어려워 보이지만 그렇게 무서워할만한 파트는 아닙니다. 오히려 한번 감을 잡으면 아주 쉽게 풀 수 있습니다.(?) 동적 프로그래밍은 재귀적 알고리즘과 반복적으로 호출되는 부분으로 찾아내는 것이 관건입니다. 이를 찾은 뒤에 나중을 위해서 현재 결과를 캐쉬에 저장하면 됩니다. 캐쉬라는 것은 별 것 아니고 쉽게 말해 배열에 현재 결과 값을 저장하고 다음에 해당 값이 필요해지면 바로 꺼내 쓰기 위한 것입니다. 가장 흔한 예시로는 피보나치 수열이 있는데 아래 사진을 보면서 DP의 위력을 비교해보겠습니다. 문제를 해결할 때 N부터 시작하여 하위로 내려가는 방식을.. 2020. 8. 24. Binary Tree & 순회 *목차 전위, 중위, 후위순회 차이 Binary Tree Binary Search Tree unbalanced Complete Binary Tree Full Binary Tree Perfect Binary Tree 전위(Preorder) 중위(Inorder) 후위(Postorder) Root, Left , Right Left, Root, Right Left, Right, Root 1 -> 2 -> 4 -> 5 -> 3 4 -> 2 -> 5 -> 1 -> 3 4 -> 5 -> 2 -> 3 -> 1 *Binary Tree 노드가 최대 2개의 자식노드를 가진다. *Binary Search Tree Root 노드를 기준으로 왼쪽자식 노드는 작은 값, 오른쪽 노드는 큰 값을 가진다. *unbalanced 왼쪽 자.. 2020. 7. 20. List ( ArrayList & LinkedList ) *목차 배열의 단점 ArrayList - 장점 - 단점 LinkedList - 장점 - 단점 Doubly LinkedList ArrayList & LinkedList 성능 비교 추가, 조회, 삭제 성능 비교 *배열의 단점 1) 배열의 크기가 고정되어 있다. 그 말은 적게 사용하든 많이 사용하든 사용량에 관계없이 고정된 메모리가 할당 된다는 것이다. 2) 새로운 요소를 넣는 과정이 굉장히 힘들다. 새로운 위치가 할당되어 기존 값들의 위치가 움직이고 새로운 값이 들어가야 하기 떄문이다. 제거 또한 마찬가지로 제거된 공간을 채우기 위해 많은 값들이 이동해야 하기 때문에 무겁다. ArrayList ArrayList는 내부적으로 배열을 구현한다. 항상 초기 size를 설정해야만 하는 배열과 달리 초기의 일정한 s.. 2020. 7. 19. 다익스트라(dijkstra) *목차 1. 다익스트라 알고리즘이란? 2. 시간복잡도 3. 수도코드 4. 백준예제 5. 생각할 점 1. 다익스트라 알고리즘이란? 음의 가중치가 없는 그래프에서 한 노드에서 다른 모든 노드까지의 최단거리를 구하는 알고리즘이다. 방향그래프, 무방향 그래프 모두 상관 없으나, 가중치가 음수인 edge가 단 하나라도 존재하면 이 알고리즘은 사용할 수 없다. 2. 시간복잡도 (V는 정점, E는 정점의 이웃노드) 처음 고안한 알고리즘은 O(V^2)의 시간복잡도를 가졌다. 이후 O((V+E)logV)의 우선순위 큐(=힙 트리)등을 이용한 더욱 개선된 알고리즘이 나왔다. O((V+E)logV)의 시간복잡도를 가지는 이유는 각 노드마다 미방문 노드 중 출발점으로부터 현재까지 계산된 최단 거리를 가지는 노드를 찾는데 O(.. 2020. 7. 13. PriorityQueue / Deque *PriorityQueue Queue 인터페이스의 구현체 중의 하나로, 저장한 순서에 관계없이 우선순위가 높은 것부터 꺼내게 된다는 특징이 있다. null은 저장할 수 없고 NullPointerException이 발생한다. 저장공간으로 배열을 사용하며, 각 요소를 '힙(heap)'이라는 자료구조의 형태로 저장한다. (힙은 이진트리의 한 종류로 가장 큰 값이나 가장 작은 값을 빠르게 찾을 수 있다.) import java.util.*; public class PriorityQueueExam { public static void main(String[] args) { // TODO Auto-generated method stub Queue pq = new PriorityQueue(); // Adding it.. 2020. 7. 10. Set<E> vs Map<K,V> Set은 중복을 허용하지 않고 Null값은 1개를 허용하고 순서를 보장하지 않는다. Map은 key 중복은 허용하지 않고 value중복은 허용하며 Null값은 key값의 경우 1개, value의 경우 여러개를 허용하고 마찬가지로 순서를 보장하지 않는다. *Set 타입 메소드 설명 boolean add(E e) 데이터를 set에 추가한다. boolean contains(Object o) 데이터가 있는지 확인한다. boolean remove(Object o) 데이터를 제거한다. ex) HashSet, LinkedHashSet, TreeSet, SortedSet import java.io.*; import java.util.*; import java.util.Map.Entry; public class Main.. 2020. 7. 10. BufferedReader 백준 2751 수 정렬하기 2 문제를 풀던 중, 100만개의 데이터를 정렬할 때, Collections.sort(list)에 문제점이 있나 확인하면서 찾았지만, 정렬이 문제가 아닌 데이터를 읽는 시간이 문제였다. Scanner로 읽으면 성능이 매우 떨어져서 시간초과가 났는데 BufferedReader로 데이터를 읽었을 때 성공했다. BufferedReader는 무엇인지 빠른 성능으로 입력을 받을 때 어떤 라이브러리를 사용하는지 확인해본다. 1.1 입출력이란? I/O란 Input과 output의 약자로 입력과 출력, 간단히 입출력이라고 한다. 입출력은 컴퓨터 내부 또는 외부의 장치와 프로그램간의 데이터를 주고받는 것을 말한다. 1.2 스트림(Stream) 자바에서 입출력을 수행하려면, 즉 어느 한쪽에서 다.. 2020. 7. 6. Comparable & Comparator Comparable This interface imposes a total ordering on the objects of each class that implements it. This ordering is referred to as the class's natural ordering, and the class's compareTo method is referred to as its natural comparison method. Lists (and arrays) of objects that implement this interface can be sorted automatically by Collections.sort (and Arrays.sort). Objects that implement this.. 2020. 7. 6. 투 포인터(Two Pointer) 투 포인터는 1차원 배열에서 선형시간에 2개의 배열요소(인접 할 경우 2개 이상의 배열요소)를 이용하여 문제를 해결해야 하는 경우 사용한다. 2개의 배열요소를 이용한다는 것은 2개를 비교한다는 것을 의미한다. 보통의 방식으로는 배열에서 요소 2개를 배교하면 시간복잡도 O(N^2)로 풀게 되는데, 왜냐하면 모든 배열 요소들을 처음부터 끝까지 확인해야 하기 때문이다. 하지만, 이전에 방문한 것을 다시 방문하지 않는 투 포인터 방식을 사용하면 O(N)만에 해결이 가능하다. 투 포인터의 포인터는 당연하게도 C언어와 관련한 포인터가 아닌 배열의 특정 원소위치를 가리키는 것을 의미한다. 기본적인 개념을 넘어가고 백준 알고리즘에서 풀었던 문제에 대한 팁을 몇가지 적는다. 2003번: 수들의 합 2 import jav.. 2020. 7. 5. 이전 1 다음 반응형
