문제 링크 13334번: 철로 입력은 표준입력을 사용한다. 첫 번째 줄에 사람 수를 나타내는 양의 정수 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 각 줄에 정수 쌍 (hi, oi)가 주어진다. 여기서 hi와 oi는 −100,000,000이상, 100,000,0 www.acmicpc.net 요새 취업 시장에서 그리디 문제가 많이 나온다기에 열심히 관련 문제들을 풀고 있습니다! 👨💻 그리디 문제들을 풀다 보면 정렬을 사용하는 그리디와 정렬을 사용하지 않는 그리디가 있고, 여러 자료 구조 중 하나를 선택하여 푸는 그리디가 있는데, 그 중 대표적인 것이 우선순위 큐였습니다. 우선순위 큐를 이용하는 그리디 문제 중에 좋은 문제가 있어서, 하나 포스팅을 해보려고 합니다. 😊 풀이 정렬과 우선순위..
골드
문제 링크 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 이번 문제는 이전 벽 부수고 이동하기 시리즈 1~3과는 조금 다릅니다. 이전 문제들은 벽을 부수고 지나가면서 최단 경로를 구하는 문제였지만, 이번 4번째 문제는 벽을 부수고 이동할 수 있는 칸의 개수를 세어보는 경우의 수 문제로 바뀌었습니다. 이번 문제는 풀면서 저도 우여곡절이 살짝 있었기에, 그런 우여곡절들을 공유하면서 풀이해보겠습니다. 풀이 DFS로 풀이했습니다. (BFS도 가능) 보통 경우의 수는 백트래킹으로 풀이하는데, 백트..
문제 링크 16933번: 벽 부수고 이동하기 3 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 링크 : 벽 부수고 이동하기 1 링크 : 벽 부수고 이동하기 2 벽 부수고 이동하기 1과 2에 이어서 3번 문제입니다! 이번 문제도 저번 문제들의 연장선에 있습니다. 저번 문제에서 낮과 밤이 추가됐죠! 이번 문제도 한번 풀어보겠습니다~ 풀이 이전 문제와 마찬가지로 4중배열 VST + BFS로 풀이하면 됩니다. 이전 문제의 DP는 \(k\)(벽을 부술 수 있는 한도)와 \(n, m\)(맵의 행렬 길이)로 풀 수 있었습니..
문제 링크 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})\)이하..
문제 링크 22856번: 트리 순회 노드가 $N$개인 이진 트리가 있다. 트리를 중위 순회와 유사하게 순회하려고 한다. 이를 유사 중위 순회라고 하자. 순회의 시작은 트리의 루트이고 순회의 끝은 중위 순회할 때 마지막 노드이다. www.acmicpc.net 요즘들어 또 비가 주륵주륵 내리기 시작합니다... 여름이 다 가고 있기도 하구요. 이럴 때일수록 감기에 조심해야 됩니다! 이 글을 보는 모든 분들 환절기에 감기 안걸리고 건강하시길 기원하겠습니다! 🙋♂️ 이전 글에 이어서 트리 관련 문제를 풀어보겠습니다~ 풀이 DFS로 풀이하면 됩니다. (문제의 숨겨진(?) 트릭을 발견하면 쉽습니다) 문제에서 백트래킹에 의한 중위순회를 그림으로 보여주고 있습니다. 그러고나서 순회의 횟수를 세라고 하고 있습니다. 하지..
문제 링크 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 요새 트리를 많이 접하지 않고, 그래프만 접하고 있는 것 같아 오늘부터 트리 연습을 하기로 했습니다! 🌲 오늘도 열심히 문제를 풀어봅시다~ 풀이 문제에서 주어진대로 구현(재귀)하거나, DFS로 풀으면 됩니다. 저는 문제에서 주어진대로 노드를 삭제하고, 리프 노드의 개수를 셌습니다. 문제에서 제시하는 풀이는 어렵지 않지만, 예외처리를 하는데 조금 번거로움이 있었습니다. 백준 질문 게시판을 참고한 반례를 통해 알아낸 몇 가지 예외와 푸는 데 도움이 ..
