728x90 분할 정복 썸네일형 리스트형 [백준알고리즘] 17829번: 222-풀링-C++ 17829번: 222-풀링 (acmicpc.net) 17829번: 222-풀링 조기 졸업을 꿈꾸는 종욱이는 요즘 핫한 딥러닝을 공부하던 중, 이미지 처리에 흔히 쓰이는 합성곱 신경망(Convolutional Neural Network, CNN)의 풀링 연산에 영감을 받아 자신만의 풀링을 만들고 이를 22 www.acmicpc.net 다른 문제를 풀다가.. 틀렸습니다에 고생하고 있다. 그래서 머리 식힐 겸 실버 문제를 풀어봤다. (그런데 한번 틀렸다 ㅎ) 이 문제가 가장 쉬운 형태의 분할 정복 문제 중의 하나라고 생각한다. 문제 풀이 분할 정복을 적용하면 쉽게 문제를 통과할 수 있다. 단순하게 큰 행렬(matrix)를 \(2 \times 2\) 크기로 나눠서 두 번째로 큰 값을 뽑아낸다. 그렇게 뽑아낸 값.. 더보기 [백준알고리즘] 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.. 더보기 [백준알고리즘] 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로 변경해주었.. 더보기 [백준알고리즘] 1802번: 종이 접기 -C++ [백준알고리즘] 1802번: 종이 접기 -C++ 1802번: 종이 접기 (acmicpc.net) 1802번: 종이 접기 첫째 줄에 테스트 케이스의 개수 T가 주어진다. T는 1000보다 작거나 같은 자연수이다. 둘째 줄부터 T개의 줄에 각각의 종이가 어떻게 접혀있는지가 주어진다. 종이의 정보는 문자열로 주어지며, 1 www.acmicpc.net 문제만 읽었을 때는 되게 어려운 문제라고 생각했다. 문제를 푸는 방법을 찾았을 때도 시간 초과가 괜찮을지 걱정했었는데 여유로운 시간이었다. 정답 비율만 보고 살짝 어려운 문제인가 싶었는데 실버 문제는 실버 문제였다. 분할 정복으로 분류되어 있는데, 분할 정복인가.. 싶긴 하다. 문제 풀이 문제의 내용은 사실 대부분이 불필요한데 괜히 길다. 아무튼 원룡이가 막 접었.. 더보기 [백준알고리즘] 11729번: 하노이 탑 이동 순서 -Python [백준알고리즘] 11729번: 하노이 탑 이동 순서 -Python https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다. 이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다. 아래 그림은 원판이 5 www.acmicpc.net 오랜만에 하노이탑 문제를 푼 것 같다. 분할 정복 문제.. 더보기 [백준알고리즘] 2740번: 행렬 곱셈 -Python [백준알고리즘] 2740번: 행렬 곱셈 -Python https://www.acmicpc.net/problem/2740 2740번: 행렬 곱셈 첫째 줄에 행렬 A의 크기 N 과 M이 주어진다. 둘째 줄부터 N개의 줄에 행렬 A의 원소 M개가 순서대로 주어진다. 그 다음 줄에는 행렬 B의 크기 M과 K가 주어진다. 이어서 M개의 줄에 행렬 B의 원소 K개가 차례대로 주어진다. N과 M, 그리고 K는 100보다 작거나 같고, 행렬의 원소는 절댓값이 100보다 작거나 같은 정수이다. www.acmicpc.net 분할 정복까지는 아닌 것 같지만 소개에도 "행렬의 거듭제곱을 계산하기 전에 먼저 풀어야 할 문제"라고 나와있다. 행렬의 곱셈을 할 줄만 안다면 코드를 짜는 건 쉽기 때문에 코드만 올린다. 이 문제 역시.. 더보기 이전 1 2 다음
