알고리즘 문제/DFS and Simillar
-
백준 12784 인하니카 공화국알고리즘 문제/DFS and Simillar 2018. 5. 29. 17:16
백준 12784인하니카 공화국 문제는 흥미로운 문제였다. 인하니카는 섬으로 이루어진 나라인데, 각 섬은 다리들이 연결하고 있다. (그래프 ,,, ?)다리는 모든 섬을 연결할 수 있는 최소한의 개수로 사용되고 있다. (트리 .. !)다리가 한 개인 마을에 살인마가 존재하기 때문에 내가 사는 곳(1번 노드) 과 끊어야한다.이때 각 각의 다리를 끊는 비용은 주어질 때, 살인마가 존재 할 가능성이 있는 모든 마을에 대해 다리를 끊을 때 최소비용 을 구하라. 라는 문제이다. 이 문제는 난해할 수 있는데, 생각대로 깊이 우선탐색을 구현하면 쉽게 해결 할 수 있다.그러나 나는, 이 문제를 통해 좀 더 확장할 수 있는 재귀탐색 기법을 보여주고 싶었는데이 문제는 조금만 뉘앙스를 바꾸면, 트리에서 루트노드에서부터 모든 리..
-
백준 2447 별찍기10알고리즘 문제/DFS and Simillar 2018. 3. 6. 05:23
문제보기https://www.acmicpc.net/problem/2447분할정복 문제 재귀에 대해 능숙하다면 금방 해결 할 수 있는 문제이다. 10~20분 소요. 나는 알고리즘을 처음 시작할 때가 작년 7월 정도였으니, 한 9개월 정도 공부한 것이다. 내가 별찍기 11을 작년 8월- 그러니까 한 알고리즘 시작한지 1개월 도 안되었을 때 도전했다가 실패했을 것이다. 그때 좀 우울했다. 그러니까 이 문제를 해결하고, 포스팅 하는거지만,.. 나에겐 의미가 있는 포스팅이다 ㅋ. 이런류의 또 이런 수준의 문제는 다른사람의 코드를 보고 이해하고 분석하고 왜 틀린 이유를 짚으려면 나에겐 아직 조금 난해하기도 하고, 어렵다 그런만큼 초보 수준에서 별찍기 마스터를 하겠다 해서 괜히 이런문제에 상처받질 않기를 원한다. 왜..
-
884C Bertown Subway알고리즘 문제/DFS and Simillar 2017. 11. 5. 17:05
Difficulty : 4/10I couln't solve this problem during the contest.but It is not a difficult probelm. this problem can be solved in various way. I solved it with "union find algorithm". because union find is good algorithms to express "disjoint set". but the problem has a constraint. It is a "all station has just two degree, Just in and out".so it can be solved with just loop using parent, visit a..
-
BoJ 1717 : 집합의 표현알고리즘 문제/DFS and Simillar 2017. 10. 29. 19:55
문제 보기https://www.acmicpc.net/problem/1717 기본적으로 Disjoint를 알면 쉬운문제, 근데 애초에 엘리먼트 크기가 1,000,000 이므로 disjoint 말고는 풀수 있는 경우가 딱히 없을듯하다. 대표적인 Dis-joint set 문제이다. 또는 Union Find 문제라고도 불린다. disjoint 는 집합에서 공통된 원소가 없을 때 두 집합이 disjoint 하다고 표현한다.일단 제 포스트보다 더 설명 잘되있는 곳을 소개해드립니다.https://ko.wikipedia.org/wiki/%EB%94%94%EC%8A%A4%EC%A1%B0%EC%9D%B8%ED%8A%B8-%EC%85%8B_%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0http://koo..