목록백준 (183)
Study hard
https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1≤N ≤64의 범위를 가진다. 두 번째 줄부터는 길이 N 의 문자열이 N 개 들어온다. 각 문자열은 0 또는 www.acmicpc.net [풀이] 분할 정복으로 풀었다. 1. 현재 크기 n인 영상 안에 다른 숫자가 있는지 확인 2. 다른 숫자가 있으면 '(' 출력 후 n=n/4크기의 4개의 영상에 대해 1번 반복, 4개의 영상에 대한 재귀 끝나면 ')' 출력 3. 영상의 크기가 1이거나 영상 안에 다른 숫자가 없을 경우 영상안에 있는 숫자 출력 ※입력에 띄어쓰기가 없으므로 char배열에 한 글자씩 입력받거나 scanf(..
https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net [풀이] 하노이의 탑 알고리즘 아래 순서대로 재귀 1. 맨 아래 원판을 제외하고 나무지 원판 모두를 tmp장대로 옮긴다. 2. 맨 아래 원판을 to장대로 옮긴다. 3. 남은 tmp장대에 있는 판 모두 to장대로 옮긴다. 옮긴 횟수를 출력한 뒤 수행 과정을 출력해야 하므로 vector에 수행과정을 정장해두고 재귀가 끝난 뒤 한꺼번에 출력해주었다. #include #include #inc..
https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다. www.acmicpc.net [풀이] 분할 정복으로 풀었다. 종이의 크기가 1*1이거나 종이에 쓰여 있는 수가 모두 같을 경우 해당 수로 채워진 종이의 개수를 추가하였다. 만약 종이에 쓰여있는 수 중 다른 게 있으면 현재 종이를 9등분한 정보를 인수로 재귀함수를 호출하였다. #include using namespace std; #define Max 2187//3^7 int N; int Paper[Max][Max];..
https://www.acmicpc.net/problem/11728 11728번: 배열 합치기 첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000) 둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거�� www.acmicpc.net [풀이] mergesort의 merge를 차용하여 풀었다. cin, cout을 쓰면 시간 초과가 떠서 printf와 scanf를 사용하였다. #include using namespace std; #define Max 1000000 int N, M; int A[Max], B[Max]; int C[Max+Max]; void solution() { cin >> N..
https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net [풀이] 10815번 숫자 카드와는 다르게 상근이가 해당 숫자 카드를 몇 개 가지고 있는지 확인하는 문제였다. 기본 이분탐색으로는 카드의 유무만 판단할 수 있기 때문에 upperbound와 lowerbound를 구하는 방식을 사용했다. upperbound는 찾으려는 값보다 큰 값이 처음 나오는 위치이고, lowerbound는 찾으려는 값 이상인 값이 처음 나오는 ..
https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net [풀이] 상근이가 가진 숫자카드를 배열에 저장하고 정렬해 놓고, 확인할 카드가 입력될 때마다 이분 탐색으로 해당 수가 있는지 확인하였다. 입출력 때문에 시간 초과가 나서 cin.tie(0)과 ios_base::sync_with_stdio(false)를 추가해줬다. #include #include //sort using namespace std; #define Max ..