크래프톤 정글 - 1Week 24.01.12 - 24.01.18

벌써 1주가 또 지났다.

배운 것, 공부한 것은 많은 느낌이지만 내 것이 안됐다.

지식들이 머리속에서 붕 떠있다는 느낌이 든다.

빠르게 캐치해서 내 것으로 만들지않는다면 그대로 날아가지 않을까 생각한다.

조금 더 공부할 때 집중해서, 효율을 늘려봐야겠다. 시간은 이미 많이 투자하고 있으니 집중의 정도를 늘려 효율의 향상을 기대해보는게 맞지 않을까..?

CSAPP

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

• 모든 시스템 내부의 정보 - 디스크 파일, 메모리 상의 프로그램 , 데이터, 네트워크를 통해 전송되는 데이터는 - 비트들로 표시된다.
• 서로 다른 객체들을 구분하는 방법은 이를 바라보는 컨텍스트에 의해서 결정된다.
• 다른 컨텍스트에서는 동일한 일련의 바이트가 정수, 부동소수, 문자열 또는 기계어 명령을 의미 할 수 있다.
• 프로그램은 연속된 바이트들로 파일에 저장된다. 각 바이트는 특정 문자에 대응되는 정수 값을 갖는다
• 대부분의 컴퓨터 시스템은 텍스트 문자를 아스키(ASCII) 표준을 사용하여 표시한다. 아스키 표준은 각 문자를 바이트 길이의 정수 값으로 나타낸다.
• 아스키 문자들로만 이루어진 파일들은 텍스트 파일이라고 부른다. 다른 모든 파일들은 바이너리 파일이라고 한다.

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

• GCC 컴파일러 드라이버는 소스파일을 읽어서 실행파일로 번역한다. 번역은 4개의 단계를 거쳐서 실행된다. 이 네 단계를 실행하는 프로그램들(전처리기, 컴파일러, 어셈블러, 링커)을 합쳐서 컴파일 시스템이라고 한다.
• 전처리 단계 : 전처리기(cpp)는 본래의 C프로그램을 #문자로 시작하는 디렉티브(directive)에 따라 수정한다. 그 결과 일반적으로 .i로 끝나는 새로운 C프로그램이 생성된다.
• 컴파일 단계 : 컴파일러(ccl)은 텍스트파일 .i를 텍스트 파일인 .s로 번역하며, 이 파일에는 어셈블리어 프로그램이 저장된다.
• 어셈블리 단계 : 어셈블러(as)가 .s를 기계어 인스트럭션으로 번역하고, 이들을 재배치 가능 목적프로그램의 형태로 묶어서 .o라는 목적파일에 그 결과를 저장한다. 이 파일은 인스트럭션들을 인코딩하기 위한 17바이트를 포함하는 바이너리 파일이다.
• 링크 단계 : 프로그램이 C컴파일러에서 제공하는 표준 C라이브러리에 들어있는 함수를 호출하는 것에 주목할 필요가 있다. printf 함수는 이미 컴파일러 된 별도의 목적파일인 printf.o에 들어 있으며, 이 파일은 hello.o 파일과 어떤 형태로든 결합 되어야 한다. 링커 프로그램(ld)이 이 통합작업을 수행한다.

왜 컴파일 시스템이 어떻게 동작하는지 알아야 하는가.

• 프로그램 성능 최적화
• 링크 에러 이해
• 보안 약점 피하기

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

버스(Buses)

• 시스템 내를 관통하는 전기적 배선군을 버스라고 하며, 컴포넌트 간 바이트 정보들을 전송한다.
• 버스는 일반적으로 워드 word라고 하는 고정 크기의 바이트 단위로 데이터를 전송하도록 설계된다.
• 한 개의 워드를 구성하는 바이트 수는 시스템마다 보유하는 기본 시스템 변수다. 4바이트(32비트), 8바이트(64비트)

입출력 장치

• 시스템과 외부 세계와의 연결을 담당한다.
• 각 입출력 장치는 입출력 버스와 컨트롤러나 어댑터를 통해 연결된다. 이 두장치의 차이는 패키징(packaging)에 있다. 컨트롤러는 디바이스 자체가 칩셋이거나 시스템의 머더보드에 장착된다. 어댑터는 머더보드의 슬롯에 장착되는 카드이다.

메인 메모리

• 프로세서가 프로그램을 실행하는 동안 데이터와 프로그램을 모두 저장하는 임시 저장장치다.
• 물리적으로 메인 메모리는 DRAM칩들로 구성되어 있다.
• 논리적으로는 메모리는 연속적인 바이트들의 배열로, 각각 0부터 시작해서 고유의 주소(배열의 인덱스)를 가지고 있다.
• 일반적으로 한 개의 프로그램을 구성하는 각 기계어 인스트럭션은 다양한 바이트 크기를 갖는다.

프로세서

