큐
-
[프로그래머스] 게임 맵 최단거리알고리즘/프로그래머스 2021. 7. 21. 14:46
문제 링크 풀이법 큐를 이용해서 풀 수 있습니다. 이 문제는 깊이 우선이 아니라 너비 우선 방식으로 풀어야 합니다. 너비 우선 방식을 이용하면 모든 노드에 도달하는 카운트가 최소가 됩니다. 현재 노드에서 동서남북 방향을 훑어 보고 처음 방문한 곳이면서 노드 값이 1인 경우에 탐색을 합니다. 이 과정이 순차적으로 이루어지며, 탐색을 선점하게 되면 해당 위치의 카운트는 갱신되지 않게 코드를 작성할 것이기 때문입니다. 프로그래머스에선 이차원 배열을 vector로 선언했을 때 속도가 더 빠르게 나오는 걸 확인했습니다. 하지만 효율성 테스트와 비주얼 스튜디오 2019에선 당연히 정적으로 선언한 경우가 더 빨랐습니다. 예제 1번 기준으로는 0.2ms 차이가 났고, 효율성 테스트에서는 0.05~0.07ms로 작은 차..
-
[프로그래머스] 프린터알고리즘/프로그래머스 2021. 7. 19. 14:42
문제 링크 풀이 이 문제는 크게 두 가지 방법으로 풀 수 있는 것 같습니다. 효율성이나 성능을 고려했을 때 반복문을 줄이는 게 좋다고 생각합니다. 이 관점에서, 우선순위 큐를 사용하면 알고리즘 헤더의 max_element를 매번 사용하지 않아도 되기 때문에 빠르고 효율이 좋습니다. pair을 연습해볼 수도 있어서 좋습니다. 코드1 #include #include #include using namespace std; int solution(vector priorities, int location) { int answer = 1; queue index_value_q; priority_queue pq; for (int i = 0; i < priorities.size(); ++i) { index_value_q...
-
[프로그래머스] 탑알고리즘/프로그래머스 2019. 12. 2. 19:06
문제 설명 수평 직선에 탑 N대를 세웠습니다. 모든 탑의 꼭대기에는 신호를 송/수신하는 장치를 설치했습니다. 발사한 신호는 신호를 보낸 탑보다 높은 탑에서만 수신합니다. 또한, 한 번 수신된 신호는 다른 탑으로 송신되지 않습니다. 예를 들어 높이가 6, 9, 5, 7, 4인 다섯 탑이 왼쪽으로 동시에 레이저 신호를 발사합니다. 그러면, 탑은 다음과 같이 신호를 주고받습니다. 높이가 4인 다섯 번째 탑에서 발사한 신호는 높이가 7인 네 번째 탑이 수신하고, 높이가 7인 네 번째 탑의 신호는 높이가 9인 두 번째 탑이, 높이가 5인 세 번째 탑의 신호도 높이가 9인 두 번째 탑이 수신합니다. 높이가 9인 두 번째 탑과 높이가 6인 첫 번째 탑이 보낸 레이저 신호는 어떤 탑에서도 수신할 수 없습니다. 송신 탑..