Problem 💻이 문제는 L ≤ 10^8 이므로 2차원 배열을 만들어 하나하나 뱀을 이동시켜가며 풀 수 있는 문제는 아니다. 그러므로 머리의 회전 횟수 N을 이용해 문제를 해결해야 한다.  Approach 1 ⭕구현해당 문제는 뱀이 머리를 1초마다 하나씩 늘려가며 어떤 시간에는 회전도 하고 하면서 최종 죽는 시간을 구하는 문제이다. 문제의 주체를 뱀이 아니라 사람이라고 생각하면 자신이 가던 경로와 겹치는 순간 혹은 범위의 밖으로 가는 순간 죽는 것으로 해석할 수 있다. 뱀은 오로지 수직, 수평으로만 머리가 늘어난다. 그래서 방향을 바꾸는 시간 차이와 바꾸는 방향이 주어지면 바꾸는 시간 전까지는 같은 방향으로만 이동한다. 그래서 해당 방향 전까지 하나하나 이동하지 않고 단번에 ‘x + time’ 또는 ..

Problem 💻결정 문제로 이분탐색 + 다익스트라 or BFS, DFS로 풀 수 있는 문제이다.컴퓨터 N개를 연결하는 최소 비용을 구하는데, 어떤 비용 X에 대하여 해당 비용 X보다 작으면 돈을 내고, 크면 무료로 연결하여 최소 비용을 구하도록 문제의 요구 조건을 바꾸면 된다.  Approach 1 ⭕이분탐색 + 다익스트라이분탐색을 통하여 최소한으로 내야할 금액을 결정하고, 다익스트라를 통해 무료로 연결한 횟수를 가중치로 하여 1 → N 컴퓨터로의 최소 무료 연결 횟수를 구한 다음 해당 횟수가 k를 넘는지 확인하면 된다.k를 넘는다면 연결할 수 없는 경우이므로 다시 비용을 더 증가시켜보고, k를 넘지 않거나 같다면 비용을 더 줄일 수 있는지를 확인한다. 그렇게해서 예제를 보면 최소 4의 비용은 되어야..

Problem 💻단순한 브루트포스 문제지만 어떻게 풀어야할지 좀 고민해봐야 하는 문제이다. Approach 1 ❌좌표 완전 탐색별 기준으로 완전 탐색처음 풀이는 2가지였다. 좌표 완전 탐색과 별 기준 완전 탐색. 좌표 완전 탐색은 (1, 1)부터 (M-L, N-L)까지 x ~ x+L, y ~ y+L 사이의 겹치는 좌표가 있는지 하나하나씩 찾아서 최고값을 갱신해주는 방법이다. 하지만, 문제의 조건에 N, M은 최대 500,000으로 되어있기 때문에 이렇게 할 경우 L = 1인 최악의 경우 500,000 * 500,000으로 2500억 가까이 되는 연산이 일어난다. 당연히 시간초과이다. 그래서 생각한 방법이 별 기준으로 완전 탐색이다. 처음엔 별 좌표 기준으로 x ~ x+L, y ~ y+L 까지 겹치는 별..

Problem 💻1863. 스카이라인 쉬운거 입력은 다음과 같은 스카이라인을 나타낸다................................XX.........XXX........XXX.XX.......XXXXXXX.....XXXXXXXXXX....XXXXXXXXXXXX 다음과 같이 여섯 개의 빌딩이 있을 때가 최소 개수의 빌딩이 있는 상황이다................................22.........333........111.22.......XX333XX.....X111X22XXX....XX333XXXXXXX...............................XX.........XXX........XXX.XX.......5555555.....4444444444....555555..

Problem 💻4485. 녹색 옷 입은 애가 젤다지? 링크가 ‘도둑루피’로 가득찬 동굴에서 (0, 0) → (n-1, n-1)까지 최소한의 루피를 잃으면서 도착해야 하는 문제이다. 동굴의 각 칸마다 도둑루피의 가치가 주어지고 해당 가치가 클수록 잃는 돈이 많아지는 것이다. Approach 1 ⭕다익스트라 (00:13:12) 이 문제의 해결방법은 ‘도둑루피’를 조금 다르게 생각해 해당 노드로 가는 ‘가중치’라고 생각하는 것이다. 해당 노드로 가는 모든 간선의 가중치가 도둑루피의 가치로 고정되는 것이다. 그럼, 가중치 그래프의 최단 거리를 구하기 위해서 사용할 수 있는 알고리즘인 ‘다익스트라’를 생각할 수 있다. Approach 2 ⭕BFS (00:10:27) 두 번째로는 BFS를 이용한 방법이 있다. ..

문제https://www.acmicpc.net/problem/1238 접근 1 ⭕플로이드 워셜 (00:21:37)각각의 1~N번 마을에 살고 있는 학생들이 X번 마을을 왕복할 때 가장 시간이 많이 걸리는 학생이 누군지 찾는 문제이다. 즉, 1~N번 마을에서 X번 마을까지의 최단 거리를 구하고, X번 마을에서 1~N번 마을까지의 최단 거리를 구한 다음에 1↔X, 2↔X, …, N↔X 중 최대값을 구하면 되는 문제이다. 두 가지의 최단 거리를 한번에 구하는 가장 쉬운 방법이 바로 ‘플로이드 워셜’이다. 플로이드 워셜은 모든 정점에서 시작해 모든 정점까지의 최단 거리를 구하는 알고리즘이다! 접근 2 🔺다익스트라 (00:30:12)두 번째 해결 방법으로는 다익스트라가 있다.💡 1~N번 마을에서 X번 마을까지..

개요그래프의 한 정점에서 다른 정점으로 갈 때의 최단 경로를 구하는 대표적인 알고리즘은 `다익스트라 알고리즘`과 `플로이드 워셜 알고리즘`이 있다. 다익스트라 알고리즘은 어느 한 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘이고, 여기서 알아볼 플로이드 워셜 알고리즘은 모든 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘이다. 💡 플로이드 워셜 알고리즘은 모든 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘이다. 플로이드 워셜 알고리즘의 순서는 다음과 같다.모든 정점에서 각자의 간선에 따른 최단 거리 테이블을 갱신한다.2~N번 정점이 1번 정점을 거쳐갈 수 있는 경로가 있거나 최소가 되는 경로가 있다면 최단 거리 테이블을 갱신한다.1, 3~N번 정점이 2번 정점을 거쳐..

펜윅트리는 이진트리기반의 자료구조이며, 세그먼트 트리의 원리를 가지고 있습니다. 세그먼트 트리?여러 개의 데이터가 존재할 때 특정 구간의 합 혹은 최소값, 최대값 등을 구하는데 사용하는 이진 트리 형태의 자료구조입니다. 저는 이것을 어떻게 써야할지 단번에 이해가지 않아서 BOJ BOOK의 설명에 따라 그림과 함께 이해하였습니다. 만약, 이러한 문제가 있다고 합시다.크기가 n인 정수 배열 a가 있으며, 다음 연산을 최대 m번 수행합니다. 1. 구간 l, r이 주어졌을 때, a[l] + ... + a[r] 합 출력하기 2. i번째 수를 v로 바꾸기int[] a = {4, 6, 2, 1, 7, 5, 8}; 주어진 a 배열은 위와 같습니다. 일단 문제에서 구간 l, r이 주어졌을 때의 구간합을 구한다라고 하면 ..