computational thinking_01

01비트연산

1.논리연산

• 논리 피연산자 : true, false
• 논리 연산자 : &&, ||
• ex) A&&(A||B)&&!(B&&C)

 

2.AND &&

• A가 참이고 B도 참이여야 항상 참이다.

 

3.OR ||

• A가 참이고 B가 거짓이어도 참이다.
• A가 거짓이고 B가 거짓이면 거짓이다.

 

4.NOT !

• 'A는 참이다.' 를 뒤집으면 'A는 거짓이다.' 가 된다.

 

5.비트연산

• 비트 피연산자 : 2진수
• 비트 연산자 : &, |, ^, ~, -, <<, >>

 

6.AND &

A	1	0	1	1	1	0	1
B	0	1	0	1	1	1	0
A&B	0	0	0	1	1	0	0

 

7.OR |

 

A	1	0	1	1	1	0	1
B	0	1	0	1	1	1	0
A | B	1	1	1	1	1	1	1

 

8.XOR ^

• 만약 어떤 위치에서 A,B값이 다르다면 1이 되고, 서로 같다면 0이 된다.

A	1	0	1	1	1	0	1
B	0	1	0	1	1	1	0
A^B	1	1	1	0	0	1	1

 

9.NOT ~

• 모든 비트를 뒤집으면 된다.

A	1	0	1	1	1	0	1
~A	0	1	0	0	0	1	0

 

10.음수 표현법

• 보통 가장 왼쪽 비트가 1인 수들을 음수, 0인 수들을 양수로 본다.
• 부호를 의미하는 가장 왼쪽 비트를 제외하고, 양수는 왼쪽부터 1일 빨리 나올수록 큰 수이다.
• 음수는 왼쪽 부터0이 빨리 나올 수록 절댓값이 큰 수이다.

 

11.Shift 연산 >>, <<

• 전체 비트를 하나씩 왼쪽 혹은 오른쪽을 옮긴다.
• 왼쪽 shift 연산의 경우 가장 왼쪽에 있는 비트는 범위를 벗어나므로 사라지게 되고, 가장 오른쪽에 있는 0이 새로 추가된다.
• 왼쪽 shift 산은 2를 곱한 것과 같은 효과, 오른쪽 shift연산은 2로 나눈 것과 같은 효과를 갖는다.

A	1	0	1	1	1	0	1
A<<1	0	1	1	1	0	1	0

 

02진법

1.10진법

• 우리가 일반적으로 사용하는 수는 10진법이다.
• abc 라는 백의 자리수가 있다면 
• a*100 + b*10 + c*1로 나타낼 수 있다.
• 따라서 10진법에서는 0~9까지의 수를 사용할 수 있다.
•  

2.N진법

• n진법의 경우 0~n-1의 수까지 사용할 수 있다.
• ex 8진법의 경우 1321을 표현하는 방법은 
• 1321/8 = 165...1
• 165/8 = 20...5
• 20/8 = 2...4
• 2/8 = 0...2
• 나눈 나머지를 역순으로 적으면 8진법의 수가 된다.
• 2451이다.

03팩토리얼

팩토리얼이란 1부터 n까지의 모든 정수를 곱한 값을 의미한다.

7! = 1*2*3*4*5*6*7

따라서 수가 점점 커지므로 그 성질을 이용해서 푸는 경우가 많다.

 

04조합

1.포함배제의 원리

• 여러 경우를 한번에 처리할 때 주의할 점이 있다.
• 1부터 n까지의 정수 중 2의 배수도 아니고 3의 배수도 아닌 수를 찾는다고 하자.
• 1부터 n까지의 정수 중 2의 배수는 n/2로 구할 수 있다는 내용을 팩토리얼의 원리에서 알 수 있다.
• 마찬가지로 1부터 n까지의 정수 중 3의 배수는 n/3으로 구할 수 있다.
• 추가로 3의 배수와 2의 배숭의 수를 구한다면 n/2를 추가하면 된다.
• 하지만 중복된 수가 있을 수 있으니 n -n/2 -n/3 + n/6로 계산해줘야 한다.
• 여러 경우를 하나로 묶으려는 시도를 하다보면 중복되는 것을 세는 경우가 생기므로 잘 제거해서 계산해야 한다.

 

 

가장 중요한 것은 규칙을 찾는 것.

문제 수도 별로 없는데 어떻게 반복 숙달할지가 문제다...