📑 문제🌱 아이디어최단거리를 구하고, 최단거리 루트의 경로 역추적을 통해 풀어보자! 최단거리 문제이다. 하지만 최단거리로 갈 때 바로 첫 노드를 출력하는 문제이다. 가령 1 → 5번 노드로 가야 한다면 여러 가지 루트 중 가장 최단 경로 1 → “3” → 4 → 5 일 때위 문제에서 요구하는 답은 "3"번 노드를 출력하는 게 조건이다. 즉 경로 역추적 알고리즘이 필요하다. 그리고 또 하나 i → j로 갈 때 바로 직행하는 방법도 있지만 이러한 루트는 최단루트가 아닐 수 있다.i → j ,  i → h → j ⇒ 직행루트 와 경유지가 있는 루트를 비교해야 한다결국 플로이드워셜 알고리즘을 사용하는 게 가장 좋아 보이는 문제이다.기본적인 플로이드 워셜 알고리즘을 구현하는 것은 어렵지 않았으나. 경로 역추적..

📑 문제🌱 아이디어분할정복을 이용한 행렬제곱 문제, 큰 문제를 작은 단위로 나눠서 풀어보자 분할 정복의 가장 기본적인 개념은 큰 문제를 작은 단위로 나눠서 푸는 것이다.. 예를 들면 N^8 은 N*N*N*N*N*N*N*N 이다. 즉 N을 8번 곱해야 한다.  분할 정복을 통해 작은 단위로 나눠서 bottom up 방식으로 푼다면  (((N^2)^2)^2) 3번만 연산하면 된다. 이는 O(logn)의 시간복잡도를 가지며 N^B, B가 클수록 좋은 성능을 보여준다.  그리고 행렬 A와 행렬 B를 곱한다면 A =1234 B =5678  A X B =1*5+2*71*6+2*83*5+4*73*5+4*8 위와 같이 행렬곱셈과 동시에 분할정복으로 작은 단위 ~ 큰 단위로 답을 도출해야 한다.🌱 코드 및 풀이 만..

📑 문제🌱 아이디어관리인이 보는 방향은 항상 현재 자리 -> 오른쪽으로 본다. 경험상 이러한 구조는 스택으로 구현가능하다. 이 문제는 N ≤ 80000 이므로 O(N^2)이 소요되는 알고리즘으로는 풀 수 없다. 즉 이미 계산된 값을 이용해서 다음값을 구하는 방식으로 중복계산을 줄여 시간을 단축해야 한다. 스택과 다이나믹 프로그래밍을 사용해서 풀어보자! 예제 1번을 통해 논리의 흐름을 그려 보았다 말로 하는 것보다 효과적일 것이라 생각한다.너무 길어서 읽기 힘들겠지만 천천히 보다 보면 흐름이 보일 것이다 1. dp 배열 = 각 위치에서 볼 수 있는 옥상 수2. stack1, stack2 = 빌딩 번호3. arr1 배열 = 빌딩 높이   5번 빌딩과 6번 빌딩의 높이를 비교합니다1 ) 5번 빌딩이 더 클..

📑 문제🌱 아이디어데드라인 별 가장 최적의 값을 선택하여 최댓값을 출력하는 문제! 그리디 알고리즘이다! 정렬속도가 빠른 우선순위 큐를 이용해 보자! 문제 자체는 이해하기도 쉽고 어렵지 않았다. 덕분에 그리디, 우선순위큐를 이용하면 되겠다는 생각도 빨리 도출해 내었던 문제이다.하지만 깊게 생각을 해야 하는 문제였다 ㅠ 다음 예제를 보자 반례 1) 41 502 303 603 70ans = 180 가장 처음 구현했을 때 데드라인을 1 ~ N까지 오름차순 데드라인별 최적값을 구하는 형식으로 풀었지만결과는 150이 나왔다. 50 + 30 + 70 이렇게 컵라면을 획득한 것이다. 하지만 문제의 정답은 50 + 60 + 70 = 180 이다. 즉 가장 낮은 데드라인이 항상 최적의 값을 보장하지 않기 때문에N ~ ..

📑 문제🌱 아이디어"시간이 되돌아가는 경우" -> 만약 음수 사이클이 존재한다면 무한히 시간을 되돌릴 수 있다즉 그래프 내 음수 사이클을 판별하기 위해 벨만포드 알고리즘을 사용해야 한다! 벨만포드 알고리즘은 최단거리를 구하는 알고리즘입니다. 음수 사이클이 존재한다면 계속 최단거리가 업데이트된다는 특징이 있기 때문에이러한 특징을 바탕으로 밸 만 포드 알고리즘 N번까지 실행했을 때 마지막까지 최단거리가 업데이트된다면 음의 사이클이 존재한다는 것을 증명할 수 있다.   위 그래프는 예제 입력 2번을 토대로 만든 그래프와 가중치이다. 밸만포드 알고리즘을 N번까지 실행해 보자1회 차 : 1(-2) / 2(4) / 3(0)2회 차 : 1(-4) / 2(2) / 3(-2)3회 차 : 1(-6) / 2(0) / 3..