Algorithm (66) 썸네일형 리스트형 617 : Merge Two Binary Trees ( leetcode / java ) leetcode.com/problems/merge-two-binary-trees/ Merge Two Binary Trees - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com *해결과정 Tree 2개를 합쳐야 한다. 2가지 방법이 있다. 1. DFS로 새로운 Tree를 만들고 Tree1, Tree2를 전부 더해준다. 2. 새로운 tree를 생성하지 않고 기존의 Tree1에 Tree2를 더해서 반환한다. 결국 초기조건을 잘 잡아야 하는데, 1번 같은 경우 DFS이면.. 3687 : 성냥개비 ( 백준 / java ) www.acmicpc.net/problem/3687 3687번: 성냥개비 각 테스트 케이스에 대해서 입력으로 주어진 성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수와 가장 큰 수를 출력한다. 두 숫자는 모두 양수이어야 하고, 숫자는 0으로 시작할 수 없다. www.acmicpc.net *해결과정 이 문제는 느낌상 dp였다. 하지만... dp는 항상 어렵다.. 특히 이 문제는 더욱 어려웠다. 규칙을 찾는 방식이 너무 독특했다. 먼저 dp에서 가장 핵심은 구해야 하는 것이 무엇이냐!?이다. 우리는 가장 작은 수와 큰 수를 구해야한다. 즉 dp에 저장되는 값들은 성냥을 이용한 갯수도 아니고 어떤 종류도 아니고 가장 작은 수, 큰 수가 저장되어야 하는 것이다. 따라서 2개의 dp배열을 만들어야 하며 100.. 2579번 : 계단 오르기 ( 백준 / java ) www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net *해결과정 연속된 세개의 계단을 모두 밟아서는 안된다. 단, 시작점은 계단에 포함되지 않는다. 이 부분이 가장 핵심적이라고 생각한다. 처음에는 건널 수 있는 계단 조합을 생각해서 212칸 이동 + 121칸 이동 12칸 이동 / 21칸 이동 / 2칸 이동 등등 어떻게 하면 모두를 만족시키면서 dp를 최대값으로 계속 추가할 수 있는지 고민하였다. 하지만 접근 방법이 잘못되었다. 계속 최선의 계단의 점수로 업데이트를 하는 것은 .. DP 동적 프로그래밍은 Dynamic Programming이며 짧게 DP라고 줄여서 부릅니다. 이름 자체가 "동적" " 역동성" 이어서 난이도가 높아보이고 용어가 어려워 보이지만 그렇게 무서워할만한 파트는 아닙니다. 오히려 한번 감을 잡으면 아주 쉽게 풀 수 있습니다.(?) 동적 프로그래밍은 재귀적 알고리즘과 반복적으로 호출되는 부분으로 찾아내는 것이 관건입니다. 이를 찾은 뒤에 나중을 위해서 현재 결과를 캐쉬에 저장하면 됩니다. 캐쉬라는 것은 별 것 아니고 쉽게 말해 배열에 현재 결과 값을 저장하고 다음에 해당 값이 필요해지면 바로 꺼내 쓰기 위한 것입니다. 가장 흔한 예시로는 피보나치 수열이 있는데 아래 사진을 보면서 DP의 위력을 비교해보겠습니다. 문제를 해결할 때 N부터 시작하여 하위로 내려가는 방식을.. 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 왼쪽 자.. List ( ArrayList & LinkedList ) *목차 배열의 단점 ArrayList - 장점 - 단점 LinkedList - 장점 - 단점 Doubly LinkedList ArrayList & LinkedList 성능 비교 추가, 조회, 삭제 성능 비교 *배열의 단점 1) 배열의 크기가 고정되어 있다. 그 말은 적게 사용하든 많이 사용하든 사용량에 관계없이 고정된 메모리가 할당 된다는 것이다. 2) 새로운 요소를 넣는 과정이 굉장히 힘들다. 새로운 위치가 할당되어 기존 값들의 위치가 움직이고 새로운 값이 들어가야 하기 떄문이다. 제거 또한 마찬가지로 제거된 공간을 채우기 위해 많은 값들이 이동해야 하기 때문에 무겁다. ArrayList ArrayList는 내부적으로 배열을 구현한다. 항상 초기 size를 설정해야만 하는 배열과 달리 초기의 일정한 s.. 다익스트라(dijkstra) *목차 1. 다익스트라 알고리즘이란? 2. 시간복잡도 3. 수도코드 4. 백준예제 5. 생각할 점 1. 다익스트라 알고리즘이란? 음의 가중치가 없는 그래프에서 한 노드에서 다른 모든 노드까지의 최단거리를 구하는 알고리즘이다. 방향그래프, 무방향 그래프 모두 상관 없으나, 가중치가 음수인 edge가 단 하나라도 존재하면 이 알고리즘은 사용할 수 없다. 2. 시간복잡도 (V는 정점, E는 정점의 이웃노드) 처음 고안한 알고리즘은 O(V^2)의 시간복잡도를 가졌다. 이후 O((V+E)logV)의 우선순위 큐(=힙 트리)등을 이용한 더욱 개선된 알고리즘이 나왔다. O((V+E)logV)의 시간복잡도를 가지는 이유는 각 노드마다 미방문 노드 중 출발점으로부터 현재까지 계산된 최단 거리를 가지는 노드를 찾는데 O(.. 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.. 이전 1 ··· 4 5 6 7 8 9 다음
