BOJ 9466 : 텀 프로젝트 https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net DFS 문제이다. 크게 어렵지는 않은데, 주의할 만한 점은 vertex의 개수가 100000이므로 (edge의 개수도 당연히 100000이다) 모든 정점에 대해 BFS를 수행하면 O(VE)니까 TLE가 뜬다. 따라서 한 번 방문한 vertex에 대해서는 다시 방문하면 안 되고, cycle이 발생하는 경우에도 잘 체크를 해 줘야 한다. 어떤 방식으로든 한 번 방문한 ver..

https://www.acmicpc.net/problem/2749 2749번: 피보나치 수 3 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net • 접근 보통 피보나치 문제를 접근할 때에는 divide and conquer 또는 DP로 접근한다. n이 매우 작은 경우(BOJ 2747 참조)에는 재귀로 풀어도 풀 수 있다. 시간복잡도가 O(2^N)이기 때문이다. 그보다 n이 조금 더 커진다면 DP로 풀 수 있다. 이 경우 time complexity가 O(N)이므로 N이 대략 2억 언저리인 경우까지도 해결이 가능하다. 이 문제는 다르다. n의 upper bound가 1e18이다. 이런 경우에는 O(N)으로 풀 수 없다. ..

• 개요 Bellman-Ford algorithm에 대해서 찾아보는데, 대부분 간단하게, 또 과정 위주로 설명되어 있고 왜 Bellman-Ford algorithm이 정당성을 가지는지, 또 왜 그러한 순서로 해도 문제가 발생하지 않는지에 대해 설명이 부족한 것 같아 직접 정리하기로 하였다. • Single Source Shortest Path problems(SSSP) SSSP는 그래프 이론에서 아주 중요하고 또 자주 출제되는 문제이다. non-negative weighted graph와 관련된 문제의 경우에 Dijkstra's algorithm이 풀이에 사용되는데, 이는 time complexity가 O(VlogE)이므로 일반적인 graph에서 다른 알고리즘보다 빠른 측면이 있기 때문이다. 그러나 Di..

보호되어 있는 글입니다.

JordanoAboutInterestsComputer ScienceAlgorithm, Problem-SolvingMachine LearningComputer VisionPose EstimationObject DetectionAction RecognitionSegmentationData Science ChannelWebpage: csjihwanh.comGithub: https://www.github.com/jordano-jacksonContacte-mail: csjihwanh at gmail dot com

• Topological sort의 필요 directed acyclic graph(dag)의 경우 가끔씩 순서에 따라 linear한 정렬이 필요한 경우가 있다. 예를 들어 다음과 같은 상황을 가정해 보자. 수강할 강의를 선택하려고 한다. 매 학기 하나의 강의만 선택할 수 있고, 어떤 강의는 선수과목이 존재하여 선수강의를 수강하지 않았을 경우 수강할 수 없다. 이 경우 수강할 강의를 선택하는 방법을 제시하라. 위와 같은 상황을 graph로 나타내면 다음과 같을 것이다. 맨 처음 선택할 수 있는 과목은 A와 G 뿐이다. A를 수강한 다음이라야 비로소 B를 수강할 수 있고, D를 수강하려면 B와 G를 수강하여야 한다. F 과목을 수강하기 위해서는 F를 제외한 그래프 안의 모든 강의를 수강하여야 한다. 이런 문..