반응형 알고리즘/자료구조12 백준 1197번 : 최소 스패닝 트리 java 이 문제는 최소 비용 신장 트리를 만드는 문제입니다. 최소 비용 신장 트리를 만들기 위한 알고리즘에는 크루스칼 알고리즘과 프림 알고리즘이 있습니다. 크루스칼 알고리즘은 간단히 말해서 전체의 간선 중에서 가장 가중치가 낮은 간선들을 선택해서 최소 비용 신장 트리를 만드는 알고리즘입니다. 그리고 프림 알고리즘은 임의의 정점을 고른 후 그 정점에서 연결된 간선 중에서 가장 가중치가 낮은 간선을 선택하여 최소 비용 신장 트리를 만드는 알고리즘입니다. 저는 이 중에서 크루스칼 알고리즘을 이용하여 이 문제를 푸는 것을 선택하였습니다. 프림 알고리즘에 대한 설명은 아래의 링크에서 확인하실 수 있습니다. 프림 알고리즘 - 위키백과, 우리 모두의 백과사전 프림 알고리즘(Prim's algorithm)은 가중치가 있는 연.. 2022. 6. 14. 백준 17299번 : 오등큰수 java 이 문제는 스택 구조를 이용한 문제로 아래의 문제인 오큰수와 유사한 문제입니다. 이 문제를 풀기 전에 아래의 문제를 보고 오시는게 좋을 겁니다. 백준 17298번 : 오큰수 java 이 문제는 자료구조 중에서 스택을 이용하여 푸는 문제입니다. 이 문제를 풀 때 해당 인덱스의 수보다 오른쪽에 있으면서 해당 수보다 큰 수 중에서 가장 왼쪽에 있는 수를 찾으면 됩니다. 이를 dy-coding.tistory.com 이 문제에서는 수가 배열에 몇 개가 들어있냐를 기준으로 수를 집어넣습니다. 입력된 자료들을 순회하며 데이터들이 몇 개씩 있는지를 확인한 후 조건에 맞게 정답 배열을 채웁니다. 위의 그림은 위 문제의 예제 1번을 나타낸 그림입니다. data의 개수들은 count배열에 넣었습니다. 이제 stack에 da.. 2022. 6. 14. 백준 17298번 : 오큰수 java 이 문제는 자료구조 중에서 스택을 이용하여 푸는 문제입니다. 이 문제를 풀 때 해당 인덱스의 수보다 오른쪽에 있으면서 해당 수보다 큰 수 중에서 가장 왼쪽에 있는 수를 찾으면 됩니다. 이를 위해서는 입력받은 수들을 먼저 배열에 넣은 후 0번 index부터 차례대로 값을 stack에 넣습니다. 그리고 stack에 새로 들어오는 값이 이전에 있던 값보다 작다면 이전에 있던 값을 pop하지 않고 새로운 값을 add합니다. 만약 새로 들어오는 값이 이전에 있던 값보다 작다면 우리가 찾던 오큰수이므로 answer배열에 그 값을 넣어줍니다. 이 과정을 그림을 통해서 설명드리겠습니다. 예제 1번을 예시로 풀어보겠습니다. 0번 index는 stack에 비교할 값이 없기 때문에 그 값을 바로 stack에 넣어줍니다. 1.. 2022. 6. 13. 백준 11286번 : 절댓값 힙 java 이 문제는 자료구조 힙 안에 자료를 저장하고 제거하는 기능을 구현하는 문제입니다. 힙이란 완전 이진트리로 구성되어 있는 일종의 자료구조로써 자료들을 저장할 수 있게 도와줍니다. 완전 이진 트리란 왼쪽의 그림과 같이 트리가 있을 때 가장 위의 트리부터, 위 층이 다 채워지면 왼쪽부터 채우는 이진 트리를 의미합니다. 트리에서는 자료가 있는 칸을 노드라고 부릅니다. 이 그림에서 노드가 채워지는 순서는 알파벳 순입니다. 왼쪽의 그림과 같이 왼쪽에서부터 차례대로 채우지 않은 이진 트리는 완전 이진트리가 아닙니다. 힙은 보통 최대 힙, 최소 힙으로 나뉩니다. 최대 힙은 다음과 같이 가장 큰 수가 가장 위에 위치한 힙을 나타냅니다. 최대 힙에서는 새로운 자료가 들어오면 비교를 통해 자식 노드보다 부모 노드가 항상 큰.. 2022. 5. 26. 이전 1 2 다음 반응형
