알고리즘 검색 결과
8 개의 검색 결과가 있습니다.
알고리즘

[BOJ 3584번] 가장 가까운 공통 조상 Tree 구조에서 찾아보기- Java

문제 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 노드를 모두 자손으로 가지면서 깊이가 가장 깊은(즉 두 노드에 가장 가까운) 노드를 말합니다. 예를 들어 15와 11를 모두 자손으로 갖는 노드는 4와 8이 있지만, 그 중 깊이가 가장 깊은(15와 11에 가장 가까운) 노드는 4 이므로 가장 가까운 공통 조상은 4가 됩니다. 루트가 있는 트리가 주어지고, 두 노드가 주어질 때 그 두 노드의 가장 가까운 공통 조상을 찾는 프로그램을 작성하세요 입력 첫 줄에 테스트 케이스의 개수 T가 주어집니다. 각 테스트 케이스마다, ..

2021. 8. 31. 20:42
알고리즘

Prim 알고리즘 자바로 구현 (백준 1197번)

2021.08.30 - [알고리즘] - Minimum Spanning Tree를 구현하는 Prim 알고리즘에 대해 Minimum Spanning Tree를 구현하는 Prim 알고리즘에 대해 Minimum Spanning Tree와 Prim 알고리즘에 대해 설명하기 전, 먼저 Spanning Tree의 정의부터 살펴보자. Spanning Tree란 그래프 중 모든 정점이 간선으로 연결되어 있고 간선 간의 싸이클이 없는 그래프를 의미 lemonlemon.tistory.com 저번 포스팅에서 프림 알고리즘에 대해 다루었다. 그래프로 설명하면 어렵지 않지만 이를 자바 코드로는 어떻게 구현할 수 있을까? 참고로 Minimum spanning tree를 코드로 구현하는 문제를 풀고 싶다면 백준 1197번을 참고하면..

2021. 8. 30. 15:21
알고리즘

Minimum Spanning Tree를 구현하는 Prim 알고리즘에 대해

Minimum Spanning Tree와 Prim 알고리즘에 대해 설명하기 전, 먼저 Spanning Tree의 정의부터 살펴보자. Spanning Tree란 그래프 중 모든 정점이 간선으로 연결되어 있고 간선 간의 싸이클이 없는 그래프를 의미한다. 여기 앞에 Minimum이 붙으면 각 간선간의 weight의 총합이 최소가 되게 연결이 되는 그래프를 뜻하는 것이다. 즉, 모든 vertex가 다 연결되도록 spanning tree를 만드는 방식이 여러 개가 있을 때 그 중 간선의 합들이 최소가 되도록 연결하는 것을 의미한다. 즉 위와 같은 그래프에서는 Minimum Spanning Tree는 아래와 같은 모양이다. 연결하는 다른 방법도 있지만 위와 같이 연결하면 총 weight가 최소가 된다. 그렇다면 위..

2021. 8. 30. 15:09
알고리즘

[백준] 11058번: 크리보드 문제 다이나믹 프로그래밍으로 풀기

www.acmicpc.net/problem/11058 11058번: 크리보드 N = 3인 경우에 A, A, A를 눌러 A 3개를 출력할 수 있다. N = 7인 경우에는 A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V를 눌러 9개를 출력할 수 있다. N = 11인 경우에는 A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V, Ctrl-A, Ctrl-C, Ctrl www.acmicpc.net 문제 크리보드는 kriii가 만든 신기한 키보드이다. 크리보드에는 버튼이 4개만 있으며, 하는 역할은 다음과 같다. 화면에 A를 출력한다. Ctrl-A: 화면을 전체 선택한다 Ctrl-C: 전체 선택한 내용을 버퍼에 복사한다 Ctrl-V: 버퍼가 비어있지 않은 경우에는 화면에 ..

2021. 4. 29. 14:07
알고리즘

[백준] 11066번 파일합치기 다이나믹 프로그래밍으로 풀어보기

www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net 문제 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본이 들어있는 한 개의 파일을 만든다. 이 과정에서 두 개의 파일을 합쳐서 하나의 임시파일을 만들고, 이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고..

2021. 4. 27. 17:53
알고리즘

[백준] 11060번 점프 점프 문제 2가지 방법으로 풀어보기

www.acmicpc.net/problem/11060 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 www.acmicpc.net 문제 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 떨어진 칸으로 한 번에 점프할 수 있다. 예를 들어, 3번째 칸에 쓰여 있는 수가 3이면, 재환이는 4, 5, 6번 칸 중 하나로 점프할 수 있다. 재환이는 지금 미로의 가장 왼쪽 끝에 있고, 가..

2021. 4. 27. 15:18
알고리즘

Union-Find의 시간복잡도

Union-Find를 구현하는 방식에는 두 가지가 있다. 첫 번째는 linked list를 활용하여 구현하는 방식이고, 두 번째 방식은 우리가 일반적으로 알고 있는, Tree를 사용해서 구현하는 방식이다. 각각에 대하여 시간복잡도가 다르기 때문에 두 경우로 나누어서 분석해보겠다. 모든 경우에 대해서 총 m개의 연산 (make, find, union)이 가능하고, make-set의 개수 (=원소의 개수)는 n개라고 가정하에 시간복잡도를 계산해보겠다. 1. Linked List를 활용하는 경우 : O(m+ nlogn) 이 경우에는 시간복잡도가 O(m +nlogn)이라고 알려져있다. 직관적으로 설명한다면 linked list의 경우 길이가 짧은 linked list를 길이가 긴 linked list에 붙이는 ..

2021. 4. 20. 01:06
알고리즘

Red-Black Tree 속성/검색/삽입/삭제

이진트리 중 Binary Search Tree인 경우에는 한쪽에만 노드들이 치우쳐 있어 균형잡힌 트리가 만들어지지 않을 수 있다. 그렇다면 탐색을 하기 위한 시간이 늘어나게 되는 단점이 있는데, 이를 보완하여 균형잡힌 트리를 만들고자 만들어진 자료구조가 Red-Black Tree라는 것이다. Red-Black Tree는 각 노드의 색깔을 red, black 중에 선택하여, 주어진 조건을 만족시켰을 때 성립하는 Tree이다. Red-Black Tree의 성립조건은 다음과 같다. 루트 노드는 언제나 Black이다. Leaf 노드 (말단 노드) 또한 언제나 Black이다. 만약 노드가 Red라면, 그 노드의 자식들은 언제나 Black이다. 즉, red node가 연속으로 올 수 없다. 루트에서 말단 노드까지의..

2021. 4. 17. 13:55