프로그래민👨‍💻

분할정복을 이용하여 해결할 수 있던 문제였다. 이 문제 같은경우 맨처음 문제자체를 이해하지 못하였다. 하지만 분할정복이라는게 떠올랐고, 머지소트와 비슷한 원리로 접근해보았다. 우선 7일을 출력하기 위해 result란 이차원배열을 만들어두고, 분할정복을 시도하였다. 우선 start와 end값을 받고, 이들의 중간값인 mid를 구하게 된다. 이렇게 start~mid, mid~end 까지 두 그룹으로 나누고 알파벳을 각 각 배정해준다. 이렇게 되면 두그룹은 서로 한번은 적으로 만나는 것이 보장이되게 된다. 이런식으로 재귀호출하여 분할정복을 적용해보았다. 단 맨끝 결과에 오로지 B로만 차있는 경우가 생기게 되는데 이경우엔 A를 임의로 하나 넣어주었다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ..

재귀를 이용한 분할정복 문제였다. 처음에 문제를 보고 이해하는데 오래걸렸다. 이문제는 전체 그림을 4등분하여 같은 숫자를 가진다면 하나의 숫자로 묶는 문제였다. 찾아야하는 범위의 숫자가 계속 반(나누기2) 되는 성질을 보니 재귀를 이용하여 풀수 있을 것 같았다. 그래서 함수 하나를 만들었고, 조건을 만족하지 못한다면 4방향에 대해 범위를 반으로 줄여서 계속 호출해주었다. 이 문제를 풀면서 100%에서 계속 틀렸었는데, 이유는 N=1, N=2인 경우에 문제와 다르게 푼경우가 생겼기에 계속 틀렸다. 항상 예외처리를 할땐 최대와 최소를 의심하는 습관을 들여야겠다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 3..

간단해보이는 문제지만 다양한 개념들이 사용된 문제이다. 다음과 같은 개념들이 사용되었다. 모듈러연산의 특징 모듈려는 /을 제외한 +, -, * 에 대해서 다음과 같은 특징을 가진다. (a mod n + b mod n) mod n = (a + b) mod n (a mod n - b mod n) mod n = (a - b) mod n (a mod n * b mod n) mod n = (a * b) mod n 합동관계 두 a, b숫자가 n을 mod한 결과 값이 같다면 모듈러 합동관계라 한다. 즉, a mod n = b mod n의 관계를 a ≡ b (mod n)으로 표현할 수 있다. 페르마의 소정리 p가 소수이고 a가 p로 나누어지지 않는 정수이면 다음과 같은 특징을 가진다. a^p ≡ a (mod p) a^..

재귀를 이용하여 분할정복을 하는 문제이다. 아이디어를 생각하기까지 오랜시간이 걸렸다. 삼각형의 가장 꼭대기 점을 기준으로 아래에 있는 두 개의 삼각형을 호출해주는 형식으로 풀었다. 그리고 기저조건으로는 높이로 가져가는 size가 3이 되면 출력해주도록 해주었다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 package chap06; import java.io.BufferedReader; import java.io.InputStreamReader; public clas..

재귀를 이용하여 분할정복하는 문제이다. func(int i, int j, int size) 함수를 이용하여 size==1이 될때까지 계속 호출하는 형태로 재귀를 반복하게 된다. 기저조건은 size가 1이 될때 cnt++를 해주고 return을 한다. 재귀는 Z모양으로 4번을 호출하게 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 package chap06; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public..

재귀를 이용하는 기초적인 문제이다. 주어진 숫자의 범위가 2,147,483,647이므로 일반적인 방법으로 접근하면 시간초과가 발생할수밖에 없다. 따라서 재귀를 사용해야하는데 위와 같은 성질을 이용하여 재귀를 사용해준다. 즉, 지수를 계속 제곱해준다는 개념으로 접근하여 B의 값까지 도달하는 것을 구하는 방법으로 해결하면 되는 문제이다. 기저조건으로는 B의 값이 0이 될때를 사용하였다. 또한 보통 분할정복을 사용하는 알고리즘은 3가지의 구성요소를 가지고있다. 1. 문제를 더 작은 문제로 분할하는 과정 (divide) 2. 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정 (merge) 3. 더 이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제 (base case) 1 2 3 4 5 ..