반응형 재귀3 프로그래머스 표현 가능한 이진트리 - C++ 풀이 1. 주어진 십진수를 이진수로 변환한다. 2. 변환한 이진수는 트리를 중위순회한 결과와 같다. 3. 중위순회 결과를 가지고 포화이진트리를 만들었을 때, 부모는 더미노드인데 자식은 실제노드인 경우 표현 불가능한 구조이다. 1. 주어진 십진수를 이진수로 변환한다. 먼저 십진수를 이진수로 변환한다. 2. 변환한 이진수는 트리를 중위순회한 결과와 같다. 노드를 왼쪽부터 순서대로 살펴보는 것은 중위순회하는 것과 같다. 따라서 변환한 이진수는 트리를 중위순회한 결과와 같고, 이진수의 길이는 트리의 노드 개수와 같다. 포화이진트리는 노드의 개수가 2^n-1개이므로 포화이진트리가 되도록 부족한 길이는 0으로 채워준다. (더미 노드를 추가하는 것은 문제가 되지 않음) 3. 중위순회 결과를 가지고 포화이진트리를 만들었을 .. 2023. 7. 22. 백준 2023번 신기한 소수 - C++ 풀이 1. 길이 n짜리 신기한 소수의 집합을 P(n)이라고 하면 P(n) = (P(n-1)*10 + i) 중 소수인 것의 집합 (단, i는 0 ≤ i ≤ 9) 1. 길이 n짜리 신기한 소수의 집합을 P(n)이라고 하면 P(n) = (P(n-1)*10 + i) 중 소수인 것의 집합 (단, i는 0 ≤ i ≤ 9) 길이 n짜리 신기한 소수 x가 있다고 하자. 그럼 x[0...(n-2)] 또한 신기한 소수이다. 따라서 재귀를 이용하여 구할 수 있다. 길이 n짜리 신기한 소수의 집합을 P(n)이라고 하면, P(n) = P(n-1)*10+i 중에서 소수인 것의 집합이 된다. 기저 사례는 n=1인 경우이고, 10 미만의 소수 {2, 3, 5, 7}을 리턴해주면 된다. #include #include using names.. 2022. 9. 14. 백준 2630번 색종이 만들기 - 스위프트(Swift) 풀이 + 그림 설명 그림부터 너무 분할 정복처럼 생긴 분할 정복 문제. 1. 색종이를 4개로 쪼갠다. 2. 재귀적으로 4개의 조각에 대해 각각 하얀색과 파란색의 개수를 센다. 3. 4개 조각에서 구한 하얀색과 파란색의 개수를 더해 전체 개수를 구한다. 4. 만약 4개 조각이 모두 같은 색인 경우, 같은 색이 4개 있는 것이 아니라 큰 하나의 색종이인 것을 조심한다. 1. 색종이를 4개로 쪼갠다. 모두 같은 색이면 더 이상 자르지 말라고 했다. 하지만 생각을 달리해서 일단 자른 다음에, 모두 같은색이면 다시 붙일 것이다..! 2. 재귀적으로 4개의 조각에 대해 각각 하얀색과 파란색의 개수를 센다. 다음과 같은 함수를 정의했다. 전체 종이에서 (row, col)이 왼쪽 꼭짓점이고, 크기가 size인 조각 내의 (하얀색 수, 파.. 2022. 1. 16. 이전 1 다음 반응형
