전산학 이론 정리

운영체제

https://gist.github.com/Curookie/efc37b9a7e58135de365034584c1c8f1

커널(Kernel)은 운영체제에서 중요한 기능을 맡고있는 부분으로서 운영체제의 성능은 커널이 좌우한다.
프로세스, 메모리, 저장장치 관리 등의 기능을 맡고 있으며, 직접 접근을 막기 위해 인터페이스인 시스템 호출과 하드웨어를 제어할 수 있게 돕는 드라이버가 존재한다.

프로세스와 쓰레드

프로세스
= 하나의 작업 단위.
= 요리에 비유했을 때 요리 작업 전체.
= 프로그램을 실행한 것.
= 실행을 위해 메모리에 올라온 동적인 상태.
= 프로그램이 프로세스가 되면 운영체제로부터 프로세스 제어 블록을 얻는다, 반대로 종료되면 제어 블록이 폐기됨.
= 프로세스 4가지 상태 (생성, 준비, 실행, 완료)
= 오늘날 프로세스 5가지 상태 (생성, 준비, 실행, 대기, 완료)
생성단계에서 PCB를 할당받고, 준비단계에서 큐에 담겨 CPU 스케줄러에 의해 관리된다.
실행단계에서 CPU를 할당받아 실행하고, 대기단계는 실행상태에서 프로세스가 입출력을 요청하면 완료될 때가지 기다리는 상태다.
끝나면 준비단계로 간다. 완료상태는 프로세스가 종료되는 단계로 PCB를 폐기한다.
= 프로세스 4가지 구조 (코드=요리책, 데이터=재료, 힙=재료, 스택=조리도구) 정적할당 영역인 코드와 데이터, 동적할당인 힙과 스택영역이 존재한다.
코드가 코드영역에 담기고, 데이터 영역에는 실행될때 사용되는 데이터들 읽고 쓰여질, 전역변수들이 담긴다. 스택에는 스코프와 관련된 내용들 돌아올 주소나 지역변수들 힙에는 프로세스가 실행되는 동안 할당되는 변수의 영역으로 malloc 함수등이 있다.

쓰레드
= 프로세스의 코드에 정의된 절차에 따라 CPU에 작업 요청을 하는 실행의 단위이다.
= CPU스케줄러가 CPU에 전달하는 일 하나.
= 요리에서 요리를 완성하기 이해 수행되는 각각의 조리에 해당되는 것.
= 오늘날에는 멀티스레드를 사용한다.

두 개를 비교했을 때 운영체제 입장에서의 작업단위는 프로세스, CPU 입장에서의 작업단위는 쓰레드이다.
프로세스를 처리할 때 2개 이상의 스레드를 가지면 멀티 스테드라고 한다.

쓰레드는 프로세스 내부에서 서로 강하게 연결되어 있다.

멀티태스크는 시간을 공유하는 개념으로 독립된 쓰레드가 동시에 진행되는 것이고, CPU에 작업을 줄 때 시간을 잘게 나누어 배분하는 기법 =시분할 시스템
멀티쓰레드는 같은 쓰레드들이 강하게 연결되어 변수나 파일등을 공유하고 동시에 종료된다. 작업의 부담을 줄이는 프로세스 운영 기법이다.
멀티프로세싱은 CPU를 사용하여 여러 개의 쓰레드를 동시에 처리하는 작업 환경을 말한다.

크롬이 멀티테스킹, 익스플로러는 멀티쓰레드

장점은 작업효율, 단점은 하나의 쓰레드가 문제가 생기면 연달아 문제가 생김.

캐시 적중(cache hit), 캐시 미스(cache miss), 적중률(hit ratio)

캐시 적중 (cache hit)
CPU가 원하는 데이터가 이미 캐시에 적재되어 있는 상태를 의미한다.

캐시 미스 (cache miss)
CPU가 원하는 데이터가 캐시에 없는 상태를 캐시 미스라고 한다.

CPU 스케쥴링 Preemptive vs Non-preemptive (선점 (先占) : 비선점(非先占))
선점 Preemptive : CPU가 어느 프로세스를 실행하고 있는데(아직 끝나지도 않았고 IO를 만난 것도 아닌데) 강제로 쫓아내고 새로운 것이 들어갈 수 있는 스케쥴링(응급실)
우선순위가 높은 프로세스를 빠르게 처리할 수 있음
주로 빠른 응답시간을 요구하는 대화식 시분할 시스템에 사용
선점으로 인한 많은 오버헤드를 초래함
선점을 위해 시간 배당을 위한 인터럽트용 타이머 클럭(Clock)이 필요

비 선점 Non-preemptive : 프로세스가 끝나거나 IO를 만나기 전엔 안됨(은행)
프로세스가 CPU를 할당받으면 해당 프로세스가 완료될 때까지 CPU를 사용
모든 프로세스에 대한 요구를 공정하게 처리 가능
일괄 처리 방식에 적합, 중요한 작업이 기다리는 경우가 발생할 수 있음
응답시간 예측이 용이
Scheduling criteria : 스케쥴링 척도
CPU Utilization (CPU 이용률) : CPU가 얼마나 놀지않고 부지런히 일하는가
Throughput (처리율) : 시간당 몇 개의 작업을 처리하는가
Turnaround time (반환시간) : 작업이 레디큐에 들어가서 나오는 시간의 차이(병원에서 진료 받을 때..대기하고 CT 찍고, … 나오는 시간 차) 짧아야 좋음
Waiting time (대기시간) : CPU가 서비스를 받기 위해 Ready Queue에서 얼마나 기다렸는가
Response time (응답시간) : Interactive system에서 중요. 클릭-답, 타이핑-답. 첫 응답이 나올 때 까지 걸리는 시간

