Computational thinking
Table of contents
- 수식 기호 및 표현
- 답이 잘 정리된 곳 - SangWoo Blog
프로그래밍이 어려운 점 두 가지
- 프로그래밍 언어 문법과 라이브러리 사용
- 배울 때 약간의 어려움이 있지만 훈련에 비례하여 실력이 느는 경향이 있음
- 논리
- Hard logic vs Soft logic
- 프로그래밍은 hard logic 을 사용한다.
- 직관은 논리적인 느낌을 주는것
- 직관은 장잠은 빠르지만 단점은 정확하지 않고 강한 착각을 일으킨다.
- Soft logic 으로 알고리즘을 이해하려 하면 직관적으로 이해되는 알고리즘이 있지만 직관으로 완전한 이해를 얻는것은 사실상 불가능하다.
- 증명
- 많은 오해가 p -> q 와 p <-> 를 혼동하는 것에서 일어난다.
- 대부분
- 수학적 귀납법
논리 연습
- 다음 명제식 형태로 쓰고 참인지 거짓인지 판단하시오
- 만약 0이 홀수라면, 미국에서 2080년 월드컵이 열린다.
- 만약 1984893490239409이 Prime number 라면 2는 짝수다.
- p -> q 가 거짓이라고 하자. 다음 명제식의 참 거짓은 어떻게 되는가?
- ~p -> q : T
- p v q : T
- q -> p : T
- 다음 명제들의 역, 이, 대우를 쓰시오
- 만약 0이 홀수라면, 미국에서 2080년 월드컵이 열린다.
- 만약 1984893490239409이 Prime number 라면 2는 짝수다.
- 다음 명제식의 진리표를 만드시오
- p ∧ (q -> ~p)
- (p ∧ ~q) -> r
논리와 증명
- 항진명제 임을 진리표를 이용하여 보이시오
- ~(~p ∧ q) v q
- (~p v q) v (p ∧ ~q)
- 모순명제 임을 진리표를 이용하여 보이시오
- (~p v q) ∧ (p ∧ ~q)
- (p ∧ q) ∧ (p ∧ ~q)
- 두 명제가 동등한지 진리표로 확인
- p ∧ (p v q) == p
- ~p v ~q == ~(p v q)
- 명제식 변형으로 간소화
- (p ∧ ~q) v (p ∧ q)
- (p v ~q) ∧ (~p v ~q)
- 참인지 확인. R 은 실수의 집합, Z 는 정수의 집합
- ∀x ∈ R, X^2 >= x
- ∀x ∈ Z, X^2 >= x
- ∃x ∈ R, X^2 < x
- ∃x ∈ Z, X^2 < x
- n 이 짝수이면 3n + 5 이 홀수임을 증명
- n 이 홀수이면 n^2 + n 은 짝수 임을 증명
- m 이 짝수 이고 n 이 홀수이면 2m + 3n 은 홀수 임을 증명
- (대우 증명) 자연수 n 에 대해서 n^2 + 5 가 홀수이면 n 이 짝수임을 증명
- n^2 이 짝수이면 n 이 짝수임을 증명
- 자연수 n 에 대해서 n^2 + 5n + 3은 항상 홀수 임을 증명
- n^2 이 3의 배수이면 n 은 3 의 배수임을 증명
- n 이 홀수이면 n^2 을 8로 나눈 나머지는 1임을 증명
- 어떤 자연수를 제곱해도 그 결과를 3으로 나눈 나머지는 2가 아님을 증명 하라
- (귀류법) 유리수와 무리수의 합은 무리수임을 증명 하라
- \sqrt[2]{n} 이 무리수 임을 증명하라
- log2(5) 는 무리수임을 증명하라
- 수학적 귀납법 : 1 + 2 + 3 + 4 + … + n = n*(n+1)/2 을 증명하라
- 1^2 + 2^2 + 3^2 + 4^2 + … + n^2 = n*(n+1)(n+2)/6 을 증명하라
- r != 1 일 때 sum(0~n) \sum_{i=0}^{n} r^i = \frac {r^{n+1}-1} {r-1} 임을 증명하라
- 2 이상의 자연수 n 에 대해서 n^3 - n 은 6으로 나누어 떨어짐을 증명하라
- 2 이상의 자연수 n 에 대해서
\sqrt n < \frac {1}{\sqrt 1} + \frac {1}{\sqrt 2} + ... + \frac {1}{\sqrt n}을 증명하라 - nxn 체스판에서 감염되지 않은 칸은 인접 칸들 중 2개 이상이 감염일 때 감염된다. 모두 감염 시키기 위해서 초기에 n 칸 이상이 감염 되어 있어야 함을 증명하라.
수와 표현
- 2진수 표현에서 log n 비트로 표현 할 수 있는 숫자 범위는
- 스무고개에서 맞출 수 있는 답의 종류는?
- n 이 충분히 큰 값일 때 다음중 어느 값이 더 큰가?
- 2n ?? n^2
- 2^{\frac {n}{2}} ?? \sqrt {}{3^n}
- 2^{n\log n} ?? n!
- \log 2^{2n} ?? n \sqrt{}{n}
- x = \log_{a} yz 일 때 x 를 2를 밑으로 하는 로그로 표현하시오. 단, 로그 함수의 인자는 모두 문자 하나여야 한다.
- 다음 함수들의 역함수를 구하시오
- f(x) = log(x-3) - 5
- f(x) = 3log(x+3) + 1
- f(x) = 2 x 3^x - 1
집합과 조합론
- \binom{n}{k} + \binom{n}{k - 1} = \binom{n + 1}{k}
- 수학적 귀납법으로 증명 : (x + y)^n = \sum_{k=0}^{n} \binom{n}{k}x^{n-k}y^k
- 결과를 이용하여 n 개의 원소를 가진 집합의 가능한 부분집합의 종류는 2^n 개임을 증명하라
- 귀류법을 이용하여 증명 : (A-B)∩(B-A) = ∅
- 두 집합이 다르다는 것을 명제와 동치임을 증명하라. 증명에는 앞에서 설명한 내용과 기본 논리만 사용한다.
- ∃x (x ∈ A ∧ x ∉ B) v (x ∈ B ∧ x ∉ A)
- 다음이 사실임을 증명하라.
- (A ∪ B) ∩ (A ∩ B)^c = (A - B) ∪ (B - A)
- (A⨁B) 는 합집합에서 교집합을 뺀것을 말한다. (A⨁B)⨁B = A 이 항상 성립함을 증명하라
- 8x8 체스판에 똑같은 말 두개를 놓으려 한다. 가능한 방법은 몇가지 인가?
- n 개의 원소를 가진 집합의 가능한 부분집합의 종류는 2^n 개임을 조합론을 이용해 증명하라
- 비밀번호를 0-9 까지의 숫자를 가지고 만들 때 각 숫자는 한번만 사용할 수 있다 4개 이상 6개 이하의 숫자를 쓸 수 있을 때 가능한 비밀번호의 가짓수는?
- 52개의 트럼프 한 세트에서 5장 카드의 조합은 몇가지 인가?
- 52개 한 셋트 5개의 카드 조합 중 같은 무늬 카드가 정확히 3개인 경우는 몇가지 인가?
- x + y + z = 100 의 자연수 해는 몇가지 인가?
- (포함 배제의 원리) 5개의 원소를 가진 집합에서 3개의 원소를 가진 집함으로 가는 전사 함수는 몇가지가 있는가?
- 52개의 카드에서 5개 조합을 만들 때 숫자가 같은 카드가 한 쌍도 없는 경우는 몇가지 인가?
- n 개의 원소를 가진 배열에서 연속된 구간을 잡으려고 한다. 잡을 수 있는 가능한 구간은 몇가지 인가? 단 구간의 크기는 1 이상이다.
기초 수식
다음 재귀 식들은 O() notation 수준으로 풀어라.
- T(n) = T(n - 1) + 1
- T(n) = T(n - 1) + n
- T(n) = T(n - 1) + \log n
- T(n) = T(\frac {n} {2}) + 1
- T(n) = T(\frac {n} {2}) + n
- T(n) = 2T(\frac {n} {2}) + n
- T(n) = 3T(\frac {n} {2}) + n
- T(n) = T(n-1) + \frac {1}{n}
- T(n) = T(n/2) + T(n/4) + T(n/6) + T(n/12) + 1
- T(n) = \sqrt{}{n} \cdot T(\sqrt{}{n}) + n
재귀
다음 문제들을 푸는 재귀 알고리즘을 수도 코드로 작성하고, 정확성 증명 및 시간 복잡도 계산을 수행하라
- 피보나치 수열 : F(n) = F(n-1) + F(n - 2), F(1) = F(2) = 1
- Merge sort
- 다음 소팅 알고리즘이 항상 성공한다는 것을 증명하라
def stupid(arr): if len(arr) == 2 and arr[0] > arr[1]: arr[0], arr[1] = arr[1], arr[0] else: m = ceiling(2n/3) stupid(arr[0:m-1]) stupid(arr[len(arr)-m:n-1]) stupid(0:m-1) - 위의 알고리즘에서 swap 의 횟수는 최대 몇번 인가?
- 어떤 배열 A[1..n] (음수 포함, asc 정렬됨) 잇음. A[i] 가 i 가 되는 알고리즘을 수도코드로 작성하고 증명 및 시간 복잡도를 증명하라. 자연수로 제한되면 어떻게 풀 수 있는가?
- 루트에 있는 트리를 입력으로 받아 아래와 같이 출력하는 알고리즘을 작성하라. 1000미만의 자연수가 저장되어 있다. 트리를 출력하라.
[030]--+--[054]-----[001] +--[002] o--[045]-----[123] - 무한한 크기의 물통 3개가 있다 초기에는 자연수 만큼의 물이 들어 있다. 가능한 작업은 두개의 물통을 잡아서 그 중 많거나 같은 양의 물이 들어 이는 곳에서 작으 ㄴ쪽으로 물을 부어서 작은 쪽의 물의 양을 두배로 만드는 것이다. 즉, 4리터, 3리터를 잡았다면 1리터 6리터가 될 것이다. 입력으로 초기 물의 양을 받아서 한 물통에 들어 있는 물의 양을 0 리터로 만들고 싶다. (실행 시간이 많이 걸려도 좋으니) 그렇게 만드는 과정을 계산하는 알고리즘을 작성하라.
동적 프로그래밍
다음 문제들을 푸는 동적 프로그래밍 알고리즘을 수도 코드로 작성하고 정확성 및 시간 복잡도 계산을 수행하라
- Memozation 피보나치 수열
- Dynamic programming 피보나치 수열
- 실제로 실행 시키면 어느것이 가장 빠를 것으로 예상 되는가?
- 행열 곱하기 n 개의 행열을 곱하려고 한다. 크기가 axb 인 행열과 크기가 bxc 인 행열을 곱하는데 드는 계산량을 axbxc 라고 한다. n 개의 행열들을 곱하는데 필요한 계산량을 최소화 하는 순서를 찾는 알고리즘을 작성하라. 행열들의 크기는 다르고, 입력으로 주어진다고 가정하라.
- 배열에 정수(음수 포함) 들이 저장되어 있다. 연속인 구간들 중 그 합이 가장 큰 구간을 찾는 알고리즘을 작성하라. 구간의 크기는 1이상이 허용된다.
- 배열에 정수 들이 저장되어 있다 배열의 일부 값들을 골라서 배열에 있는 순서대로 보면 증가하는 순서가 될 수 있다. 이러한 것들 중 가장 긴 것을 찾는 알고리즘을 작성하라.
조합론 프로그래밍
- 52장의 카드에서 만들 수 있는 페어가 정확히 하나만 있는 5장 조합을 모두 출력하는 프로그래밍을 만들어라. 출력이 많으면 카드를 줄일 수 있다.
- x + y + z = 100 의 자연수 해를 모두 출력하는 프로그램을 작성하라.
- m 개의 원소를 가진 집합에서 n 개의 원소를 가진 집합으로 가는 전사함수의 갯수를 출력하는 프로그램을 작성하라. m 과 n 의 값을 바꾸어 보면서 값이 너무 커지지 않는 입력의 범위가 어느 정도인지 확인하라.
- m 개의 원소를 가진 집합에서 n 개의 원소를 가진 집합으로 가는 전사 함수를 모두 출력하는 프로그램을 작성하라. 출력을 어떻게 하는 것이 적절할 지 생각해 보아야 한다.
기초 프로그래밍
- 피보나치 수열을 계산하는 3가지 방법을 모두 작성하고 실행시간을 비교하라.
- n 개의 행열 을 곱하려고 한다. axb 인 행열과 bxc 인 행열을 곱하는데 드는 계산량을 axbxc 라고 한다. n 개의 행렬 들을 곱하는데 필요한 계산량을 최소화 하는 순서를 찾는 알고리즘을 작성하라. 행렬들의 크기는 다르고 입력으로 주어진다고 가정하라.
- 배열에 정수(음수포함) 들이 저장되어 있다. 연속인 구간들 중 그 합이 가장 큰 구간을 찾는 프로그램을 작성하라.
- 배열에 정수 (음수포함) 이 있다. 배열의 일부 값을골라서 배열에 있는 순서대로 보면 증가하는 순서가 될 수 있다. 이런한 것들 중 가장 긴 것을 찾는 프로그램을 작성하라.
- 루트에 있는 트리를 입력으로 받아 아래와 같이 출력하는 프로그램을 작성하라. 1000 미만의 자연수가 저장되어 있다. 트리의 노드 연결 관계를 다음과 같이 표현해야 한다. 아래 출력에서 루트는 자식이 3개 있고 그 자식들 중 하나는 더이상 자식이 없는 것임을 알 수 있다.
[030]--+--[054]-----[001] +--[002] o--[045]-----[123]