Study hard

https://www.acmicpc.net/problem/1517 1517번: 버블 소트 첫째 줄에 N(1≤N≤500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0≤|A[i]|≤1,000,000,000의 범위에 들어있다. www.acmicpc.net [풀이] 버블소트 문제지만 버블소트로 풀면 시간초과가 나온다. (시간복잡도O(n^2)) 그래서 시간복잡도가 O(nlogn)인 mergesort를 사용하여 풀었다. 버블 소트 swap은 인접해 있는 두 수를 바꾸는 것이므로, merge를 할 때 두 수의 앞뒤 순서가 바뀌면 두 수의 거리를 카운트하는 변수에 더하면 된다. #include #include using namespace std; ..

https://www.acmicpc.net/problem/2448 2448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (k ≤ 10) www.acmicpc.net [풀이] 분할 정복을 사용하여 풀어야 한다. 배열 star[N][2 * N - 1] 별을 저장한 다음 재귀함수에서 벗어나면 출력하는 방식으로 했다. 아래와 같이 N이 가장 작은 수인 3일 때의 형태가 기본단위가 된다. 즉, N이 3이 될때까지 재귀를 돌리고, N이 3이 되면 기본단위를 그려주면 된다. 위 형태를 보면 제일 위의 꼭지점 좌표가 (x,y)라고 할 때(x=0, y=N-1), 각 기본단위의 꼭지점의 위치가 (x,y), (x + N/2, y - N/2), (x ..

https://www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 � www.acmicpc.net [풀이] 분할 정복을 이용한 별 찍기 문제였다. 가장 작은 단위는 N이 3일 때 이고, 빈칸의 좌표는 (1,1)이다. 기본 단위가 여러개 붙어있으면 이와 같은 모양이고, 빈칸의 좌표는 (1,1), (1,4), (1,7), (1,10), (1,13), (1,16), (1,19), (1,22), (1,25)이다. 즉, x%3=1이고, y%3=1인 좌표에서 빈칸이 나와야 ..

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];..