NLP Learner in Switzerland

까다로운 부분 알아가기 Mathematical induction 수학적 귀납법 방식으로 푸는데는 정해진 단계가 있다. 1. Base case를 찾는다. 보통은 n=0 또는 1이고 대부분 문제에 주어지거나 추측할 수 있다. 이를 통해서 T(0) 혹은 T(1)을 구하고 구한 값이 가설과 일치하는지 확인한다. 2. Inductive Hypothesis를 세운다. n일 때 가설이 참이라고 가정한다. Assume T(n) True. 3. Inductive Step을 따라간다. n+1인 경우의 점화식을 도출하고, 2단계에서 가정한 참T(n)값을 반영하여 n+1일 때도 가설이 참임을 증명할 수 있는지 확인하는 단계이다. 정답

까다로운 부분 알아가기 아래의 점근적 복잡도 대소비교를 어딘가 적어두면 편하다. (참고) 이 가장 작은 이유는? 결국 상수 2값을 가지므로 가장 작다. 정답

까다로운 부분 알아가기 [1] C코드는 Pseudocode에 주어진 그대로 수행을 하면 되기 때문에 설명할 것이 없다. [2] 문제에서 Exact running time T(n)을 구하라고 하면 cost와 수행횟수를 나타내는 표를 그린다. 각 코드 한줄마다 cost는 c1,c2,c3...식으로 달아주고, 수행횟수를 계산해서 넣어준다. 그 후 cost와 수행횟수를 코드 한줄마다 곱해서 전부 더해준다. [3] Asymptotic complexity는 점근복잡도이기 때문에 최고차항을 나타내면 된다. 답안 및 출력결과 a) 내림차순으로 정렬하면서 가장 큰 원소부터 k번째 가장 큰 원소까지의 합계를 반환한다. b) #include int whatIDo(int A[],int n, int k){ int sum=0; ..

까다로운 부분 알아보기 [1] Pascal triangle 파스칼 삼각형은 i행j열의 원소가 i-1행j-1열 + i-1행j열로 이루어져 있다고 되어있다. ▶ 예시를 생각해보면 (3,2) = (2,1)+(2,2) 즉, 3=2+1가 되는 것이다. ▶ 다음항이 계속해서 (i-1,j-1)+(i-1,j)로 출력되므로 그대로 Recursive 구현하면 된다. [2] 삼각형을 살펴보면 0행일때, 0열일때, 그리고 행=열이 같을 때 전부 1을 출력한다는 것을 알 수 있다. ▶ 따라서 이 내용을 Recursion의 Stop condition으로 준다. [3] 첫번째 보기처럼 직각삼각형으로 출력을 하려면 ▶ Pascal함수의 return 값 = 해당 (행,열)의 값을 차례로 읽어오면 되는데, 여기서 row가 끝나면 다음 ..

까다로운 부분 알아가기 [1] 입력받을 string을 선언해주어야 한다. ▶ const를 사용해서 string의 최대 size를 제한해준다. [2] 문자열내의 첫번째 대문자는 어떻게 찾아낼까? ▶ 문자는 ASCII 아스키코드로 숫자 치환되어 대소비교가 가능하다. 예를 들어서, 아스키코드로 'A'는 65이며, 'Z'는 90이다. 따라서 특정 문자가 'A'와 'Z'의 사이에 있으면 그 문자는 대문자라고 판단할 수 있다. [3] iterative는 while loop 또는 for loop이 필요하겠군 ▶ string의 특성상 맨 끝에 '\0'가 있으므로 \0를 만나기전까지 계속 읽어들인다. 대문자를 못찾고 끝나면, 즉 \0를 만나면 -1을 Return하라고 문제에 명시되어 있다. [4] recursive는 i..

까다로운 부분 알아가기 [1] 2가지 이상의 조건을 가진 수열 생성하기. ▶역시나 Recursion이므로 if statement 떠올리기 - Stop condition 생각하기부터 진행한다. ▶ 여기서는 다행히 문제 안에 주어져있다. first two integers(index기준으로 0과 1)이 각각 1과 2이다. 그대로 if문에 넣어준다. [2] 주어진 multiple 조건들을 그대로 else문에 넣어준다. ▶ 수열내의 바로 직전 원소 또한 Recursion의 결과물이므로 계속 다음값을 Return할 수 있게 만들어 준다. [3] 수열 전체를 출력하기. ▶ Return 값 자체가 계속해서 그 다음 원소이므로 Recursion함수 자체를 for loop에 넣어 출력해준다. #include int seq..

까다로운 부분 알아가기 [1] 코드는 짧아보이지만 실제로 Recursion은 생각해내는게 간단하지 않다. ▶ 코딩초심자로서 일단 다른건 다 제쳐놓고 Recursion이면 무조건 if statement를 떠올리고, ▶ Stop condition(특정 조건일 때 이 Recursion이 멈춤)을 생각해서 이걸 제일 먼저 if에 코드화 해주고, ▶ 해당 Recursion함수내의 index 또는 차수의 감소/증가로 stop condition에 도달할 수 있게 이 두가지만 되더라도 일단 infinite loop의 늪에서 빠져나올 수 있는 것 같다. [2] 거듭제곱을 어떻게 코드로 구현할까? ▶ 거듭제곱은 base(밑)^power(지수) 형태이다. 그리고 이를 expansion하면 base를 power번만큼 곱해준 ..

까다로운 부분 알아가기 [1] array size를 설정하지 않으면 자꾸 어디선가 에러가 난다... ▶ 직접 대괄호안에 숫자를 넣어주거나 const int로 제한해준다. 다른 방법은 아직 모르기로 함. [2] Selection Sort(선택정렬) 알고리즘은 ▶ 오름차순인경우에는 매 루프마다 가장 작은 값을 '선택'해서 얘랑 맨 앞 값이랑 바꿔준다. 그러면 가장 작은 애가 계속 앞으로 오게되므로 오름차순으로 정렬이 되는 것. 여기까지는 어딜가도 설명이 되어있다. 문제는 그래서 코드를 어케 만든다는겨... ▶ 일단, 가장 작은 애를 선택 하려면 뭔가랑 비교해서 얘가 작은지 큰지를 알아야 할텐데 어떻게 알지? 선택정렬 알고리즘에서는 계속 루프를 돌면서 더 작은 애, 더 작은 애로 계속 업데이트 해나가면서 찾아..