Noosphere It

벨만포드 알고리즘은 모든 노드에 대해서 업데이트를 하는 것에 반해, SPFA는 업데이트된 노드와 그 노드에 연결된 간선만 확인하고 업데이트하는 것이다. O(VE)로 벨만 포드 알고리즘과 동일하지만, 특정 경우에 O(V+E)에 빠르게 연산가능하다는 점이다. 밸만포드 알고리즘과 동일하게 visited 변수를 활용해 1->n 루트에서 음수의 사이클이 있는지 확인한다. 큐와 큐에 있는지 확인하는 배열(inQ)를 활용해 업데이트한 노드를 큐에 넣을 수 있도록하고, cycle[MAXN] 변수를 두어 노드를 n번이상 방문하면 벨만포드에서 n번째 순회를 했을 때랑 동일하게 음수의 사이클이 있다고 판단한다. #include #include #include #include #include #define MAXN 100+1..

최대한 유리한 경로를 찾는 문제이다. 길을 지날때마다 금품을 잃거나, 금품을 획득하게 된다고 한다. 음의 가중치를 가진 간선이 존재하므로 다익스트라는 불가능이다. 그럼 벨만포드 알고리즘이다. 우리가 아는 알고리즘(다익스트라, 벨만포트, 플로이드 워셜)은 간선을 지날 때마다 비용을 지불한다. 그래서 최소의 비용을 찾는 문제이다. 그런데 1738번은 최대의 금품을 가지는 것을 찾는 문제다. 그래서 벨만포드 알고리즘에 활용하기 위해서 기존의 금품을 획득할 때 +A로 표시하는 것을 반대로 표시한다.(+A -> -A, -A -> +A) 그 것을 통해서 최소의 비용을 찾는 알고리즘인 밸만포드 알고리즘을 사용할 것이다. 최적의 경로가 존재하지 않는 상황은 1->N로 가는 경로를 찾았는데, 그 경로상에서 음수의 싸이클..

어려운 문제는 아니지만 내가 보통 푸는 방법과 다르게 풀어서 정리해두려고 한다. 문제 Objective Welcome to the last day! Today, we're discussing bitwise operations. Check out the Tutorial tab for learning materials and an instructional video! Task Given set . Find two integers, and (where ), from set such that the value of is the maximum possible and also less than a given integer, . In this case, represents the bitwise AND operator..

문제 이중 우선순위 큐(dual priority queue)는 전형적인 우선순위 큐처럼 데이터를 삽입, 삭제할 수 있는 자료 구조이다. 전형적인 큐와의 차이점은 데이터를 삭제할 때 연산(operation) 명령에 따라 우선순위가 가장 높은 데이터 또는 가장 낮은 데이터 중 하나를 삭제하는 점이다. 이중 우선순위 큐를 위해선 두 가지 연산이 사용되는데, 하나는 데이터를 삽입하는 연산이고 다른 하나는 데이터를 삭제하는 연산이다. 데이터를 삭제하는 연산은 또 두 가지로 구분되는데 하나는 우선순위가 가장 높은 것을 삭제하기 위한 것이고 다른 하나는 우선순위가 가장 낮은 것을 삭제하기 위한 것이다. 정수만 저장하는 이중 우선순위 큐 Q가 있다고 가정하자. Q에 저장된 각 정수의 값 자체를 우선순위라고 간주하자. ..

문제 설명 이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다. 명령어수신 탑(높이) I 숫자 큐에 주어진 숫자를 삽입합니다. D 1 큐에서 최댓값을 삭제합니다. D -1 큐에서 최솟값을 삭제합니다. 이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 return 하도록 solution 함수를 구현해주세요. 제한사항 operations는 길이가 1 이상 1,000,000 이하인 문자열 배열입니다. operations의 원소는 큐가 수행할 연산을 나타냅니다. 원소는 “명령어 데이터” 형식으로 주어집니다.- 최댓값/최솟값을 삭제하는 연산에서 최댓값/최솟값이 둘 이상인 경우, 하나만 삭제합..

프로그래머스에도 비슷한 문제가 있어서 그때는 파이썬으로 heapq 활용해서 간단하게 구현했었는데, 이번에는 C++로 풀었다. 파이썬에서 max(리스트) 기능이 얼마나 소중한거인지 깨달았다... 두개의 우선순위큐(min heap, max heap) 를 써야되는 것은 알고있었다. 그런데 시간초과가 문제였다. 처음에는 Delete할때마다 다른 큐에서도 pop하면서 찾아서 다시 넣어주고 그랬는데, 최악 케이스 N log(N)이라서 문제였나보다. 그래서 검색하던 도중 lazy update에 대해서 보게되었다. delete 해야할 것들을 따로 저장해주고, Delete때마다 pop()해서 나오는 힙에서 확인해주었다. qLen라는 것을 저장해두어 qLen이 0일때 발생하는 불필요한 동기화를 없애주었다. // 반례 ht..

문제 설명 초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요. 제한사항 prices의 각 가격은 1 이상 10,000 이하인 자연수입니다. prices의 길이는 2 이상 100,000 이하입니다. 입출력 예pricesreturn [1, 2, 3, 2, 3] [4, 3, 1, 1, 0] 풀이 스택을 활용하여 풀었다. 스택에 집어넣으면서, 스택 맨위값과 비교하면서 감소하면(stack[num_element-1][1] > price 상황)스택에서 pop하며 현재의 시간에서 price의 시간을 뺴서(idx - ith) 떨어지지 않은 기간을 기록한다. for문을 다 돌고, stack에 남아있다면..

문제 설명 트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다. 예를 들어, 트럭 2대가 올라갈 수 있고 무게를 10kg까지 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다. 경과 시간다리를 지난 트럭다리를 건너는 트럭대기 트럭 0 [] [] [7,4,5,6] 1~2 [] [7] [4,5,6] 3 [7] [4] [5,6] 4 [7] [4,5] [..

문제 설명 일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린터를 개발했습니다. 이 새롭게 개발한 프린터는 아래와 같은 방식으로 인쇄 작업을 수행합니다. 1. 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냅니다. 2. 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에 넣습니다. 3. 그렇지 않으면 J를 인쇄합니다. 예를 들어, 4개의 문서(A, B, C, D)가 순서대로 인쇄 대기목록에 있고 중요도가 2 1 3 2 라면 C D A B 순으로 인쇄하게 됩니다. 내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 ..

문제 설명 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다. 먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요. 제한 사항 작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다. 작업 진도는 100 미만의 자연수입니다. 작업 속도는 100 이하의 자..