전체 글

문제 링크 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 풀이를 하면 됩니다. 이 문제에서 정말 다행인 것은 항상 순서대로 곱셈을 할 수 있는 크기의 입력만 주어진다는 것입니다. 문제에서 주어진 예시에 따..

문제 링크 18353번: 병사 배치하기 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 이번 문제는 저번에 풀이를 올렸던 LIS 2번 문제를 응용해서 풀 수 있는 문제입니다! 열심히 풀어봅시다~ 풀이 LIS(DP+이분탐색)을 내림차순으로 풀이하면 됩니다. 내림차순으로 풀이 후에, 열외할 병사를 출력하기 위해 내림차순으로 저장한 배열(seq)의 크기를 n에서 빼주었습니다. 전에 썼던 LIS 2번 문제 와 흐름이 거의 동일하니, 자세한 풀이는 링크를 참고해주세요! 풀이코드 #include using namespace std; #de..