[TIL] Day 1 - Computational Thinking

해당 내용은 다음 출처에서 가져왔습니다.

https://swexpertacademy.com/main/learn/course/subjectList.do?courseId=AVuPCwCKAAPw5UW6 

SW Expert Academy

SSAFY 시리즈
1. [후기] SSAFY 8기 지원과정 (자소서/코딩테스트)
2. [후기] SSAFY 8기 지원과정 (면접)
3. [TIL] Day 1 - Computational Thinking
4. [TIL] Day 2 - Computational Thinking
5. [TIL] Day 3 - Computational Thinking

---

 

 

프로그래밍과 논리/수학

개요

만약 Problem Solving 문제를 풀어도 감이 오지 않는다면
→ 논리적으로 정확하게 확인하는 과정에 대한 연습이 없기 때문이다.
따라서, 정확하게 확인하는 훈련이 되어 있어야 단순 작업 이상의 코드를 작성할 수가 있어진다.

 

프로그래밍의 어려운 점 2가지

1. 프로그래밍 언어 문법과 라이브러리 사용
2. 논리 (Hard Logic)

프로그래밍 언어 문법이 어려운 것은 자명한 사실이다. 하지만 이는 훈련에 비례하게 실력이 느는 경향이 있다.
일반 상식으로 원래 알고 있는 것이 아니기 때문에, 훈련의 필요성에 반감이 없다.
실제로 진입 장벽을 느끼게 되는 것은 Hard Logic 부분.

 

Hard Logic vs. Soft Logic

두 가지의 차이의 예시를 들어보자면, 카드 문제가 있다.

만약 한쪽이 D이면, 반대쪽은 3 이다.

라는 위와 같은 주장이 있다면 이가 사실인지 확인하기 위해서 다음 4장의 카드 중 반드시 뒤집어봐야하는 것은 무엇이고 어느 것인가?
정답은 D와 3이 아닌, D와 7이다.
(일단 D를 뒤집어야 하는 것은 누구라도 생각할 수 있다.)
사실 3은 뒤에 어떤 알파벳이 있든 위의 주장을 깨뜨리지 않는다.
하지만 7 뒤에 만약 D가 있다면 위 주장을 깨뜨릴 수 있다. 왜냐하면 뒤에 D가 있게 되면 주장이 성립하지 않기 때문이다.

다른 문제를 살펴보자. 이번에는 맥주집 문제이다.

20세 이하인 사람은 맥주를 마실 수가 없다.

라는 주장이 있다. 그렇다면 확인이 필요한 사람은 4명 중 누구인가?
이는 우리가 직관적으로 알 수 있다. 17세와 맥주이다.

카드와 맥주집 문제는 논리적 구성은 완전히 동일한 문제이지만, 우리가 보기에 맥주집 문제가 더 쉽게 풀린다.
왤까? 왜냐하면 우리는 맥주집 문제에서 논리를 사용한 것이 아니기 때문이다.
우리는 맥주집 문제에서 논리적인 느낌을 주는 직관을 사용해서 풀었다.
직관은 빠르지만, 단점은 정확하지가 않다. 또한 강한 착각을 일으킨다.

"너 과자 몇 개 먹었니?" 하고 물었을 때, 만약 상대방이 "과자 하나 먹었어요" 라고 대답을 했다.
근데 확인을 해보니 과자를 3개를 먹었다.
일상생활에서 봤을 때 상대방을 거짓말은 한거지만, 사실 논리적으로 따져 보았을 때는 하나는 먹었긴 먹었기 때문에 거짓말이 아니다.
이처럼 우리는 일상 생활에서 Soft Logic 을 주로 사용한다. 왜냐하면 빠르기 때문에 유용하기 때문이다.
또한, Soft Logic에선 논리적으로 부정확한 상황이더라도 어떤 의미인지 모든 사람들이 공유를 하고 있다는 가정이 존재한다.

허나 프로그래밍에서는 Hard Logic 을 사용한다.
여기에서 오해가 생긴다. 알고리즘을 Soft Logic 으로 이해하려고 하기 때문이다.
알고리즘 설명을 보고 또 봐도 이해가 안되는 것은 증명을 안 보고, 직관으로 이해하려고 하기 떄문이다.

 

논리 연습

Q. 다음을 명제식 형태로 쓰고 참인지 거짓인지 판단하시오.
1) 만약 0이 홀수라면, 미국에서 2080년 월드컵이 열린다.
2) 만약 1989234234123139이 Prime Number라면, 2는 짝수이다.

[1번 문제]
p → q
p: 0은 홀수이다. (거짓)
q: 미국에서 2080년 월드컵이 열린다. (알 수 없음)

p 명제가 거짓이므로, q 명제의 참/거짓 여부에 상관없이 해당 명제식은 참이 된다.
예를 들어,
p: A가 국어 시험을 100점을 넘으면
q: B가 밥을 사준다. 라는 명제식이 있다면
A가 국어 시험을 100점을 넘었을 때는, B가 밥을 사줘야만 참이 된다.
만약 밥을 사주지 않으면 거짓이 된다.
하지만 A가 국어 시험을 100점을 넘기지 않았을 때는 B가 밥을 사주든, 사주지 않든 상관이 없다. 따라서 참이 된다.

[2번 문제]
p → q
p: 1989234234123139이 Prime Number이다. (알 수 없음)
q: 2는 짝수 이다. (참)

대우로 따지게 되면 ~q → ~p 이다. 이렇게 되면 ~q가 거짓이다. 따라서 명제식은 참이 된다.
대우가 참이므로, 본 명제식도 참이 된다.
q 명제가 참이기 때문에 명제식은 참이다.

