이론이론이론이론 썸네일형 리스트형 Knapsack 알고리즘 (배낭싸기 알고리즘 ) " 당신이 보석을 털러 보석점에 침입했다. 각각의 보석 n개가 있고 보석마다 무게와 가치가 다르다. 당신의 가방에 담을 수 있는 무게에 한계가 있을 때, 당신이 가져나올 수 있는 보석들의 가치 합은 최대 얼마인가. " 무게와 가치가 따로 있고 가져갈 수 있는 최대 가치를 묻는 문제들, 이런 류의 문제는 Knapsack 알고리즘으로 풀 수 있다. 모든 경우를 다 따져보는 알고리즘, 즉 Greedy 알고리즘으로 이 문제를 해결할 수 있다. 하지만 시간복잡도가 2^n이기 때문에 n이 커지면 시간이 오래걸린다. 그리고 항상 최적의 답을 낼 거라는 보장이 없다. Greedy 알고리즘은. 그렇기에 Knapsack 문제는 다이나믹 프로그래밍으로 풀어야한다. w[i]가 i번째 보석의 무게, v[i]가 i번째 보석의 가.. 맵(map) 클래스 배열의 인덱스로 String이나 큰 수를 넣고 싶은데 불가능하다면, #include map은 STL(Standard Template Library)이 제공하는 자료구조 중 하나. map의 배개변수 Key - map에 저장되는 키 데이터 형식Type - map에 저장되는 요소 데이터 형식Traits - 함수 개체를 제공하는 형식은 map 내에서의 상대적인 순서를 결정하는 정렬 키로 두 요소 값을 비교 가능Allocator - map의 메모리 할당 및 할당 취소에 대한 세부 정보를 캡슐화하는 저장된 할당자 개체를 나타냄 map 클래스 특징 - 연결된 키 값을 기반으로 요소 값을 효율적으로 검색하는 다양한 크기의 컨테이너.- 이는 해당 요소에 엑세스할 수 있는 양방향 반복기를 제공하기 떄문에 되돌릴 수 있다... 투 포인터스 알고리즘 (Two Pointers Algorithm) 투 포인터스 알고리즘 (Two Pointers Algorithm) 절대 정답이 되지 않는 경우를 Skip하는 알고리즘. 보통 a부터 b까지의 합이 ~되는 경우를 묻는 문제에서 이중 포문을 사용해야하는데 경과되는 시간을 줄이기 위해 사용하는 알고리즘이다. 위의 배열에서 i번쨰 인덱스부터 j번째 인덱스까지 합이 7이 되는 경우의수를 모두 구하는 문제라 가정해보자. (배열의 길이가 짧아 이중포문을 사용하면 금방 구할 수 있지만 배열의 크기가 어느 수준 길어지면 시간초과가 발생한다.) 투 포인터스 알고리즘은 Left (시작:0), Right (시작:0)을 선언하고 Right를 한칸씩 이동시키면서 답을 찾으면 Left를 한칸 이동시키는 알고리즘이다. Right를 이동시켜줄떄마다 변한 Right에 위치하는 값을 s.. 우선순위 큐 활용법 http://koosaga.com/9 플로이드 워셜 알고리즘 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)은 그래프에서 가능한 모든 노드 쌍에 대해 최단 거리를 구하는 알고리즘이다. 시간복잡도는 O(V^3)O(V3)이다. 다익스트라 알고리즘과는 달리 모든 노드 쌍에 대해 최단 거리를 구하고, 음의 가중치를 가지는 그래프에서도 쓸 수 있다는 것이 특징. 플로이드-워셜 알고리즘은 임의의 노드 s에서 e까지 가는 데 걸리는 최단거리를 구하기 위해, s와 e 사이의 노드인 m에 대해 s와 m까지 가는 데 걸리는 최단거리와 e와 m까지 가는 데 걸리는 최단거리를 이용한다. s : 시작 노드e : 목표 노드m : s와 e 사이의 노드 알고리즘 123456void Floyd_Warshall() { for(m=1; m 이전 1 다음
