Scat

yongmin's dev blog

[BOJ] 1197번 최소 스패닝 트리 - C++

"최소 신장 트리"

문제 최소 스패닝 거리 풀이 최소 신장 트리를 형성하는 알고리즘에는 크게 두 가지가 있다. 크루스칼(Kruscal) 알고리즘과 프림(Prim) 알고리즘이 있다. 크루스칼 알고리즘은 그리디 알고리즘에 속해있다. 먼저, 간선의 가중치들을 오름차순으로 sort를 한다. 그 이후, 작은 것부터 차례대로 간선을 union, 집합을 형성한다. 만약 이 때,...

Posted by Yongmin on August 24, 2021

[BOJ] 20040번 사이클 게임 - C++

"유니온 파인드"

문제 사이클 게임 풀이 기본적인 union find구현을 기본으로 한다. 새로운 testcase가 있을 때마다 union find로 집합을 만드는 것을 시도한다. 이 때, 이미 그 숫자들의 root가 같다면, 이 두개를 연결하면 사이클이 형성되므로 iteration의 숫자, 즉 몇번째인지를 출력한다. m개의 testcase를 통과했다면 사이클이 형...

Posted by Yongmin on August 23, 2021

[BOJ] 4195번 친구 네트워크 - C++

"유니온 파인드"

문제 친구 네트워크 풀이 문자열로 된 집합들을 union & find하는 문제이다. 문자열로 된 것들을 map<string, int> testcase로 선언한 map에 key와 value로 나타난 순서대로 labelling을 해주었다. 그 이후는 기본적인 union find와 같은 맥락이다. 사이즈를 비교하여 작은 것이 큰 것으...

Posted by Yongmin on August 23, 2021

[BOJ] 1976번 여행 가자 - C++

"유니온 파인드"

문제 여행 가자 풀이 기본 union-find에서 크게 다르지 않은 문제이다. union-find를 이용하여 길 간의 합집합을 하고, 가고자 하는 경로 중 집합이 다른 root를 갖는 경로가 존재하면 NO를 출력하게끔 한다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 2...

Posted by Yongmin on August 23, 2021

[BOJ] 1717번 집합의 표현 - C++

"유니온 파인드"

문제 집합의 표현 풀이 유니온 파인드(Union find) 자료구조에 대한 문제이다. union(두 집합을 하나로 합치는 연산), find(원소가 속한 집합을 반환)하는 자료구조이다. find에서는 parent배열을 통하여 부모 노드를 계속해서 재귀함수 호출을 이용하여 찾아내 root가 뭔지를 확인한다. 만약 root가 같다면 그 두 원소는 같은 ...

Posted by Yongmin on August 23, 2021

[BOJ] 4803번 트리 - C++

"트리"

문제 트리 풀이 트리인지 확인하는 문제이다. 즉, 싸이클이 없는지 있는지를 체크하는 문제가 되겠다. 기존의 dfs를 이용하여 탐색하되, 돌아가는 경로가 있는지를 확인하기 위해서 그 전 node를 포함한채로 재귀를 진행했다. 만약 다음에 갈 곳과 그 전에 간 곳이 일치한다면 다시 역방향으로 가는 케이스이므로 무시해준다. 또 만약, 방문한 곳이 이미 ...

Posted by Yongmin on August 19, 2021

[BOJ] 5639번 이진 검색 트리 - C++

"트리"

문제 이진 검색 트리 풀이 preorder가 주어졌을 때, postorder를 구하는 코드이다. while(scanf("%d", &input) != -1)를 통해 입력의 갯수, 입력의 마지막 제한이 없는 입력을 받았다. preorder의 root는 맨 앞에 위치해있으며, root보다 큰 수가 나오기 직전 까지 왼쪽 루트에 해당하고 그 이후부...

Posted by Yongmin on August 19, 2021

[BOJ] 2263번 트리의 순회 - C++

"트리"

문제 트리의 순회 풀이 inorder, postorder가 주어졌을 때, preorder를 출력하는 문제이다. postorder의 끝 값이 항상 최상단 root가 되고 inorder에서는 그 root값 왼쪽은 왼쪽 자식, 오른쪽은 오른쪽 자식으로 만들 수 있다. 원리를 토대로 postorder에서 맨끝값을 찾아내고, inorder에서 그 root ...

Posted by Yongmin on August 19, 2021

[BOJ] 1991번 트리 순회 - C++

"트리"

문제 트리 순회 풀이 preorder, postorder, inorder 트리 순회를 출력하는 문제이다. preorder란 루트-왼쪽-오른쪽, inorder란 왼쪽-루트-오른쪽, postorder란 왼쪽-오른쪽-루트로 순회하는 트리를 의미한다. dfs에서 각자의 출력에 맞게 printf 배치하여 정답을 출력한다. 소스 코드 1 2 3 4 5 6...

Posted by Yongmin on August 18, 2021

[BOJ] 1167번 트리의 지름 - C++

"트리"

문제 트리의 지름 풀이 트리의 지름은 어떤 정점에서 다른 정점까지 최대 거리를 의미한다. 지름을 찾기 위한 알고리즘은 어떤 임의의 정점에서 최대 거리로 떨어진 정점을 찾고, 한번 더 최대 거리 떨어진 정점에서 시작하여 최대 거리로 떨어진 다른 정점을 찾아서 그 거리가 곧 트리의 지름이 된다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11...

Posted by Yongmin on August 18, 2021

FEATURED TAGS
Format BOJ C++ Python Algorithm
ABOUT ME

짱구