Q. p와 q가 명제이고 p → q가 거짓이라고 하자. 다음 명제식의 참/거짓은 어떻게 되는가?
1) ~p → q
2) p V q
3) q → p

p → q 가 거짓이라는 것은, 한 가지 경우 밖에 없다.
p는 참이고 q는 거짓이다.
[1번 문제] 참
[2번 문제] OR 연산이다. 참
[3번 문제] 참

 

역, 이, 대우

본 명제: p → q
역: q → p
이: ~p → ~q
대우: ~q → ~p

 

진리표 만들기

 

증명

뜻

증명이라는 것은 정확한 명제식으로 표현할 수 있는 것이다.
보통은 정확한 명제식까지는 쓰지 않으나, 근본적으로는 명제식으로 바꿀 수 가 있어야 한다.
증명에 대한 수많은 오해가, p → q 를 p ↔ q와 혼동하는 것에서 일어난다.

• p 이면 q 이다.
• p 이면 q 이고, q 이면 p 이다. (즉, p와 q의 진리값이 같다.)

 

수학적 귀납법

P(1)이 참이고,
P(n) → P(n+1)이 참이면
P(n)은 모든 자연수 n에 대해서 참이다.

 

당구공 Paradox

모든 당구공은 색이 같다는 다음 증명에서 잘못된 것은 무엇인가?

여기서 P(n) 이 참이라고 가정한다. 따라서, n개의 당구공의 집합은 모두 색이 같다.
n + 1 개의 당구공이 있는 집합을 생각해보자.
여기서 하나의 당구공을 빼보자.
그래서 P(n) 이므로 모든 당구공의 색은 같다.
방금 뺀 당구공을 다시 넣고, 다른 당구공을 빼보자. 그러면 이도 P(n) 이므로 역시 모든 당구공의 색이 같다.
위 상황으로 첫번째, 두번째 뺀 당구공도 모두 색이 같은 것을 알 수 있다.
그러므로 식이 성립하게 된다.

하지만 과연 그런가?
여기서 만들어지는 모순은 바로 P(1) 이다.
만약 두개의 당구공이 있다고 생각을 해보자.
두개의 당구공 중에서 하나의 당구공을 빼본다. 그러면 안에 담겨있는 당구공의 색은 모두 같다.
(당연하다 하나밖에 없으니)
아까 뺐던 당구공을 넣고, 다른 당구공을 빼본다. 그러면 하나 남은 당구공은 색이 하나이므로 담겨져 있는 당구공의 색은 모두 같다.
혼자 있기 때문에 색이 같은 것이지, 두 개의 공이 같이 있을 때 공의 색이 같은지는 알 수 없다.
따라서 n = 1 일 때, 잘못된 증명을 일으킨다.

 

프로그래밍에서 수학적 귀납법

int sum(int x) {
	if (x < 0) return 0;
    return x + sum(x-1);
}

상세한 증명은 답이 맞는 것이 당연하다 라고 말하는 것으로 충분하지 않다.
증명이 가능한 명제를 만들어야 한다.
따라서, 이 경우에는 증명이 가능한 명제는 다음과 같다.

sum(x)가 return 하는 값은 1 + 2 + ... + x 와 같이 항상 같다.

이렇게 되면 수학적 귀납법을 적용할 수 있게 된다.
따라서, sum(x - 1) 볼 필요가 없이 이를 참으로 가정하고,
sum(x)가 1 + 2 + ... + (x-1) + x = 1 + 2 + .. + x 를 리턴하는지 확인만 하면 된다.
익숙해질 때까지 연습이 필요하다.
버블Sort 같은 경우는 A[1] < A[2] < .. < A[n] 이라는 증명 가능한 명제가 만들어 질 것이다.

** 버블 소트 증명 **
(주관적 생각이니 답이 아님)
bubbleSort(n) 이라는 함수가 존재한다.
버블 소트에서 증명이 가능한 명제는 다음과 같다.
-> bubbleSort(n) 이 리턴하는 값은 A[1] < A[2] < ... < A[n] 과 같다.
(값이 오름차순으로 정렬되어있다는 말)

1) P(1)은 참이다.
-> A[1] 로 원소가 하나이기 때문에 참이다.

2) P(x) -> P(x+1) 이 참이다.
-> bubbleSort(x) 가 A[1] < A[2] < ... < A[x] 을 리턴하면
bubbleSort(x+1) 은 A[1] < A[2] < ... < A[x] < A[x+1] 을 리턴한다를 증명하면 된다.

bubbleSort(x) 은 A[1] < A[2] < ... < A[x] 로 오름차순으로 정렬되어있다 가정했다.
따라서 bubbleSor(x+1) 은 bubbleSort(x) < A[x+1] 을 리턴함을 확인할 수 있다.

 

 

 

 회고 

이번 주 정말 너무 바쁩니다
짬나는 시간이 별로 없어요 그래도 짐 다 옮기고 안정되면 공부할 시간이 좀 나겠죠
오랜만에 증명을 하니까 재미있었습니다
좀 시간이 지나고 보니까 낯설긴 하지만^^ 뭐 계속 보다보면 익숙해지겠죠
진짜 잘하고 싶어요.. 왜 이렇게 잘하는 거에 욕심을 부리는지 모르겠어요
첨엔 하잘것 없더라도 노력하면 그 가까이에는 가지 않을까요?
달을 향해 쏴라 라는 말이 있잖습니까. 항상 총구는 하늘을 향해 둬야 합니다.
그러나 야속하게도 결과는 항상 아름답지 않으니 이를 유념하면서 상심은 하지말아야해요

 

 

# SWEA 프로그래밍과 논리수학 # 싸피 8기 # swea 증명 풀이

---