728x90 재귀 썸네일형 리스트형 [백준알고리즘] 4256번: 트리-C++ 4256번: 트리 (acmicpc.net) 4256번: 트리 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 노드의 개수 n이 주어진다. (1 ≤ n ≤ 1,000) BT의 모든 노드에는 1부터 n까지 서로 다른 번호가 매겨져 있다. 다음 www.acmicpc.net 이전에 풀었던 '트리의 순회' 문제와 유사하다. [백준알고리즘] 2263번: 트리의 순회-C++ (tistory.com) [백준알고리즘] 2263번: 트리의 순회-C++ 2263번: 트리의 순회 (acmicpc.net) 2263번: 트리의 순회 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 suri78.. 더보기 [백준알고리즘] 4779번: 칸토어 집합-C++ 4779번: 칸토어 집합 (acmicpc.net) 4779번: 칸토어 집합 칸토어 집합은 0과 1사이의 실수로 이루어진 집합으로, 구간 [0, 1]에서 시작해서 각 구간을 3등분하여 가운데 구간을 반복적으로 제외하는 방식으로 만든다. 전체 집합이 유한이라고 가정하고, www.acmicpc.net 칸토어 집합이 뭔지 궁금해서 찾아봤다. 칸토어 집합 - 위키백과, 우리 모두의 백과사전 (wikipedia.org) 근데 내용이 뭔 말인지 모르겠어서 일단 풀었다. 문제 자체는 문자열을 이용해 쉽게 풀 수 있었다. 같은 구조가 내부적으로 반복되기 때문에 분할 정복 알고리즘을 이용했다. 문제 풀이 선의 길이가 1이 될 때까지 반복하면서, 선을 계속해서 3등분을 했다. 첫 번째 조각과 마지막 세 번째 조각은 재귀적으.. 더보기 [백준알고리즘] 2339번: 석판 자르기-C++ 2339번: 석판 자르기 (acmicpc.net) 2339번: 석판 자르기 첫 번째 줄에는 석판의 크기 N(1 ≤ N ≤ 20)이 들어온다. 다음 줄부터 N줄에 걸쳐서 석판의 상태가 입력으로 들어온다. 여기서 1은 불순물을 의미하며, 2는 보석 결정체, 0은 불순물과 보석결정체가 www.acmicpc.net 이번 문제도 분할 정복 방식이다. 사실 문제를 처음 보자마자 아이디어는 떠올랐다. 그런데, 분할할 때마다 조건을 검사하는 과정에서 조각난 석판을 반복해서 검사하는 게 시간이 많이 소요될 것 같았다. 그래서 어떤 방식으로 처리를 해야 할지 고민하느라 시간을 많이 소요했다. 그래서 시간을 많이 소요하지 않게 하기 위한 방법을 고민하다 보니 메모리가 걸렸다. 결국에는 일일이 조건을 검사해도 시간이 여유로운.. 더보기 [백준알고리즘] 14601번: 샤워실 바닥 깔기 (Large)-C++ 14601번: 샤워실 바닥 깔기 (Large) (acmicpc.net) 14601번: 샤워실 바닥 깔기 (Large) 첫 번째 줄에는 바닥의 한 변의 길이를 표현하는 자연수 K(1 ≤ K ≤ 7) 가 주어진다. 이때 바닥의 크기는 2K 가 됨에 유의하라. 두 번째 줄에는 배수구의 위치를 나타내는 자연수 x, y (1 ≤ x, y ≤ 2K) www.acmicpc.net 분할 정복을 사용해야 하는 문제인 것은 감이 왔는데, 어떻게 분할 정복을 적용할지가 고민이었다. 그래서 생각보다 시간이 꽤 소요됐다. 처음에 생각했던 방식은 큰 'ㄱ'자 모양들로 분할해 나가는 것이다. 그런데 이건 큰 'ㄱ'자 모양 안에 작은 'ㄱ'자 타일들로 배치하는 게 생각보다 귀찮은 문제로 다가왔다. 다음으로 생각한 것은 큰 정사각형 .. 더보기 [백준알고리즘] 2263번: 트리의 순회-C++ 2263번: 트리의 순회 (acmicpc.net) 2263번: 트리의 순회 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 정답률과 골드 문제여서 쉽게 봤다가 시간을 많이 잡아먹었다. 그런데 접근법 자체 때문인 건 아니고, 메모리 초과가 발생했어서 코드를 약간 수정하는 게 너무 귀찮아서 오래 걸렸다. list를 여러번 생성하면서 재귀적으로 문제를 풀었는데, 10만 개가 한 줄로 이어진 경우에는 스택이 모자란 것으로 보인다. 그래서 list를 매번 생성해서 넘겨주는 것이 아닌, 인덱스로 접근하는 방법을 선택했다. 그러다 보니, list를 vector로 변경해주었.. 더보기 [백준알고리즘] 5639번: 이진 검색 트리 -C++ [백준알고리즘] 5639번: 이진 검색 트리 -C++ 5639번: 이진 검색 트리 (acmicpc.net) 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 생각보다 애를 먹었다. 처음에 list 자료형을 이용해 splice 함수로 이리저리 preorder를 postorder로 바꾸려고 시도해봤다. 동작은 하는 것 같으나, 시간 초과/메모리 초과가 발생해 고민을 많이 했다. 그러다가 배열을 쓰는게 훨씬 빠르다는 것을 보고, 배열과 인덱스를 이용해 처리하도록 변경했다. 문제 풀이 트리 탐색 방법은 전.. 더보기 [백준알고리즘] 17478번: 재귀함수가 뭔가요? -C++ [백준알고리즘] 17478번: 재귀함수가 뭔가요? -C++ 17478번: 재귀함수가 뭔가요? (acmicpc.net) 17478번: 재귀함수가 뭔가요? 평소에 질문을 잘 받아주기로 유명한 중앙대학교의 JH 교수님은 학생들로부터 재귀함수가 무엇인지에 대하여 많은 질문을 받아왔다. 매번 질문을 잘 받아주셨던 JH 교수님이지만 그는 중앙대 www.acmicpc.net 또다시 오랜만에 문제를 풀 수밖에 없었어서 실버 단계로 시작했다. 쉬워 보이는데 정답률이 왜 낮나 했더니 오타가 잘 발생하는 듯하다. 나도 그대로 복사했다고 생각했는데 IDE에서 어쩌다가 자동으로 조절되면서 오타가 발생했던 거였다. 참고로 오타는 Online Diff 사이트를 통해 직접 확인해서 고쳤다. 어디가 오타인지 모르겠는 분들은 그냥 di.. 더보기 [백준알고리즘] 5904번: Moo 게임 -C++ [백준알고리즘] 5904번: Moo 게임 -C++ 5904번: Moo 게임 (acmicpc.net) 5904번: Moo 게임 Moo는 술자리에서 즐겁게 할 수 있는 게임이다. 이 게임은 Moo수열을 각 사람이 하나씩 순서대로 외치면 되는 게임이다. Moo 수열은 길이가 무한대이며, 다음과 같이 생겼다. m o o m o o o m o o m o o o www.acmicpc.net 분할 정복 문제로, 이래저래 고민하다가 길이를 기준으로 재귀적으로 풀었다. 최악의 경우라도 수의 범위나 시간이 재귀적으로도 충분할 것이라 생각했다. 잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다 문제 풀이 문제에서 주어진 조건을 이용했다. \(M(k) =\ 'o'가\ k+2개인\ mo..o\ 문자열\) \(S(k) = S(.. 더보기 이전 1 2 다음
