알고리즘
[알고리즘] 이진 트리 (Binary Tree)의 순회방법 (Java)
이진트리 (Binary Tree) 🔗 최대 두개의 자식을 같은 구조 이진트리를 순회하는 방법은 크게 3가지가 있다. Inorder (left, root, right) : 본인이 왼쪽과 다음 사이에 끼인 순서 Preorder (root, left, right) : 왼쪽과 다음 전의 순서 Postorder (left, right, root) : 왼쪽과 다음 후의 순서 코드 package study; /* * (1) / \ * (2) (3) / / *(4) (5) * Inorder (left, root, right): 4 2 5 1 3 * Preorder (root, left, right): 1 2 4 5 3 * Postorder (left, right, root): 4 5 2 3 1 * * */ class ..
[알고리즘] 정렬만 되어있으면 검색하기 참- 좋은데, 트리의 이진검색(Java)
이진 검색 트리 (BST : Binary Search Tree) 최대 두 개의 자식을 가지는 구조 노드의 왼쪽 자식의 값이 반드시 자신의 값 이하이며, 오른쪽 자식의 값은 반드시 자신의 값 이상이다. 이진 검색 트리의 장점 가운데 하나로 룩업 연산(트리에 있는 특정 노드의 위치를 알아내는 연산)을 빠르고 간단하게 처리할 수 있다. ⛔️ 순차 탐색보다 조금 더 효율적이지만, 미리 정렬이 되어있어야 한다. 순차 탐색은 O(n)의 복잡도를 가지는 반면 이진 탐색은 O(log n)이다. 코드 흐름 0,1,2,3,4,5,6,7,8 1. 중간 값 4가 root가 된다. 만약 짝수 개인 경우 더 작은 숫자를 root로 설정한다. 2. 앞 뒤로 0,1,2,3 / 5,6,7,8에서 중간 값 1, 7을 4의 자식 노드로 ..
[알고리즘] 힙 (Heap) - 최소힙, 최대힙
힙 (Heap) 최댓값이나 최솟값을 빠르게 하기 위해서 고안된 완전 이진트리(왼쪽부터 추가하는 구조)를 기본으로 한 자료구조이다. 트리 구조를 기반으로 한 구조 방식이라고 생각하면 된다. 🥇 최소힙, 최대 힙 최소 힙은 작은 값을 항상 트리의 위에 두어, root에 가장 작은 값이 온다. 그렇기에 자식의 부모 요소는 자식보다 작다. 최대 힙은 가장 큰 값을 항상 트리의 위에 두어, root에 가장 큰 값이 온다. 그렇기에 자식의 부모요소는 자식보다 크다. 🥇 최소 힙에 노드 추가하기 완전 이진트리에 맞게 맨 마지막 레벨에 왼쪽부터 노드를 추가해준다. 추가한 노드의 값과 부모 요소를 비교하여 더 작으면 자리를 바꾼다. 부모 노드보다 작도록 반복한다. 한번 돌 때마다 절반식 경우가 줄어들기에 시간 복잡도는 ..
[알고리즘] 트리 (Tree)의 종류
트리 부모 자식의 관계를 가짐 계층이 있고, 그룹이 있음 노드가 하나이상의 자식을 가지기 때문 더 이상 자식이 없는 노드를 leaf라고 부름 트리의 종류 🎄 삼항 트리, 이진트리 삼항 트리 (Ternary tree) 최대 세개의 자식을 같은 구조 이진트리 (Binary Tree) 최대 두 개의 자식을 같은 구조 🎄 이진트리, 이진 검색 트리 이진트리 (Binary Tree) 최대 두 개의 자식을 같은 구조 -> 12를 찾는다고 할 때 2 레벨에서 9가 더 커서 오른쪽으로 이동해도 찾을 수가 없다. 이진 검색 트리 (BST : Binary Search Tree) 최대 두 개의 자식을 가지는 구조 노드의 왼쪽 자식의 값이 반드시 자신의 값 이하이며, 오른쪽 자식의 값은 반드시 자신의 값 이상이다. 이진 검색..
알고리즘 공부를 위한 자료구조 알아보기 (Array, Hash Table, Stack, Queue)
자료 구조 데이터를 정리하는 것이다. 데이터를 어떻게 정리하냐(어떤 데이터 구조를 사용하냐)에 따라서 어플리케이션의 속도에 영향을 준다. 검색,읽기, 삽입, 삭제 4개가지 상황을 염두하고 데이터 구조를 보고 적절히 사용해야 한다. Array배열 reading 🟢 index값을 통해 간단히 값을 가져올 수 있다. searching 🔴 배열에서 값을 찾으려면 하나하나 체크하는 과정을 거쳐야 함으로 좋은 방법이 아니다. 이런 식으로 처음부터 끝까지 순차적으로 검색해야하는 것을 "Linear Search 선형 검색"이라고 한다. add 🟡 배열에 여분의 공간이 있을때, 맨 마지막에 값을 추가하는건 문제가 없다. 하지만 처음이나 중간에 값을 추가하거나 남아있는 공간이 없을 경우에는 기존의 값들이 이동하거나 복사까..
시간 복잡도(Big O)란 무엇인가?
코딩테스트를 준비하면서, 알고리즘에 대한 학습이 부족하다는 걸 깨닫고 공부 시작!👩🏻💻 ✔️시간 복잡도 데이터 구조의 오퍼레이션 혹은 알고리즘이 얼마나 빠르고, 느린지 측정하는 방식이다. 알고리즘의 속도 측정 방식이다. 1초, 2초와 같은 시간을 측정하는 것이 아니라, 얼마나 많은 단계(steps)가 있는가로 측정한다. 즉, 단계가 적을수록 좋은 것이다. ▪️O(N) 선형 검색의 시간 복잡도(Linear Time Complexity)는 O(N)이라고 한다. array데이터 구조에서 10개를 선형검색하면선형 검색하면 10번의 step이 실행되고, 20개를 선형 검색하면 20개의 step이 실행된다. 즉, 인풋값과 step이 비례한다. 만약 for문을 두 번 돌리면 step이 두배가 되니까 O(2N)이 되..