전체 글107 [Dijkstra] 메시지 보내기 문제 N개의 도시가 있고 각 도시에서 메시지를 다른 도시로 보낼 수 있다. 도시간의 도로는 양방향이 아니고 일방향이다 도로를 가는 데에는 일정 시간이 소모된다 C라는 도시에서 메세지를 보낼 때, 최대한 많은 도시에 보내려고 한다면 메시지를 받는 조시의 개수는 총 몇개이며 도시들이 모두 메시지를 받는 데까지 걸리는 시간은? 1 2021. 8. 5. Floyd-Warshall 플로이드 워셜 문제 문제 1번부터 N번까지의 노드가 있는데 중간에 소개팅녀를 만나는 노드를 거쳐야 한다 따라서 n번 노드를 가야한다면 중간에 소개팅녀가 있는 k번 노드를 지나야 한다는 것 각 노드 사이는 양방향으로 갈 수 있고 1의 cost를 가진다 플로이드 워셜 알고리즘 모든 지점에서 다른 모든 지점까지의 최단 경로 구하는 알고리즘 (cf. 다익스트라 - 한 지점에서 다른 특정 지점까지의 최단 경로를 구하는 알고리즘) 2차원 배열을 사용하여 각 노드에서 다른 노드로 가는 모든 최단 거리를 구해야함 -> O(N^2)의 시간 복잡도가 필요 방문판매원이 1번 노드에서 4번 노드까지 최단거리로 방문해야 한다면 1번에서 출발하여 2번 노드를 경유해서 4번 노드로 가는 경우 1번에서 출발하여 3번 노드를 경유해서 4번 노드로 가는 .. 2021. 7. 30. Sum-of-Subsets 문제 문제 합이 G가 되는 모든 element들의 합의 집합들을 찾아라 입력 5 // data의 개수 21 // 합 G의 값 5 6 10 11 16 // data 값 출력 5, 6, 10, 5, 16, 10, 11, 경우의 수 문제로 최대한 적게 경우의 수를 찾을 수 있는 방법을 생각해야 한다. 합이 G를 넘어버리면 중간에 경우에 대한 계산을 중단하고 다른 경우의 수 즉, 방법으로 넘어가야 한다 처음 생각해낸 방법은 중간에 결과가 G를 넘어버리면 다시 back tracking으로 전으로 돌아가야 한다는 대략적인 밑그림이었다. back tracking 을 사용한다면 State Space Tree (상태 공간 tree)를 생각해야 한다 상태 공간 tree의 각 상태를 어떻게 정의하는가에 대해서 생각해보았다. 각각.. 2021. 5. 12. [Queue] 백준 1158 - 요세푸스 문제 생각하기 큐는 순환시 이용하는 자료구조 1부터 N까지 큐에 넣는다 (큐가 빌 때까지) K번째 숫자라면 pop하고 아니면 pop 시킨후 다시 push 시킨다 #include #include #include #include #include #include #include using namespace std; #define endl '\n' #define MAX 1000000 int N, K; int alpha[26]; int main() { ios_base::sync_with_stdio(0); cin.tie(0), cout.tie(0); cin>>N>>K; queue q; vector ans; for(int i=1; i 2021. 2. 26. 이전 1 ··· 19 20 21 22 23 24 25 ··· 27 다음