• 주처리장치(CPU) 또는 간단히 프로세서는 메인 메모리에 저장된 인스트럭션들을 해독(실행) 하는 엔진이다.
• 프로세서의 중심에는 워드 크기의 저장장치(또는 레지스터)인 프로그램 카운터(PC)가 있다.
• 시스템에 전원이 공급되는 순간부터 전원이 끊어질 때까진 프로세서는 프로그램 카운터가 가리키는 곳의 인스트럭션을 반복적으로 실행하고 PC값이 다음 인스트럭션 위치를 가리키도록 업데이트 한다. 프로세서는 자신의 인스트럭션 집합 구조(ISA)로 정의되는 매우 단순한 인스트럭션 실행 모델을 따라 작동하는 것 처럼 보인다.
• 프로세서는 PC가 가리키는 메모리로부터 인스트럭션을 읽어오고, 이 인스트럭션에서 비트들을 해석하여 인스트럭션이 지정하는 간단한 동장을 실행하고, PC를 다음 인스트럭션 위치로 업데이트 한다. 이 위치는 연속적일 수도 있고, 그렇지 않을 수도 있다.
• 인스트럭션 요청에 의해 CPU가 실행하는 단순한 작업
  • 적재(Load) - 메인 메모리에서 레지스터에 한 바이트 또는 워드를 이전 값에 덮어쓰는 방식으로 복사
  • 저장(Store) - 레지스터에서 메인 메모리로 한 바이트 또는 워드를 이전 값을 덮어쓰는 방식으로 복사
  • 작업(Operate) - 두 레지스터의 값을 ALU로 복사하고 두 개의 워드로 수식연산을 수행한 뒤, 결과를 덮어쓰기 방식으로 레지스터에 저장
  • 점프(Jump) - 인스트럭션 자신으로부터 한 개의 워드를 추출하고, 이것을 PC에 덮어쓰기 방식으로 복사

캐시가 중요하다.

• 시스템이 정보를 한 곳에서 다른곳으로 이동시키는 일에 많은 시간을 보낸다. 그래서 시스템 설계자들의 주요 목적은 이러한 복사과정들을 가능한 한 빠르게 동작하도록 한다.
• 프로세서 - 메모리 간 격차에 대응하기 위해 시스템 설계자는 보다 작고 빠른 캐시 메모리라고 부르는 저장장치를 고안하여 프로세서가 단기간에 필요로 할 가능성이 높은 정보를 임시로 저장할 목적으로 사용한다.
• L1,L2,L3 캐시는 SRAM이라는 하드웨어 기술을 이용해 구현한다.
• 캐시 시스템의 이면에 깔려 있는 아이디어는 프로그램이 지엽적인 영역의 코드와 데이터를 액세스 하는 경향인 지역성(locality)을 활용하여 시스템이 매우 크고 빠른 메모리 효과를 얻을 수 있다.

• 계층의 꼭대기에서부터 맨 밑바닥까지 이동할수록 저장장치들은 더 느리고, 더 크고, 바이트당 가격이 싸진다.
• 메모리 계층 구조의 아이디어 - 한 레벨의 저장장치가 다음 하위 레벨의 저장장치의 캐시역할을 한다.

운영체제는 하드웨어를 관리한다.

• 운영체제는 하드웨어와 소프트웨어 사이 소프트웨어 계층
• 응용프로그램이 하드웨어를 제어하려면 언제나 운영체제를 통해서 해야 한다.

운영체제의 2가지 목적

1. 제멋대로 동작하는 응용 프로그램들이 하드웨어를 잘못 사용하는 것을 막기 위해서
2. 응용 프로그램들이 단순하고 균일한 매커니즘을 사용하여 복잡하고 매우 다른 저 수준 하드웨어 장치를 조작할 수 있게 한다.

• 이러한 두 가지 목적을 추상화를 통해 달성한다
  • 추상화란 어떤 복잡한 것들을 단순화 시켜서 표현한 것.

프로세스

• 프로세스는 실행 중인 프로그램에 대한 운영체제의 추상화이다.
• 운영체제는 문맥전환(Context Switching)을 사용해 교차실행을 수행한다.
• 운영체제는 프로세스가 실행 하는데, 필요한 모든 상태정보의 변화를 추적한다. 상태정보는 컨텍스트라고 부르는데 컨텍스트는 PC, 레지스터 파일, 메인 메모리의 현재값을 포함하고 있다.
• 운영체제는 현재 프로세스에서 다른 새로운 프로세스로 제어를 옮기려고 할 때 현재 프로세스의 컨텍스트를 저장하고 새 프로세스의 컨텍스트를 복원시키는 문맥전환을 실행하여 제어권을 새 프로세스로 넘겨준다. 새 프로세스는 이전에 중단했던 바로 그 위치부터 다시 실행된다.
• 하나의 프로세스에서 다른 프로세스로의 전환은 운영체제 커널Kernel에 의해 관리된다. 커널은 운영체제 코드의 일부분으로 메모리에 상주한다.
• 응용프로그램이 운영체제에 작업을 요청하면 컴퓨터는 특정 시스템 콜을 실행해서 커널에 제어를 넘겨준다. 그러면 커널은 요청된 작업을 수행하고 응용프로그램으로 리턴한다.
• 커널은 별도의 프로세스가 아니라 모든 프로세스를 관리하기 위해 시스템이 이용하는 코드와 자료구조의 집합이다.

쓰레드(Thread)

• 프로세스가 마치 한 개의 제어흐름을 가지고 있는 것으로 생각할 수 있지만, 시스템에서는 프로세스가 쓰레드라고 하는 다수의 실행 유닛으로 구성되어 있다.
• 쓰레드는 해당 프로세스의 컨텍스트에서 실행되며 동일한 코드와 전역 데이터를 공유한다. 점점 쓰레드의 중요성이 커지고 있는데, 다수의 프로세스들에서보다 데이터 공유가 쉽다는 점과 쓰레드가 프로세스보다 더 효율적이라는 점 때문이다.
  • context switching시에 overhead 때문에 → cache memory 초기화 등 무거운 작업
    • overhead - 어떤 처리를 하기 위해 들어가는 간접적인 처리 시간

가상메모리(Virtual Memory)

