💻 OnlineJudge/Baekjoon

[백준 / BOJ] C++ 11279 최대 힙

https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 문제 풀이 그냥 간단하게 우선순위큐로 구현하여 풀 수 있다. 다만 시간초과가 계속나서 신경을 써야한다.. 시간제한 1초라니 C++ 개행을 endl로 해도 시간초과가 날정도로 짧다. 아래는 코드이니 참조하자. Code ( C++ ) #include #include using namespace std; int main() { ios::sync_with_stdio(false); ..

[백준 / BOJ] C++ 1992 쿼드트리

https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 문제 풀이 이 문제는... 처음에 이해하는게 힘들었다. 풀이 하자면 문제에서 요구하는 방법은 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 즉 Z 순서로 숫자를 비교하고 탐색하는 것이다. 위 이미지 같은 경우 (01(1101)(0011)이 되는것 이다. 그렇다면, N은 항상 2의 제곱수로 주어지니, 첫번째로 영상의 모든 수가 동일한지 확인하고, 동일하지 않다면 모든 비디오 영상을 4..

[백준 / BOJ] C++ 1780 종이의 개수

https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 문제 풀이 한변의 크기가 N인 정사각형을 입력받는다. 입력 받은 후 문제에서 제공되는 조건으로 종이를 자르거나 더해주거나 한다. 우선 전체 입력받을 종이 3^7 사이즈 2차원 배열과, 결과값을 저장할 result 배열을 선언한다. 다음 해당 종이의 행과 열의 숫자들을 비교하고, 모두 동일한 수인지 판단을 한다. 동일한 수가 아닐 경우, 입력받은 크기 N에 3을 나누어 해당 크기만큼 다시..

[백준 / BOJ] C++ 1764 듣보잡

https://www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net 문제 풀이 N 만큼 입력받은 문자열들과 M만큼 입력받은 문자열들 중, 겹치는 문자열을 정렬한채로 출력하는 문제이다. 알파벳 순으로 정렬되는 기능인 sort를 사용하였고, 입력되는 문자열들은 vector에 저장하였다. 그리고 겹치는 문자열이 있는지 유무 확인은 이진탐색(binary_search)으로 하였다. 이후 겹치는 문자열들을 출력할 vector에 저장하고, 출력하였다. 특정한 알고리즘을 사용..

[백준 / BOJ] C++ 1676 팩토리얼 0의 개수

https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 풀이 팩토리얼 계산을 하게되면 적은숫자면 모르지만 큰수를 입력할 경우 오버플로우 오류가 생긴다. (숫자가 너무 커서) 문제를 풀어서 생각해보면, 0이 아닌 숫자가 나올 때 까지 0의 개수를 구하는것이다. 처음 0이 아닌 숫자가 나오는 경우는 10의 거듭제곱 밖에 없다. 결국 10은 2와 5로 소인수 분해를 할 수가 있다. 숫자는 2부터 입력받은 수까지 반복하며 소인수 분해한 2와 5중 더 작은 개수를 출력하면 된다. Code ( C++ ) #include using namesp..

[백준 / BOJ] C++ 1463 1로 만들기

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 풀이 문제에서 주어지는 조건은 3가지이다. 1. X가 3으로 나누었을때 나누어 떨어지면 3으로 나눈다. 2. X가 2로 나누었을때 나누어 떨어지면 2로 나눈다. 3. 그냥 1을 뺀다. 예시로 확인해보자. 1의 경우는 연산작업이 필요가 없기에 연산 수는 0 2의 경우는 2로 나누어떨어지기에 연산 횟수는 1 3의 경우는 3으로 나누어 떨어지기에 연산회수는 1 10의 경우에는 (10 - 1) / 3 / 3의 연산을 해야하기에 연산 횟수는 3 이를 따라, 점화식을 구해보자면 2의 경우는 dp[i] = dp[i/2..

[백준 / BOJ] C++ 2798 블랙잭

https://www.acmicpc.net/problem/2798 2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장 www.acmicpc.net 문제 풀이 브루트포스 알고리즘의 가장 전형적인 예이다. 3장의 카드들이 입력된 M보다 작아야하며 가장 큰 수를 완전탐색하면된다. 아주 간단한 문제인 브루트포스 알고리즘 입문 문제이다. 근데 실제로 브루트포스 알고리즘은 나는 잘 안쓰게된다... Code ( C++ ) #include #include using namespace std; int N, M; int ans..

[백준 / BOJ] C++ 1107 리모컨

https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 문제 풀이 브루트포스 알고리즘이다. 문제에서의 함정이있는데, 이동하고자 하는 채널 N은 0 N >> M; for (int i = 0; i > btn; remote[btn] = true; } int result = abs(100 - N); for (int i = 0; i 0) { int b = abs(N - i); if (result >..