IT 복수전공 일기장

상근이의 할머니는 아래 그림과 같이 오래된 다이얼 전화기를 사용한다.전화를 걸고 싶은 번호가 있다면, 숫자를 하나를 누른 다음에 금속 핀이 있는 곳 까지 시계방향으로 돌려야 한다. 숫자를 하나 누르면 다이얼이 처음 위치로 돌아가고, 다음 숫자를 누르려면 다이얼을 처음 위치에서 다시 돌려야 한다.숫자 1을 걸려면 총 2초가 필요하다. 1보다 큰 수를 거는데 걸리는 시간은 이보다 더 걸리며, 한 칸 옆에 있는 숫자를 걸기 위해선 1초씩 더 걸린다.상근이의 할머니는 전화 번호를 각 숫자에 해당하는 문자로 외운다. 즉, 어떤 단어를 걸 때, 각 알파벳에 해당하는 숫자를 걸면 된다.예를 들어, UNUCIC는 868242와 같다.할머니가 외운 단어가 주어졌을 때, 이 전화를 걸기 위해서 필요한 최소 시간을 구하는 ..

분할 정복 알고리즘의 또 다른 예제로 행렬의 거듭제곱(Matrix Exponentiation)을 사용할 수 있습니다. 이는 특히 코딩 테스트에서 종종 사용되는 주제입니다. 행렬의 거듭제곱을 이용하면 피보나치 수열 등의 문제를 빠르게 해결할 수 있습니다.문제 설명피보나치 수열의 n번째 숫자를 구하는 문제를 해결하기 위해 분할 정복을 이용한 행렬의 거듭제곱을 사용해보겠습니다. 피보나치 수열은 다음과 같이 정의됩니다:F(0) = 0F(1) = 1F(n) = F(n-1) + F(n-2) for n >= 2행렬의 거듭제곱을 이용하면 O(log n) 시간에 피보나치 수열의 n번째 숫자를 구할 수 있습니다.행렬의 거듭제곱을 이용한 피보나치 수열피보나치 수열을 행렬의 곱셈으로 표현할 수 있습니다:[\begin{bmat..

분할 정복(Divide and Conquer)은 문제를 더 작은 하위 문제로 나누고, 이 하위 문제들을 독립적으로 해결한 후, 그 결과를 결합하여 원래 문제를 해결하는 알고리즘 설계 기법입니다. 이 방법은 문제를 해결하기 위해 세 가지 단계를 거칩니다:분할(Divide): 해결하고자 하는 문제를 동일한 하위 문제들로 나눈다.정복(Conquer): 하위 문제들을 재귀적으로 해결한다. 하위 문제가 충분히 작으면 직관적으로 해결한다.결합(Combine): 하위 문제들의 해를 합쳐서 원래 문제의 해를 얻는다.이제 이 개념을 설명하기 위해 병합 정렬(Merge Sort)을 예제로 사용해 보겠습니다.병합 정렬 (Merge Sort) 예제병합 정렬은 분할 정복 알고리즘을 사용하는 정렬 알고리즘입니다. 다음은 병합 정..

https://www.youtube.com/watch?v=92WHN-pAFCs 정지 문제(Halting Problem)는 컴퓨터 과학 및 계산 이론에서 중요한 개념으로, "어떤 주어진 프로그램과 입력이 있을 때, 그 프로그램이 유한 시간 내에 멈출지 아니면 무한히 실행될지 결정할 수 있는 알고리즘이 존재하는가?"라는 문제입니다. 이 문제는 1936년에 앨런 튜링(Alan Turing)에 의해 제기되었습니다.정지 문제의 정식 정의정지 문제는 다음과 같이 정의됩니다:입력: 프로그램 P와 입력 I.출력: 프로그램 P가 입력 I를 가지고 실행될 때 유한 시간 내에 멈추면 'YES', 그렇지 않으면 'NO'.튜링의 증명앨런 튜링은 정지 문제가 비결정적(non-decidable)임을 증명했습니다. 이는, 어떤 프로..

최장 공통 서열(Longest Common Subsequence, LCS) 문제는 두 문자열이 주어졌을 때, 두 문자열 모두에서 공통으로 나타나는 가장 긴 부분 서열을 찾는 문제입니다. 이 문제를 해결하는 방법을 단계별로 설명하겠습니다.1) 재귀적 관계 파악하기먼저, 두 문자열 (X)와 (Y)의 LCS를 찾기 위해 재귀적 관계를 정의합니다. 각 문자열의 마지막 문자가 일치하는지 여부에 따라 다음과 같은 경우로 나눌 수 있습니다:경우 1: (X)와 (Y)의 마지막 문자가 일치하는 경우이 경우, (X)와 (Y)의 마지막 문자를 LCS에 추가하고, 나머지 부분 문자열에 대한 LCS를 구합니다.예: (X = "ABC"), (Y = "BDC")일 때, 마지막 문자 'C'가 일치합니다. 따라서, LCS("ABC",..

Complexity Analysis특정 입력값에 대한 연산 수연산의 기준: 기본 연산(operation)의 수를 세기점근적 표기법(Asymptotic Notation)단순하게 기본 연산의 수를 세기최악의 경우 분석(Worst-case Analysis)모든 경우를 고려하기 위해 최악의 경우를 따짐평균적 경우(Average Case), 최선의 경우(Best Case)도 고려 가능최악의 경우 분석을 위해 상수는 무시반복의 횟수도 분석: 연산의 시간은 상수for (i = 1; i

재귀함수의 시간복잡도를 분석하는 것은 조금 까다로울 수 있지만, 몇 가지 일반적인 접근 방법을 통해 체계적으로 분석할 수 있습니다. 다음은 재귀함수의 시간복잡도를 분석하는 일반적인 단계입니다.1. 재귀 관계식 세우기재귀함수의 시간복잡도를 분석하려면 먼저 함수의 실행 시간에 대한 재귀 관계식을 세워야 합니다. 이 재귀 관계식은 함수가 호출될 때마다 얼마나 많은 시간이 걸리는지를 나타냅니다.예를 들어, 피보나치 수열을 계산하는 간단한 재귀함수를 생각해봅시다.int fib(int n) { if (n 이 함수의 시간복잡도 T(n)은 다음과 같은 재귀 관계식을 따릅니다:[ T(n) = T(n-1) + T(n-2) + O(1) ]여기서 O(1)은 함수 호출 자체에 소요되는 시간입니다.2. 초기 조건 찾기다음 ..

1. 자음모음#include int main() { char ch; printf("문자를 입력하시오: "); scanf("%c", &ch); if ((ch >= 'a' && ch = 'A' && ch   2. 자유이용권#include int main() { int age; printf("나이를 입력하시오: "); scanf("%d", &age); (age >= 0 && age = 7 && age = 13 && age  3. 사분면#include int main() { int x, y; printf("x 좌표를 입력하시오: "); scanf("%d", &x); printf("y 좌표를 입력하시오: "); scanf("%d", &y); ..

CHAPTER 5. 수식과 연산자1) 3개의 정수 값을 입력받아 3개의 정수 값 중에서 최대값을 출력하는 프로그램을 작성하시오.#include int main(){ int a, b, c, x; printf("엔터를 통해 3개의 정수를 입력하세요\n"); scanf("%d", &a); scanf("%d", &b); scanf("%d", &c); # x = (a>b?a:b)?(a>c?a:c):(c>b?c:b); b) ? ((a > c) ? a : c) : ((b > c) ? b : c); printf("%d",x); return 0;}   2) 100보다 작은 정수를 입력 받아 십의 자리, 일의 자리로 분리하여 출력하는 프로그램을 작성하시오. #include int mai..

동적 프로그래밍(Dynamic Programming, DP)은 복잡한 문제를 작은 부분 문제들로 나누고, 각 부분 문제의 결과를 저장하여 동일한 부분 문제를 여러 번 풀지 않도록 하는 알고리즘 기법입니다. 이는 특히 중복 계산을 피함으로써 효율성을 크게 향상시키며 주로 최적화 문제에서 사용됩니다.동적 프로그래밍의 사용 조건1. 최적 부분 구조(Opptimal Substructure):큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다. 2. 중복 부분 문제(Overlapping Subproblems):동일한 작은 문제를 반복적으로 해결해야 한다동적 프로그래밍은 메모이제이션(Memoization)과 타뷸레이션(Tabulation) 두 가지 접근 방법으로 구현될 수 ..