코린이의 소소한 공부노트

1. Input 1) int[] nums 2. Output 1) nums의 요소들로 높이 균형 이진 검색 트리를 만들어서 반환 - 답이 여러 가지일 경우 1개만 반환 3. Constraint 1) 1

N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. (1) 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다. (2) (1)이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다. 이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오. 1. 입력 - 첫째 줄에 N(1 ≤ N ≤ 3^7, N은 3^k 꼴)이 주어진다. - 다음 N개의 줄에는 N개의 정수로 행렬이 주어진다. 2. 출력 - 첫째 줄에 -1로만 채워진 종..

흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다. 흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축하여 간단히 표현할 수 있다. 주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과는 "1"이 된다. 만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지를 못하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영상으로 나누어 압축하게 되며, 이 4개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현한다. 위 그림에서 왼쪽의 영상은 오른쪽의 배열과 같이 숫자로 주어지며, 이 영상을 쿼드..

한수는 크기가 2^N × 2^N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 크기가 2^(N-1) × 2^(N-1)로 4등분 한 후에 재귀적으로 순서대로 방문한다. N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오. 1. 입력 - 첫째 줄에 정수 N, r, c가 주어진다. - 1 ≤ N ≤ 15 - 0 ≤ r, c < 2^N 2. 출력 - r행 c열을 몇 번째로 방문했는지 출력한다. 3. 예제 4. 코드 1) 첫 코드 - 맞긴 하나 시간초과 import java.util.*; import java.io.*; class Main { st..

1. Problem - nCk를 계산해보자. 2. Input 1) 음이 아닌 정수 n 2) 음이 아닌 정수 k - 이때 k

1. Problem - 두 개의 n*n 행렬의 곱을 해보자. 여기서 n은 2의 거듭제곱이다. - 슈트라센은 행렬을 4개로 나눠서 계산하는 방식을 택했다. 2. Input 1) 행렬의 길이 n 2) n*n 행렬 A 3) n*n 행렬 B 3. Output 1) A와 B의 곱이 담긴 행렬 C 4. PseudoCode void strassen(int n, matrix A, matrix B, matrix C){ if(n

1. Problem - n개의 key를 오름차순으로 정렬해보자 - 퀵 정렬은 특정 값(pivot)을 기준으로 그 값보다 작은 것과 큰 것으로 나눠서 정렬한다. 2. Input 1) 양수 n 2) 배열 S 1-indexed 3. Output 1) 오름차순으로 정렬된 S 4. PseudoCode void quicksort(index low, index high){ index pivotpoint; if(low 작은 값(1)의 인덱스 -> 작은 값과 pivot의 위치를 바꾼다. -> 1 {2} 6 3 5 4 // -> pivot이었던 2의 위치는 확정됐고, 2의 위치를 기준으로 왼쪽은 2보다 작은 값, 오른쪽은 큰 값이 된다. // 2를 기준으로 나눠진 왼쪽과 오른쪽에 대해서도 퀵 정렬을 똑같이 진행한다. //..

1. Problem - n개의 key를 오름차순으로 정렬하자 2. Input 1) 양수 low 2) 양수 high 3) 배열 S indexed from 1 to n 3. Output 1) 오름차순으로 정렬된 배열 S 4. PseudoCode void mergesort2(index low, index high, keyptype[] S){ index mid; if(low

1. Problem - n개의 key를 오름차순으로 정렬하자 2. Input 1) 양수 n 2) 배열 S indexed from 1 to n 3. Output 1) 오름차순으로 정렬된 배열 S 4. PseudoCode void mergesort(int n, keytype[] S){ if(n>1){ const int h = n/2, m = n-h; keytype U[1..h], V[1..m]; copy S[1]~S[h] to U[1]~U[h]; copy S[h+1]~S[n] to V[1]~V[m]; mergesort(h,U); mergesort(m,V); merge(h,m,U,V,S); } } // 정렬된 배열 U와 V의 요소를 합해서 정렬된 S를 만든다. void merge(int h, int m, co..

1. Problem - 크기가 n인 정렬된 배열 S에서 x를 찾아보자 2. Input 1) 양수 n 2) 오름차순으로 정렬된 S indexed from 1 to n 3) key x 3. Output 1) x의 위치 2) S에 x가 없다면 0 4. PseudoCode index location(index low, index high){ index mid; if(low>high) return 0; else{ mid = floor((low+high)/2); if(x==S[mid]) return mid; else if(x 13 -> 18 static int location(int low, int high, int[] S, int x) { int answer; if(low>high) answer = 0; else..