반응형 분류 전체보기313 우선순위 큐(Priority Queue) 이번에 공부할 자료구조는 우선순위 큐이다. 우선순위 큐는 데이터들이 우선순위를 가지며, 우선순위가 높은 데이터가 먼저 출력된다. 또한, 스택이나 큐도 우선순위 큐를 사용하여 얼마든지 구현할 수 있다. 우선순위 큐는 배열, 연결 리스트 등의 여러 가지 방법으로 구현이 가능한데, 가장 효율적인 구조는 트리에서 언급한 힙(Heap)이다. 힙은 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료 구조이다. 힙은 일종의 반정렬 상태를 유지한다. 이를 활용하여 우선순위 큐를 구현한다. 힙은 삽입, 삭제 연산이 O(log n)의 시간 복잡도를 가질 만큼 훌륭하다. 힙은 여러 개의 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 만들어진 자료 구조이다. 간단히 말하면 부모 노드의 키값이 자식 .. 2021. 6. 30. 트리(Tree) 이전까지 공부했던 스택, 큐, 덱은 선형 자료구조라고 말한다. 트리는 선형 자료구조가 아닌 계층적인 구조를 가지는 자료구조이다. 트리는 한 개 이상의 노드로 이루어진 유한 집합이다. 이들 중 하나인 루트(Root)라는 노드를 기준으로 계층적인 구조를 유지하면서 아래로 뻗어나가는 자료구조이다. 트리의 종류에는 여러 가지가 존재하지만 이번에는 자식 노드의 개수가 최대 2개인 이진 트리를 다뤄보겠다. 이진 트리의 정의는 다음과 같다. 공집합이거나 루트와 왼쪽 서버 트리, 오른쪽 서브 트리로 구성된 노드들의 유한 집합으로 정의된다. 이진 트리의 서브 트리들은 모두 이진트리여야 한다. 이진 트리는 형태에 따라 다음과 같이 분류할 수 있다. 포화 이진 트리 : 트리의 각 레벨에 노드가 꽉 차 있는 이진 트리 완전.. 2021. 6. 30. 덱(Deque) 덱(Deque)은 double-ended queue의 줄임말로서 큐의 전단(Front)과 후단(Rear)에서 모두 삽입과 삭제가 가능한 큐를 의미한다. 스택(Stack)과 큐(Queue), 2개의 자료구조를 덱(Deque)을 활용하여 구현 및 사용할 수 있다. 전단 삽입(add_front), 삭제(delete_front), 후단 삽입(add_rear), 삭제(delete_rear) 총 4 가지 기본 연산을 가지고 있다. 덱(Deque)은 큐(Queue)를 업그레이드한 자료구조로써 JAVA에선 큐(Queue)처럼 간단하게 라이브러리를 추가하여 별다른 구현 없이 생성할 수 있다. import java.util.Deque; import java.util.LinkedList; Deque "덱 이름" = new .. 2021. 6. 29. 큐(Queue) : FIFO 큐(Queue)는 선입 선출(FIFO : First-In First-Out)의 형식으로 입출력이 일어나는 자료구조이다. 앞서 설명한 스택(Stack)은 동일한 위치에서 삽입, 삭제 연산이 수행되는 반면, 큐(Queue)는 삽입, 삭제 연산이 서로 다른 위치에서 수행된다. 삽입이 일어나는 곳을 후단(Rear)이라고 하고, 삭제가 일어나는 곳을 전단(Front)이라고 한다. 스택(Stack)처럼 삽입(Enqueue), 삭제(Dequeue) 2가지 기본 연산을 가지고 있다. JAVA에선 간단하게 라이브러리를 추가하여 별다른 구현 없이 사용할 수 있으나 일반적으로 LinkedList로 생성한다. import java.util.Queue; import java.util.LinkedList; Queue "큐 이름".. 2021. 6. 29. 스택(Stack) : LIFO 스택(Stack)은 후입 선출(LIFO : Last-In First-Out)의 형식으로 입출력이 일어나는 자료구조이다. 가장 최근에 입력되었던 자료의 위치를 Top이라는 변수로 가리키도록 하여 모든 연산에 활용한다. 스택은 삽입(Push), 삭제(Pop) 2가지 기본 연산을 가지고 있다. JAVA에선 간단하게 라이브러리를 추가하여 별다른 구현 없이 사용할 수 있다. import java.util.Stack; Stack "스택 이름" = new Stack(); 스택(Stack)은 선형 자료구조로써 배열, 연결 리스트를 이용하여 구현할 수 있다. 배열로 구현하는 방법은 스택의 크기가 고정되는 단점이 있지만 구현이 쉽고, 데이터 접근이 빠르다. 반면, 연결 리스트로 구현하는 방법은 구현이 약간 복잡한 반면, .. 2021. 6. 29. 백준 1593 : 문자 해독 https://www.acmicpc.net/problem/1593 1593번: 문자 해독 첫째 줄에 고고학자들이 찾고자 하는 단어 W의 길이 g와 발굴된 벽화에서 추출한 문자열 S의 길이 |S|가 빈 칸을 사이에 두고 주어진다. (1≤g≤3000, g≤|S|≤3,000,000) 둘째 줄에 W, 셋째 줄에 S의 실 www.acmicpc.net [ 문제풀이 ] W의 길이가 최대 3000이기 때문에 W의 문자들로 만들 수 있는 모든 순열을 생성 후 검사한다면 시간초과가 발생하게 된다.검사해야하는 문자열의 길이는 고정이기 때문에 슬라이딩 윈도우 기법을 사용하여 구간을 검사해나가면 된다. import java.io.BufferedReader; import java.io.BufferedWriter; import j.. 2021. 6. 29. [Java] final, finally, finalize Java에는 final 접두사가 들어가는 final, finally, finalize, 3가지 용어가 존재한다. 비슷한 이름 때문에 헷갈릴 수도 있는 이들에 대해서 한번 정리해보도록 하자. final final은 변경이 불가능하도록 해주는 기능으로 변수, 메서드, 클래스에 적용할 수 있다. 각 영역에 적용하면 다음과 같은 특징을 가지게 된다. finally finally는 try-catch 블록에 사용되는 문법으로 무조건 실행되는 블록을 정의해 주는 기능이다. try-catch 블록은 try 문을 실행하다가 Exception이 발생하게 되면 즉시 catch 문이 실행되기 때문에 남은 try 문은 실행될 수 없다. BufferedReader br = null; try { br = new Buffered.. 2021. 6. 29. 이전 1 ··· 32 33 34 35 다음 반응형
