본문 바로가기

알고리즘57

[ 알고리즘 ] 우선순위 큐 (2) - 힙 @ 궁금증 배열로 구현한 우선순위 큐가 너무 비효율적이라서 트리를 통해서 구현하는 방법을 공부해 보자 @ 공부 ## 자료구조 힙 힙 이란? 부모의 값이 항상 자식보다 작은 완전 이진 트리 - 즉 부모일수록 우선 순위가 높다. 루트에 있는 값은 가장 우선 순위가 높은 값이 된다. ( 현재 예제에서는 숫자가 낮을 수록 우선 순위가 높은 것입니다. ) 1) 추가 2) 제거는 어떻게 하는가? ## 완전 이진 트리 ( 높이 ) - 완전 이진 트리란? 이진 트리(binary tree)란 한 노드가 최대 두 개의 자식 노드를 가지는 트리를 뜻한다. 보통 첫 번째 노드를 부모 노드라고 하며 자식 노드는 왼쪽(left)과 오른쪽(right)으로 불린다. 이진 트리는 이진 탐색 트리 와 이진 힙의 구현에 흔히 쓰인다. -.. 2019. 9. 20.
[ 알고리즘 ] 우선순위 큐 (1) - 배열 @ 왜 궁금했는가? 요즘 알고리즘 공부하는데,, 우선순위 큐 문제가 자주 출제 되서 한번 정리하고 싶은 생각에 !!! @ 공부 우선 순위 큐란? - 큐 자제가 들어간 순서대로 나오는것인데 우선순위 큐는 값에 따라서 가장 큰 우선순위인 값이 나온다. 예) 일반 큐 (2)-(3)-(4)-(5) : pop() 하면 2가 나온다. 우선 순위 큐 (2)-(3)-(4)-(5) : pop() 하면 5가 나온다. @ 구현 ## 배열로 구현 4 5 3 2 1 pop : 5 4 [ ] 3 2 1 앞 공간 채워 줘야 한다. 4 3 2 1 Push: O(1) Pop: O(n) > 누가 우선 순위가 가장 큰지 확인하고 다 땡겨 주는데 O(2N) 이므로 O(N) 이 됩니다. - 구현 public class PriorotyQue .. 2019. 9. 19.
[ 알고리즘 ] 트리 @ 왜 궁금해 졌나? 카카오 문제를 풀다 보니까 생각보다 기초적인 부분에서 문제가 많다는 것을 알게 되었다. 그래서 트리, 그래프, 등, 기초적인 것부터 자바로 어떻게 짜는지 공부를 하기 위해서 적게 되었다. @ 공부 ## 트리 만들기 ## 트리 관련 알고리즘 ## 순회 전위 순회(preorder traverse) : 뿌리(root)를 먼저 방문 ⊙ 중위 순회(inorder traverse) : 왼쪽 하위 트리를 방문 후 뿌리(root)를 방문 ⊙ 후위 순회(postorder traverse) : 하위 트리 모두 방문 후 뿌리(root)를 방문 ⊙ 층별 순회(level order traverse) : 위 쪽 node들 부터 아래방향으로 차례로 방문 위와 같은 트리가 있다고 한다면 각각 순회방법은 다음과 .. 2019. 9. 5.
[ 알고리즘 ] 2중 배열안에서 같은 수 찾기 ( 3중 for ) @ 카카오 후보키 문제 package sol4; import java.util.LinkedList; import java.util.List; public class Main { public static void main(String[] args) { Solution sol = new Solution(); String [][] a = {{"100","ryan","music","2"},{"200","apeach","math","2"},{"300","tube","computer","3"},{"400","con","computer","4"},{"500","muzi","music","3"},{"600","apeach","music","2"}}; int result = sol.solution(a); System.o.. 2019. 9. 4.

티스토리툴바