분류 전체보기45 [BOJ] [JAVA] 11003번 최소값 찾기 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net 슬라이딩 원도우를 이용하여 풀려고 했으나 내가 계속 시도했던 방식은 최소값이 빠져나가면 다시 큐의 최소값을 찾는 방식이었기 때문에 시간 초과가 되었다. 큐에 배열을 넣고 푸는 방식으로 다시 풀었다. 며칠 전에 배웠던 모노 스택 개념과 유사하다고 느꼈다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import j.. 2024. 2. 10. [알고리즘] [11] 트리 탐색 1. Breadth First Search 너비 우선 탐색은 인접 노드를 차례로 방문한 후 방문한 노드를 기준으로 하여 다시 해당 노드의 인접 노드를 차례로 방문하는 방식이다. 인접 노드를 탐색 후 다시 너비 우선 탐색을 진행하므로 선입선출 자료구조인 큐를 활용한다. 2. Depth First Search 깊이 우선 탐색은 루트 노드에서 출발하여 한 방향으로 경로가 있는 곳까지 탐색한 후 더 이상 갈 곳이 없을 때 가장 마지막에 만났던 갈림길 간선이 있는 노드로 되돌아와 다른 방향의 노드 탐색을 반복하는 순회 방법이다. 재귀적으로 구현하거나 후입선출 자료구조인 스택을 활용한다. 3. 이진트리 순회 (traversal) 전위 순회 (preorder traversal) : 부모 노드 방문 후 자식 노드를 좌.. 2024. 2. 7. [BOJ] [JAVA] 1167번 트리의 지름 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 트리의 지름을 구하는 방식이 재밌다. 임의의 한 노드에서 가장 멀리 떨어진 노드를 찾는다. 찾은 노드에서 가장 멀리 떨어진 노드를 찾으면 이 두 노드 사이의 거리가 트리의 지름이 된다. 트리라고 해서 부모와 자식 관계를 자꾸 떠올려서 이상한 방향으로 계속 생각했는데 트리도 결국 그래프이므로 인접한 노드를 방문한다는 아이디어를 가지고 가야 했다. import java.io.BufferedReader; import java.io.IOException.. 2024. 2. 7. [알고리즘] [10] 트리 1. 트리(Tree) 비선형 자료구조 원소들 간 관계가 일대다인 계층형 자료구조 노드 (Node)는 트리의 원소이며, 최상위 노드를 루트 (root)라고 한다. 노드에 연결된 나머지 노드들은 각각 하나의 트리로 묶이며(재귀적 정의) 이를 부트리 (subtree)라 한다. 트리 용어 형제 노드 (sibling node) : 같은 부모를 가지는 자식 노드들 조상 노드 : 간선을 따라 루트 노드까지 이르는 경로의 모든 노드들 서브 트리 (subtree) : 부모 노드와의 간선을 끊었을 때 생기는 새로운 트리 자손 노드 : 서브 트리에 있는 하위 노드들 차수 (degree) >> 노드의 차수 : 노드에 연결된 자식 노드 수 >> 트리의 차수 : 트리에 있는 노드 차수 중 가장 큰 값 >> 단말 노드 (리프 노드.. 2024. 2. 6. 이전 1 2 3 4 5 6 7 ··· 12 다음
