pinevienna blog

알파벳을 숫자로 암호화한 뒤, 다시 알파벳으로 복호화 할 때 발생할 수 있는 모든 경우의 수를 구하는 문제 암호는 두 가지 중 하나이다. 1. 한 자릿수 암호 : 1(A) ~ 9(I) 2. 두 자릿수 암호 : 10(J) ~ 26(Z) 점화식을 세워보자 case1 : 한 자리만 복호화 하는 경우 dp[N] = dp[N] + dp[N-1] case2 : 두 자리를 복호화 하는 경우 dp[N] = dp[N] + dp[N-2] 단, 맨 앞 문자는 두 자리로 해석할 수 없으며 && 두 자리 중 앞자리가 0이라면 해석할 수 없다. 이를 해결하기 위해 입력받은 문자열 앞에 0을 붙여줬고, if문의 조건을 아래와 같이 정해줬다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20..

3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구하는 문제 타일 채우기 아우 지겨워~ 하고 풀었다가 멍청한 나한테 질렸다.. 모든 예외들을 잘 고려해줘야 한다. 1. N이 홀수일 때 해보면 알겠지만 3x1, 3x3, 3x5 ··· N이 홀수일 땐 채울 수 없다. 2. 3x2 3x2의 경우엔 이렇게 세 가지 모양으로 채울 수 있다. 각각을 A, B, C라 칭하겠음! 3. 3x4 1번에 A, B, C + 2번에 A, B, C를 조합하여 채우는 형태로 생각할 수 있다 이러면 3x3=9, 총 9개의 형태로 채울 수 있다!! 하지만 답은 9가 아니다. 3x4부터 예외가 발생한다... 단순히 A, B, C를 조합해서는 만들 수 없는 모양으로, 3x4부터 이런 형태가 등장한다. 이런 경우를 '..

합병 정렬은 배열을 앞부분과 뒷부분으로 나누어 각각 정렬하는 작업을 반복하는 알고리즘이다. n개를 log n번 돌리기 때문에 최선, 평균, 최악 모두 O(n log n)의 시간복잡도를 가진다. 1) 배열을 반으로 나눈다. 2) 각 파티션이 두 개의 요소를 가질 때 까지 계속 반으로 나눠준다. 3) 두 개의 요소를 비교하여 더 작은 요소가 앞으로 오도록 한다. 4) 두 개의 파티션을 비교하여 더 작은 요소가 앞으로 오도록 병합한다. 5) 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 42 43 private static void mergeSo..

퀵 정렬은 분할 정복 알고리즘 중 하나이며 이름처럼 정렬 속도가 매우 빠르다. 최선, 평균 = O(N log N) / 최악 = O(N^2)의 시간복잡도를 가진다. 1) 배열의 정 가운데 요소를 '피벗'으로 정한다. 2) 왼쪽부터 L 커서가 피벗 3보다 큰 값을 탐색, 오른쪽부터 R 커서가 피벗보다 작은 값을 탐색한다. 3) 발견한 값 5와 2를 교환한다. 4) 다시 피벗 3보다 큰 값, 작은 값을 각각 탐색한다. 4와 3을 교환한다. 5) R과 L이 교차했으므로 loop를 종료한다. 이때 L 기준으로 파티션을 나눈다. 왼쪽은 L 보다 작은 값들이 있고, 오른쪽은 큰 값들이 있다. 각 파티션의 요소가 한 개가 될 때까지 퀵정렬을 진행하면 모두 정렬이 되어있다. 1 2 3 4 5 6 7 8 9 10 11 1..

삽입 정렬의 장점은 살리고 단점을 보완하여 만든 정렬 알고리즘이다. 삽입정렬 장단점 장점 : 초기리스트가 "거의 정렬"되어 있을 경우 효율적이다. 단점 : 한 번에 한 요소의 위치만 결정되기 때문에 비효율적이다. 셸 정렬은 정렬할 배열을 subfile로 쪼개서 각 subfile에서 삽입 정렬을 수행한 뒤 마지막에 모두 합쳐서 삽입정렬을 진행한다. (subfile=그룹?) 최선의 경우 O(N), 평균적으로 O(N^1.5), 최악의 경우 O(N^2)의 시간복잡도를 가진다. 각 subfile을 구성할 때는 배열의 k번째 요소를 추출하여 만드는데 이 k를 gap이라고 한다. 단계별로 gap을 줄여 subfile의 요소 개수가 증가시키고 gap이 1이 될 때 까지 반복한다. gap은 보통 배열 전체 길이의 절반에..