Development Artist

도입 백준 단계별 풀기에서 이분탐색 첫 번째 문제이다. 풀이 1. 이분탐색이 무엇인가! 쉽게 얘기해 보자면 인덱스값을 나타내는 변수를 하나 두고, 반씩 쪼개면서 찾는 방법이다. 0~99까지의 정수를 가지는 크기 100의 배열이 있다. 오름차순으로 정렬이 되어있다. 인덱스 0에 0이 인덱스 1에 1이 있는 그런 배열이다. 여기서 62를 찾으려고 한다. 기존의 경우, for문으로 0부터 차례대로 찾는다면 62번을 for문 안을 반복 한다. 이분탐색에서, mid라는 변수에 "배열의 길이/2"로 초기화하고 한번씩 수행할 때마다 mid=mid/2를 수행한다고 해보자. (여러 추가적인 것들 다 배제하고) 그렇다면 처음 mid값:50, 찾는 수(62)는 50보다 크니, 다음 51(mid+1)~99(right)사이의 ..

도입 백준 단계별 풀기에서 분할정복 여덟 번째 문제이다. 풀이 1. n이 매우 크다. - 점화식으로 푸는 DP 방법 = $O(N)$ -> 비추천 - 행렬로 변환한 풀이법(행렬 거듭제곱) - $O(M^3 * logN)$ -> 사용 2.1. 점화식을 행렬로 변환해보자. 2.2. 여기서 f1 과 f2 는 1이다. 그리고 거듭제곱 결과의 2x2 행렬을 a b c d로 치환하면 2.3. $F_{n+2} = a+b$ 이고 $F_{n+1} = c+d$가 된다. 2.4. 이제 $F_{n}$을 구해보자. n에 n-1을 대입한다. 그렇다면 n-1의 거듭제곱을 구하고 2번째 행의 2개 값을 더해주면 된다. 3. 곱셈 연산자 오버로딩을 사용한다. c++에서는 '연산자 오버로딩'을 찾아보면 더 자세한 내용들이 많을 것이다. p..

도입 백준 단계별 풀기에서 분할정복 일곱 번째 문제이다. 풀이 1.1. 행렬의 거듭제곱을 어떤식으로 할 것인가! 정사각형 행렬 A를 13번 거듭제곱을 한다고 가정해보자. A의 제곱부터 차례차례 A를 곱하는 방법이 있다. 하지만, 이렇게 하지 않는다. $A^{13}$이 $(A^6)^2*A$ 으로 표시할 수 있고, 여기서 $A^6$을 알고 있다면? 제곱연산을 2번만 하면 된다. 1.2. 지수가 홀수인가, 짝수인가. 홀수라면 $(A^k)*A$ 일 것이고, 짝수라면 $(A^k)^2$ 으로 표현할 수 있다. 1.3. 13을 2진법으로 표현해보자. $1101_2$ 이다. MSB로 계산을 한다. (LSB아님) 1일 때는 홀수로 계산하고 0일때는 짝수로 계산. 1 - $(A^0)^2*A$ = $A$ 1 - $(A^1)..

도입 백준 단계별 풀기에서 분할정복 두 번째 문제이다. 풀이 1. 앞의 '색종이 만들기' 문제와 유사하다. 재귀함수를 활용한다. 정사각형을 4개씩 쪼개면서 재귀함수를 호출하는 방식은 같으나, 출력에서 '('와 ')'를 해주어야 하는데 어디서 해야할까? 4개씩 재귀를 호출하는 곳에서 시작에서 '('를 해주고 재귀를 마칠때 ')'를 출력해주면 된다. 함수call의 특성에서 a라는 함수가 수행 되는 중 b라는 함수가 call이 되면 a 함수는 사라지는 것이 아니다. stack구조 처럼 생각하자. a함수 수행 중 b함수가 call이 되면 a함수는 stack에 push된다(대기한다). 그리고 b가 다 수행이 되면 a함수가 stack에서 pop되면서 이전의 수행지점을 찾아 그 이후부터 수행이 된다. 따라서, a함수..