• 각 프로세스들이 메인 메모리 전체를 독점적으로 사용하고 있는 것 같은 환상을 제공하는 추상화 각 프로세스들은 가상주소라는 균일한 메모리의 모습을 가지게 된다.
  • 프로그램 코드, 데이터 : 코드는 모든 프로세서들이 같은 주소에서 시작. 다음 C전역변수에 대응되는 데이터 위치들이 따라온다. 코드와 데이터 영역은 .O목적 파일에서 직접 초기화한다.
  • 힙(heap) : 런타임 프로세스가 실행되면서 런타임에 동적으로 크기가 줄었다가 늘었다가 한다.
  • 공유 라이브러리 : 주소공간 중간 부근에 C표준 라이브러리나 수학 라이브러리와 같은 코드와 데이터를 저장하는 영역
  • 스택(stack) : 사용자 가상 메모리 맨 위 컴파일러가 함수 호출을 구현하기 위해 사용하는 사용자 스택. 힙과 마찬가지로 동적으로 늘었났다 줄어들었다 한다. 특히, 함수를 호출할 때 스택이 커지고 함수에서 리턴 될 때는 줄어든다.
    • 스택은 현재 활성화 된 함수에 로컬로 고정된 길이의 변수를 저장하는데 자주 사용한다. 프로그래머가 명시적으로 스택을 사용하여 가변길이의 로컬데이터를 저장하도록 선택할 수 있다. Stack-Based Memory Allocation(SBMA) 힙(HBMA)와 대조된다.
    • 힙에 비해서 훨씬 빠르고, 메모리 자동 회수가 가능하다. 작아서 스택오버플로우 충돌이 가능하다.
  • 커널 가상 메모리 - 주소 공간의 맨 윗부분은 커널을 위해 예약되어있다. 응용프로그램은 이 영역을 읽거나 쓰는것이 금지되어있다.

시스템은 네트워크를 사용하여 다른 시스템과 통신한다.

• 최신 시스템들은 네트워크에 의해 다른 시스템과 종종 연결된다. 이러한 개별 시스템의 관점에서 볼 때 네트워크는 또 다른 입출력 장치로 볼 수 있다.

중요한 주제들

Amdahl의 법칙

• 일부 성능 개선의 효율성에 대해 간단하지만 직관적인 관찰
• 우리가 어떤 시스템의 한 부분의 성능을 개선할 때, 전체 시스템에 대한 효과는 그 부분이 얼마나 중요한가와 이 부분이 얼마나 빨라졌는가에 관계된다.
• 시스템에 주요 부분에 대해 실질적인 개선을 해도, 총 속도향상은 적을 수 있다. 전체 시스템을 상당히 빠르게 하기 위해서는 전체 시스템의 매우 큰 부분의 성능을 개선해야 한다.

동시성과 병렬성

• 동시성(Concurrency) : 다수의 동시에 벌어지는 일을 갖는 시스템에 관한 일반적인 개념
• 병렬성(Parallelism) : 동시성을 사용해서 시스템을 보다 빠르게 동작하도록 하는 것.

쓰레드 수준 동시성

• 쓰레드를 이용하면 한 개의 프로세스 내에서 실행되는 다수의 제어흐름을 가질 수도 있다.
• 1960 초반 시간공유(time-sharing) 기법의 출현으로 동시 실행에 대한 지원이 컴퓨터 시스템에 나타났다. 한 개의 컴퓨터가 실행하는 프로세스를 빠르게 전환하는 방법을 사용한다. 이런 형태의 동시성은 여러 명이 한 개의 웹 서버로부터 페이지를 사용하고자 할 때처럼 다수의 사용자들이 시스템과 동시에 교신할 수 있게 한다.
• 단일 프로세서 시스템 : 실질적인 계산은 한 개의 프로세서에 의해 실행
• 멀티 프로세서 시스템 : 여러 개의 프로세서를 가지고 하나의 운영체제 커널의 제어 하에 동장하는 경우.
  • 멀티코어 프로세서는 여러 개의 CPU(코어라고 하는)를 하나의 집적화된 칩에 내장하고 있다.
  • 이 프로세서 칩은 다수의 코어를 가지고 있으며, 각각 별도의 L1,L2 캐시를 가지고 메인 메모리 인터페이스뿐만 아니라 상위 수준 캐시를 공유한다.
• 멀티쓰레딩, 하이퍼쓰레딩 : 하나의 CPU가 여러 개의 제어 흐름을 실행할 수 있게 해주는 기술.
  • 하이퍼쓰레드 프로세서에서는 매 사이클 마다 실행할 쓰레드를 결정한다. 어느 쓰레드가 데이터를 캐시에 로딩하기 위해 대기해야 한다면, CPU는 다른 쓰레드를 실행할 수 있다.
• 멀티프로세싱 이용으로 시스템 성능을 두가지 방법으로 개선할 수 있다.
  1. 다수의 태스크를 실행할 때, 동시성을 시뮬레이션할 필요를 줄여준다.
  2. 멀티 프로세싱으로 한 개의 응용프로그램을 빠르게 실행할 수 있지만, 프로그램이 병렬로 효율적으로 실행할 수 있는 멀티쓰레드의 형태로 표현되었을 때에만 가능하다.

인스트럭션 수준 병렬성

• 최근 프로세서들은 훨씬 낮은 수준에서 추상화로 여러 개의 인스트럭션을 한 번에 실행할 수 있다. 이런 특성을 인스트럭션 수준 병렬성이라고 한다. 4장에서 파이프라이닝 기법에 대해 배운다.
• 파이프라이닝 기법은 하나의 인스트럭션을 실행하기 위해 요구되는 일들을 여러 단계로 나누고 프로세서 하드웨어가 일련의 단계로 구성되어 이들 단계를 하나씩 각각 수행한다. 이들 단계는 병렬로 동작할 수 있다.