CPU Scheduling Algorithms
비선점
First-Come, First-Served (FCFS) : 먼저 온 놈 먼저 처리
Shortest-Job-First (SJF) : 작업 시간이 짧은 놈 먼저 처리
Shortest-Remaining-Time-First
Priority : 우선 순위가 높은 놈부터

선점
SJT
Round-Robin (RR) : 빙빙 돌면서 순서대로
Multilevel Queue : 큐를 여러개 돌림
Multilevel Feedback Queue

네트워크

패리티 비트(Parity bit)는 정보의 전달 과정에서 오류가 생겼는지를 검사하기 위해 추가된 비트입니다.
전송하고자 하는 데이터의 끝에 1 비트를 더하여 전송하는 방법으로 2가지 종류의 패리티 비트(홀수, 짝수)가 있습니다.
패리티 비트는 오류 검출 부호에서 가장 간단한 형태로 쓰입니다.

CPU가 메모리에 데이터를 저장할 때 어느 순서로 저장하는가에 따라서 리틀 엔디안과 빅 엔디안으로 나뉘게 됩니다.
리틀 엔디안(Little Endian)은 메모리의 첫 주소에 하위 데이터(데이터의 맨 오른쪽)부터 저장하고
빅 엔디안(Big Endian)은 메모리의 첫 주소에 상위 데이터(데이터의 맨 왼쪽)부터 저장합니다.
리틀 엔디안
0x78 0x56 0x34 0x12
빅 엔디안
0x12 0x34 0x56 0x78

OSI 7 계층

물데네 전세표응
1계층 - 물리계층(Physical Layer)

이 계층에서는 주로 전기적, 기계적, 기능적인 특성을 이용해서 통신 케이블로 데이터를 전송하게 된다. 이 계층에서 사용되는 통신 단위는 비트이며 이것은 1과 0으로 나타내어지는, 즉 전기적으로 On, Off 상태라고 생각하면 된다. 이 계층에서는 단지 데이터를 전달만 할뿐 전송하려는(또는 받으려는)데이터가 무엇인지, 어떤 에러가 있는지 등에는 전혀 신경 쓰지 않는다. 단지 데이터 전기적인 신호로 변환해서 주고받는 기능만 할 뿐이다. 이 계층에 속하는 대표적인 장비는 통신 케이블, 리피터, 허브등이 있다.

-> 케이블, 리피터, 허브를 통해 데이터 전송한다.

2계층 - 데이터 링크계층(DataLink Layer)

물리계층을 통해 송수신되는 정보의 오류와 흐름을 관리하여 안전한 정보의 전달을 수행할 수 있도록 도와주는 역할을 한다. 따라서 통신에서의 오류도 찾아주고 재전송도 하는 기능을 가지고 있는 것이다. 이 계층에서는 맥 주소를 가지고 통신하게 된다. 이 계층에서 전송되는 단위를 프레임이라고 하고, 대표적인 장비로는 브리지, 스위치 등이 있다.(여기서 MAC주소를 사용한다.)

-> 브릿지나 스위치를 통해 맥주소를 가지고 물리계층에서 받은 정보를 전달함. -> 프레임에 주소부여(MAC - 물리적주소) 에러검출/재전송/흐름제어

3계층 - 네트워크 계층(Network Layer)

이 계층에서 가장 중요한 기능은 데이터를 목적지까지 가장 안전하고 빠르게 전달하는 기능(라우팅)이다. 여기에 사용되는 프로토콜의 종류도 다양하고, 라우팅하는 기술도 다양하다. 이 계층은 경로를 선택하고 주소를 정하고 경로에 따라 패킷을 전달해주는 것이 이 계층의 역할이다. 이 계층의 대표적인 장비는 라우터 이며, 요즘은 2계층의 장비 중 스위치라는 장비에 라우팅 기능을 장착한 Layer 3 스위치도 있다. (여기서 IP주소를 사용한다.)

4계층 - 전송 계층(Transport Layer)

통신을 활성화하기 위한 계층이다. 보통 TCP프로토콜을 이용하며, 포트를 열어서 응용프로그램들이 전송을 할 수 있게 한다. 만약 데이터가 왔다면 4계층에서 해당 데이터를 하나로 합쳐서 5계층에 던져 준다. 단대단 오류제어 및 흐름제어 이 계층 까지는 물리적인 계층에 속한다.(TCP/UDP프로토콜을 사용한다.)

5계층 -세션 계층(Session Layer)

데이터가 통신하기 위한 논리적인 연결을 말한다. 통신을 하기위한 대문이라고 보면 된다. 하지만 4계층에서도 연결을 맺고 종료할 수 있기 때문에 우리가 어느 계층에서 통신이 끊어 졌나 판단하기는 한계가 있다. 그러므로 세션 계층은 4 계층과 무관하게 응용 프로그램 관점에서 봐야 한다. 세션 설정, 유지, 종료, 전송 중단시 복구 등의 기능이 있다.

세션 계층(Session layer)은 양 끝단의 응용 프로세스가 통신을 관리하기 위한 방법을 제공한다. 동시 송수신 방식(duplex), 반이중 방식(half-duplex), 전이중 방식(Full Duplex)의 통신과 함께, 체크 포인팅과 유휴, 종료, 다시 시작 과정 등을 수행한다. 이 계층은 TCP/IP 세션을 만들고 없애는 책임을 진다. -> 통신하는 사용자들을 동기화하고 오류복구 명령들을 일괄적으로 다룬다. 통신을 하기 위한 세션을 확립/유지/중단 (운영체제가 해줌)

6계층 - 표현 계층(Presentation Layer)

