침대 밖은 위험해!

1. 2진수

1.1 2진수와 16진수

- 변환 : 16진수는 십진수로 0~15까지 표현이 가능하다. 이진수로는 0000~1111까지 표현이 가능하다.

          2진수에서 16진수로 변환은 오른쪽부터 4bit씩 잘라서 변환하면 된다.

          1110001(2) =>  111(2) = 2^3 - 1 = 7

                              0001(2) = 1

          1110001(2) = 71(16)

1.2 용어

- word : 사용하는 프로세서가 몇 비트냐에 따라 워드의 크기가 바뀐다.

           한번에 처리할 수 있는 단위(일반적으로 레지스터의 크기라고 보며된다.)

           32bit processor라면 32bit = 1word

※ 현재 공부하고 있는 프로세서가 몇 비트인지 알아둬야 한다.

   (단, 32bit 임에도 SW상에서는 16bit를 1word로 처리하는 프로세서가 있다.)

   (이유는 나중에... 나에게 별로 중요하지 않은 부분이라 앞으로 설명할 기회가 있을지는 모르겠다.)

- MSB(Most Significant Bit), LSB(Least SIgnificant Bit)

  MSB : 최상위 비트

  LSB : 최하위 비트

  101100(2) 에서  

    1        0 1 1 0        0

  MSB                     LSB

1.3 2진수의 표현

- Signed-Magnitude

- One's Complement

- Two's Complement

- 앞으로는 2의 보수만 사용할 것이다. 1의 보수나 부호와 크기 표현은 대표적으로 0이 두개인 문제가 발생함.(다른 문제도 있음)

(설명은 귀찮으니 패스...)

- 2의 보수에서 표현 범위 : [-2^(N-1) ~ 2^(N-1)-1] (참고로 '[ ]'는 닫힌구간)

1.4 Overflow / Underflow

- Overflow : 절대값의 표현범위가 자료형이 나타낼 수 있는 범위를 넘어설 때

  17.12.19 추가 : 코딩시 signed인지 unsigned인지 확인이 중요

  c++에서 벡터 v.size() - 1 은 overflow를 일으킬 수 있음. v.size()는 unsigned int 형으로 만약 벡터 크기가 0일 경우

  0 - 1은 4,294,967,295(1111 1111 | 1111 1111 | 1111 1111 | 1111 1111, 32bit) 가 나옴

  (위와 같은 경우를 underflow라고 하는건 잘못된 표현, underflow는 엄연히 다른 표현임)

  overflow를 피하려면 1. (explicit) type casting  

                             2. v.size() - 1 표현을 안쓰는 것

- Underflow : 부동소수점 표현방식에서 지수부가 타입의 한계를 넘어 작아지면 0에 가까워 지는 것

(난 잘 주워오니까 그림으로 때우겠다)

출처는 아래에 있습니다.

- 2의 보수 표현(signed)에서 양수 + 음수의 덧셈은 오버플로우를 일으키지 않음

- 음수 + 음수의 크기가 -2^(N-1)보다 작거나 양수 + 양수의 크기가 2^(N-1) - 1 보다 큰 경우를 오버플로우

  즉, 캐리의 여부와 관계없이 앞의 부호가 바뀌는 경우가 오버플로우(단, 2의 보수 표현에서만)

1.5 sign-extention

- MSB를 계속 늘리면 됨

- 3  = 0011(2) = 0000 0011(2)

- -3 = 1101(2) = 1111 1101(2)

-출처

http://slideplayer.com/slide/5946574/

https://courses.cs.washington.edu/courses/cse370/98sp/lectures/04-combex/sld026.htm

http://slideplayer.com/slide/9942560/

https://namu.wiki/w/%EC%98%A4%EB%B2%84%ED%94%8C%EB%A1%9C

https://stackoverflow.com/questions/6360049/what-are-arithmetic-underflow-and-overflow-in-c

2. 논리 게이트

2.1 논리 게이트

- 하나 또는 그 이상의 2진수 입력을 받아서 하나의 출력을 만들어 내는 간단한 디지털 회로

2.2 논리 게이트 종류

※ 논리게이트의 심벌과 진리표는 구글 검색

  1) NOT

  2) BUF : 버퍼 : 논리적 관점 - 데이터의 전달

                      아날로그적 관점 - 많은 양의 전류를 공급, 하나의 입력을 다른 많은 게이트에게 전달, 데이터 복원

  3) AND

  4) OR

  5) XOR

  6) NAND

  7) NOR

  8) XNOR

- N input gate : 2개씩 나눠서 진리표 써보면 됨

※ N input XOR는 parity gate라고도 함

정리할 책은 "Digital Design and Computer Architecture -David Harris 외 1명-" 기준입니다.

책 + 보면서 궁금한 점을 검색하여 쓸겁니다.

앞으로 순서

1. 2진수를 표현 하는 방법

2. 논리게이트 란?

3. 조합논리

- 부울 식

- 카르노 맵

등

4. 논리 디자인

- 래치와 플리플롭

- FSM

등

5. 하드웨어의 표현

6. 디지털 빌딩 블록

