C++에서는 `bool`을 사용하고, Java에서는 `int`로 -1, 0, 1로 구분해서 사용하기 때문에, 혼동이 올 때가 많았습니다. 그래서 항상 헷갈리기에 정리해둔 것을 적어두겠습니다. C++ 오름차순 : `a b` (갈수록 작아진다!) 1차원 배열일 경우 #include using namespace std; #define endl "\n" int main() { int arr[] = {5, 7, 2, 3, 6, 1, 4}; int size = 7; // --------------------------------------------------- // 오름차순 sort(arr, arr + 7, [](const auto& a, const auto& b..
Study
문제 링크 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로 풀으면 됩니다. 저는 문제에서 주어진대로 노드를 삭제하고, 리프 노드의 개수를 셌습니다. 문제에서 제시하는 풀이는 어렵지 않지만, 예외처리를 하는데 조금 번거로움이 있었습니다. 백준 질문 게시판을 참고한 반례를 통해 알아낸 몇 가지 예외와 푸는 데 도움이 ..
문제 링크 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net 어제 쓴 포스팅(행렬 곱셈 순서)에 이어서, 비슷한 유형의 문제가 있기에 풀어봤습니다. 유형은 똑같은데 다른 점이 딱 하나 있었습니다. 저는 그 다른 점을 찾지 못해서 결국 구글링을 통해 알아냈습니다..... 자세한 설명을 해주신 블로그 글의 주인분께 감사의 인사를 드립니다. 풀이 트리형태 DP + 누적합 DP를 사용하여 풀이하면 됩니다. 트리형태 DP라는 의미는 어제 쓴 포스팅(행렬 곱셈 순서)를 참고해 주시면 될 듯합니다. 전에 푼 문제와 ..
문제 링크 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net 주말을 이용해서 이 문제를 풀기로 했는데... DP를 잘 못 하는 저로서는 좀 쉽지 않았습니다. 그래서 chatGPT에게 힌트를 물어보니 DP 구성 방법에 대한 힌트를 잘 설명해 줬고, 그것을 기반으로 문제를 풀 수 있었습니다. 제가 푼 방식을 필기해 둘 겸해서 블로그에 작성해봅니다. 풀이 DP 풀이를 하면 됩니다. 이 문제에서 정말 다행인 것은 항상 순서대로 곱셈을 할 수 있는 크기의 입력만 주어진다는 것입니다. 문제에서 주어진 예시에 따..
