본문 바로가기

분류 전체보기215

이진 탐색 트리 이진 탐색 트리의 정의모든 원소는 유일한 키를 가짐왼쪽 서브 트리의 키들은 루트 키보다 작음오른쪽 서브 트리의 키들은 루트 키보다 큼왼쪽과 오른쪽 서브 트리 또한 이진 탐색 트리 - 찾아야 하는 값과 루트 노드의 값을 비교하여 탐색을 효율적으로 수행할 수 있음- 이진 탐색 트리에서 탐색을 구현하는 방법으로는 순환적인 방법과 반복적인 방법 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.
백준 9372: 상근이의 여행(java) 문제풀이 신창 트리를 이용하면 간단히 풀이할 수 있다. 신장 트리(spanning tree)란 그래프 내의 모든 정점을 포함하는 트리로, 모든 정점들이 연결되어 있어야 하고 사이클을 포함하지 않는다. 그래프에 n개의 정점이 있을 때, 이들을 (n-1)개의 간선으로 연결하는 것이다. 신장 트리는 그래프의 최소 연결 부분 그래프가 되는데, 이때 '최소'는 간선의 수가 가장 적음을 의미한다. n개의 정점을 가지는 그래프는 최소한 (n-1)개의 간선을 가져야 하며, (n-1)개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 되고 이것이 바로 신장 트리이다.  상근이는 국가를 방문하고자 하므로, 각 국가를 정점으로 생각한다면 M이나 a, b 쌍을 고려할 필요 없이 (N-1)을 출력함으로써 풀 수 있는 문제이다.. 2024. 8. 19.
스레드 이진 트리 스레드 이진 트리(threaded binary tree)- 함수를 호출해야 하므로 비효율적인 순환 호출 대신 스레드 이진 트리 사용 가능- 스택 사용 x - 트리의 노드 개수가 n개일 때- 총 링크의 개수는 2n개(각 노드 당 2개의 링크가 있으므로)- NULL이 아닌 링크의 개수는 (n-1)개- NULL인 링크의 개수는 (n+1)개 - 중위 순회 시 NULL 링크에 스레드를 저장- 선행 노드인 중위 선행자(inorder predecessor)나 후속 노드인 중위 후속자(inorder successor)를 저장해 놓은 트리가 스레드 이진 트리- 스레드를 이용하여 노드들을 순회 순서대로 연결- NULL 링크에 스레드가 저장되면, 링크에 자식을 가리키는 포인트가 저장되어 있는지 NULL 대신 스레드가 저장되.. 2024. 8. 19.

티스토리툴바