Scat

yongmin's dev blog

[BOJ] 1629번 곱셈 - C++

"분할정복"

문제 곱셈 풀이 브루트포스로 하면 시간초과가 나는 문제이다. 분할정복을 통해, 거듭제곱 연산으로 바꾸어 풀어준다. 거듭제곱하는 수가 짝수이면, 반절만큼의 거듭제곱들을 서로 곱해주는 식으로, 홀수이면 반절만큼의 거듭제곱들(소수점 이하 버림 을 서로 곱해준 뒤, 한 번을 더 곱해주는 식으로 분할한다. 결국 1에 도달했을 때는, 그 숫자를 return 함...

Posted by Yongmin on June 23, 2021

[BOJ] 1780번 종이의 개수 - C++

"분할정복"

문제 종이의 개수 풀이 쿼드트리와 비슷한 문제이다. 이 문제는 x,y 좌표 1/3씩 총 9개로 나눠서 합이 NxN이면 모두 1, -NxN이면 모두 -1, 그리고 0은 0이 아닌 수가 나오면 바로 bool 함수를 이용해서 false와 true로 구분해냈다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1...

Posted by Yongmin on June 23, 2021

[BOJ] 1992번 쿼드트리 - C++

"분할 정복"

문제 쿼드트리 풀이 분할정복을 이용한 문제이다. NxN에서 모든 원소의 합이 0이면 0을 출력, NxN이면 모두 1이라는 소리이므로 1을 출력한다. 그렇지 않다면, x, y 좌표를 기억하며, N/2만큼 x, y좌표 각각 떨어진 4개로 분할하여 함수를 호출한다. ( )의 위치는 왼쪽 위가 나오기 전, 오른쪽 아래가 나온 이후로 각각 배치하여 문제의 정...

Posted by Yongmin on June 22, 2021

[BOJ] 1966번 프린터 큐 - C++

"큐, 덱"

문제 프린터 큐 풀이 중요도의 내림차순을 나타내는 imp 어레이와 큐 자료구조로 넣은 기존의 testcase, 그리고, 해당 문서인지 아닌지의 여부를 확인해주는 check 어레이를 선언해주었다. 중요도 순서에 해당되나, 해당 문서가 아니라면(=false) pop을 해주어 printf를 해주면서 cnt를 +1 해주고, 중요도 순서에도 포함 안되고, 해...

Posted by Yongmin on June 21, 2021

[BOJ] 11866번 요세푸스 문제 0 - C++

"큐, 덱"

문제 요세푸스 문제 0 풀이 큐를 이용한 구현 문제이다. N-1개의 앞에 있는 수들을 pop하고 그 숫자들을 뒤로 붙이는 식으로 해서, N번째 수들을 result 함수로 넣은 뒤 형식에 맞게 출력하면 되는 문제이다. 소스 코드 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...

Posted by Yongmin on June 21, 2021

[BOJ] 1874번 스택 수열 - C++

"스택"

문제 스택 수열 풀이 오름차순으로 스택에 넣어둬야 되기 때문에, testcase에 있는 i번째 수가 스택에 쌓아둔 숫자보다 작을 때는 그 숫자를 넣을 수 없게 된다.(s.top() > result[i] ==> NO). 그 외에는 스택에 오름차순으로 숫자를 계속 넣어주며, testcase에 있는 숫자와 s.top()이 같을 때까지 pop을...

Posted by Yongmin on June 19, 2021

[BOJ] 9012번 괄호 - C++

"스택"

문제 괄호 풀이 스택을 이용한 문제이다. ‘(‘가 나왔을 때는 다른 벡터에 push를 해주고, ‘)’가 나왔을 때는 ‘(‘가 담겨져 있던 벡터에 pop을 해주어서 그 괄호가 닫혔다는 것을 의미하게 해주는 것이다. 이 때, ‘)’ 가 나왔을 때는 벡터가 empty상태라면 곧 바로 NO를 출력해주고, 끝까지 도달했을 때, 벡터 안에 원소 ()가 모두 닫...

Posted by Yongmin on June 19, 2021

[BOJ] 10773번 제로 - C++

"스택"

문제 제로 풀이 기본적인 스택문제이다. 스택을 특성을 고려하여 pop_back 함수를 이용하여 마지막 수를 제거한 뒤, 덧셈해주면 된다. 소스 코드 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 #include <iostream> #include <vect...

Posted by Yongmin on June 17, 2021

[BOJ] 2004번 조합 0의 개수 - C++

"정수론 및 조합론"

문제 조합 0의 개수 풀이 0의 개수를 구하는 문제는 2와 5의 문제 중 갯수가 작은 수를 찾는 문제이다. 이 문제 역시도 같은 문제이다. combination 공식에 따라 분자의 팩토리얼에서 나온 2와 5의 개수들을 분모의 팩토리얼에서 나온 2와 5의 개수들을 빼서 2와 5 중 개수가 작은 수를 출력하면 되는 문제이다. 기존 방법으로 O(N^2)으...

Posted by Yongmin on June 16, 2021

[BOJ] 1676번 팩토리얼 0의 개수 - C++

"정수론 및 조합론"

문제 팩토리얼 0의 개수 풀이 10의 i제곱수로 나누었을 때 나누어 떨어지면 그 숫자는 끝에 i개의 0을 가지고 있다. 10은 2와 5로 이루어져있는데, 2x5가 얼마나 곱해졌는지 확인하면 된다. 팩토리얼은 1부터 N까지 모두 곱하는 수이기 때문에, 5의 갯수가 2의 갯수보다 작거나 같게 된다. 그러므로 5의 갯수를 찾으면 된다. 곱해진 수들 각각을...

Posted by Yongmin on June 16, 2021

FEATURED TAGS
Format BOJ C++ Python Algorithm
ABOUT ME

짱구