데이터 표현이 상이한 응용 프로세스의 독립성을 제공하고, 암호화 한다. 표현 계층(Presentation layer)은 코드 간의 번역을 담당하여 사용자 시스템에서 데이터의 형식상 차이를 다루는 부담을 응용 계층으로부터 덜어 준다. MIME 인코딩이나 암호화 등의 동작이 이 계층에서 이루어진다. 예를 들면, EBCDIC로 인코딩된 문서 파일을 ASCII로 인코딩된 파일로 바꿔 주는 것,
해당 데이터가 TEXT인지, 그림인지, GIF인지 JPG인지의 구분 등이 표현 계층의 몫이다.

-> 사용자의 명령어를 완성및 결과 표현. 포장/압축/암호화

7계층 - 응용 계층(Application Layer)

최종 목적지로서 HTTP, FTP, SMTP, POP3, IMAP, Telnet 등과 같은 프로토콜이 있다. 해당 통신 패킷들은 방금 나열한 프로토콜에 의해 모두 처리되며 우리가 사용하는 브라우저나, 메일 프로그램은 프로토콜을 보다 쉽게 사용하게 해주는 응용프로그램이다. 한마디로 모든 통신의 양 끝단은 HTTP와 같은 프로토콜이지 응용프로그램이 아니다.

응용 계층(Application layer)은 응용 프로세스와 직접 관계하여 일반적인 응용 서비스를 수행한다. 일반적인 응용 서비스는 관련된 응용 프로세스들 사이의 전환을 제공한다. 응용 서비스의 예로, 가상 터미널(예를 들어, 텔넷), "Job transfer and Manipulation protocol" (JTM, 표준 ISO/IEC 8832) 등이 있다.

-> 네트워크 소프트웨어 UI 부분, 사용자의 입출력(I/O)부분

서브넷 마스크란?
IP 주소에는 반드시 서브넷 마스크가 있습니다 서브넷 마스크는 기본적으로 255와 0으로 이루어져 있습니다
여기서 255는 네트워크 부분이며 0은 호스트 부분이 됩니다
그리하여 255로 된 부분은 무시하시고 0으로 된 부분에서 IP를 나눠쓰는 혹은 IP를 쪼개는 개념입니다.

서브넷 마스크를 사용하는 이유
브로드캐스트 영역(네트워크)를 나누기 위함 입니다.

한 네트워크에 수 많은 호스트가 있을 경우 원활한 통신이 불가능해지게 됩니다.
이를 해결하기 위해서 네트워크를 적절하게 나누어 주셔야 합니다.
또한 네트워크를 적절하게 구분지어주기 때문에 IP 주소를 아끼는 효과가 있습니다.

A 11111111.00000000.00000000.00000000 /8 OR 255.0.0.0

B 11111111.11111111.00000000.00000000 /16 OR 255.255.0.0

C 11111111.11111111.11111111.00000000 /24 OR 255.255.255.0

Nagle Algorithm (네이글 알고리즘)

설명 : 네트워크 자원은 한정된 자원이다.

전송 하고자 하는 패킷이 한번의 세그먼트로 보낼 수 있는데, 이것을 여러개의 세그먼트로 보낸다면 전송효율이 떨어질 것이다. 즉, 필요이상의 작은 세그먼트들은 병합해서 보낼 수 있어야 할 것이다.

Nagle 알고리즘은 세그먼트 크기를 구하는 공식에 의해 결정된, 크기보다 작은 세그먼트들은 전송된 세그먼트의 수신이 확인되거나, 완전한 크기의 세그먼트가 전송될 수 있을 때까지 지연시키는 방법 으로 전송효율을 높인다. 그러나, 전체적인 전송효율을 높일 수 있지만, 완전한 세그먼트가 모일 때까지 지연될 수 있다는 점이 단점이 될 수 있다.

예로 반응속도가 중요한 온라인게임등에 Nagle알고리즘을 적용시킬 경우 반응속도가 떨어질 수 있다. 이런 이유로 서버는 Nagle 알고리즘을 활성화 하고 클라이언트측은 Nagle 알고리즘을 비활성 하는 등 의 방법을 사용한다.

정리 :

Nagle 알고리즘
- Nagle On
  1. packet의 수가 작다.
  2. nagle off 의 경우보다 속도는 느리다.
- Nagle Off
  1. packet의 수가 많아진다.
  2. Nagle on의 경우보다 속도는 빠르다.
- Nagle off가 무조건 네트워크의 속도를 빠르게 하는것은 아니다.

HTTP의 GET vs POST
GET
HTTP Request Message의 Header 부분의 url 에 담겨서 전송된다.
url 이라는 공간에 담겨가기 때문에 전송할 수 있는 데이터의 크기가 제한적이다.
또 보안이 필요한 데이터에 대해서는 데이터가 그대로 url 에 노출되므로 GET방식은 적절하지 않다.

POST
HTTP Message의 Body 부분에 데이터가 담겨서 전송된다.
데이터 크기가 GET 방식보다 크고 보안면에서 낫다.(하지만 보안적인 측면에서는 암호화를 하지 않는 이상 고만고만하다.)

[TCP] 3-way-handshake & 4-way-handshake

연결 성립(Connection Establishment)

클라이언트는 서버에 접속을 요청하는 SYN(a) 패킷을 보낸다.
서버는 클라이언트의 요청인 SYN(a)을 받고 클라이언트에게 요청을 수락한다는 ACK(a+1)와 SYN(b)이 설정된 패킷을 발송한다.
클라이언트는 서버의 수락 응답인 ACK(a+1)와 SYN(b) 패킷을 받고 ACK(b+1)를 서버로 보내면 연결이 성립(establish)된다.

연결 해제(Connection Termination)

