재귀6 [백준 24460] 특별상이라도 받고 싶어 (C++) 문제HCPC 2021에 참석한 N×N명의 사람들이 의자가 정사각형 형태로 배치된 대회장에서 대회를 한다. 모든 의자에는 서로 다른 추첨번호가 적혀있으며 HCPC 2021의 마지막에는 아래에 설명된 규칙에 따라 특별상을 받을 사람 한 명을 정한다.특별상을 받을 수 있는 사람이 한 명이라면, 그 사람이 뽑힌다.그렇지 않은 경우, 대회장을 같은 크기의 정사각형 네 개로 나누어 각 구역에서 이 규칙을 재귀적으로 적용해서 구역마다 한 명씩 총 네 명을 뽑는다.뽑힌 네 명 중 의자에 적힌 추첨번호가 두 번째로 작은 사람이 뽑힌다.HCPC 2021에 참가한 지원이는 자신의 실력이 부족해서 수상권이 아니라고 생각하였고, 실력과 무관하게 받을 수 있는 특별상을 노리고 있다.아래 예시를 참고하자. 따라서, 추첨번호 3이 .. 2025. 3. 30. [백준 21870] 시철이가 사랑한 GCD (C++) 문제Q1. 사막에서 바늘을 찾는 방법은?A1. 대학원생을 시킨다.Q2. 신촌에서 자취방을 구하는 방법은?A2. 대학원생을 시킨다.연희동 최고의 대학원생 시철이는 오늘도 바쁘다. 그런 시철이도 이번 주말만큼은 꼭 해야 하는 일이 있었는데, 바로 자취방을 구하는 일이다!시철이는 신촌에서 가장 아름다운 자취방을 구하고 싶다. 하지만 시철이는 매우 바빴기 때문에 직접 방을 찾아다닐 수 없었다. 그래서 시철이는 인터넷에서 본 매물번호와 GCD(Greatest Common Divisor, 최대공약수)를 이용해 자취방의 아름다움을 예측하려 했다. 아름다움을 측정하는 자세한 방법은 다음과 같다.매물번호를 나타내는 정수 배열 S가 있다. (|S|=N, |S|는 S의 원소의 개수)배열 S의 원소를 왼쪽부터 ⌊|S|2⌋$\.. 2025. 3. 6. [백준 10872] 팩토리얼 (C++) https://www.acmicpc.net/problem/10872문제0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오. 입력첫째 줄에 정수 N(0 ≤ N ≤ 12)이 주어진다. 출력첫째 줄에 N!을 출력한다. 문제 풀이dp 혹은 재귀를 이용하는 문제. N이 12까지이므로 dp나 재귀 어느쪽을 사용해도 된다. dp는 작은 수부터 계산하고 해당 값을 저장하여 이전에 저장한 값을 이용하며, 재귀는 N부터 숫자를 줄여나가며 이후에 구해질 값에 숫자를 곱하는 방식으로 구현된다. 아래는 코드.더보기#include using namespace std;long long fac(int N){ if (N > N; cout 2024. 12. 12. [백준 5639] 이진 검색 트리 (C++) https://www.acmicpc.net/problem/5639문제이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다. 예를 들어, 위의 이진 검색 트리의 전위 순회 결과는 50 30 24 5 28 45 98 52 60 이고, 후위 순회 결과는 5 28 24 45 30 60 52 .. 2024. 10. 11. [백준 17829] 222-풀링 (C++) https://www.acmicpc.net/problem/17829문제조기 졸업을 꿈꾸는 종욱이는 요즘 핫한 딥러닝을 공부하던 중, 이미지 처리에 흔히 쓰이는 합성곱 신경망(Convolutional Neural Network, CNN)의 풀링 연산에 영감을 받아 자신만의 풀링을 만들고 이를 222-풀링이라 부르기로 했다.다음은 8×8 행렬이 주어졌다고 가정했을 때 222-풀링을 1회 적용하는 과정을 설명한 것이다행렬을 2×2 정사각형으로 나눈다.각 정사각형에서 2번째로 큰 수만 남긴다. 여기서 2번째로 큰 수란, 정사각형의 네 원소를 크기순으로 a4 ≤ a3 ≤ a2 ≤ a1 라 했을 때, 원소 a2를 뜻한다.2번 과정에 의해 행렬의 크기가 줄어들게 된다.종욱이는 N×N 행렬에 222-풀링을 반복해서 적.. 2024. 9. 5. [백준 16974] 레벨 햄버거 (C++) https://www.acmicpc.net/problem/16974 문제상근날드에서 오랜만에 새로운 햄버거를 출시했다. 바로 레벨-L 버거이다. 레벨-L 버거는 다음과 같이 만든다.레벨-0 버거는 패티만으로 이루어져 있다.레벨-L 버거는 햄버거번, 레벨-(L-1) 버거, 패티, 레벨-(L-1)버거, 햄버거번으로 이루어져 있다. (L ≥ 1)예를 들어, 레벨-1 버거는 'BPPPB', 레벨-2 버거는 'BBPPPBPBPPPBB'와 같이 생겼다. (B는 햄버거번, P는 패티)상도가 상근날드에 방문해서 레벨-N 버거를 시켰다. 상도가 햄버거의 아래 X장을 먹었을 때, 먹은 패티는 몇 장일까? 한 장은 햄버거번 또는 패티 한 장이다. 입력첫째 줄에 N과 X가 주어진다. 출력첫째 줄에 상도가 먹은 패티의 수를 출.. 2024. 8. 24. 이전 1 다음
