Study

CHAPTER 3 프로그램의 기계수준 표현 3.7 프로시저 프로시저 호출 : 스프트웨어에서의 주요 추상, 지정된 인자들과 리턴 값으로 특정 기능을 구현하는 코드를 감싸주는 방법을 제공 잘 설계된 소프트웨어 : 무슨 값이 게산되는가, 이 프로시저가 프로그램 상태에 무슨 효과를 갖는가 에 대한 간결한 인터페이스 정의 제공 일부 동작의 구체적인 구현은 감춰주는 방식으로 프로시저를 추상화 메커니즘으로 이용 ex. 프로시저 P가 프로시저 Q를 호출, Q가 실행한 후 다시 P로 리턴 제어권 전달 : 프로그램 카운터는 진입할 때 Q에 대한 코드의 시작주소로 설정되고, 리턴할 때는 P에서 Q를 호출하는 인스트럭션 다음의 인스트럭션으로 설정되어야 함 데이터 전달 : P는 하나 이상의 매개변수를 Q에 제공할 수 있어야 하며, Q는 다시 P로 하나의 값을 리턴할 수 있어야 함. 메모리 할당과 반납 : Q는 시작할 때 지역변수들을 위한 공간을 할당할 수도, 리턴할 때 이 저장소를 반납할 수 있음. 3.7.1 런타임 스택 C언어와 다른 대부분의 언어에서의 프로시저 호출 동작방식 : 스택 자료구조가 제공하는 후입선출 메모리 관리 방식을 활용 ...

Chapter 3 프로그램의 기계수준 표현 컴퓨터 : 데이터를 처리하고, 메모리를 관리하고, 저장장치에 데이터를 읽거나 쓰고, 네트워크를 통해 통신하는 등의 하위 동작들을 인코딩한 연속된 바이트인 기계어 코드(machinc code)를 실행한다. 컴파일러 : 프로그램 언어의 규칙, 대상 컴퓨터의 인스트럭션 집합, 운영체제의 관례 등에 따라 기계어 코드 생성 GCC C 컴파일러 : 기계어 코드를 문자로 표시한 어셈블리 코드의 형태로 출력을 만들어 프로그램의 각 인스트럭션 생성 GCC : 어셈블러와 링커 호출 => 어셈블리 코드로부터 실행 가능한 기계어 코드 생성 ...

삽입 정렬 : 점진적인 방법 사용 원소 A[j]를 정렬된 부분 배열 A[1 .. j-1]의 적절한 위치에 삽입 2.3.1 분할정복 접근법 재귀적 구조 : 주어진 문제를 풀기 위해 자기 자신을 재귀적으로 여러 번 호출함으로써 밀접하게 연관된 부분 문제를 다룸. => 분할정복 접근법 분할정복 접근법 : 전체 문제를 원래 문제와 유사하지만 크기가 작은 몇 개의 부분 문제로 분할하고, 부분 문제를 재귀적으로 품. 찾은 해를 결합하여 원래 문제의 해를 만들어 낸다. 분할정복의 3단계 ...

2.2 알고리즘의 분석 알고리즘의 분석은 그 알고리즘을 실행하는 데 필요한 자원을 예측하는 것을 의미한다. 메모리, 통신 대역, 하드웨어 등 대부분은 계산 시간을 의미한다. 이 책에서의 가정 알고리즘은 단일 프로세서와 랜덤 접근 기계(RAM, random-access machine) 모델로 가정 : 명령어는 동시X, 하나씩 실행 산술 연산, 데이터 이동연산, 제어 연산 등 : 상수 시간 RAM 모델의 데이터형 : 정수(integer)와 부동소수(floating point) 각 워드 크기에 제한을 가정 : 입력 크기가 n인 입력을 다룰 때 정수는 상수 c>= 1에 대해 clg2비트로 표현된다고 가정(워드는 상수로 처리하므로 너무 크면 안된다.) ...

