민우의 코딩노트

1. Binary Search단순 Binary Search 코드이다.정렬된 배열에서 특정 값을 찾는 효율적인 알고리즘이다. 검색 범위를 절반씩 줄여나가면서 목표 값을 찾는다.l = 0, r = n-1으로 초기화한 다음에, 중간 값을 찾아서, 범위를 좁혀나간다.a[m] > x 인 경우, 즉 m의 배열값이 x보다 큰 경우 r = m-1로 설정한다. (0~m-1 탐색)a[m]   증명 (Proof by Invariant)invariant는 불변 법칙이다. invariant를 설정하고, invariant가 깨지지 않음을 통해 증명한다.a[i] = x 라면, i는 l과 r의 인덱스 범위 안에 무조건 있을 것이다. 이는 l과 r이 아무리 변해도, a[i] = x인 i는 l과 r의 인덱스 범위 안에 무조건 있기 ..

[문제] https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net [풀이] 이전 문제와 똑같이 재귀함수로 푸는 문제이다. vector를 이용하여 쿼드트리를 저장하였음. test함수에서 모두 0, 1로 되어있는지 판단하고, 아니면 false, 맞으면 true 값을 반환하였다. true인 경우 1 혹은 0을 벡터에 넣어 쿼드 트리 완성, 괄호는 재귀함수에 넣을때 같이 벡터에 넣어주었고 숫자 사이에 괄호를 없애서 문제를 풀었다. [코드] #inc..

[문제] https://www.acmicpc.net/problem/2630 [해결 방법] 우선 void check(int x, int y, int N) 함수를 정의하여, 재귀 함수를 통해 풀려고 하였다. (x, y는 판 내 좌표, N은 전체 종이의 크기) 첫번째로, 일단 (0,0) 좌표와 사용자에게 입력받은 N(그림에서는 8)을 check 함수에 인자로 전달하였다. 그리고 for문을 통해서 check(x,y,N/2)를 통해 (그림 내에서) 8 X 8 -> 4 X 4 -> 2 X 2 -> 1 X 1 이런식으로 분할하려고 하였다. bool test(int x, int y, int N) 은 주어진 좌표에서 (x,y) ~(가로 + N, 세로 + N) 만큼 범위에서 같은 수 인지 아닌지 파악하는 함수이다. 만약 ..