클라이언트가 연결을 종료하겠다는 FIN플래그를 전송한다.
서버는 클라이언트의 요청(FIN)을 받고 알겠다는 확인 메세지로 ACK를 보낸다.
2-1) 그리고나서는 데이터를 모두 보낼 때까지 잠깐 TIME_OUT이 된다.
데이터를 모두 보내고 통신이 끝났으면 연결이 종료되었다고 클라이언트에게 FIN 플래그를 전송한다.
클라이언트는 FIN 메세지를 확인했다는 메세지(ACK)를 보낸다.
클라이언트의 ACK 메세지를 받은 서버는 소켓 연결을 close한다.
클라이언트는 아직 서버로부터 받지 못한 데이터가 있을 것을 대비해 일정 시간 동안 세션을 남겨놓고 잉여 패킷을 기다리는 과정을 거친다.(TIME_WAIT)

SYN :: synchronize sequence number ACK :: acknowledgement

TCP 대부분의 인터넷 응용 분야들은 신뢰성과 순차적인 전달을 필요로 한다.
TCP 는 멀티캐스팅이나 브로드캐스팅을 지원하지 않는다.
모든 TCP 연결은 전이중(full-duplex), 점대점(point to point)방식이다.
3-way-handshake를 통해 행해진다.

UDP 비연결형 프로토콜 이다. IP 데이터그램을 캡슐화하여 보내는 방법과 연결 설정을 하지 않고 보내는 방법을 제공한다.
흐름제어, 오류제어 또는 손상된 세그먼트의 수신에 대한 재전송을 하지 않는다.
UDP를 사용한 것들에는 DNS가 있다.

HTTP 의 문제점
HTTP 는 평문 통신이기 때문에 도청이 가능하다.
통신 상대를 확인하지 않기 때문에 위장이 가능하다.
완전성을 증명할 수 없기 때문에 변조가 가능하다.

흐름제어, 혼잡제어 방식

TCP/IP 는 도청 가능한 네트워크이다.

통신 자체를 암호화
SSL(Secure Socket Layer) or TLS(Transport Layer Security)라는 다른 프로토콜을 조합함으로써 HTTP 의 통신 내용을 암호화할 수 있다.
SSL 을 조합한 HTTP를 HTTPS(HTTP Secure) or HTTP over SSL이라고 부른다.
콘텐츠를 암호화 말 그대로 HTTP 를 사용해서 운반하는 내용인, HTTP 메시지에 포함되는 콘텐츠만 암호화하는 것이다.
암호화해서 전송하면 받은 측에서는 그 암호를 해독하여 출력하는 처리가 필요하다.

통신 상대를 확인하지 않기 때문에 위장이 가능하다.
위 암호화 방법으로 언급된 SSL로 상대를 확인할 수 있다.
SSL 은 상대를 확인하는 수단으로 증명서 를 제공하고 있다.
증명서는 신뢰할 수 있는 제 3 자 기관에 의해 발행되는 것이기 때문에 서버나 클라이언트가 실재하는 사실을 증명한다.

컴퓨터구조

메모리의 구조.
프로그램이 실행되기 위해서는 먼저 프로그램이 메모리에 로드(load)되어야 합니다.
또한, 프로그램에서 사용되는 변수들을 저장할 메모리도 필요합니다.
따라서 컴퓨터의 운영체제는 프로그램의 실행을 위해 다양한 메모리 공간을 제공하고 있습니다.
프로그램이 운영체제로부터 할당받는 대표적인 메모리 공간은 다음과 같습니다.

코드(code) 영역.
데이터(data) 영역.
스택(stack) 영역.
힙(heap) 영역.
다음 그림은 운영체제가 제공하는 메모리 공간을 표현하고 있습니다.

메모리 구조
코드(code) 영역
메모리의 코드(code) 영역은 실행할 프로그램의 코드가 저장되는 영역으로 텍스트(code) 영역이라고도 부릅니다.
CPU는 코드 영역에 저장된 명령어를 하나씩 가져가서 처리하게 됩니다.

데이터(data) 영역.
메모리의 데이터(data) 영역은 프로그램의 전역 변수와 정적(static) 변수가 저장되는 영역입니다.
데이터 영역은 프로그램의 시작과 함께 할당되며, 프로그램이 종료되면 소멸합니다.

스택(stack) 영역
메모리의 스택(stack) 영역은 함수의 호출과 관계되는 지역 변수와 매개변수가 저장되는 영역입니다.
스택 영역은 함수의 호출과 함께 할당되며, 함수의 호출이 완료되면 소멸합니다.
이렇게 스택 영역에 저장되는 함수의 호출 정보를 스택 프레임(stack frame)이라고 합니다.
스택 영역은 푸시(push) 동작으로 데이터를 저장하고, 팝(pop) 동작으로 데이터를 인출합니다.
이러한 스택은 후입선출(LIFO, Last-In First-Out) 방식에 따라 동작하므로, 가장 늦게 저장된 데이터가 가장 먼저 인출됩니다.
스택 영역은 메모리의 높은 주소에서 낮은 주소의 방향으로 할당됩니다.

힙(heap) 영역.
메모리의 힙(heap) 영역은 사용자가 직접 관리할 수 있는 '그리고 해야만 하는' 메모리 영역입니다.
힙 영역은 사용자에 의해 메모리 공간이 동적으로 할당되고 해제됩니다.
힙 영역은 메모리의 낮은 주소에서 높은 주소의 방향으로 할당됩니다.

기억장치 계층수조
CPU 레지스터 > 캐시 > 주기억장치 > 버퍼 및 디스크캐시 > 보조기억장치

