Krafton_jungle 5기 6일차 TIL - CS:APP, 탐색 알고리즘

CS:APP

hello world!

 

1. 정보는 비트와 컨텍스트로 이루어진다.

bit	메모리를 구성하는 최소 단위로 0과 1을 저장할 수 있다.
hello.c	위 사진과 같은 프로그램은 0과 1의 비트들의 연속으로, 8비트(1byte)로 구성된다.
ASCII	대부분의 컴퓨터는 문자를 ASCII 표준을 사용해서 표현한다. 개행 문자의 경우, \n으로 표현되는 것을 알 수 있다. hello.c는 오로지 아스키 문자열로 이루어져 있으며, 이런 파일들을 텍스트 파일이라고 한다. 그 외 모든 파일을 바이너리 파일이라고 함.

컨텍스트	호출 응답간의 환경 정보, 서로 다를 객체들을 구분하는 방법이라고 한다. 딱 정의되어 있는 개념이 아닌 추상적인 개념이라 컴퓨터 공학을 공부하다 보면 심심치않게 만나볼 수 있는 단어. 아직은 익숙하지 않아 응답간의 환경 정보로 이해했다. 위 코드와 다른 컨텍스트에서는 정보를 표현하는데 동일한 바이트가 정수, 부동소수, 문자열 또는 기계어 명령을 의미할 수 있다.
C언어의 기원	유닉스 운영체계와 밀접하게 연결. 유닉스가 거의 전적으로 C로 작성되었기 때문에 새로운 컴퓨터에 쉽게 포팅될 수 있음. C는 시스템 수준 프로그래밍을 위해 선택된 언어. C언어의 포인터는 혼란과 프로그래밍 에러의 공통적 원인. 이를 보완한 것이 C++
포팅이란?	컴퓨터 과학에서 실행 가능한 프로그램이 원래 설계된 바와 다른 환경에서 동작할 수 있게 하는 과정

 

 

1.2 프로그램은 다른 프로그램에 의해 다른 형태로 번역된다.

소스 코드	hello.c 프로그램은 인간이 바로 읽을 수 있음. 그러나 시스템에서 실행시키려면, 각 C 문장들은 다른 프로그램들에 의해 저급 기계어 인스트럭션들로 번역되어야 한다. 실행 가능 목적파일로 변환되어야 하는데 이는 0과 1로 이루어진 명령어를 뜻한다. 대표적인 컴파일러 gcc는 소스파일에서 오브젝트 파일로 번역한다. (gcc -o hello hello.c) 4단계를 거쳐 실행된다. C전처리기, 컴파일러, 어셈블러, 링커. 이를 합쳐서 컴파일 시스템이라고 부른다.
저급 기계어 인스트럭션	컴퓨터에 일을 시키는 단위. 컴퓨터가 알아들을 수 있는 기계어로 구성. 지시 또는 명령이라고 함.

 

 

1.3  컴파일 시스템이 어떻게 동작하는지 이해하는 것은 중요하다.

프로그램 성능	C프로그램 작동 시 컴파일러가 어떻게 지시를 내리는지 알아야함. 예를 들어 switch문과 if else 문은 어떤 상황에 더 효율적일지, 함수 호출시 발생하는 오버헤드는 얼마나 되는지, while루프와 for루프의 차이 등등, 어떤 상황에 어떤 지시를 내려야 최적의 코드를 작성할 수 있는지 알게된다.
오버헤드	어떤 처리를 하기 위해 들어가는 간접적인 시간, 메모리
링크 에러 이해하기	큰 큐모의 소프트 웨어를 개발하다 보면 빌드 단계에서 링크에 의해 에어가 발생하는데 이는 정말 해결하기 까다롭다. 예를들어 링커가 어떤 참조를 풀어낼 수 없다고 할 떄는 무엇을 의미하는가? 정적 변수와 전역 변수의 차이는 무엇인지, 만약 각기 다른 파일에 동일한 이름의 두 개의 전역변수를 정의한다면 무슨 일이 일어나는지, 정적 라이브러리와 동적 라이브러리의 차이는 무엇인지 등등
보안약점 피하기	안전한 프로그래밍을 배우는 첫 단계는 프로그램 스택에 데이터와 제어 정보가 저장되는 방식 떄문에 생겨나는 영향을 이해하는 것 이다.

 

 

1.4 프로세서는 메모리에 저장된 인스트렉션을 읽고 해석한다

