본문 바로가기

전체 글215

백준 2075: N번째 큰 수(java) 문제풀이 우선순위 큐를 이용하면 쉽게 풀 수 있다. N*N개의 수를 모두 우선순위 큐에 삽입하고 (N-1)개의 요소를 삭제한 뒤 N번째 요소를 출력하면 된다.N번째로 큰 수를 출력해야 하므로 최대 우선순위 큐를 사용하고, 이를 위해 PriorityQueue 객체 생성 시 Comparator.reverseOrder()를 지정해야 함에 주의하자. 전체 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Comparator;import java.util.PriorityQueue;import java.util.StringTokenizer;public class Main .. 2024. 8. 24.
백준 11279: 최대 힙(java) 문제풀이 최대 우선순위 큐를 이용하는 문제이다. PriorityQueue 객체 생성 시 내림차순 정렬하는 것을 제외하면 1927번 문제와 풀이 방식이 동일하다. 내림차순 정렬을 위해 Comparator.reverseOrder()을 사용한다.PriorityQueue queue=new PriorityQueue(Comparator.reverseOrder()); 전체 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Comparator;import java.util.PriorityQueue;public class Main { public static void main(.. 2024. 8. 24.
백준 1927: 최소 힙(java) 문제풀이 우선순위 큐(priority queue)를 이용하는 문제다. 배열에서 가장 작은 수를 출력해야 하므로 최소 우선순위 큐를 사용한다. PriorityQueue 클래스를 이용하면 별도의 큐 구현 과정 없이 간단하게 풀이할 수 있다. PriorityQueue 객체에서 요소를 poll하면 자동으로 가장 작은 값이 반환되므로, N만큼 반복하며 0이 입력되면 poll하고 아니라면 offer해주기만 하면 끝난다. 전체 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.PriorityQueue;public class Main { public static void ma.. 2024. 8. 24.
히프 히프(heap) 개념- 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 이진 트리- 여러 개의 값들 중 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 만들어진 자료 구조- 히프 트리에서는 중복된 값을 허용(완전 이진 트리에서는 허용 x)- "느슨한 정렬 상태 유지": 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있는 정도- 삭제 연산마다 가장 큰 값을 찾아내기만 하면 되므로 완전히 정렬할 필요 x- 히프는 완전 이진 트리히프의 종류- 2가지의 히프 트리 존재 1. 최대 히프(max heap)- 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리- key(부모 노드) ≥ key(자식 노드) 2. 최소 히프(min heap)- 부모 노드의 키 값이 자식 노드의 키 값보다 .. 2024. 8. 24.
우선순위 큐의 구현 배열을 사용하는 방법 1. 정렬되지 않은 배열 사용- 배열의 맨 끝에 새로운 요소를 추가- 삽입 시의 시간 복잡도는 O(1)- 삭제 시 우선 순위가 가장 높은 요소를 찾아야 함- 정렬되어 있지 않으므로 배열의 처음부터 끝까지 모든 요소를 스캔- 삭제 시의 시간 복잡도는 O(n) - 요소 삭제 후, 삭제된 요소 뒤에 있는 요소들을 앞으로 이동시켜야 함 2. 정렬된 배열 사용- 요소 삽입 시, 다른 요소와 값을 비교하여 적절한 삽입 위치를 결정- 삽입 위치 뒤의 요소들을 이동시켜 빈자리를 만든 다음 삽입- 삽입 시의 시간 복잡도는 O(n)- 삭제 시 맨 앞 또는 맨 뒤의 요소를 삭제하면 됨- 삭제의 시간 복잡도는 O(1)연결 리스트를 사용하는 방법- 배열을 사용한 방법과 유사 1. 정렬되지 않은 연결 리스트.. 2024. 8. 24.
우선순위 큐 우선순위 큐- 보통의 큐는 선입 선출(FIFO)의 원칙에 의하여 먼저 들어온 데이터가 먼저 나가게 됨- 우선순위 큐는 데이터들이 우선 순위를 가지고 있고, 우선 순위가 높은 데이터가 먼저 나가게 됨- 적절한 우선 순위를 부여하여 우선순위 큐를 스택이나 큐로 사용할 수 있음- 우선순위 큐는 0개 이상의 요소의 모임- 각 요소들은 우선 순위 값을 가지고 있음- 우선순위 큐는 최소 우선순위 큐와 최대 우선순위 큐로 나뉨최소 우선순위 큐: 우선 순위가 낮은 요소를 먼저 삭제최대 우선순위 큐: 우선 순위가 높은 요소를 먼저 삭제 2024. 8. 24.
이진 탐색 트리 이진 탐색 트리의 정의모든 원소는 유일한 키를 가짐왼쪽 서브 트리의 키들은 루트 키보다 작음오른쪽 서브 트리의 키들은 루트 키보다 큼왼쪽과 오른쪽 서브 트리 또한 이진 탐색 트리 - 찾아야 하는 값과 루트 노드의 값을 비교하여 탐색을 효율적으로 수행할 수 있음- 이진 탐색 트리에서 탐색을 구현하는 방법으로는 순환적인 방법과 반복적인 방법 2가지가 존재순환적인 탐색 연산- 특정한 키 값을 가진 노드를 찾기 위해 주어진 값과 루트 노드의 키 값을 비교- 이 결과는 아래의 3가지로 나뉨주어진 키 값과 루트 노드의 키 값이 같을 경우: 탐색 종료주어진 키 값이 루트 노드의 키 값보다 작을 경우: 루트 노드의 왼쪽 서브 트리에 대해 다시 탐색주어진 키 값이 루트 노드의 키 값보다 클 경우: 루트 노드의 오른쪽 서.. 2024. 8. 23.
백준 1966: 프린터 큐(java) 문제풀이LinkedList를 이용해 프린터를 표현했다.LinkedList list=new LinkedList(); list의 요소는 int형 1차원 배열로 하여 아래와 같이 문서의 인덱스와 중요도를 저장한다.N과 M을 입력받고, for문을 이용하여 list에 값을 넣으면 아래와 같은 초기 상태를 완성할 수 있다.for(int j=0; j 현재 문서보다 중요도가 높은 문서가 하나라도 있다면 그 문서를 먼저 출력해야 하므로, 인덱스가 0일 때부터 1씩 증가시키며 비교해야 한다. int[] current=list.poll();boolean isMax=true;우선 현재 문서를 저장할 int형 current 배열과 현재 문서의 중요도가 최대인지를 나타내는 boolean형 변수 isMax를 선언한다. curren.. 2024. 8. 23.
백준 11047: 동전 0(java) 문제풀이 동전의 개수가 최소가 되려면, 가치가 큰 동전이 최대한 많이 포함되어야 한다. 입력받은 동전의 가치가 K보다 클 경우 사용할 수 없으므로, 가치가 K 이하인 동전들만 염두에 두고 풀이한다.List list=new ArrayList();for(int i=0; i고려할 동전의 개수를 알지 못해 가변적 크기의 컨테이너가 필요해 배열이 아닌 컬렉션을 사용한다. 이후 Collections.sort()를 이용해 동전들을 정렬해야 하므로 List형 컬렉션 list를 선언했다.Collections.sort(list);int count=0;for(int i=list.size()-1; i>=0; i--) { int num=list.get(i); count+=K/num; K%=num;}list를 오름차순으로 .. 2024. 8. 20.
백준 14244: 트리 만들기(java) 문제풀이 정점 0의 레벨을 1이라 하자. 정점 0은 무조건 정점 1과만 연결된 리프여야 하고, 최하위 (m-1)개의 정점들은 모두 바로 위 정점과 연결된 리프이므로 레벨 (n-m-1)까지의 정점들은 바로 다음 정점과만 연결된다.for문을 사용해 위 내용을 그대로 구현하면 된다. 위 방식으로 풀었을 때 예제 4가 예시 출력과 다르게 출력됐는데, 정답으로 채점되기는 한다. 전체 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { public static void main(String[] args) thr.. 2024. 8. 20.

티스토리툴바