Clock Pulse (클럭)
CPU를 구성하는 요소는 아니지만, Timing 을 제공하기 위해서 필요하다.
1.6Mhz인 CPU는 1초에 1백 6십만번의 연산을 하게 된다.
즉, CPU의 클럭속도가 높으면 초당 처리하는 명령어의 개수가 많아지므로 컴퓨터의 전체적인 성능은 좋아지게된다.
왜? 클럭신호에 맞추어서 CPU는 동작해야하는가?
다른 장치, 블록과의 동기화를 위해서 필요하다. 뒤처지거나 밀리는 작업이 없도록 가장 느린 장치의 속도에 맞추어 진행하면 밀리지 않는다.

부동소수점 = IEEE 754

IEEE 754 에선 지수부와 가수부 라는 표현을 사용한다.

우선 32비트 단정도(single) 실수는
부호 비트 : 1
지수(exponent) 비트 : 8
가수(mantissa) 비트 : 23 의 자릿수로 표현 됩니다.

-118.625 를 -1.18625 × 10의 2승 이라고 표현하는 것이다. 2진수로 나타내면
-1.110110101 × 2의 6승이다.

정수는 가장 앞의 한 자리만 남도록 소수점의 위치를 조정하고 소수점의 원래 위치는 지수로 표현하는 것이다.
이렇게 하면 어디까지 정수, 어디까지 소수를 할당할 것인가? 소수점의 위치는 어떻게 표현할 것인가? 라는 문제는 모두 해결된다.

부호는 -
가수는 1.110110101
지수(소수점 위치)는 6

자료구조

중위 표기법(Infix)

중위 표기라는 것은 우리한테 상당히 익숙한 식. 우리는 수식을 쓸때 피연산자 사이에 연산자를 포함시켜 계산
1+3*2+4/2

이렇게 피연산자(숫자) 사이에 연산자(덧셈, 곱셈, 뺄셈, 나눗셈)가 있는 식을 우리는 중위표기, 바로 Infix라고 부른다.

하지만 우리는 왜 prefix라던가 postfix를 쓸까? 우리가 계산하는 방식과 컴퓨터가 계산하는 방식이 다르기 때문.

만약 위의 식을 우리가 계산한다면 1+6+2=9라는 것을 금방 알 수 있다.
하지만 컴퓨터는 1+3 이후 다음 연산자를 보고 결정해야하기 때문에 계산하기 어려워져 전위표기법이나 후위표기법을 사용한다.

전위 표기법(Prefix)

이름에서도 알 수 있듯이 전위표기는 연산자가 피연산자 앞에 나오는 방식. 이를테면 3+4는 +34라고 표현할 수 있게 됨.

1+2*3+1+2/2는 다음과 같은 변환을 한다.

우선 연산자 우선순위에 맞게 괄호를 친다.

((1+(2*3))+(1+(2/2)))

이제 이 괄호안에 있는 연산자들을 앞으로 뺀다. +((+1*(23))(+1/(22)))

이제 괄호를 모두 없앤다.

++1*23+1/22

이렇게 나온 식이 전위표기법으로 나타낸 식입니다.

후위표기법(Postfix)

마찬가지로 연산자가 뒤에 오는 수식이다. 피연산자는 그대로 쓰면되는 것.

후위표기법은 컴파일러가 사용하는 것으로 스택을 사용하는 예들 중 가장 빈번하게 등장함.

우선 1+2*3+(4+2)/2를 마찬가지로 후위표기식으로 바꾼다.

다시 연산자 우선순위에 맞게 괄호를 쳐준다.

((1+(2*3)+((4+2)/2)))

이제 이 괄호에 있는 연산자를 괄호뒤로 빼준다.

((1(23)*)+((42)+2)/))+

이제 괄호를 모두 없애면 후위 표기로 바뀌게 됨.

123*+42+2/+

또한 이런 스택을 사용해서도 위의 식을 표현해 낼 수 있다.

