본문 바로가기

Programming456

[C/C++] 백준 #1991 트리순회(깊이 우선 탐색) 트리를 순회하는 방법은 크게 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS)가 있습니다. 깊이 우선 탐색은 스택(또는 재귀호출)을 이용하고 너비 우선 탐색은 큐를 사용하죠. 그런데, 깊이 우선 탐색의 경우에는 방문을 했다는 표시를 하는 방법에 따라서 전위(pre), 중위(in), 후위(post) 탐색으로 나눌 수 있습니다. 이번문제는 깊이 우선 탐색에서 전위, 중위, 후위 탐색의 결과를 출력하는 것입니다. 이 세가지 방법은 사실 기본적으로 호출하는 것은 똑같지만, 언제 방문 여부를 표시하는가에 따라서 다를 뿐입니다. 각각의 탐색 방법에 따라 함수를 따로 만드는 것이 시간상으로 더 효율적이겠지만, 저는 하나의 함수로 작성해보았습니다. 이 방법이 좋다는 것은 아니지만, 세가지 탐색 방법을 알아보기 좋게 .. 2023. 1. 13.
[C/C++] 백준 #1987 알파벳(깊이 우선 탐색) 이번 문제는 깊이 우선 탐색(DFS)를 이용해서 풀었습니다. 백트랙킹과도 같은 기법이긴 합니다. 백트랙킹 자체가 깊이 우선 탐색을 이용하여 푸는 것인만큼 딱히 구분을 지을 필요는 없어보입니다. 갈 수 있는 길이냐 아니냐를 따지기 위해서는 알파벳 마스크(Alphabet mask)를 사용합니다. 일반적인 깊이 우선 탐색은 방문했는지 여부를 따지게 되는 것과는 다릅니다. 알파벳은 오직 한번만 지나갈 수 있기 때문에, 이미 지나온 자리는 다시 방문할 수가 없습니다. 다음으로는 가장 짧은 경로가 아니라 가장 긴 경로를 찾는 것이기 때문에 모든 경로를 다 살펴보아야 합니다. 그러다보면 꽤 많은 경로를 검색하게 됩니다. 문제에서 행과 열의 개수가 상당히 적기 때문에 (\( 1 \ge R,~C \ge 20\)), 깊이.. 2023. 1. 12.
[C/C++] 백준 #1981 배열에서 이동(이분탐색) 이번 문제는 보통의 그래프 문제와 다르게 경로상의 최저값과 최고값의 차이가 가장 적게 나오는 경로에서의 그 차이를 출력하는 문제입니다. 최저값과 최고값의 차이를 가지고 다루는 문제이기 때문에 다익스트라 알고리즘과 같은 탐욕 알고리즘 기반을 사용할 수가 없습니다. 제가 접근한 방법은 최고값과 최저값의 차이를 주어지고, 깊이우선 탐색(DFS)을 통해서, 시작점과 끝점까지 가는데, 그 차이를 가지는 경로가 있는지 확인하도록 했습니다. 최고값과 최저값의 차이는 이분탐색을 이용했습니다. 제일 먼저 모든 간선값들의 최저값과 최고값을 찾아서 그 차이값을 상한값으로 하였습니다. 이 값은 반드시 경로가 존재하게 되겠죠. 그리고 경로가 존재할 수 없는 값은 -1이 되겠죠. 모든 간선값이 같은 경우에는 0이 나와야 하니까요.. 2023. 1. 2.
[C/C++] 백준 #1978 소수 찾기(수학) 이번 문제는 N개의 수중에 소수인 수의 갯수를 찾는 것입니다. 소수의 범위가 크지 않기 때문에 사실 미리 소수를 구해도 되고, 에라토스테네스의 체를 이용해도 됩니다. 소수의 범위 K(이 문제에서는 1,000)라고 한다면, 에라토스테네스의 체를 사용하면 \(O(K \sqrt{K})\)의 시간안에 소수를 찾을 수가 있습니다. 또한 이것 자체가 소수인지 아닌지 판별하는 배열이 되기 때문에 소수의 개수를 구하는 것도 \(O(N)\) 시간안에 찾을 수 있습니다. 저는 에라토스테네스의 체가 아니라, 주어진 수마다 소수인지 판별을 했습니다. 이 경우 \(O(N \sqrt{K})\) 시간안에 찾을 수가 있습니다. 알고리즘 효율로 본다면, \(N 2022. 12. 20.
[C/C++] 백준 #1976 여행 가자(배타적 집합) 이번문제는 도시와 도시간 연결 정보를 알고 있으면, 중간에 다른 도시를 경유해서라도, 원하는 도시들을 여행할 수 있는지를 알아보는 것입니다. 사실 이 문제는 그래프를 만들어서 DFS나 BFS를 통해서 원하는 도시들을 다 방문하는지 찾아보아도 됩니다. 저는 배타적 집합(Disjoint Set)을 이용했습니다. 배타적 집합에서 집합을 찾고 합집합을 하는 것이 모두 상수시간이 걸리기 때문에, 전체적으로 \(O(N^2)\)의 알고리즘 효율로 할 수 있습니다. 연결된 도시가 나타나면, 각각의 도시가 속한 집합을 합집합을 하게 됩니다. 그러면 서로 분리된 한개 이상의 집합들이 나오게 되는데, 여행하고자 하는 도시들이 같은 집합에 있는지 검사하면 됩니다. 제가 작성한 소스입니다. //------------------.. 2022. 12. 20.
[C/C++] 백준 #1966 프린터 큐(구현) 네트워크 프린터에서는 전해진 문서들이 큐에 쌓이고, 차례대로 찍히는 것이 일반적입니다. 이 문제에서의 프린터 큐는 중요도가 있어서, 중요도가 높은 것이 후위에 있으면, 해당 문서를 찍지 않고, 큐의 마지막으로 옮겨지게 됩니다. 이번 백준 문제는 이러한 시스템에서 m번째 문서가 몇번째 찍히는지 계산하는 것입니다. 문제 뜻대로 그대로 구현을 한다면, 큐에서 문서를 하나 빼낼때마다, 매번 뒤의 문서들을 검색해야 합니다. 이 경우 우선순위가 낮은 것부터 높은것 순서대로 되어 있는 최악의 경우라면, 문서를 검사하는 비용이 \(O(N^2)\)이 됩니다. 사실 N이 100 이하이므로 이렇게 구현을 해도 됩니다. 검사비용말고, 큐에 추가하는 것을 따진다면, 최악의 경우 역시 \(O(N^2)\)이므로, 검사비용이 낮아지.. 2022. 12. 14.

티스토리툴바