Cycle
-
[백준 BOJ/C++] 4803 트리알고리즘, 코딩테스트/알고리즘 문제풀이 2023. 10. 10. 00:54
4803번: 트리 기본적인 사이클 탐지 알고리즘 문제다. 그래프(Graph) 내에서 사이클(Cycle) 이 존재하는지를 찾는 문제는 흔한 그래프 탐색 문제 유형 중 하나다. 이 문제에서는 트리(Tree) 의 정의를 이용해서 주어진 그래프 내에서 사이클이 존재하는지 확인하고 사이클을 이루는 노드들에 연결되지 않은 트리의 수를 찾아야 한다. 트리는 그래프의 한 종류로 그래프가 트리가 되기 위해서는 몇가지 조건이 있지만 이 문제에서는 사이클만 신경써주면 된다. 문제에서 입력 자체가 두 노드 사이에 간선은 하나만 주어지고 간선에 가중치가 있는것도 아니기 때문에 사이클의 존재 여부로만 트리인지 아닌지 판단할 수 있다. 단, 주의해야하는 점은 예제로 주어진 입력과 같이 주어지는 간선정보에 포함되지 않은, 다른 노드..
-
[백준 BOJ/C++] 2668 숫자 고르기알고리즘, 코딩테스트/알고리즘 문제풀이 2023. 10. 3. 00:55
2668번: 숫자 고르기 문제를 처음 접하면 아이디어가 잘 떠오르지 않는 어려운 문제이기도 하지만 막상 제대로 파악하고 나면 의외로 간단히 풀 수 있는 문제다. 그래프(Graph)와 관련된 문제이고 사이클(Cycle)을 찾는 문제임을 발견하기만 한다면 그 이후부터는 크게 까다로울 것은 없다. 문제는 정체를 알 수 없는 표가 주어지고 여기에서 집합을 찾는다는 표현으로 접근 방법을 어렵게하고 있다. 이 문제의 핵심은 바로 이 표가 그래프로 나타내어질 수 있음을 발견하는 것 그리고 찾고자 하는 집합의 조건이 그래프에서 사이클을 형성하는 노드들임을 발견하는 것이다. 대놓고 그래프 문제임을 보여주거나 연결과 탐색, 경로와 같이 큰 고민 없이 그래프로 연상할 수 있는 키워드를 사용하는 문제들도 많지만 이렇게 특이한..