본문 바로가기
반응형

Algorithm66

559 : Maximum Depth of N-ary Tree ( leetcode / java ) *해결 과정 먼저 기본적으로 주어진 Node 의 형태를 확인해보자. N차 노드이기 때문에 자손이 List로 선언되었다는 것에 유의한다. 특히 우리는 depth를 구해야 하는데, Node에는 depth 변수가 선언되있지 않기 때문에 별도의 변수 선언이 필요하다. 여기서 해결 방안은 2가지이다. 1. 새로운 class를 만들어 depth를 추가한다. 2. depth에 대한 전역변수를 만들고 계속 업데이트하면서 값을 구한다. *1번 class Point{ Node node; int depth; public Point(Node node, int depth){ this.node=node; this.depth=depth; } } class Solution { int ans=0; public int maxDepth(.. 2020. 10. 28.
897 : Increasing Order Search Tree ( leetcode / java ) *해결 과정 모든 Tree를 순회하고, 오른쪽 트리만 계속 만들면 된다. 나는 ArrayList를 사용하고 get()을 통해 순회하였다. 여러가지 해설을 찾아보니 LinkedList로 선언하고 remove로 제거하면서 while에서 해결하는 것도 괜찮은 방법이라 생각한다. *ArrayList 사용 import java.util.*; class Solution { List list = new ArrayList(); public TreeNode increasingBST(TreeNode root) { DFS(root); Collections.sort(list); TreeNode node = new TreeNode(list.get(0)); list.remove(0); makeTree(node, 0); retur.. 2020. 10. 28.
700 : Search in a Binary Search Tree ( leetcode / java ) *해결 과정 void를 통한 함수를 사용하는 것과 TreeNode를 통한 함수를 사용하는 방법 2개가 있다. class Solution { TreeNode tree = null; public TreeNode searchBST(TreeNode root, int val) { DFS(root,val); return tree; } public void DFS(TreeNode root, int val){ if(root.val==val) { tree=root; return; } if(root.left!=null) searchBST(root.left,val); if(root.right!=null) searchBST(root.right,val); } } class Solution { public TreeNode sea.. 2020. 10. 28.
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이면.. 2020. 10. 27.
3687 : 성냥개비 ( 백준 / java ) www.acmicpc.net/problem/3687 3687번: 성냥개비 각 테스트 케이스에 대해서 입력으로 주어진 성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수와 가장 큰 수를 출력한다. 두 숫자는 모두 양수이어야 하고, 숫자는 0으로 시작할 수 없다. www.acmicpc.net *해결과정 이 문제는 느낌상 dp였다. 하지만... dp는 항상 어렵다.. 특히 이 문제는 더욱 어려웠다. 규칙을 찾는 방식이 너무 독특했다. 먼저 dp에서 가장 핵심은 구해야 하는 것이 무엇이냐!?이다. 우리는 가장 작은 수와 큰 수를 구해야한다. 즉 dp에 저장되는 값들은 성냥을 이용한 갯수도 아니고 어떤 종류도 아니고 가장 작은 수, 큰 수가 저장되어야 하는 것이다. 따라서 2개의 dp배열을 만들어야 하며 100.. 2020. 10. 27.
2579번 : 계단 오르기 ( 백준 / java ) www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net *해결과정 연속된 세개의 계단을 모두 밟아서는 안된다. 단, 시작점은 계단에 포함되지 않는다. 이 부분이 가장 핵심적이라고 생각한다. 처음에는 건널 수 있는 계단 조합을 생각해서 212칸 이동 + 121칸 이동 12칸 이동 / 21칸 이동 / 2칸 이동 등등 어떻게 하면 모두를 만족시키면서 dp를 최대값으로 계속 추가할 수 있는지 고민하였다. 하지만 접근 방법이 잘못되었다. 계속 최선의 계단의 점수로 업데이트를 하는 것은 .. 2020. 10. 26.
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.
반응형

티스토리툴바