1. 숫자가 나오면 그대로 출력한다.
2. (나오면 스택에 push한다.
3. * / 나오면 스택에 push한다.
4. + - 연산이 나오면 여는 괄호('('), 여는 괄호가 없다면 스택의 끝까지 출력하고 그 연산자를 스택에 push한다.
5. 닫는 괄호(')')가 나오면 여는 괄호('(')가 나올때까지 pop하여 출력한다.

전위순회 (Pre-order)

Pre-Order Traversal

            A  
     B             C  
  D     E              F  
G   H                I

순서 A B D G H E C F I

Root 를 방문한다
왼쪽 subtree를 방문한다
오른쪽 subtree 를 방문한다
특징 : 루트가 가장 먼저 나온다

노드를 먼저 들린다, 그래서 Pre

PreOrderTraversal( Node* pNode ){
 if( pNode != m_pNodeTail )
 {
  visit(pNode); // 해당 노드에서 왼쪽, 또는 오른쪽으로 갈지를 정하기 전에 해당 노드를 들린다
  PreOrderTraversal(pNode->pLeft );
  PreOrderTraversal(pNode->pRight );
 }
}

tip : 노드와 처음 마주칠때 방문한다

중위순회 (in-order)

            A  
     B             C  
  D     E              F  
G   H                I

순서 G D H B E A C I F

왼쪽 Subtree 를 방문한다
Root 를 방문한다.
오른쪽

특징 : 가장 왼쪽노드가 먼저 나온다

노드를 중간에 들린다, 그래서 In

InOrderTraversal( Node* pNode ){
 if( pNode != m_pNodeTail )
 {
  InOrderTraversal(pNode->pLeft );
  visit(pNode); // 왼쪽 먼저 트리를 찾아 갔다가 왼쪽이 없으면 방문하고 오른쪽을 가기 때문에 중위 순회
  InOrderTraversal(pNode->pRight );
 }
}

tip : 왼쪽으로 갔다가(왼쪽 끝까지 갔다가) 다시 올라올때 방문한다

후위순회 (post-order)

            A  
     B             C  
  D     E              F  
G   H                I

순서 G H D E B I F C A

왼쪽 subtree 를 방문한다.
오른쪽 subtree 를 방문한다.
root 를 방문한다

특징

가장 쪽 노드가 첫번째 나온다
루트가 가장 나중에 나온다

노드를 마지막에 들린다, 그래서 Post

PostOrderTraversal( Node* pNode ) {
 if( pNode != m_pNodeTail )
 {
  PostOrderTraversal( pNode->pLeft );
  PostOrderTraversal( pNode->pRight );
  visit(pNode); // 왼쪽, 오른쪽 다 들린 후 마지막에 올라올때 들린다
 }
}

tip : 현재 노드에서 오른쪽으로 갔다가 오른쪽 끝까지 간 후 다시 올라올때 방문한다

Array vs LinkedList

Array의 설명
논리적 저장 순서와 물리적 저장 순서가 일치하는 자료구조
인덱스로 해당 원소에 접근하는 방식

Array의 장점
인덱스를 알고 있다면 O(1)에 해당 원소로 접근할 수 있다. 접근에 유리

Array의 단점
하지만 삭제 또는 삽입의 과정에서 배열의 연속성을 깨지 않기 위해서 삭제/삽입 한 원소보다 큰 인덱스를 갖는 모든 원소들을
Shift 해줘야하는 비용이 발생하고 이 경우 시간복잡도는 O(n)이 된다.

LinkedList의 설명
논리적 저장 순서와 물리적 저장 순서가 일치하지 않는 자료구조
각각의 원소들은 자기 자신 다음에 어떤 원소인지만을 기억하는 자료구조

LinkedList의 장점
삭제/삽입을 O(1)만에 해결할 수 있지만 삭제/삽입하기 위해 원소를 찾아가는 과정에서 O(n)이 걸리므로 따지고 보면 비용은 O(n)이다.
단, 사용하기 편하다는 장점(삭제/삽입 시 Shift를 할 필요없기에), 트리에서 유용성이 들어나는 장점이 있다.

LinkedList의 단점
접근 시 첫 번째 원소부터 n을 찾을 때까지 O(n)의 시간이 걸리게 된다. 접근에 불리

Personal Recommendation

Array 를 기반으로한 LinkedList 구현
ArrayList 를 기반으로한 LinkedList 구현

Stack & Queue
Stack
Stack의 설명
선형 자료구조의 일종 LIFO(Last In First Out)
원소가 들어가면 차곡차곡 쌓이는 구조로 호출 시 맨 위에 요소를 호출하는 구조.

Queue
Queue의 설명
선형 자료구조의 일종 FIFO(First In First Out)
원소가 들어가면 터널을 통해서 나오는 형식으로 호출 시 맨 처음에 넣었던 요소를 호출하는 구조.

Personal Recommendation

Stack 을 사용하여 미로찾기 구현하기
Queue 를 사용하여 Heap 자료구조 구현하기
Stack 두 개로 Queue 자료구조 구현하기
Stack 으로 괄호 유효성 체크 코드 구현하기

Tree Tree 설명
트리는 비선형 자료구조이다. 계층적인 관계를 표현하는 자료구조다. Node 트리를 구성하는 요소, Edge 노드와 노드를 연결하는 선을 의미하는 것

Binary Tree 특징
Root Node를 중심으로 두 개의 서브 트리로 나뉘어 진다. 나뉘어진 서브 트리도 모두 이진 트리어야 한다. 재귀적 정의를 만족한다.
Full Binary Tree(포화), Complete Binary Free(완전)가 있는데
모든 레벨이 꽉 찬 이진 트리가 포화(Full)이고, 위에서 아래 왼쪽에서 오른쪽 순서대로 차곡차곡 채워진게 완전(Complete) 트리다.
포화, 완전 이진 트리의 중요한 특징으로 노드의 개수가 n 개 일 때,
i 번째 노드에 대해서 parent(i) = i/2 , left_child(i) = 2i , right_child(i) = 2i + 1 의 index 값을 갖는다.
이진 탐색 트리의 평균적인 탐색 연산은 O(log n)의 시간 복잡도를 갖는다.
하지만 저장 순서에 따라 계속 한 쪽으로만 노드가 추가되는 경우가 발생하기 때문에
이럴 경우 성능에 영향을 미치게 되며, 탐색의 Worst Case 가 되고 시간 복잡도는 O(n)

HashTable hash는 내부적으로 배열을 사용하여 데이터를 저장하기 때문에 빠른 검색 속도를 갖는다.
특정한 값을 Search 하는데 데이터 고유의 인덱스로 접근하게 되므로 O(1)이 되는 것이다.
하지만 문제는 이 인덱스로 저장되는 key값이 불규칙하다는 것이다.
그래서 특별한 알고리즘을 이용하여 저장할 데이터와 연관된 고유한 숫자를 만들어 낸 뒤 이를 인덱스로 사용한다.
특정 데이터가 저장되는 인덱스는 그 데이터만의 고유한 위치이기 때문에, 삽입 연산 시 다른 데이터의 사이에 끼어들거나,
삭제 시 다른 데이터로 채울 필요가 없으므로 연산에서 추가적인 비용이 없도록 만들어진 구조이다.

hash function 해쉬테이블에서 사용하는 특별한 알고리즘

Graph 정점과 간선의 연결관계에 있어서 방향성이 없는 그래프를 Undirected Graph(무방향) 라 하고,
간선에 방향성이 포함되어 있는 그래프를 Directed Graph(방향) 라고 한다.

트리 또한 그래프이며, 그 중 사이클이 허용되지 않는 그래프를 말한다.

인접 행렬(adjacent matrix) : 정방 행렬을 사용하는 방법 해당하는 위치의 value 값을 통해서 vertex 간의 연결 관계를 O(1) 으로 파악할 수 있다.
Edge 개수와는 무관하게 V^2 의 Space Complexity 를 갖는다.
Dense graph 를 표현할 때 적절할 방법이다.

인접 리스트(adjacent list) : 연결 리스트를 사용하는 방법
vertex 의 adjacent list 를 확인해봐야 하므로 vertex 간 연결되어있는지 확인하는데 오래 걸린다.
Space Complexity 는 O(E + V)이다.
Sparse graph 를 표현하는데 적당한 방법이다.

깊이 우선 탐색(Depth First Search: DFS)
그래프 상에 존재하는 임의의 한 정점으로부터 연결되어 있는 한 정점으로만 나아간다라는 방법을 우선으로 탐색한다.
일단 연결된 정점으로 탐색하는 것이다.
연결할 수 있는 정점이 있을 때까지 계속 연결하다가 더이상 연결되지 않은 정점이 없으면
바로 그 전 단계의 정점으로 돌아가서 연결할 수 있는 정점이 있는지 살펴봐야 할 것이다.
갔던 길을 되돌아 오는 상황이 존재하는 미로찾기처럼 구성하면 되는 것이다. 어떤 자료구조를 사용해야할까? 바로 Stack 이다.
Time Complexity : O(V+E) … vertex 개수 + edge 개수

너비 우선 탐색(Breadth First Search: BFS)
그래프 상에 존재하는 임의의 한 정점으로부터 연결되어 있는 모든 정점으로 나아간다.
Tree 에서의 Level Order Traversal 형식으로 진행되는 것이다.
BFS 에서는 자료구조로 Queue 를 사용한다.
연락을 취할 정점의 순서를 기록하기 위한 것이다.
우선, 탐색을 시작하는 정점을 Queue 에 넣는다.
(enqueue) 그리고 dequeue 를 하면서 dequeue 하는 정점과 간선으로 연결되어 있는 정점들을 enqueue 한다.
즉 vertex 들을 방문한 순서대로 queue 에 저장하는 방법을 사용하는 것이다.
Time Complexity : O(V+E) … vertex 개수 + edge 개수 ! BFS 로 구한 경로는 최단 경로이다.

Binary Heap
자료구조의 일종으로 Tree 의 형식을 하고 있으며,
Tree 중에서도 배열에 기반한 Complete Binary Tree이다.
배열에 트리의 값들을 넣어줄 때, 0 번째는 건너뛰고 1 번 index 부터 루트노드가 시작된다.
이는 노드의 고유번호 값과 배열의 index 를 일치시켜 혼동을 줄이기 위함이다.
힙(Heap)에는 최대힙(max heap), 최소힙(min heap) 두 종류가 있다.
Max heap에서는 Root node 에 있는 값이 제일 크므로, 최대값을 찾는데 소요되는 연산이 O(1)이다.
그리고 complete binary tree이기 때문에 배열을 사용하여 효율적으로 관리할 수 있다.
하지만 heap 의 구조를 계속 유지하기 위해서는 제거된 루트 노드를 대체할 다른 노드가 필요하다.
여기서 heap 은 맨 마지막 노드를 루트 노드로 대체시킨 후,
다시 heapify 과정을 거쳐 heap 구조를 유지한다. 이런 경우에는 결국 O(log n)의 시간복잡도로 최대값 또는 최소값에 접근할 수 있게 된다.

알고리즘

기본 정렬 개념 https://gist.github.com/Curookie/36f0007f67769c26ee173ed026e842a7

Bubble Sort
버블정렬은 가장 쉬운 알고리즘이다.
처음부터 끝까지 자신과 자신의 다음 데이터를 비교해가면서 가장 큰 수를 맨 뒤로 보내는 식으로 동작하는 알고리즘이다

배열 전체를 순회하며 비교하기 때문에 시간복잡도는 O(n²)이며
배열 하나만 사용하기 때문에 공간복잡도는 O(n) 이다.

Selection Sort
선택정렬이라고도 불리며, 배열의 가장 작은 값을 가지는 인덱스를 찾아서 가장 작은 값을 앞에서부터 채워나가면서 정렬하는 방식.

for loop 2번을 통해 배열을 훑고, swap하는 방식으로 시간복잡도는 O(n²)
공간복잡도는 O(n) 이다.

Insertion Sort
삽입정렬이라고 불리며, 최소값을 찾아서 이하 배열들의 원소와 비교하여 자신이 위치해야할 곳을 찾아 삽입해나가며 정렬하는 방식이다.

for loop 혹은 while loop를 2중첩으로 구현되어 시간복잡도는 O(n²)
공간복잡도는 O(n) 이다.

Merge Sort
병합정렬이라고도 불리며, 배열을 반씩 쪼개서 하나의 원소를 가진 배열로 만든 후 비교를 통해 각 배열을 정렬하여 병합하여 최종 정렬된 배열을 구하는 정렬방식이다.

배열을 반씩 쪼개며 정렬을 하고 다시 그것을 병합하는 방법으로 시간복잡도는 O(nlogn)이다.
공간복잡도는 O(n) 이다.

Quick Sort
병합정렬과 어찌보면 비슷한 로직으로 돌아가는 정렬이며, 기준이 되는 기준점을 가지고 앞/뒤 배열로 쪼개서
각 앞/뒤배열을 기준값 보다 작은수를 앞으로 몰고 기준값보다 큰 수를 재귀함수를 통해 뒤로 몰아가는 정렬방식

배열을 기준점으로 나누어 해당 기준값을 기준으로 좌,우의 배열을 다시한번 탐색하며 정렬하는 방식으로 시간복잡도는 O(nlogn)
공간복잡도는 O(n) 이다.

프로그래밍 일반

자바스크립트에서 call by reference는 존재하지 않고 call by value만 존재한다.
참조 타입을 인자로 넘기면 참조값에 대한 복사본이 넘어간다.
이러한 혼동을 줄이고자 call by sharing이란 용어로 부르기도 한다.

equal() 메소드는 비교하고자 하는 대상 내용을 비교하지만, ==는 비교하고자 하는 대상의 주소값을 비교한다.

에러(Error)와 예외(Exception)
에러는 시스템 레벨에서 발생하여, 개발자가 어떻게 조치할 수 없는 수준을 의미. ex. JVM OOM
예외는 개발자가 구현한 로직에서 발생하며, 개발자가 다른 방식으로 처리가능한 것들, JVM은 정상 동작. ex. 인덱스범위 검사

NullPointerException : Null 레퍼런스를 참조할때 발생, 뭔가 동작시킬 때 발생한다.
(XXX)IndexOutOfBoundsException : 배열과 유사한 자료구조(문자열, 배열, 자료구조)에서 범위를 벗어난 인덱스 번호 사용으로 발생
(XXX)FormatException : 문자열, 숫자, 날짜 변환 시 잘못된 데이터(ex. "123A" -> 123 으로 변환 시)로 발생, 보통 사용자의 입력, 외부 데이터 로딩, 결과 데이터의 변환 처리에서 자주 발생한다.
ArthmeticException : 정수를 0으로 나눌때 발생
ClassCastException : 변환할 수 없는 타입으로 객체를 변환할 때 발생
IllegalArgumentException : 잘못된 인자 전달 시 발생
IOException : 입출력 동작 실패 또는 인터럽트 시 발생
IllegalStateException : 객체의 상태가 매소드 호출에는 부적절한 경우
ConcurrentModificationException : 금지된 곳에서 객체를 동시에 수정하는것이 감지될 경우 발생
UnsupportedOperationException : 객체가 메소드를 지원하지 않는 경우 발생

재귀함수 vs 반복문 장단점 재귀함수는 구현이 편하고 공간복잡도가 낮다. 하지만 재귀적으로 함수를 호출하므로 시간복잡도가 높아서 검색시간이 오래걸린다. 반복문은 재귀함수에 비해 구현이 복잡하고 배열을 사용해야하므로 공간복잡도가 높다. 하지만 재귀함수에 비해 시간복잡도가 낮아 검색이 빠르다.

private void call_C() throws Exception {
  System.out.println(1 / 0); 
} 

public static void main(String[] args) throws Exception { 
  ThrowsEx test = new ThrowsEx(); 
  test.call_A(); 
}

.Java primitive type byte,short,int,long,float,double,char,boolean

DB

https://gist.github.com/Curookie/a93a54fea8953126591396dcd66554e6

JOIN 예

아직 입양을 못 간 동물 중,
가장 오래 보호소에 있었던 동물 3마리의 이름과 보호 시작일을 조회하는 SQL문을 작성해주세요.
이때 결과는 보호 시작일 순으로 조회해야 합니다.

Inner Join 교집합
Outer Join 합집합

SELECT A.NAME, A.DATETIME
FROM ANIMAL_INS A LEFT JOIN ANIMAL_OUTS B ON A.ANIMAL_ID = B.ANIMAL_ID
WHERE B.ANIMAL_ID IS NULL
ORDER BY A.DATETIME ASC LIMIT 3

SELECT ANIMAL_ID, NAME
FROM ANIMAL_INS
WHERE ANIMAL_TYPE = 'Dog' AND NAME LIKE '%el%'
ORDER BY NAME ASC

SELECT NAME, COUNT( * )
FROM ANIMAL_INS
WHERE NAME IS NOT NULL
GROUP BY NAME HAVING COUNT( * ) >= 2

트랜잭션의 격리 수준(Isolation Level)이란?
동시에 여러 트랜잭션이 처리될 때
특정 트랜잭션이 다른 트랜잭션에서 변경하거나 조회하는 데이터를 볼 수 있도록 허용할지 말지를 결정하는 것.
트랜잭션 격리 수준은 어떤게 있을까?
READ UNCOMMITTED
READ COMMITTED
REPEATABLE READ
SERIALIZABLE

RAID 0
(최소한 2개의 저장장치를 필요로 합니다), (같은 모델, 같은 용량의 저장장치로 구성되야만 합니다.
[Striping] - 데이터를 분산시켜 여러 드라이브에 분산 저장 함으로서 빠른 입출력을 가능하게 함.
RAID 0 이 위의 RAID 중에서 가장 빠르며, 그만큼 안정성이 떨어집니다.

RAID 1
(2N개의 저장장치를 필요로 합니다.)
[Mirroring] - 두개의 하드디스크에 똑같은 데이터를 똑같이 저장합니다.

RAID 10
(4개의 저장장치를 필요로 합니다.)
Mirroring : 두개의 하드디스크에 똑같은 데이터를 똑같이 저장
Parity : 데이터의 손실여보를 점검할 수 있는 데이터 저장체
위에 2개의 disk씩 묶인 것은 Raid1과 같습니다.
서로 mirroring이 되서, 복구시킬 수 있도록 구성하였고, 여기에 용량이 추가시킬려면 Raid1을 하나 더 붙이는 것입니다.
이 상황에서 Raid0방식으로 그냥 이어 붙이는 것입니다.
그렇게 되면 다음과 같이 용량은 Raid1에 비해 2배가 되는 것을 확인할 수 있습니다.
이 경우 다음과 같은 Disk fail이 나더라도 복구할 수 있습니다.

보안

공개키 기반 구조(PKI)에서 최상위 인증기관(CA)를 무엇이라고 하는가? => root CA

Curookie/전산학 이론 정리.md