3. 프로그램의 기계수준 표현

• 어셈블리 코드를 짤 때 저급 인스트럭션을 명시해야 하는데, 대개의 경우 고급 언어가 제공하는 높은 수준의 추상화를 사용하는 것이 보다 더 생산적이고 안정적이다.

그렇다면 왜 WHY? 기계어를 사용하고 공부할까?

• 컴파일러를 적절한 커맨드라인 인자와 함께 호출하면 컴파일러는 어셈블리 코드 형태의 파일로 출력을 생성한다. 이 코드를 이해하면 컴파일러의 최적화 성능을 알 수 있고, 코드에 내재된 비효율성을 분석할 수 있다.
• 프로그램이 얼마나 효율적으로 실행될지 이해하기 위해서 생성된 어셈블리 코드를 컴파일하고 분석해 보곤한다. 더욱이 고급언어에서 제공하는 추상화 계층 때문에 이해 가능한 프로그램의 런타임 동작이 감춰지는 경우도 종종 있다.
• 악성 프로그램이 시스템을 감염 시킬 수 있도록 프로그램을 공격하는 방법 중 상당수가 프로그램이 런타임 제어정보를 저장하는 방식의 미묘한 차이와 관련이 있다. 이러한 취약성이 어디서 발생하는지, 이런 공격을 어떻게 막을 수 있는지 이해하려면 프로그램의 기계수준 표현에 대한 지식이 필요하다.

상세한 내용을 완벽히 이해하면 보다 심오하고 보다 근본적인 개념들을 이해할 수 있게 된다. ‘일반적인 원리는 이해해도 자세한 내용은 배우고 싶지 않다.’ 고 말하는 사람들은 자신을 속이는 것이다.

기계수준 코드

• 컴퓨터 시스템은 보다 간단한 추상화 모델을 이용해서 세부 구현 내용을 감추면서 추상화의 여러가지 다른 형태를 사용하고 있다. 이들 중 두 가지가 기계 수준 프로그래밍에서 특히 중요하다.
  1. 기계수준 프로그램 형식과 동작은 인스트럭션 집합구조(Instruction Set Architecture) 즉 ‘ISA’에 의해 정의된다. 이 ISA는 프로세서의 상태, 인스트럭션의 형식, 프로세서 상태에 대한 각 인스트럭션들의 영향을 정의한다. x86-64를 포함해 대부분의 ISA는 인스트럭션이 순차적인 실행을 하는 것 처럼 프로그램 동작을 설명한다. 프로세서 하드웨어는 훨씬 정교해서 여러 인스트럭션을 동시에 실행하지만 ISA에 의한 순차적 동작과 일치하는 전체동작을 보이도록 해주는 안전장치를 사용한다.
  2. 기계수준 프로그램이 사용하는 주소는 가상주소이며, 메모리가 매우 큰 바이트 배열인 것처럼 보이게 하는 메모리 모델을 제공한다.
• 컴파일러는 전체 컴파일 순서에서 C에서 제공하는 추상화 된 실행모델로 표현된 프로그램을 프로세서가 실행하는 매우 기초적인 인스트럭션들로 변환하는 대부분의 일을 수행한다.
• 어셈블리 코드 표현은 기계어 코드와 매우 유사하다. 주요 특징은 바이너리 기계어 코드 형식과 비교할 때 더 읽기 쉬운 텍스트 형식이라는 것이다.
• X86-64를 위한 기계어 코드
  • 프로그램 카운터(PC x86-64에서는 %rip) : 실행할 다음 인스트럭션의 메모리 주소
  • 정수 레지스터 파일 : 64비트 값을 저장하기 위한 16개의 이름을 붙인 위치를 갖는다. 이들 레지스터는 주소나 정수 데이터를 저장할 수 있다. 일부 레지스터는 프로그램의 중요한 상태를 추적하는 데 사용할 수 있으며, 다른 레지스터들은 함수의 리턴 값뿐만 아니라 프로시저의 지역변수와 인자 같은 임시 값을 저장하는데 사용한다.
    • 프로시저 : 일련의 쿼리를 마치 하나의 함수처럼 실행하기 위한 쿼리의 집합 함수랑 비슷한 느낌.
  • 조건코드 레지스터 : 가장 최근에 실행한 산술 또는 논리 인스트럭션에 관해 상태 정보 저장. if나 while문 구현할 때 필요한 제어나 조건에 따른 데이터 흐름의 변경을 구현하기 위해 사용한다.
  • 벡터 레지스터 - 하나 이상의 정수나 부동소수점 값 저장
• C가 다른 종류의 데이터 타입을 선언하고 메모리에 할당 할 수 있는 모델을 제공하는 반면, 기계어 코드는 메모리를 단순히 바이트 주소지정이 가능한 큰 배열로 본다. C에서 배열과 구조체 같은 연결된 데이터 타입들은 기계어 코드에서는 연속적인 바이트들로 표시된다.
  • 심지어 포인터와 정수형 사이에도 구분을 하지 않는다.
• 프로그램 메모리는 프로그램의 실행 기계어 코드, 운영체제를 위한 일부 정보, 프로시저 호출과 리턴을 관리하는 런타임 스택, 사용자에 의해 할당된 메모리 블록들을 포함하고 있다. 언제나 가상주소의 일부 제한된 영역만이 유효하다
• 운영체제는 이 가상 주소공간을 관리해서 가상주소를 실제 프로세서 메모리 상의 물리적 주소 값으로 번역해준다.
• 하나의 기계어 인스트럭션은 매우 기초적인 동작만을 수행한다.