- 연산 회로

- 메모리 어레이

등

7. 파이프라이닝

7. 메모리 시스템

- 메모리 종류

- 캐시

등

앞으로 진행하면서 나온다면 설명하겠지만

우선 이 책은 mips processor 기준으로 작성되었고,

앞으로 포스팅은 제가 필요하다고 생각되는 부분만 할 것이기에

프로세서나 어셈에 대해서는 잘 다루지 않을 것입니다.

문제를 풀면서 무엇이 부족한지 모르기에 좀 더 절차적으로 접근

1. 알고리즘 문제 해결을 위한 전략

1) 문제를 읽고 이해하기

- 문제가 원하는 바를 완전히 이해

- 사소한 제약조건, N값의 범위, 메모리 크기

2) 문제를 익숙한 용어로 재정의 = 재정의와 추상화

- 문제를 직관적으로 이해하기 위한 발판

- 문제의 본질만 남기고 축약 => 어떤 부분을 추상화할 것인를 선택하는 작업, 문제를 재정의하는 방법들에 대한 고찰

3) 계획 세우기

- 문제를 어떤 방식으로 해결할지, 사용할 알고리즘과 자료구조 선택

※ 문제 해결 전략 => 체계적인 접근

- 비슷한 문제를 풀어본 적이 있는가? => 원리를 이해하고 변형할 수 있는 능력

  문제의 목적을 보고 적절한 접근법을 선택하기 위해서는 문제를 분류(최적화, 경우의 수, 검색 등)하고, 각 알고리즘들이 어느 경우에 사용될 수 있는지

- 단순한 방법 => 점진적으로 개선점을 찾아가는 방법

- 수식화

- 문제를 단순화

- 그림으로

- 문제를 분해

- 뒤에서 부터 시작

- 순서를 강제

- 특정 형태의 답만 고려(답이 여러개가 나올 수 있는 경우)

4) 계획 검증하기

- 빅오, 메모리

5) 계획 수행하기

- 구현에서 유의점과 좋은 프로그램 작성

※ 좋은 코드 짜기

- 간결한 코드 - 전역변수(대회 한정)

- 코드 재사용 - 모듈화 : 항상 깔끔하게 작성하고 그것이 습관이 되도록 노력

- 표준 라이브러리 공부

- 항상 같은 형태로 프로그램 작성 - 행열, 범위, for 등

- 일관적이고 명료한 명명법 사용

- 자료를 정규화 - 각도, 시간, 분수 등 : 정규화는 프로그램이 자료를 입력 받거나 계산하자마자 바로 시행하는 것이 좋음

- 코드와 데이터 분리

  fig1 코드 처럼 데이터를 코드 안에 넣기 보다는 fig2 처럼 논리와 상관없는 데이터는 상수화

string getMonthName(int month){
   if (month == 1) return "January";
   if (month == 2) return "February";
   ...
   return "December";
}

<fig1>

const string monthName[] = { "January", "Fabruary", ..., "December" };

<fig2>

코드와 상관없는 데이터 부분은 따로 분리. 맵에서 움직일 수 있는 위치 보다 움직일 수 있는 상대좌표를 이용하는 것이 좋음

단, 오타 조심

※ 자주하는 실수

- 산술 오버플로우

  int를 벗어나는 큰 결과 또는 중간값 : 자료형을 변경, 중간값의 수식을 변경하여 초과하지 않도록 함

  무한대 - 987654321 : 2^30에 가까운 수로 어느 정도의 수가 더해지더라도 오버플로우가 안생김

  자료형의 프로모션 - 보통 부호있는 값과 없는 값이 계산될 때 : 특히 벡터의 사이즈는 부호없는 size_t를 반환함

  실수 연산 - 안쓰는게 제일 좋음. 써야 한다면 값을 늘려서 정수형으로 변환. 그것도 안되면 그냥 크게 잡는게 좋음(부동 소수점의 유효숫자)

- Out of Index

- 상수 오타

- 스택 오버플로우 - C++의 경우 지역 변수로 선언한 배열이나 클래스 인스턴스가 스택을 사용하기 때문에 조심. 그냥 전역이 제일 좋음

- 다차원 배열 인덱스 바꿔쓰기

- 최대, 최소 예외

- 연산자 우선순위

- 변수 초기화 - 입력 예제를 똑같은걸 두번 쓰면 어느 정도 피할 수 있음

- 계산 중간 결과를 출력하는 것이 디버깅을 덜 돌리게 함

6) 회고하기

- 문제를 풀 때마다 코드와 함께 자신의 경험을 기록

- 문제의 간단한 해법 + 어떤 방식으로 접근했는지 + 문제 해결을 위한 결정적 깨달음

- 오답 원인

=> 나중에 읽으면서 그때 뭘 배웠는지 되새김. 문제들 간의 공통 해법 등 파악하는데 좋음

- 다른 사람의 코드

다음 2편은 빅오에 대해

- 해당 내용은 종만북에서 가져옴 -

- 알고리즘 문제 해결 전략 1편 중 -

- 저작권 문제시 삭제하겠습니다 -