전체 글

문제 링크 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 저번에 작성했던 벽 부수고 지나가기 첫 문제 포스팅에 이어 두번째 문제입니다. 이번 문제는 첫번째 문제에서 조건 하나만 변경한 문제이니, 그렇게 차이는 나지 않습니다! 풀이해보겠습니다~ 풀이 이전 문제와 마찬가지로 VST(3중배열) + BFS로 풀이하면 됩니다. 대신 이전 문제는 2개까지만 벽을 부수는 것을 허용했지만, 이번 문제는 10개까지 벽을 부술 수 있습니다. 따라서 그만큼 VST배열의 크기를 늘려서 저장하고,..

문제 링크 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 요새 프로젝트를 진행한다고 블로그 글을 잘 못쓰네요 😂 그래서 오늘부터 간단하게 벽 부수고 이동하기 문제 시리즈를 진행할 계획입니다. 시리즈는 1부터 4까지 있고, 이번 포스팅부터 시작합니다! 풀이 VST (3중배열) + BFS로 풀이하면 됩니다. 이 문제는 흔하게 볼 수 있는 BFS를 이용한 최단 거리 문제의 응용 버전이라고 볼 수 있겠습니다. 보통 최단 거리 문제는 `visit` 배열로 전에 갔던 경로를 체크하여 가지 않는..

문제 링크 1311번: 할 일 정하기 1 N명의 사람과 N개의 일이 있다. 각 사람은 일을 하나 담당해야 하고, 각 일을 담당하는 사람은 한 명 이어야 한다. 또한, 모든 사람은 모든 일을 할 능력이 있다. 사람은 1번부터 N번까지 번호가 매 www.acmicpc.net 요새 DP 문제에 빠져 있습니다.... 바텀업 DP부터 트리DP까지 공부하고 있는 도중, 예전에 외판원 순회 문제를 풀면서 접하게 되었던 비트마스크를 이용한 DP 문제를 우연히 보게 되었습니다! 이번 문제는 비트를 어떻게 이용하는지만 블로그를 참고했고, 문제풀이는 스스로 생각해서 풀(어서 뿌듯했)었습니다. 같이 풀이를 살펴보시죠! 😄 풀이 비트마스크를 이용한 DP로 풀이하면 됩니다. 이 문제를 풀 수 있으면, 외판원 순회 문제도 도전해 ..

문제 링크 20303번: 할로윈의 양아치 첫째 줄에 정수 $N$, $M$, $K$가 주어진다. $N$은 거리에 있는 아이들의 수, $M$은 아이들의 친구 관계 수, $K$는 울음소리가 공명하기 위한 최소 아이의 수이다. ($1 \leq N \leq 30\ 000$, $0 \leq M \leq 100\ 000$, www.acmicpc.net 이번에는 두가지 알고리즘을 합친 혼종 문제를 풀어보겠습니다.. 이번 문제는 반은 맞고 반은 다른 분의 블로그를 참고해서 풀었습니다,, 언젠가는 대부분의 문제를 저 혼자서 풀 날이 오겠죠??? 그 때를 기다리며 오늘도 열심히 달려보겠습니다~ 풀이 분리 집합(유니온-파인드) + 배낭 문제 풀이로 풀었습니다. 저도 처음에 배낭 문제가 아니라, 그저 분리 집합으로 연결된 아이..

문제 링크 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net 저번주에 트리를 공부하다가 트리DP라는 친구를 만났는데 참 만만치 않았습니다. 😂 그래서 DP를 공부해야겠다 생각했고, DP 관련해서 열심히 공부해보고자 이번 문제를 풀어보게 되었습니다! 풀이 N의 크기가 크기 때문에, DP를 이용해서 풀어야 합니다. 종만북(알고리즘 문제 해결 전략)에 의하면, N의 크기가 150만이면 \(O(N\log{N})\)정도에서 커버가 가능하다고 합니다. 다시말해, \(O(N\log{N})\)이하..