프로그램의 인코딩

• 일반적으로 최적화 수준을 올리게 되면 최종 프로그램은 더 빨리 동작하게 되지만, 컴파일 시간이 증가하고 디버깅 도구를 실행하기가 어려워질 위험이 있다.
• 높은 수준 최적화를 적용하면 만들어진 코드가 너무 많이 변경되어서 본래의 코드와 생성된 기계어 코드 간 관계를 이해하기 어렵다.
• 컴퓨터에 의해 실제 실행된 프로그램은 단순히 일련의 인스트럭션을 인코딩한 일련의 바이트다. 컴퓨터는 인스트럭션들이 생선된 소스 코드에 대한 정보를 거의 갖고 있지 않다.
• 기계어 코드 파일의 내용을 조사하려면, 역어셈블러라고 하는 프로그램이 매우 중요하다.

기계어 코드 특징

• x86-64 인스트럭션들은 1에서 15바이트 길이를 갖는다. 인스트럭션 인코딩은 자주 사용되는 인스트럭션들과 오퍼랜드가 적은 것들이 짧은 길이를 갖도록 하고, 그 반대의 경우 좀 더 긴 인스트럭션 길이를 가지도록 인코딩한다.
  • 오퍼랜드 : 연산을 수행하는데 필요한 데이터, 데이터 주
• 인스트럭션 형식은 주어진 시작 위치에서부터 바이트들을 기계어 인스트럭션으로 유일하게 디코딩할 수 있도록 설계한다.
  • 예를 들어, pushq %rbx 인스트럭션만이 바이트 값 53으로 시작될 수 있다.
• 역어셈블러는 기계어 코드 파일의 바이트 순서에만 전적으로 의존해서 어셈블리 코드를 결정한다. 소스코드나 프로그램의 어셈블리 코드 버전을 사용하지 않는다.

Algorithm

• 알고리즘은 값이나 값의 집합을 입력으로 받아 또 다른 값이나 값의 집합을 출력하는 잘 정의 된 계산절차, 잘 정의된 계산 문제를 풀기 위한 도구
• 알고리즘이 모든 입력 사례에 대해 항상 올바른 출력을 내고, 종료할 경우 이를 타당(Correct)하다고 하며, 그 타당한 알고리즘이 주어진 계산문제를 푼다(Solve)고 말한다.
• 자료구조는 자료를 편리하게 접근하고 변경하기 위해 자료를 저장하거나 조직하는 방법을 말한다. 각 자료구조의 장점과 한계를 잘 아는게 중요하다.

정수론(Number Theory)

• 정수의 성질을 다루는 수학의 한 분야이다.
• 우리가 왜 why? 공부해야 하는가
  • 현대 암호학은 주로 정수론에서 다루어지는 수학적인 성질을 바탕으로 하기에, 암호화 알고리즘을 이해하고 구현하기 위해서는 정수론에 대한 공부가 필요하다.
  • 컴퓨터에서 정수는 정확한 값을 가질 수 있다. 실수형 타입의 경우 반올림 오차(round off error)가 발생하기 때문에 이로 인한 문제가 발생할 수 있다.
• 정수와 자연수 소수를 중심적으로 다룬다.

소수(Prime Number)

• 정수론에서 가장 중심적으로 연구하는 것
• 1과 자기 자신만을 약수로 가지는 수

에라토스테네스의 체

• 소수를 찾는 방법
• √n 까지의 배수를 지운다
• 노가다 방식이라 상당히 무식한 방식이지만 특정 범위가 주어지고 그 범위 내 모든 소수를 찾아야 하는 경우 에라토스테네스의 체보다 빠른 방법이 없다.

골드바흐 추측

• 4 이상의 모든 짝수는 두 소수의 합으로 나타낼 수 있다.

유클리드 호제법

• 두 양의 정수, 두 다항식에서 최대 공약수를 구하는 방법
• 두 양의 정수 a,b(a>b)에 대해 a = bq + r (0≤ r < b) 라면 a,b의 최대 공약수는 b,r의 최대 공약수와 같다. gcd(a,b) = gcb(b,r)
• r=0 이면 a,b 최대 공약수는 b가 된다.

정렬(Sorting)

• Key를 항목값의 대소 관계에 따라 데이터 집합을 일정한 순서로 바꾸어 늘어놓는 작업
• 오름차순(ascend_order) : 값이 작은 데이터를 앞쪽에 배치
• 내림차순(descend_order) : 값이 큰 데이터를 앞쪽에 배치

정렬 알고리즘의 안정성

• 정렬 알고리즘은 안정적인(stable), 안정적이지 않은(unstable) 정렬로 나뉜다.
• 안정적인 정렬 알고리즘은 값이 같은 원소의 순서가 정렬 후에도 유지된다. 안정적이지 않은 정렬은 순서가 유지 된다는 보장을 할 수 없다.

내부정렬 외부정렬

• 내부정렬(internal_sorting) : 정렬할 모든 데이터를 하나의 배열에 저장할 수 있는 경우 사용하는 알고리즘
• 외부정렬(external_sorting) : 정렬할 데이터가 많아서 하나의 배열에 저장할 수 없는 경우 사용하는 알고리즘

정렬 알고리즘의 핵심은 교환, 선택, 삽입이다.😊

버블정렬(Bubble Sort)

• 이웃한 두 원소에 대소관계를 비교하여 필요에 따라 교환을 반복하는 알고리즘
• 단순 교환 정렬 이라고도 한다.
• 일련의 비교, 교환하는 과정을 패스(pass)라고 한다.
• 시간복잡도 O(n²), 공간복잡도 O(n)

