본문 바로가기
  • 실행력이 모든걸 결정한다
반응형

Algorithm/Graph5

[Graph] 합승 택시 요금 - 2021 KAKAO BLIND RECRUITMENT 해결 방법 처음엔 BFS+DP로 시도해보았는데 시간초과가 나서 결국은 플로이드 와샬(Floyd Warshall) 알고리즘으로 해결했다. 플로이드 와샬 알고리즘은 각 정점끼리의 모든 최단 경로를 구해야할 때 사용되는 알고리즘이며, 구현하기 매우 쉽다는 장점이 있다. 자세한 동작을 알고싶다면 나동빈님의 블로그를 참고하길 바란다. https://blog.naver.com/ndb796/221234427842 24. 플로이드 와샬(Floyd Warshall) 알고리즘 지난 시간에는 다익스트라(Dijkstra) 알고리즘에 대해 학습했습니다. 다익스트라 알고리즘은 하나의 정점... blog.naver.com 소스 코드 #include #include using namespace std; int min_fare[201.. 2022. 9. 28.
[그래프, 난이도 중] 프로그래머즈, 순위 n명이 있고 일부의 승패 관계를 알 수 있을 때, 어떤 조건에서 자신의 정확한 순위를 알 수 있는지 알아내야 한다. 본인이 해결한 방법은 이렇다. 전체 인원 수는 n명이고 자신이 이기는 사람(우위)을 a명이라고 하고 자신을 이기는 사람(열위)을 b명이라고 하자 이 때 a+b=n-1 식이 성립해야 한다. 예를 들어 총 10명이 있다고 하자. 자신이 7명은 확실히 이길 수 있고 2명에게는 확실히 패배한다. 그렇다면 순위는 10위~4위(7명) 2020. 10. 8.
[그래프, 난이도 중] 프로그래머즈, 가장 먼 노드 노드 번호와, BFS의 깊이 변수를 가지는 구조체 node를 만들고 BFS를 수행했다. 큐에 담을 인접 노드가 하나도 없는 노드(이미 방문한 노드들 뿐)는 단일 노드라는 의미이므로, 이 노드는 가장 먼 노드의 후보가 된다. 아래 소스 코드에서 finished라는 bool 타입의 변수는, 큐에 담을 인접노드가 하나 이상 있는가의 여부를 판단한다. 가장 먼 노드의 후보로 꼽힌 노드들의 depth를 모아서 이들중 최댓값을 찾고, depth가 최댓값인 요소가 몇개 있는지 계산하면 문제가 해결된다. 테스트 케이스 9개 모두 통과 #include #include #include using namespace std; struct node{ int num; int depth; }; queue q; vector a[20.. 2020. 10. 7.
[그래프, 난이도 중상] 백준 1005번 ACM Craft 이 문제는 위상 정렬을 이용하여 풀어야 한다. 위상 정렬이란 자신을 가리키는 노드들이 전부 자신 노드에 방문을 했을 때 다음 노드로 이동할 수 있게 하는 알고리즘이다. 즉, 진입차수가 0인 노드들을 큐에 넣으며 시작하고, 큐에서 꺼낸 노드의 인접노드의 진입 차수를 1씩 감소시키며, 이 결과로 진입 차수가 0이 된 노드들을 다시 큐에 넣는 과정을 반복하는 알고리즘이다. 이전 건물을 다 짓기 전까지는 현재 건물을 짓지 못한다는 조건이 있으므로 위상 정렬을 이용해야 한다는 것이다. 그리고 시간 초과가 나지않게 동적계획법(DP)도 병행하였다. 위상정렬을 수행하며, 이 건물(노드)을 짓는데 걸리는 누적 시간을 업데이트 해주는 것이다. 이전 건물들이 모두 세워져야 현재 건물을 세울 수 있기 때문에 max함수를 이용.. 2020. 8. 20.
[SCC, 난이도 중상] 백준 9466번 텀 프로젝트 원래 알고리즘 분류상 DFS에 들어가 있던 문제인데, 강한 결합요소(SCC) 유형이라고 보는게 더 좋을 것 같아서 그래프 카테고리에 포스팅 한다. 강한 결합요소 알고리즘도 DFS를 쓴다. 강한 결합요소 알고리즘을 간단하게 설명하자면 이렇다. 일단 아래 그림은 9466번 예제에서 첫 번째 케이스를 도식화 한것이다. 3번은 자기 자신을 가리킨다는 의미로 동그라미로 감쌌다. 여기서 SCC는 5개다. (1번), (2번), (3번), (4번,6번,7번) , (5번) 여기서 (4번,6번,7번)은 사이클로 되어있으므로 하나의 SCC그룹이라고 하는 것이다. 아래 소스 코드에서 dfs함수가 SCC(강한결합요소) 알고리즘이다. 그런데 여기서 한가지 처리를 해줘야 한다. 서로 선택 받고 있는 그룹은 (3번),(4번,6번,7.. 2020. 8. 15.

티스토리툴바