쉘	쉘에 명령어를 입력해 명령을 실행한다. 만약 내장 쉘 명령어가 아니면 쉘은 실행파일의 이름으로 판단하고, 그 파일을 로딩해서 실행해준다.
시스템 하드웨어의 구성	대략적으로 살펴보자면 위쪽 사진과 비슷하다고 생각하면 된다.
버스	시스템 내부를 관통하는 전기적 배선로 컴포넌트 간 바이트 정보를 전송 대부분의 컴퓨터들은 4, 8 byte 크기의 데이터를 전송한다.
입출력 장치	키모드, 마우스, 모니터, 데이터의 장기저장을 위한 디스크 드라이브 등등 처음 작성된 hello 프로그램은 디스크에 저장되어있다.
메인 메모리 (RAM)	메인 메모리는 프로세서가 프로그램을 실행하는 동안 데이터와 프로그램을 모두 저장하는 임시 저장장치이다.
레지스터	레지스터는 메모리로 부터 명령을 읽고 실질적으로 연산을 실행하는 메모리 영역이다.
프로그램 카운터	프로그램 카운터에는 다음에 수행 할 메모리의 주소가 저장된다.
메모리 주소 레지스터	이 레지스터는 프로그램 카운터에서 수행할 주소를 넘겨받은 다음에, 그 주소를 찾아가 데이터를 가져오는 역할을 한다.
메모리 버퍼 레지스터	메모리 주소 레지스터가 가져온 데이터나 명령들을 일시적으로 저장한다. 이 레지스터에 저장된 내용 중 명령은 명령어 레지스터로 전송되고 연산에 사용될 데이터는 누산기 레지스터로 이동한다.
명령어 레지스터	명령어에 관한 데이터가 저장된다.
누산기 레지스터	연산의 결과 값이나 중간 값을 일시적으로 저장한다. 최종 결과값은 메모리 버퍼 레지스터로 이동해 메모리에 값을 저장하게 된다.
제어장치	명령어 레지스터에 있는 명령어를 받아 해석하고 해석된 명령을 실행할 시스템에 지시를 보내준다.
ALU	ALU는 산술 논리 연산을 실행한다.

 

 

 

탐색 알고리즘

 

1. 선형 탐색 알고리즘

선형 탐색 알고리즘

모든 배열을 순회하면서 모든 요소를 비교해보는 알고리즘 가장 단순하고 간단한 탐색 알고리즘이다. 시간복잡도는 O(n)으로 비교적 느린편 정렬되지 않은 리스트에서도 사용할 수 있는 방법이다.

 

 

2. 이진 탐색 알고리즘

이진 탐색 알고리즘

이진 탐색은 오름차순으로 정렬되어 있는 리스트에서 특정 값을 찾을때 사용된다. 시간복잡도는 O(log n)이 성립하며 빠른편이다. 단점은 정렬된 리스트에서만 이진 탐색을 사용 가능하다.

 

 

3. 해시 탐색 알고리즘

해시 탐색 알고리즘

해시 탐색 알고리즘은 key값이 입력되면 해시 함수로 연산한 결과가 해시 주소가 되고, 이를 인덱스로 사용하여 항목에 접근하는 방법이다. 이 방법은 얼핏보면 무조건 O(1)의 시간복잡도를 제공할 것 같지만, 해시 충돌이라는 개념이 추가되면 조금 달라진다. 그 이유는 해시 함수를 거쳐가며 같은 인덱스가 산출되는 경우가 있는데, 이를 해시 충돌이라고 한다. 이를 주로 체이닝 방법을 통해 해결하는데, 해시 테이블의 각 버킷에 연결리스트나 유사한 자료구조를 사용하여 충돌된 항목을 저장한다. 충돌이 발생하더라도 연결 리스트를 통해 해당 버킷에 속한 모든 항목에 접근할 수 있으므로 충돌을 해결하기가 비교적 간단하다. 하지만 이 방법은 최악의 경우 시간 복잡도가 O(n)으로 올라간다는 단점이 있다.

 

 

4. 이진 탐색 트리

이진 탐색 트리 알고리즘

이진 탐색과 연결리스트를 결합한 자료구조. 자료 입력, 삭제등 수정을 용의하게 만들기 위해 사용됨. 이진 탐색에서 노드의 추가, 삭제가 용의하게 만들기 위해 개선된 방식 왼쪽 노드는 부모의 노드보다 작아야 하고, 오른쪽 노드는 부모 노드보다 커야 함