단순 선택 정렬(Straight Selection Sort)

• 가장 작은 원소부터 선택해 알맞은 위치로 옮기는 작업
  1. 아직 정렬하지 않은 부분에서 값이 가장 작은 원소 a[min]을 선택한다.
  2. a[min]과 아직 정렬하지 않은 부분에 맨 앞에 있는 원소를 교환한다.
• 시간복잡도 O(n²), 공간복잡도 O(n)

단순 삽입 정렬(Straight Insertion Sort)

• 주목한 원소보다 더 앞쪽에서 알맞은 위치로 삽입하며 정렬하는 알고리즘
• 아직 정렬되지 않은 부분의 맨 앞 원소를 정렬된 부분의 알맞은 위치에 삽입한다.

종료조건

1. 정렬된 배열의 왼쪽 끝에 도달한 경우
2. tmp보다 작거나 키값이 같은 원소 a[j-1]을 발견한 경우

계속조건

1. j가 0보다 큰 경우
2. a[j-1]의 값이 tmp보다 큰 경우

장단점

• 장점 : 이미 정렬을 마쳤거나 정렬이 거의 끝나가는 상태에서 속도가 아주 빠르다.
• 단점 : 삽입할 위치가 멀면 이동횟수가 많아진다.

셸 정렬(Shell Sort)

• 단순 삽입 정렬의 장점은 살리고 단점은 보완하여 더 빠르게 정렬하는 알고리즘
• 먼저 정렬 할 배열의 원소를 그룹으로 나눠 각 그룹 별로 정렬을 수행한다.
• 그 후 정렬 된 그룹을 합치는 작업을 반복해서 원소의 이동횟수를 줄이는 방법
  • 2개 원소에서 4-정렬수행(4개 그룹 4번)
  • 4개 원소에서 2-정렬수행(2개 그룹 2번)
  • 8개 원소에서 1-정렬수행(1개 그룹 1번)

퀵 정렬(Quick Sort)

• 가장 빠른 알고리즘
• pivot을 기준으로 배열을 두 그룹으로 나눈다.
• pivot을 선택하는 방법은 여러가지 크게 첫번째 요소, 중간요소, 마지막 요소, 랜덤으로 선택하는 방식

진행방식

1. 피벗을 선택한다.
2. 오른쪽에서 왼쪽으로 가면서 피벗보다 작은 수를 찾는다.
3. 왼쪽부터 오른쪽으로 가면서 피벗보다 큰 수를 찾는다.
4. 각 인덱스 i,j에 대한 요소를 교환한다.
5. 2,3,4 과정을 반복한다.
6. 2,3을 진행할 수 없다면 현재 피벗과 교환
7. 그 결과 피벗을 기준으로 왼쪽은 피벗보다 작은 수들이 존재하고, 오른쪽에 큰 수들이 존재한다.

