컴퓨터 공학 기초

Computer Science for Beginners 

---

Harvard cs50 : http://www.edwith.org/connect_cs/joinLectures/10008

Khan Academy : https://ko.khanacademy.org/computing/computer-science/algorithms/intro-to-algorithms/v/what-are-algorithms

---

compiler : 고급 언어로 된 프로그램을 해당 언어의 기계어로 번역해주는 프로그램

한번 컴파일이 되면 (다시 컴파일하지 않고) 반복적으로 수행이 가능하다.

interpreter : 고급언어를 알아듣는 컴퓨터를 모사. (컴파일러와 대비되는 개념)

원시 프로그램을 한꺼번에 번역하지 않고, 문장 단위로 번역해서 실행. 

실행과정이 항상 번역과정을 포함하므로 속도가 느리다. 프로그램 작성 과정에서 즉시 수행해볼 수 있어서 유연성이 크다. 

파이썬은 일단 인터프리터 언어임 ㅇㅇ 

---

Computer and Computing

컴퓨터가 숫자 세는 방법 (총 8개의 비트로 숫자 하나를 표시한다.)

                         여덟번째        일곱번째      여섯번째       다섯번째        네번째            세번째            두번째        첫번째

                            128                64             32                16                8                   4                   2              1

                          2의 7승           2의 6승        2의 5승       2의 4승        2의 3승      2의 2승         2의 1승         2의 0승

1						0	0	1
2						0	1	0
3						0	1	1
4						1	0	0
5						1	0	1
6						1	1	0
7						1	1	1
8					1	0	0	0
9					1	0	0	1
10					1	0	1	0

7까지는 세자리 숫자로 체크할 수 있다. 

11					1	0	1	1
12					1	1	0	0
13					1	1	0	1
14					1	1	1	0
15					1	1	1	1
16				1	0	0	0	0
17				1	0	0	0	1
18				1	0	0	1	0
19				1	0	0	1	1
20				1	0	1	0	0

                            128                64             32                16                8                   4                   2              1

21				1	0	1	0	1
22				1	0	1	1	0
23				1	0	1	1	1
24				1	1	0	0	0
25				1	1	0	0	1
26				1	1	0	1	0
27				1	1	0	1	1
28				1	1	1	0	0
29				1	1	1	0	1
30				1	1	1	1	0

31				1	1	1	1	1
32			1	0	0	0	0	0
33			1	0	0	0	0	1
34			1	0	0	0	1	0
35			1	0	0	0	1	1
36			1	0	0	1	0	0
37			1	0	0	1	0	1
38			1	0	0	1	1	0
39			1	0	0	1	1	1
40			1	0	1	0	0	0

이거 진짜 재밌다 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 위의 표는 내가 임의로 계산해서 작성한거라 틀릴 수도 있다. 

1이 True로 해당 자리에 소속된 값을 더해준다. 

오른쪽에서 4번째 자리에 위치한 1은 2의 3승. 즉, 8을 나타내며 여기에 2를 뜻하는 오른쪽에서 두번째 자리에 1을 해주면 짜잔. 10이 됨

https://playentry.org/hsj7625/58f47910d0d5266cb71c1bfa#!/

위와 같은 게임을 해볼 수 있는 사이트. 진짜 재밌음 ㅎㅎ 

=============================================================================================

255는 위의 이진법이 표현할 수 있는 최대의 숫자이다. 8개 전부가 11111111이다. 

이걸 16진법으로 나타내면 (1~9까지는 숫자, 10은 a, 11은 b, 12는 c, 13은 d, 14는 e, 15는 f.. 이런식으로 간다.)

1111 1111 

   f       f

그래서 255는 16진법으로 표현할 때 ff가 된다. 여기에 헥사데시멀(16진법)이라고 알려주는 0x를 붙이면? 0xff 가 된다. 

무슨 암호문 같았던 컬러 표기법을 조금 이해할 수 있을 것 같기도? 

=============================================================================================

숫자로 색깔 표현하기 - 컴퓨터의 내부 동작 원리 이해

규칙 

1. 숫자는 연속된 같은 색깔의 픽셀 수

1, 4	1	4	4	4	4
1, 1, 1, 2	1	1	1	2	2
0, 1, 3, 1	0, 1	3	3	3	1

2. 흰색에서 검은색으로 또는 검은색에서 흰색으로 바뀔 때 숫자와 숫자 사이를 " , " 로 구분

3. 0이 아닌 첫번째 숫자는 항상 '흰색' 픽셀의 수이다. 

4. 첫 번째 숫자가 " 0 "이면 검은색 픽셀로 시작한다.

http://www.edwith.org/connect_cs/lecture/14109/

---

Algorithm 

    time

|

|

|

|

|

|

|----------------------size of problem

- 좋은 알고리즘은 efficiency (효율성)이 있어야 한다. 

- 가능한 모든 상황들을 가정해야 한다. 

순차 탐색 (linear) : time 과 size of problem 간의 관계가 linear 함. size of problem이 클수록 time 도 증가한다.

이진 탐색 (Binary search) : 

버블 정렬 : 두 개의 인접한 값을 비교하면서 위치를 교환한다. 

선택 정렬 (selection sort) : 숫자를 swap하면서 정렬한다. 

삽입 정렬 (insertion sort) : 

합병 정렬 (병합 정렬) : 절반으로 나누어서 계속 체크. .. 아직 잘 이해 못했다. 

다른 정렬보다 시간 측면에서 성능이 우수하지만, 다른 정렬보다 메모리 공간 (추가 공간이 더 필요하므로)을 더 많이 차지한다. 

---

시간 복잡도

간단하게 연산 횟수를 세는 것이라고 보면 된다.

(Big - O) : 빅-오라고 부르며 가장 최악의 상황 (실행시간의 상한) 에서의 연산 횟수를 체크

(옴) : 최선의 상황 (실행시간의 하한) 에서의 연산 횟수를 체크

: 버블 정렬 실행 시간의 상한 (최악의 경우)

: binary search, 이진 탐색의 시간 복잡도 (단, 이때에는 반드시 목록이 정렬된 상태여야 한다.)

: 상수 시간, 정해진 횟수만큼만 실행한다. array의 index 접근처럼 (1번만 실행해서 index[0]의 값을 가져온다)

만약 하한 = 상한이라면 아래처럼 표시하고, 부른다. (ㅆ ㅔ타, th발음이므로)

선택 정렬은 아래 수식처럼 상한 = 하한이다. 정렬이 되었나와는 관계없이 정해진 횟수만큼 반드시 실행되기 때문.

================================================================================================

linear search : 선형 검색

binary search : 이진 검색

hashing search : index key를 만들어서 찾는 방법