본문 바로가기
728x90

분할정복

[백준알고리즘] 2104번: 부분배열 고르기-C++ 10090번: Counting Inversions (acmicpc.net) 10090번: Counting Inversions A permutation of integers from 1 to n is a sequence a1, a2, ..., an, such that each integer from 1 to n is appeared in the sequence exactly once. Two integers in а permutation form an inversion, when the bigger one is before the smaller one. As an example www.acmicpc.net 문제를 오랜만에 풀었다. 전에 풀려고 미리 좀 봤었는데 이리저리 바쁜 일정들로 인해 잊고 살았었다. .. 더보기
[백준알고리즘] 2104번: 부분배열 고르기-C++ 2104번: 부분배열 고르기 (acmicpc.net) 2104번: 부분배열 고르기 크기가 N(1 ≤ N ≤ 100,000)인 1차원 배열 A[1], …, A[N]이 있다. 어떤 i, j(1 ≤ i ≤ j ≤ N)에 대한 점수는, (A[i] + … + A[j]) × min{A[i], …, A[j]}가 된다. 즉, i부터 j까지의 합에 i부터 j까지의 최솟값을 곱 www.acmicpc.net 문제를 푸는데 되게 오래걸렸다. 처음에는 세그먼트 트리를 오랜만에 공부하려고 시작한 거라, 공부하는데 시간이 소요됐다. 그러고 나서는 어떻게 적용되면 좋을지 고민하느라 시간이 소요됐다. 마지막으로, 알 수 없는 '틀렸습니다'의 늪에서 헤어나오지 못했다. 게다가 하루에 30분 저도씩 밖에 시간을 못 쓰는 바람에 며칠이 걸.. 더보기
[백준알고리즘] 4779번: 칸토어 집합-C++ 4779번: 칸토어 집합 (acmicpc.net) 4779번: 칸토어 집합 칸토어 집합은 0과 1사이의 실수로 이루어진 집합으로, 구간 [0, 1]에서 시작해서 각 구간을 3등분하여 가운데 구간을 반복적으로 제외하는 방식으로 만든다. 전체 집합이 유한이라고 가정하고, www.acmicpc.net 칸토어 집합이 뭔지 궁금해서 찾아봤다. 칸토어 집합 - 위키백과, 우리 모두의 백과사전 (wikipedia.org) 근데 내용이 뭔 말인지 모르겠어서 일단 풀었다. 문제 자체는 문자열을 이용해 쉽게 풀 수 있었다. 같은 구조가 내부적으로 반복되기 때문에 분할 정복 알고리즘을 이용했다. 문제 풀이 선의 길이가 1이 될 때까지 반복하면서, 선을 계속해서 3등분을 했다. 첫 번째 조각과 마지막 세 번째 조각은 재귀적으.. 더보기
[백준알고리즘] 6549번: 히스토그램에서 가장 큰 직사각형-C++ 6549번: 히스토그램에서 가장 큰 직사각형 (acmicpc.net) 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net 보니까 2년 전에 풀다가 말았던 문제인 것 같다. 파이썬으로 풀려고 시도했던 흔적이 남아있다. 플레티넘 5라고 해서 너무 쉬운 방법은 안 풀릴 거 같았다. 조금 생각해서 스택을 이용해 푸는 방법을 생각했고, 약간 지저분해 보여 조금 아이디어를 가다듬고 문제를 풀었다. 사실 바로 풀릴지 모르고 했는데 돼서 놀랬다. 해당 문제에 대한 게시판.. 더보기
[백준알고리즘] 11444번: 피보나치 수 6 -C++ [백준알고리즘] 11444번: 피보나치 수 6 -C++ 11444번: 피보나치 수 6 (acmicpc.net) 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 골드 난이도면서 정답 비율이 높길래 되게 쉬운 문제인 줄 알았다. 근데 난생처음 보는 풀이를 보고 따라 풀었다. 이 문제를 푸는 방법은 2가지가 있다고 한다. 행렬 곱을 이용한 방법과 방정식을 이용한 방법이다. 아래는 방정식으로 문제를 풀었다. 문제를 푸는 방식은 백준 블로그의 글을 참고했다. 피보나치 수를 구하는 여러가지 방법 (acmicpc.net) 피보나치 수를 구하는 여러가지 방법 피보나치 수는 다음과 같이 정의되는 수열입니.. 더보기
[백준알고리즘] 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(.. 더보기
[백준알고리즘] 10830번: 행렬 제곱 -Python [백준알고리즘] 10830번: 행렬 제곱 -Python https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 빠른 모듈로 거듭제곱을 개념을 이용해 행렬 곱셈을 수행했다. 분할 정복의 개념을 사용했고 아래와 같은 방식에 각 원소마다 모듈로를 해주는 것으로 수행했다. A^11 = A^10 * A^10 * A^1 A^8 = A^4 * A^4 코드 내용은 거의 같으나 @iknoom1107 님의 코드를 보니 for문으로 작성했던 부분을 sum()을 이용해 원소의 값을 구해.. 더보기
[백준알고리즘] 2447번: 별 찍기 10 -Python [백준알고리즘] 2447번: 별 찍기 10 -Python https://www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 첫째 줄에 N이 주어진다. N은 항상 3의 제곱꼴인 수이다. (3, 9, 27, ...) (N=3k, 1 ≤ k < 8) www.acmicpc.net 모든 공간을 *로 채워준 다음에 지워야 할 부분들을 지워주었다. 각 상태에서 9개의 구역을 나눠 가운데에 위치한 구역은 모두 빈칸 ' '을 만들어주어야 한다. 그리고 나눠진 작은 구역들도 반복해서 수행해준다. 아래에 새롭게 푼 코드를 추가했는데 재귀를 사용해서 더 깔끔하게 풀었다. def rm(i, j, size): if size == 1: return new_size = size//3 for ri in .. 더보기
728x90

티스토리툴바