2.1 삽입정렬 정렬문제 입력 : n개 수들의 수열 $$ <a_1, a_2, …, a_n> $$ 출력 : $$ a’_1 <= a’_2 <= … <= a’_n $$ 을 만족하는 입력 수열의 순열(재배치) $$ <a’_1,a’_2, …, a’_n> $$ 정렬하고자 하는 숫자를 키라고 한다. 의사코드와 “실제” 프로그램 코드의 차이는, 의사 코드에서는 알고리즘을 가장 분명하고 간결하게 서술할 수 있다면 어떤 표현 방법을 사용해도 좋음. 영어, 한글 문장등이 들어갈 수 도 있음. 데이터 추상화, 모듈화, 오류처리 등의 소프트웨어 공학 관점의 문제를 고려하지 않음. ...

1.1 알고리즘 알고리즘 어떤 값이나 값의 집합을 입력으로 받아 또 다른 값이나 값의 집합을 출력하는 잘 정의된 계산 절차 어떤 입력을 어떤 출력으로 변환하는 일련의 계산과정 잘 정의된 계산 문제를 풀기 위한 도구 정렬 문제 입력 : n개 수들의 수열 $$ <a_1,a_2, …, a_n> $$ 출력 : $$ a^{’}_1≤a^{’}_2≤ …≤a^{’}_n $$ 을 만족하는 입력 수열의 순열(재배치) $$ <a^{’}_1, a^{’}_2, …, a^{’}_n> $$ ex) <31, 41, 59, 26, 41, 58>이 입력 수열로 주어지면 정렬 알고리즘은 수열 <26, 31, 41, 41, 58, 59>를 출력한다. -> 입력수열 : 정렬 문제의 사례 ...

1.2 기술로서의 알고리즘 컴퓨터는 상당히 빠를 수 있지만 ‘무한히’ 빠를수는 없다. 메모리도 매우 저렴할 수 있지만 비용이 ’전혀‘ 들지 않을 수는 없다. 효율성 동일한 문제 해결을 위한 알고리즘이 효율성 면에서 극적으로 다를 수 있다. 하드웨어, 소프트웨어로 인한 차이보다 더 심각할 수 있다. ex) 삽입 정렬 : n개의 값 정렬위해 $$ c_1n^2 $$ 에 비례하는 시간 걸림(c_1은 n에 독립인 상수). 즉, n^2에 비례함 병합 정렬 : $$ c_2nlog_2n $$ 의 시간 걸림(c2는 n에 독립인 또 다른 상수). 즉, nlog_2(n) 상수는 입력 크기 n에 비해 수행시간에 영향을 훨씬 작게 준다. ...

1.1 정보는 **비트****와** **컨텍스트****로 이루어진다.** 비트(Bit) : binary digit의 준말. 0과 1로 이루어진 가공된 데이터(정보)의 최소 단위이다. 보통 8bit = 1byte이지만, 반드시 그렇게 정의된 것만은 아니다. 1Mb 와 1MB는 다르며, 전자를 8로 나눈 결과가 후자이다. 우리가 흔히 광고에서 보는 인터넷 속도도 100Mbps도 초당 12.5MB의 속도라는 뜻이다. 컨텍스트(Context) : 단순한 정보 원본 이상으로 문맥, 상황에 따라 어떤 해석이 가미되어 이해되는 한차원 높은 공간을 의미한다. 하드웨어나 운영체제 관점에서 프로세서 안에 있는 레지스터, 플래그등의 현재 값 상태들의 집합를 의미한다. 소프트웨어 관점에서는 상황에 맞게끔 실행/결정/판단 해야 하는 부분을 의미한다. 더 나아가 문맥 교환(context switching)은 멀티태스킹 작업 수행시 태스크 상태 정보를 레저스터들에 저장 또는 이전 상태를 불러오기 위한 작업을 의미한다. 여기서 태스크 상태 정보는 CPU 레지스터, 메모리 스택을 의미한다. ...