일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
- issac3d
- 리플렉션 시스템
- fruitspuzzle
- 프로그래머스
- 코딩테스트
- 프로젝트
- 최대값과 최솟값
- network model
- gameinstancesubsystem
- Summer/Winter Coding
- timelessadventure
- unrealengine
- 백준
- fabrik ik
- 2022 kakao
- 2018 kakao
- unity
- pcce 기출문제
- Algorithm
- enetrole
- 2019 kakao
- pccp 기출문제
- 구현
- c#
- 당구 연습
- C++
- Unreal Engine
- ai controller
- 로컬 네트워크 연결
- netmode
- Today
- Total
LeeTaes 공부노트
[백준 / C++] 222-풀링 (실버2, 17829) 본문
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-풀링을 반복해서 적용하여 크기를 1×1로 만들었을 때 어떤 값이 남아있을지 궁금해한다.
랩실 활동에 치여 삶이 사라진 종욱이를 애도하며 종욱이의 궁금증을 대신 해결해주자.
입력
첫째 줄에 N(2 ≤ N ≤ 1024)이 주어진다. N은 항상 2의 거듭제곱 꼴이다. (N=2K, 1 ≤ K ≤ 10)
다음 N개의 줄마다 각 행의 원소 N개가 차례대로 주어진다. 행렬의 모든 성분은 -10,000 이상 10,000 이하의 정수이다.
출력
마지막에 남은 수를 출력한다.
예제 입력 1
4
-6 -8 7 -4
-5 -5 14 11
11 11 -1 -1
4 9 -2 -4
예제 출력 1
11
예제 입력 2
8
-1 2 14 7 4 -5 8 9
10 6 23 2 -1 -1 7 11
9 3 5 -2 4 4 6 6
7 15 0 8 21 20 6 6
19 8 12 -8 4 5 2 9
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
예제 출력 2
17
문제 풀이
이번 문제는 분할과 재귀로 가장 작은 사각형(2 x 2)부터 가장 큰 사각형 (n x n)까지 두 번째로 큰 수를 반환해야 하는 문제입니다.
가장 먼저 2 x 2 사이즈의 2번째 크기를 반환하는 로직을 세웠다면, 2 x 2 사이즈의 4개 칸을 순회한 결과물로 4 x 4 사이즈를 2 x 2로 보고 다시 동일한 로직을 수행할 수 있습니다.
즉, 다음과 같은 순서로 문제를 해결하게 되었습니다.
1. 2 x 2 사이즈의 2번째 큰 수를 반환하는 로직 세우기
// 기저사례 (사이즈가 2x2인 경우)
if (size == 2)
{
vector<int> v;
for (int i = startY; i < startY + 2; i++)
for (int j = startX; j < startX + 2; j++)
v.push_back(adj[i][j]);
// 2번째로 큰 수를 찾아 반환합니다.
return FindSecondNum(v);
}
2. 위에서 반환받은 값들을 토대로 다시 n x n에서 2번째 큰 수를 구하기
vector<int> v;
v.push_back(Go(startX, startY, size / 2));
v.push_back(Go(startX + (size / 2), startY, size / 2));
v.push_back(Go(startX, startY + (size / 2), size / 2));
v.push_back(Go(startX + (size / 2), startY + (size / 2), size / 2));
return FindSecondNum(v);
난이도는 그리 높지 않았다고 생각되지만 저는 재귀 로직을 짜는 것이 미숙하기에 적절하게 어려운 문제였다고 생각됩니다.
코드
풀이 시간 : 14m 1s
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n;
vector<int> adj[1025];
int FindSecondNum(vector<int> v)
{
sort(v.begin(), v.end());
return v[2];
}
int Go(int startX, int startY, int size)
{
if (size == 2)
{
vector<int> v;
for (int i = startY; i < startY + 2; i++)
for (int j = startX; j < startX + 2; j++)
v.push_back(adj[i][j]);
return FindSecondNum(v);
}
vector<int> v;
v.push_back(Go(startX, startY, size / 2));
v.push_back(Go(startX + (size / 2), startY, size / 2));
v.push_back(Go(startX, startY + (size / 2), size / 2));
v.push_back(Go(startX + (size / 2), startY + (size / 2), size / 2));
return FindSecondNum(v);
}
int main()
{
// input
cin >> n;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
int temp = 0;
cin >> temp;
adj[i].push_back(temp);
}
}
vector<int> temp;
cout << Go(0, 0, n);
}
'코딩테스트 > 백준 (Study)' 카테고리의 다른 글
[백준 / C++] 과일 탕후루 (실버2, 30804) (0) | 2024.09.04 |
---|---|
[백준 / C++] 탑 (골드5, 2493) (0) | 2024.09.03 |
[백준 / C++] 영역 구하기 (실버1, 2583) (0) | 2024.09.02 |
[백준 / C++] 쿼드트리 (실버1, 1992) (0) | 2024.09.02 |
[백준 / C++] 편의점 2 (실버2, 14400) (0) | 2024.09.01 |