def quick_sort(arr = list):
	if len(arr) == 1:
		return arr
	pivot = arr[len(arr)//2]
	less_arr, equal_arr, greater_arr = [], [], []
	for i in arr:
		if i < pivot:
			less_arr.append(i)
		elif i > pivot:
			greater_arr.append(i)
		else:
			equal_arr.append(i)
	return quick_sort(less_arr) + equal_arr + quick_sort(greater_arr)

병합 정렬(Merge Sort)

• 배열의 앞부분과 뒷부분의 두 그룹으로 나누어 각각 정렬한 후 병합하는 작업 반복

진행

1. 리스트 길이가 0 또는 1이면 이미 정렬된 것으로 본다.
2. 그렇지 않은 경우 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
3. 각 부분 리스트를 재귀적으로 병합 정렬을 이용해 정렬한다.
4. 두 부분 리스트를 다시 하나의 정렬된 리스트로 병합한다.

• 분할(Divide) : 입력 배열을 같은 크기의 2개의 부분 배열로 분할
• 정복(Conquer) : 부분 배열을 정렬한다. 부분 배열 크기가 충분히 작지 않으면 순환 호출을 이용해 다시 분할 정복 방법을 적용한다.
• 결합(Combine) : 정렬된 부분 배열들을 하나의 배열에 병합

2개의 정렬된 리스트 병합 과정

1. 2개의 리스트 값들을 처음부터 하나씩 비교하여 두개의 리스트의 값중에서 더 작은값을 새로운 리스트로 옮긴다.
2. 둘 중 하나가 끝날 때 까지 반복한다.
3. 하나가 끝나면 남은 리스트를 새로운 리스트로 복사한다.
4. 새로운 리스트를 원래 리스트로 옮긴다.

def merge_sort(arr = list):
	def sort(low,high):
		if high - low < 2:
			return
		mid = (low + high) // 2
		sort(low, mid)
		sort(mid, high)
		merge(low, mid, high)

	def merge(low, mid, high):
		temp = []
		l,h = low, mid

		while l<mid and h<high:
			if arr[l] < arr[h]:
				temp.append(arr[l])
				l += 1
			else:
				temp.append(arr[h])
				h += 1
			while l < mid:
				temp.append(arr[l])
				l += 1
			while h < high:
				temp.append(arr[h])
				h += 1
			for i in range(low,high)
				arr[i] = temp[i-low]

힙 정렬(Heap Sort)

• 완전 이진 트리의 일종 우선 순위 큐를 위하여 만들어진 자료구조
  • 최댓값, 최솟값을 쉽게 추출할 수 있는 자료구조

힙 정렬 알고리즘 개념

• 최대 힙 트리나 최소 힙트리를 구성해 정렬을 하는 방법
• 내림차순을 위해서는 최대 힙 구현, 오름차순을 위해서는 최소 힙 구현
  • 정렬해야 할 n개의 요소들로 힙을 만든다.
  • 한번에 하나씩 요소를 힙에서 꺼내서 배열의 뒤부터 정렬한다.
  • 삭제 되는 요소들을 값이 감소되는 순서로 정렬되게 한다.

검색(Search)

검색과 키

• 키(Key) - 데이터의 일부

검색의 종류

• 배열검색
  1. 선형검색 - 무작위로 늘어놓은 데이터 집합에서 검색 수행
  2. 이진검색 - 일정한 규칙으로 늘어놓은 데이터 집합에서 아주 빠른 검색 수행
  3. 해시법 - 추가 삭제가 자주 일어나는 데이터 집합에서 아주 빠른 검색 수행
     1. 체인법 - 같은 해시값 데이터를 연결리스트로 연결
     2. 오픈 주소법 - 데이터를 위한 해시값이 충돌할 때 재해시 하는 방법
• 연결리스트 검색
• 이진 검색 트리 검색

선형검색(Linear Search)

• 직선 모양(선형)으로 늘어선 배열에서 검색하는 경우에 원하는 키값을 가진 원소를 찾을때까지 맨 앞부터 스캔하여 순서대로 검색하는 알고리즘

종료조건

1. 검색할 값을 찾지 못하고 배열의 맨 끝을 지나간 경우 - 검색 실패
2. 검색할 값과 같은 원소를 찾은 경우 - 검색 성공

보초법(Sentinel Method)

• 선형검색은 반복할 때 마다 2가지 종료조건을 체크한다. 단순하지만 비용(cost)를 무시할 수 없다. 이 비용을 반으로 줄이는 방법이다.
• 검색하고자 하는 키값을 끝에 추가한다. 이때 저장하는 값을 보초(Sentinel)이라고 한다. 그러면 선형 검색의 종료 조건1을 체크하지 않아도 돼서 코스트가 절감된다.

복잡도

• 시간복잡도(Time Complexity) : 실행하는데 필요한 시간을 평가
• 공간복잡도(Space Complexity) : 메모리(기억공간)와 파일공간이 얼마나 필요한지

해시법(hashing)

• ‘데이터를 저장할 위치 = 인덱스’ 간단한 연산으로 구하는 것
• 해시값(hash value) : 해시값은 데이터에 접근할 때 기준이 된다.
• 해시값을 인덱스로 하여 원소를 새로 저장한 배열이 해시테이블(hash table) 이 된다. 이렇게 키를 해시값으로 변환하는 과정을 해시함수(hash function)라고 한다.
• 일반적으로 해시함수는 나머지를 구하는 연산 또는 그 연산을 응용할 때 주로 사용한다.
• 해시테이블에서 만들어진 배열을 버킷(bucket)이라고 한다.
• 키와 해시값은 일반적으로 다대1(n:1)이다.

해시충돌

• 저장할 버킷이 중복되는 형상을 충돌(Collision)이라고 한다.
• 충돌이 발생한 경우 2가지로 대처한다.
  1. 체인법 : 해시값이 같은 원소를 연결리스트로 관리
  2. 오픈주소법 - 빈 버킷을 찾을 때까지 해시를 반복

체인법(Chaining)

• 해시값이 같은 데이터를 체인(chain)모양의 연결리스트로 연결하는 방법. 오픈해시법(open-hashing)이라고도 한다.
• 배열의 각 버킷에 저장하는 것은 인덱스를 해시값으로 하는 연결리스트 앞쪽 노드를 참조하는것
• 노드(Node)
  • Key : 키
  • Value : 값
  • Next : 뒤쪽 노드를 참조

오픈 주소법(Open addressing)

• 오픈 주소법은 충돌이 발생했을 때 재해서(Rehasing)을 수행하여 빈 버킷을 찾는 방법을 말하며 닫힌 해시법(Closed hashing)이라고도 한다.
• 오픈 주소법은 빈 버킷이 나올 때까지 재해시를 반복하므로 선형탐사법(Linear Probiny)라고도 한다.

완전탐색(Exhaustive Search)

• 간단히 가능한 모든 경우의 수를 다 체크해서 정답을 찾는 방법
• 무식하게 한다는 의미로 ‘BruteFroce’라고도 부르며, 직관적이여서 이해하기 쉽고 문제의 정확한 결과값을 얻어낼 수 있는 가장 확실하며 기초적인 방법이다.

완전탐색 기법을 활용하는 방법

• 해결하고자 하는 문제의 가능한 경우의 수를 대략적으로 계산한다.
• 가능한 모든 방법을 다 고려한다.
  • BruteForce : 반복/조건문을 활용해 모두 테스트 하는 방법
  • 순열(Permutation) : n개의 원소 중 r개의 원소를 중복 허용 없이 나열하는 방법
  • 재귀호출
  • 비트마스크 : 2진수 표현 기법을 활용하는 방법
  • BFS,DFS를 활용하는 방법
• 실제 값을 구할 수 있는지 적용한다.

이진탐색(Binary Search)

• 이진탐색(이분 탐색)알고리즘은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다.
• 이진탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다.
• 변수 3개 (start, end, mid)를 사용하여 탐색한다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이 이진탐색의 과정이다.

def binary_search(target, start, end):
	if start >= end:
		return 0
	mid = (start + end) // 2
	if target == mid:
		return 1
	elif target < mid:
		end = mid -1
	else:
		start = mid + 1
	return binary_search(target,start,end)

• 시간 복잡도는 O(logN) 이다.

분할정복(Divide and Conquer)

• 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방식
• 대표적인 예
  • 퀵정렬
  • 합병정렬
  • 이진탐색
  • 선택문제
  • 고속 푸리에 변환

분할정복의 설계

1. Divide : 원래 문제가 분할하여 비슷한 유형의 더 작은 하위 문제로 분할 가능할 때 까지 나눈다.
2. Conquer : 각 하위 문제를 재귀적으로 해결한다. 하위 문제의 규모가 나눌 수 없는 단위가 되면 탈출 조건을 설정하고 해결한다.
3. Combine : Conquer한 문제들을 통합하여 원래 문제의 답을 얻어 해결한다.

• Divide를 제대로 나누면 Conquer 과정은 자동으로 쉬워진다. 그래서 Divide를 잘 설계하는 것이 중요하다.
• 분할정복 알고리즘은 재귀 알고리즘이 많이 사용되는데, 이 부분에서 분할정복 알고리즘의 효율성을 깎아 내릴 수 있다.

분할정복 특징 및 장단점

• 분할 된 작은 문제는 원래 문제와 성격이 동일하다 → 입력 크기만 작아진다.
• 분할 된 문제는 서로 독립적이다.(중복 제거X) → 순환적 분할 및 결합 가능하다.
• 장점
  • Top-down 재귀 방식으로 구현하기에 코드가 직관적이다.
  • 문제를 나누어 해결한다는 특징상 병렬적으로 문제 해결이 가능하다.
• 단점
  • 재귀 함수 호출로 오버헤드가 발생할 수 있다.
  • 스택에 다량의 데이터가 보관되는 오버플로우가 발생할 수 있다.

자료구조

스택(Stack)

• 스택이란 데이터를 임시 저장할 때 쓰는 자료구조
• LIFO 후입선출 방식이다.
• push - 스택에 데이터를 넣는 작업
• pop - 스택에서 데이터를 꺼내는 작업

큐(Queue)

• 스택과 같이 데이터를 임시 저장하는 자료구조
• FIFO 선입선출 방식이다
• 인큐(enqueue) - 큐에 데이터를 넣는 작업
• 디큐(dequeue) - 큐에서 데이터를 꺼내는 작업
• 리어(rear), tail - 데이터를 넣는 쪽
• 프런트(front), head - 데이터를 꺼내는 쪽

우선순위 큐(Priority Queue)

• 인큐할 때는 데이터에 우선순위를 부여하여 추가하고, 디큐할때 우선순위가 가장 높은 데이터를 꺼내는 방식
• python heapq 모듈에서 제공

링버퍼(Ring Buffer)

• 디큐할때 배열 안의 원소를 옮기지 않는 큐. 배열 맨 끝의 원소 뒤에 맨 앞의 원소가 연결되는 자료구조
• 링버퍼로 큐를 구현하면 원소를 옮길 필요없이 front와 rear의 값을 업데이트 하는 것만으로 인큐, 디큐를 수행한다.

덱(Double-Ended Queue)

• 맨 앞과 맨 끝 양쪽에서 데이터를 삽입, 삭제할 수 있는 자료구조
• 2개의 포인터를 사용

연결리스트(LinkedList)

• 리스트(list)는 데이터에 순서를 매겨 늘어놓은 자료구조이다.
  • 선형리스트(Linear List)
  • 연결리스트(Linked List)
• 연결리스트에서 각각의 원소(element)를 노드(node)라고 한다. 노드는 데이터와 뒤쪽노드를 가리키는(참조하는) 포인터를(Pointer)를 가지고 있다. 맨 앞 노드를 head노드 맨뒤를 tail노드 라고 한다. 또 각 노드에서 바로 앞 노드를 앞쪽노드(Predecessor node) 바로 뒤를 뒤쪽노드(Successor node) 라고한다.
• 자신과 같은 형의 인스턴스를 참조하는 필드가 있는 구조. 자기참조(self-referential)형

Node의 필드

• data - 데이터
• next - 뒤쪽 포인터

Python

sys.stdin.readline() 쓰는 이유

input()이 느린 이유

1. input()은 매개변수로 prompt message를 받는다.
2. 입력받은 값의 개행 문자를 삭제시키고 반환한다.

• 이러한 단계를 거치기 때문에 input()은 비교적 속도가 느리다.

sys.stdin.readline() 의 특징

• 문자열로 입력을 받는다.
• 개행 문자 ‘\n’을 같이 입력받는다.
• strip()을 이용해 개행 문자 없이 문자열을 입력 받을 수 있다.

집합(set)

• Python 집합은 고유한 요소의 모음이다. 집합의 목적은 단일 변수에 여러 항목을 저장하는 것이다.
• 특징
  • 순서가 없다(인덱스로 접근하지 못한다)
  • 중복은 허용되지 않는다.
  • 요소는 변경 불가능한 자료형만 사용할 수 있다.
• 집합은 순서가 없기 때문에 인덱스로 접근할 수 없다. 인덱스로 요소에 접근하려고 하면 Typeerror가 발생한다.

람다(Lambda) 함수

• 함수형 프로그래밍에서 중요한 개념 중 하나로, 익명 함수(anonymous function)라고도 부른다. 람다 함수는 이름이 없는 함수로, 일반적으로 함수를 한 번만 사용하거나 함수를 인자로 전달해야 하는 경우 매우 유용하게 사용된다.

lambda 인자 : 표현식

파이썬 join 함수

• ‘’.join(리스트), ‘구분자’.join(리스트) 형태
• join 함수는 매개변수로 들어온 리스트에 있는 요소 하나하나를 합쳐서 하나의 문자열로 바꾸어 반환하는 함수이다.
• for문에 비해서 시간복잡도를 줄일 수 있다.