가상 사설망(VPN: Virtual Private Network)은 사용자가 사설망에 연결된 것처럼 인터넷에 액세스할 수 있도록 하는 인터넷 보안 서비스

정의상 VPN 연결은 다음과 같다.

• 연결 프로세스에 실제 케이블이 없기 때문에 'Virtual'

• 이 연결을 통해 다른 사용자가 내 데이터 또는 검색 활동을 볼 수 없기 때문에 'Private'
• 컴퓨터와 VPN 서버 등 여러 디바이스가 함께 작동하여 설정된 링크를 유지하므로 'Network'

VPN 등장 배경

사설망이란?

인터넷이 성장함에 따라 IPv4 Address의 폭발적인 수요가 일어났고 IPv4의 주소는 점점 부족해지기 시작하였다. 그리하여 탄생한 것이 바로 사설망(Private Network)이다. IPv4 대역 중 일부를 Private IP로 지정하여 근거리 통신망 LAN에서 사용하도록 하여 IPv4 주소를 절약하였다. 사설망의 장점은 IPv4 주소 절약뿐만 아니라 보안적인 측면에서도 존재한다. 사설 IP를 이용해 별도의 네트워크를 구성함으로써 외부 인터넷과 내부의 네트워크를 분리하고 외부 인터넷의 접근으로부터 내부 네트워크를 보호할 수 있다. 그렇기에 필요한 경우에만 NAT(Network Address Translation)을 이용해 공인 인터넷 통신을 수행한다. 그런데, 여기저기 다양한 장소에 사설망이 구축되기 시작하면서 멀리 떨어져 있는 다른 사설망과의 연결의 필요성이 크게 증가하기 시작하였다.

전용 회선의 등장

기업의 경우, 회사 네트워크를 구축하면서 멀리 떨어져있는 지사 네트워크를 연결하기 위해 전용회선을 사용한다. 즉, 본사 사설망과 지사 사설망을 연결하는 것이다. 공인 인터넷이 아닌 인터넷 서비스 공급자(ISP)의 망 일부를 독점하여 사용하기 때문에 내부 트래픽이 아니면 접근할 수 없어 데이터의 안전이 보장된다는 것이 전용 회선의 큰 장점이다. 하지만 전용 회선은 큰 단점도 존재한다. 망 일부를 독점하여 사용하는 만큼 값이 매우 비싸다. 따라서 사람들은 비싼 전용 회선을 사용하지 않고도 사설망끼리 연결할 방법을 찾기 시작하였다.

이를 위하여 다음 두가지의 조건이 충족 되어야 한다.

• 비싼 전용 회선이 아닌 공인망을 사용하여 사설망과 사설망을 연결할 수 있어야 한다.

• 데이터가 안전하게 암호화되어야 한다.

이 두가지를 해결한 것이 바로 VPN(Virtual Private Network)이다.

VPN

VPN은 공인 인터넷을 사이에 둔 사설망과 사설망이 공인 IP로의 NAT와 같은 제약 없이 사설 IP를 이용해 통신(Routing)할 수 있도록 지원하며 데이터의 암호화를 제공한다.

VPN은 공인 인터넷에서 IP packet을 캡슐화함과 동시에 데이터를 암호화를 수행한다. 이 기술을 보통 터널링(Tunnerling)이라 한다.

터널링(Tunneling)은 간단히 말해서 원래 직접 갈 수 없는 데이터를, 다른 데이터(다른 프로토콜) 안에 넣어서 안전하게 목적지까지 보내는 기술이다. 원래 인터넷은 사설 IP를 직접 라우팅하지 않는다.(라우터 규칙)

VPN 보안

IP 숨기기

VPN을 켜면, 내 PC ↔ VPN 서버 사이에 암호화된 터널이 만들어진다.

인터넷으로 나가는 모든 요청은 내 PC에서 바로 목적지로 가는 게 아니라:

1. 먼저 VPN 서버로 감
2. VPN 서버가 대신 목적지에 접속

목적지 웹사이트/서비스 입장에서는 “VPN 서버의 IP”가 보이고, 내 진짜 IP는 감춰진다.

따라서 VPN을 이용하면 광고·트래킹·정부 검열 대상에서도 내 위치·IP를 추적하기 어려움.

데이터 암호화

내 PC ↔ VPN 서버 구간이 암호화(AES, ChaCha20 등) 되어 있으므로:

• 공용 와이파이에서 스니핑(패킷 도청) 불가
• ISP나 중간 라우터도 내가 어떤 사이트에 접속하는지, 어떤 데이터를 주고받는지 알 수 없음.

다만, VPN 서버 ↔ 목적지 사이트 구간은 암호화 안 될 수도 있음(HTTPS 안 쓰면 노출 가능).

한계

• VPN 서버 운영자는 내 접속 기록을 남길 수 있음
• 속도 저하

Docker란 Go언어로 작성된 리눅스 컨테이너 기반으로하는 오픈소스 가상화 플랫폼이다.
개발자는 Docker를 통하여 애플리케이션을 신속하게 구축, 테스트, 배포할수 있게 된다.

가상화를 사용하는 이유는?

가상화는 하나의 물리적 자원을 논리적으로 여러 개처럼 나누어 사용하는 기술이다.
쉽게 말해, 하나의 컴퓨터에서 여러 컴퓨터가 있는 것처럼 운영하는 방식이다.

가상화가 처음 등장했던 1960~70년대 상황을 살펴보면, 무어의 법칙에 의해 하드웨어의 성능은 빠르게 증가하는 가운데, 그 당시 소프트웨어의 발전 속도는 하드웨어의 발전 속도를 따라가지 못했다. 위의 타임라인을 보면 소프트웨어는 1990년대 이후 급격히 발전한 것을 볼 수 있고, 소프트웨어가 요구하는 서버 사양에 비해 소프트웨어를 실행 중인 서버의 성능이 훨씬 좋다 보니, 서버의 성능을 10% 수준밖에 활용하지 못하는 엄청난 비효율이 발생했다.

이러한 비효율을 해결하기 위하여 고안된 것이 바로 가상화개념이다. 한 대의 서버를 마치 여러 대의 서버처럼 사용할 수 있다면? 즉, 한 대의 서버 위에 동시에 여러 개의 OS를 설치하고 여러 애플리케이션을 실행시킬 수 있다면, 자원 비효율 문제를 해결할 수 있었고 실제로 가상화 적용 이후 515%에 그치던 자원 사용률은 6080% 수준까지 향상되었다고 한다.

대표적인 가상화 플랫폼으로는 VMware, virtualbox 등이 있다.

가상화의 종류

크게 두가지를 볼 수 있다.

- 하드웨어가상화(VM) : 물리적 하드웨어 위에 하이퍼바이저(Hypervisor)를 올려 여러 OS 실행
- OS수준 가상화(컨테이너) : 하나의 OS 커널을 공유하며, 프로세스/파일 시스템을 격리

커널이란 하드웨어를 제어하기 위한 명령어이다. 여기서 주목할건 "OS마다 명령어를 해석하는 규칙이 다름" ex) 인사 = hello, Hello, HELLO ex) 덧셈 = add(맥), ADD(레드햇), Add(윈도우)

나라마다 언어가 다르듯 어떠한 연산을 하려 할 때 위에 예시들처럼 같은 의미이지만 말하는 바가 다르기 때문에 처리할 명령을 이해할 수 없다.

그러면, 어떻게 이러한 명령어들을 이해해서 각각 OS를 구동하게 할 수 있을까? OS의 커널을 수정해야한다 (= OS의 소스를 까서 수정을 해야한다는 뜻 = Guest OS를 수정해야한다는 뜻)

하이퍼바이저

하이퍼바이저가 각 OS마다 말하는 명령을 하드웨어가 이해할 수 있게 하나의 명령어로 번역해준다.

컨테이너란?

운영 체제 커널을 공유하며, 경량 프로세스 격리를 제공

컨테이너는 해운업계 솔루션이였다. 화물을 어떻게 하면 효율적으로 옮길까 라고 생각해봤을 때, 표준화된 컨테이너 박스를 만들고 무엇을 넣어도 표준화된 운송선만 있다면 똑같이 세워서 효율적으로 운송할 수 있는 것이 '컨테이너'다.

이러한 컨셉을 IT에 적용한것이 바로 '컨테이너'

소프트웨어 코드, 애플리케이션 코드가 작동하기 위해 필요한 컴포넌트와 함께 표준화된 방식으로 패키징해서 컨테이너 엔진만 있으면 돌아갈 수 있도록 하는 구조를 '컨테이너'라고 정의한다.

VM vs Container

가장 큰 차이점은 Guest OS의 유무이다. VM에서는 Guest Os가 설치되어 독립되는 실행환경인 반면 컨테이너에서는 Host OS의 커널을 공유하게 된다.

컨테이너에서는 Host Os위에 어플리케이션의 실행 패키지인 이미지를 배포만 하면 되는데 VM은 하나의 어플리케이션을 실행하기 위해 VM을 띄우고 자원을 할당하고 Guest OS를 부팅한 뒤에야 비로서 애플리케이션을 실행하게 되는 것이다.

결론

Docker는 컨테이너 엔진이다. 즉, 컨테이너를 생성하고 실행하고 관리하는 소프트웨어 중 하나이다.

다음 글에서는 도커의 기초적인 사용법과 개념들을 알아보겠다.

대칭키 암호란?

대칭키 암호란 동일한 키로 암호화와 복호화를 수행하는 암호 알고리즘이다. 대표적인 알고리즘: AES, DES 특징으로는 비대칭키 암호보다 속도가 빠르다.

동일한 키로 암호화와 복호화를 수행하니 암호화 하는 사람과 복호화 하는 사람은 동일한 키를 분배 받아야한다. 이를 어떻게 할지가 본 문서의 핵심이다.

두 참가자가 키를 분배 받는 방식을 생각해보면 대략 4개로 나눌 수 있다.

1. A가 키를 선택하여 B에게 직접 전달
2. 제 3자가 키를 선택하여 A와 B에게 직접 전달
3. A와 B가 이전에 사용한 적 있는 키를 이용하여 암호화하여 상대에게 전달
4. A와 B가 제 3자인 C와 암호화된 링크가 있다면, C가 암호화 된 링크 상에서 A와 B에게 키를 전달

직접 전달 방식의 한계

여기서 1번 2번 방식은 한계가 있다. 이유는 분산 시스템이나 IP레벨에서 이루어지는 통신에서는 매우 많은 장치가 다른 매우 많은 장치들과 통신을 해야되기 때문이다. 하나의 장치가 각각 다른 장치들 모두의 키를 다르게 소유하고 있어야하기 때문에 각 장치는 매우 많은 키가 필요하다.

이전 키로 암호화하여 전달 방식의 한계

3번 방식도 마찬가지로 한계가 있다. 마찬가지로 매우 방대한 양의 키가 필요하며, 공격자가 만약 이전 키를 얻으면 이후의 키들은 모두 복호화가 가능하기 때문이다. 도미노 처럼

암호화된 링크를 통한 전달

따라서 이러한 1,2,3번 방식의 문제를 해결하기 위하여 가장 좋은 방법은 '키 분배 센터'를 이용하는 방법이다.

이 방식에서는 '필요한 키의 개수 == 사용자 수'이다. 이유는 각 사용자는 KDC(Key Distribution Scenario)와 둘만의 유일한 마스터키를 교환하기만 하면 그 이후는 세션 키를 사용함으로써 통신이 필요할 때만 키를 생성하기 때문이다. 이러한 KDC구조는 계층적으로 존재할 수도 있다. 이제 이러한 방식이 어떤식으로 동작하는지 알아보자.

KDC방식의 키 분배 시나리오

먼저 알아야 될 것은 '세션키'의 개념이다. 세션키는 하나의 통신 세션에서 사용하는 키이며, 통신이 끝나면 폐기된다. 이렇게 폐기함으로써 공격자가 키를 해독할 시간을 주지 않는 것이다. 여기서는 이러한 세션키(즉 대칭키 역할을 수행한다.)를 KDC 방식에서 어떻게 분배하는지 서술한다.

1. A가 KDC에게 자신의 식별자, B의 식별자, 임시비표 N1을 전송함으로 세션 키를 요청한다.
   • 여기서 임시비표는 난수 혹은 타임스탬프 등의 값이며 이번 통신과 다른 통신과 혼돈하지 않기 위하여 사용한다.
2. KDC는 사전에 A와 공유된 A의 마스터키로 암호화하여 세션키와 (1)에서 수신한 내용을 A에게 송신한다. 추가로 A는 B에게 KDC를 대신해서 전달해줄 B를 위한 내용도 같이 수신한다.
3. KDC와 A만 아는 A의 비밀키로 암호화되어 (1)의 내용들을 전달 받았기에 A만 세션 키를 복호화할 수 있으며, 상대방이 KDC라는 것을 확인할 수 있다. 이제 A가 세션키를 저장한 후에 B에게 KDC에게 받은 내용을 대신 전달한다. 내용은 B의 비밀키로 암호화된 세션키와 A의 식별자로 구성되어있다.
4. B는 마찬가지로 세션키를 소유하게 되며, 해당 내용이 KDC로부터 전송된것이라는 것을 알 수 있다. 또한 A의 식별자가 있기 때문에 통신 상대방이 A라는 것도 알 수 있다. 하지만 상대방이 A인 것을 확인하기 위하여 임시비표 N2를 생성하여 A에게 세션키로 암호화하여 전송한다. 세션키를 가진 사람은 A와 B뿐이기 때문이다.
5. A는 복호화하여 N2를 함수화하여 다시 B에게 전달하여 자신이 A라는 것을 인증하게 된다.

세션 키 수명 주기

현대에 대부분의 통신은 세션키를 통하여 암호화하여 안전한 통신을 한다. 세션키는 공격자에게 복호화할 시간을 주지 않기 때문에 빈번하게 갱신될 수록 안전하다. 하지만 계속 세션키를 생성하고 분뱋는 과정에서 오버헤드가 발생하기 마련이고, 대칭키 암호의 가장 큰 장점 중에 하나인 속도가 빠르다는 점을 상쇄시킨다. 따라서 안전과 효율 사이 적절한 균형을 맞출 필요가 있다.

연결형 프로토콜에서는 보통 새로운 연결마다 세션 키를 사용한다. 이 때 만약 오래 연결되어 있는 통신이라면 특정 주기마다 세션 키를 갱신해야할 필요가 있다. 비연결형 프로토콜에서는 명시적인 연결 시작과 종료가 없다. 따라서 일정 시간이나 일정 수의 교환마다 세션 키를 갱신해야할 필요가 있다.

자동화된 키 분배

연결형 프로토콜을 사용할 때 SSM(Session Key Module)을 통하여 호스트나 터미널의 개입 없이 시스템에서 자동적으로 키 교환이 수행되도록 설계할 수 있다.

비중앙집중형 키 제어

앞서 KDC없이 직접 전달 방식은 매우 많은 키를 필요로 한다는 한계가 있었다. 하지만 이러한 한계에도 불구하고 작은 규모의 환경이나 보안이 매우 중요한 환경에서는 사용된다.

이유는 다음과 같다.

• 중앙집중형 방식은 중앙 기관이 공격 당하면 키가 노출된다.
• 따라서 KDC는 신뢰할 수 있게 설계되어야한다.

이러한 요구사항들이 필요 없고, 서버 해킹에 대하여도 안전한 비중앙집중형 키 분배 방식은 효율은 비록 낮을지언정 강력한 보안을 제공하기 때문에 WhatsApp, 텔레그램 비밀대화 등에서 사용된다. 이를 종단 간 암호화라고 한다.

시나리오

A와 B는 사전에 둘만의 마스터키를 소유하고 있다고 가정한다. 통신을 위한 세션 키를 얻기 위하여 다음과 같은 절차를 수행한다.

1. A가 B에게 세션 키를 요청하기 위하여 자신의 식별자와 임시비표 N1을 생성하여 송신한다.
2. B는 A에게 둘만의 마스터키로 암호화하여 세션키와 A이 식별자, B의 식별자, 함수화된 N1, 새로운 N2를 생성하여 전달한다.
3. A는 마스터키로 복호화하여 상대방이 B인것을 알게 되며, 세션키를 저장한다. 추가로 N2를 함수화하여 세션키로 B에게 전송하며 자신이 A인것을 인증하게 된다.

이로써 A와 B는 안전하게 통신할 준비가 되었다.

다음 글에서는 비대칭키 암호를 이용한 대칭키 분배에 대하여 다뤄보겠다.

1. 해당 프로젝트 폴더에서 Git Bash를 실행

2. .gitignore파일 생성

touch .gitignore

3. 에디터로 파일 열기

• VScode로 열기

  code .gitignore

  4. 에디터로 수정

• 파일 내용을 수정한다. ```bash

  모든 파일 무시

• .c 파일만 추적

  !*.c

원하면 README도 추가

!README.md ```

• 객체 사이이 연결 관계를 표현할 수 있는 자료 구조
• 정점(vertex)와 간선(edge)들의 유한 집합
• G = {V, E}

그래프의 종류

• 무방향 그래프 (undirected graph)

• 방향 그래프 (directed graph)

• 가중치 그래프(weighted graph)

• 부분 그래프(subgraph): 어떤 그래프의 정점과 간선의 일부로 이루어진 그래프

• 차수(degree): 그 정점에 인접한 정점의 수

• 연결 그래프(connected graph): 무방향 그래프에 있는 모든 정점 쌍에 대하여 항상 경로가 존재하는것.

• 완전 그래프(complete graph): 모든 정점들이 서로 연결되어 있는 그래프

그래프의 표현 방법

• 인접 행렬(adjacency matrix): 2차원 배열을 사용
• 인접 리스트(adjacency list): 연결 리스트를 사용

그래프의 탐색

하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것

탐색의 방법

• DFS(depth first search): 깊이 우선 탐색
• BFS(breath first search): 너비 우선 탐색

최소 비용 신장 트리

신장 트리(spanning tree)

• 그래프 내의 모든 정점을 포함하는 트리
• 모든 정점이 연결 되어 있어야 하고 사이클을 포함하면 안 됨
• 따라서 n개의 정점을 정확히 n-1개의 간선으로 연결
• 하나의 그래프에는 많은 신장 트리가 존재 가능
• DFS, BFS 도중 사용된 간선만 모으면 만들 수 있음

최소 비용 신장 트리(MST)

• 네트워크에 있는 모든 정점들을 가장 적은 수의 간선과 비용으로 연결

MST 알고리즘

Kruskal의 MST 알고리즘

• 탐욕적인 방법(greedy method)
• 매 순간 가장 좋다고 생각되는 것을 선택
• kruskal의 알고리즘은 지역적인 해답 뿐만 아니라 전역적인 해답도 최적의 해

1. 간선들을 가중치의 오름차순으로 정렬
2. 사이클 형성 검사 - union-find연산
3. 간선의 개수가 정점의 개수 -1개이면 종료

시간 복잡도 분석

union-find 알고리즘을 이용하면 간선들을 정렬하는 시간에 좌우된다.

Prim의 MST 알고리즘

• 시작 정점에서부터 출발하여 신장 트리 집합을 단계적으로 확장
• 포함된 신장 트리 집합에 인접한 정점들 중에서 최소비용으로 연결된 정점을 선택
• 마찬가지로 간선의 개수가 정점의 개수 - 1개이면 종료

시간 복잡도 분석

• 주 반복문이 정점의 수 n만큼 반복, 내부 반복문이 n번 반복
• 따라서 O(n^2)

Kruskal vs Prim

희소 그래프의 경우에는 Kruskal 밀집 그래프의 경우에는 Prim

최단 경로

최단 경로(shortest path): 네트워크에서 정점 i와 정점 j를 연결하는 경로 중 가중치 합이 최소가 되는 경로

• 가중치 인접 행렬 사용

Dijkstra의 최단 경로 알고리즘

하나의 시작 정점으로부터 모든 다른 정점까지의 최단 경로를 찾는 알고리즘

Floyd의 최단 경로 알고리즘

그래프에 존재하는 모든 정점 사이의 최단 경로

복잡도 분석

• Dijkstra: O(n^2)
• Floyd: O(n^3)

하지만 모든 정점 쌍의 최단 경로 구할 때 Dijkstra도 O(n^3)이 된다. Floyd의 알고리즘은 매우 간결한 반복 구문을 사용하므로 Dijkstra의 알고리즘에 비해 상당히 빨리 모든 정점 간의 최단 경로를 찾을 수 있다.

위상 정렬

• 방향 그래프를 정렬

우선순위 큐는 우선 순위의 개념을 큐에 도입한 자료구조이다.

응용되는 사례는 다음과 같다.

• 시뮬레이션 시스템
• 네트워크 트래픽 제어
• 운영 체제에서의 작업 스케쥴링
• 수치 해석적인 계산

우선순위 큐는 여러 방법으로 구현이 가능한데, 가장 효율적인 구조는 heap이다.

Heap

• 완전 이진 트리의 일종으로 우선순위 큐를 위하여 특별히 만들어진 자료 구조
• 여러 개의 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 만들어진 자료 구조

특징으로는 느슨한 정렬 상태를 유지한다. 추가로 중복된 값을 허용한다.

Heap의 종류

• 최대 히프(max heap)

  부모노드 >= 자식노드

• 최소 히프(min heap)

  부모노드 <= 자식노드

Heap의 구현

히프는 완전 이진 트리이기 때문에 각각의 노드의 차례대로 번호를 붙일 수 있다. 따라서 히프를 저장하는 표준적인 자료구조는 배열이다.

• 왼쪽 자식의 인덱스 = (부모의 인덱스) * 2
• 오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1
• 부모의 인덱스 = (자식의 인덱스) / 2

Heap의 복잡도 분석

삽입, 삭제의 시간 복잡도 : O(log n)

Heap 정렬

• 히프의 특성을 이용하여 삽입 삭제만으로 정렬 가능

Heap 정렬의 복잡도

• O(n log n)

히프 정렬은 전체 자료를 정렬하는 것이 아니라 가장 큰 값 몇 개만 정렬 할 때 가장 유용하다.

허프만 코드

최소 히프를 이용하여 구현

• 비선형 자료구조
• 계층적인 자료를 표현하는데 적합한 자료구조 ex) 컴퓨터 디렉토리 구조, 인공지능 문제(결정트리)

트리는 한 개 이상의 노드로 이루어진 유한 집합이다.

이진 트리

• 모든 노드가 2개의 서브 트리를 가지고 있는 트리

-서브 트리는 공집합일 수 있음
-서브트리간에 순서가 존재함
-n개의 노드를 가진 이진 트리는 n-1개의 간선을 가짐
-높이 h일때 노드 개수 : 최소 h , 최대 2^h-1

이진 트리 분류

포화이진트리(full binary tree)

-트리의 각 레벨에 노드가 꽉 차있는 이진트리
-전체 노드 개수는 정확히 2^h-1
-번호 매기는 방법 : 레벨 단위로 왼쪽에서 오른쪽으로

완전 이진 트리(complete binary tree)

-높이가 k일때 레벨 1부터 k-1까지는 노드가 모두 채워져 있고 
 마지막 레벨에서는 왼쪽부터 오른쪽으로 순서대로 채워져 있는 이진트리
-따라서 포화이진트리는 항상 완전이진트리
-노드번호는 포화 이진 트리와 동일

스레드 이진 트리(threaded binary tree)

이진 트리의 NULL 링크를 활용하여 순환 호출 없이도 트리의 노드들을 순회 할 수 있음

이진 트리 표현 방법

• 배열
• 포인터

배열을 이용한 이진 트리

노드 i의 부모 노드 인덱스 = i / 2
노드 i의 왼쪽 자식 노드 인덱스 = 2i
노드 i의 오른쪽 자식 노드 인덱스 = 2i + 1

링크 표현법

왼쪽 포인터
오른쪽 포인터
데이터

순회 방법

VLR : preorder traversal(전위순회) LVR : inorder traversal(중위순회) LRV : postorder traversal(후위순회)

이진 탐색 트리(BST)

이진 탐색 트리 : 이진 탐색 트리의 성질을 만족하는 이진트리

- 모든 원소의 키는 유일한 키를 가진다.
- 왼쪽 서브 트리 키들은 루트 키보다 작다.
- 오른쪽 서브 트리의 키들은 루트의 키보다 크다.
- 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다.

삭제 연산

삭제 연산 시에는 세 가지 경우를 고려해야 한다.

1. 삭제하려는 노드가 단말 노드일 경우
2. 삭제하려는 노드가 하나의 왼쪽이나 오른쪽 서브 트리중 하나만 가지고 있는 경우
3. 삭제하려는 노드가 두개의 서브 트리 모두 가지고 있는 경우

이진 탐색 트리의 분석

• 레벨 당 두배로 노드의 개수가 늘기 때문에 이진탐색 트리의 높이는 log N
• 이진 탐색 트리에서의 탐색, 삽입, 삭제 연산의 시간복잡도는 O(트리의 높이)
• 따라서 이진 탐색 트리의 평균적인 경우의 시간 복잡도는 O(log h)
• 단 최악의 경우(경사 트리) : O(N)

배열을 이용하여 리스트를 구현하면 순차적인 메모리 공간이 할당 되므로 리스트의 순차적 표현(sequential representation)이라고 한다.

• 장점 : 빠름

• 단점 : 크기가 고정됨

연결리스트

연결 리스트는 포인터를 사용하여 데이터를 연결한다. (동적으로 공간 확보)

장점

• 크기 제한이 없다.
• 중간에서도 쉽게 삽입 삭제가 가능하다.

단점

• 구현이 복잡하다.
• 임의의 항목을 추출할 때 배열보다 오래걸림
• 포인터도 저장하여야 하므로 메모리 공간 많이 차지

하나의 프로그램에서 여러 연결리스트들은 첫번째 데이터로 구별

즉 첫번째 데이터만 알 수 있다면 연결 리스트의 나머지 데이터도 알 수 있다.

자기참조 구조체

자기참조 구조체란 자기 자신의 구조체를 가르키는 포인터를 포함하는 구조체를 의미한다.

원형 연결 리스트

중요 개념

• 원형 연결리스트에서 head는 마지막 노드

장점

• 하나의 노드에서 다른 모든 노드로 접근이 가능
• 노드의 삽입과 삭제가 단순 연결 리스트보다 용이
• 리스트의 끝에 노드를 삽입하는 연산이 효율적

응용

• 원형 연결리스트는 컴퓨터의 여러 응용프로그램을 하나의 CPU를 이용하여 실행할 때 필요하다.
• 멀티 플레이어 게임

이중 연결 리스트

이중 연결 리스트는 단순 연결 리스트에서는 선행 노드를 찾기 어렵다는 문제를 양방향으로 자유롭게 움직일 수 있게 보안하여 만들어진 자료구조이다.

장점

• 양방향으로 검색이 가능함(유용함)

단점

• 공간을 많이 차지하고 코드가 복잡함

• 실제 응용 프로그램에서는 이중 연결 리스트와 원형 연결 리스트를 혼합하여 많이 사용함

연결 리스트로 구현한 스택

• 크기가 제한되지 않는다는 큰 장점이 있다
• 하지만 배열 보다는 삽입 삭제 등 연산에 시간이 더 걸린다.

연결 리스트로 구현한 큐

• 마찬가지로 크기가 제한 되지 않는다.
• 하지만 코드가 복잡해지며 링크 필드 때문에 메모리 공간을 더 많이 차지한다.

큐는 FIFO: First-In First-Out (선입선출) 구조이다.

큐의 응용

큐는 현실세계의 실제상황을 시뮬레이션 하는 상황에서 많이 응용된다.

선형 큐(Linear Queue)

1차원 배열을 이용하여 구현한 큐

• 선형큐는 삽입과 삭제를 반복하다보면 rear이 맨 마지막 인덱스를 가리키고 앞에는 비어있을 수 있지만 이를 꽉 찼다고 인식함.
• 배열에 앞부분이 비어 있더라도 사용하지 못한다.
  • 요소들을 이동시키면 되지만 상당히 비효율

원형 큐(Calcular Queue)

배열이 원형으로 처음과 끝이 연결되어 있다는 개념 (실제로 원형으로 변화하는 것은 아니고 선형 큐와 마찬가지로 1차원 배열)

• 선형 큐의 문제점을 보안
• 선형 큐에서 간단하게 변경 가능

덱(deque)

덱(deque): double-ended queue

front와 rear에서 삽입 삭제가 가능한 큐

• 스택과 큐의 연산들을 모두 가지고 있음
• add_front, delete_front = push, pop
• add rear, delete_front = enqueue, dequeue
• 원형 큐에서 확장하면 손쉽게 구현

즉 스택은 자료의 출력순서가 입력순서의 역순으로 이루어져야 할 경우에 적합한 자료구조이다.

스택의 대표적인 예로는 다음이 있다.

• 운영체제가 사용하는 시스템 스택
• 텍스트 에디터 되돌리기 기능
• 스마트폰 되돌리기 기능

return과 exit(1) 둘 다 프로그램을 종료 시킬 수 있지만

프로그램을 즉시 종료해야할 때 는 exit(1) 을 사용하는 것이 바람직하다. ex) 치명적인 오류가 발생하여 더 이상 실행할 필요가 없을 경우 전체 프로그램을 종료

하지만 메모리 누수나 흐름 제어 문제를 유발할 수 있으므로 신중히 사용해야 한다.

새로운 기능을 개발하거나 버그를 수정할 때 별도의 브랜치를 만들어 독립적으로 작업할 수 있다.

✅ 브랜치를 사용하면 여러 명이 동시에 다른 작업을 진행하면서도, 안정적인 코드를 유지할 수 있음

• 브랜치 목록 확인

git branch

• 새로운 브랜치 생성

  git branch 브랜치이름

• 브랜치 삭제

  git branch -d 브랜치이름

• 브랜치 전환

  git checkout 브랜치이름

merge

git merge 브랜치이름

두 브랜치가 공통으로 갖고 있는 commit을 base라고 한다.

fast-foword merge

• Fast-Forward Merge는 병합하려는 브랜치가 다른 브랜치의 직선상에 있는 경우 발생

• 즉, 병합 대상 브랜치가 다른 브랜치의 최신 커밋을 포함한 직선적 역사일 때

• 새로운 병합 커밋을 만들지 않고, 브랜치 포인터만 이동하여 병합을 완료

3-way merge

• 3-Way Merge는 두 브랜치가 서로 다른 커밋을 포함하고 있을 때 발생

• 즉, 두 브랜치가 공통 조상 커밋 이후에 각각 다른 변경이 이루어진 경우

• 이때 Git은 세 개의 커밋(공통 조상, 첫 번째 브랜치의 최신 커밋, 두 번째 브랜치의 최신 커밋)을 비교하여 병합을 수행

원격 저장소 등록하기

git remote add 원격저장소이름 원격저장소주소

참 고 : origin 원격 저장소의 이름을 orgin으로 지정하면 된다. master와 마찬가지로 git 공식 명칭은 아니지만 원격 저장소의 이름으로 사용되는 이름이다.

git push

• 처음 push할 경우

  git push -u origin master

  git push --set-upstream origin master

• 이후에

  git push

git pull

• 원격 저장소의 최신 변경 사항을 로컬 저장소로 가져와서 병합(Merge) 하는 명령어

  git pull

git clone

• 원격 저장소를 복제하여 로컬 저장소를 생성(처음 원격 저장소를 받을 때 사용)

git clone <원격 저장소 주소>

.ignore

• push를 할 때 여러가지 이유로 add에 포함시키고 싶지 않은 파일을 정의할 수 있음

1. git init을 한 폴더에 .gitignore 파일을 생성
2. 양식에 맞게 제외할 파일들을 나열하면 된다.

제외할 파일 혹은 폴더의 이름을 적어도 되고 특정 확장자를 전부 제외할 수도 있다.

• git diff - show change

  git diff

git checkout

• 브랜치 전환

  git checkout 브랜치이름

• 특정 커밋 상태로 이동

  git checkout 커밋해시

  git reset

• Stagint Area에 올라간 파일을 Unstaging (git add 명령 취소)

  git reset 파일이름

• reset 옵션
• soft : 커밋 취소, Staging 상태 유지
• mixed : 커밋 취소, Staging 취소, local은 변경 상태로 유지
• hard : 커밋취소, Staging 취소, local 변경 상태 취소

git revert

git revert 커밋해시

• 지정한 커밋의 변경 사항을 취소하는 새로운 커밋을 생성
• 기존 커밋 히스토리는 유지됨
• 협업 중에 과거 커밋을 되돌릴 때 안전한 방법

git tag

git에서 관리하는 tag는 다음 두 가지가 있다.

• Lightweight tag : tag 이름만 기록
• Annotated tag : tag 이름 외에 설명(메시지), 서명, 작성자 정보, 날짜 등의 정보 포함

Lightweight tag는 특정 commit을 참조하는 포인터와 같은 기능만 가진다. 반면 Annotated tag는 참조 외에 다양한 내용을 포함하므로 git 내부 데이터베이스에 정보가 저장된다.

태그 목록 확인

git tag

Lightweight 태그 생성

git tag 태그이름 커밋해시

Annotated tag

git tag -a [tag명] [commit hash]

원격 저장소에도 태그 push

git push --tags

• 특정 파일만 add

  git add 파일명

• 한번에 add

  git add .

git status

• git에 의해 관리되는 파일들의 상태를 확인하는 명령어

  git status

git commit

• 에디터로 진입하여 commit 메세지를 입력

  git commit

• 에디터 없이 commit 메세지를 입력

  git commit -m "메세지 내용"

한번에 add와 commit

• 새로 추가된 파일이 없을 때 한정하여 사용

  git commit -am "메세지 내용"

git log

• commit 히스토리를 조회하는 기능

  git log

• 한줄로 보기

  git log --onelint

• 그래프 형태로 브랜치 파악

  git log --graph

• 모든 브랜치 파악

  git log --all --graph --decorate --oneline

• git init

  git init

1. git init은 새로운 git 저장소를 생성하고 초기화하는 명령어이다.
2. git init 명령어를 실행하면 폴더에 .git이라는 숨긴 레포지토리를 생성한다.

• git config

  git config user.name "User1"
  git config user.email "User1@gmail.com"

  git config는 유저설정하는 명령어이다.

git의 동작개념

git은 3가지의 작업 영역을 갖고 있다.

• Working Directory : 작업하고 있는 파일들이 위치하는 영역
• Staging Area : commit 하기 전 commit 할 파일들이 위치하는 영역
• Repository : 이력이 기록된 파일들이 위치하는 영역

여기서 staging Area는 별도의 폴더 공간이 있는 것은 아니라 index 파일로 관리 된다.

순환이란?

순환이란 어떤 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법이다.

순환은 본질적으로 순환적인 문제나 그러한 자료구조를 다루는 프로그램에 적합하다.

• 장점 순환은 어떤 문제에서는 반복에 비해 알고리즘을 훨씬 명확하고 간결하게 나타낼 수 있다.

• 단점

• 일반적으로 순환은 함수 호출을 하게 되므로 반복에 비해 수행속도 면에서는 떨어진다. (물론 순환이 반복보다 빠른 예제도 존재하긴 한다.)

• 순환 호출시에는 호출이 일어날 때마다 호출하는 함수의 상태를 기억되어야 하므로 여분의 기억장소가 필요하다.

순환 시에는 반드시 순환 호출을 멈추는 문장이 필요하다. 만약 멈추는 문장이 없다면 무한히 순환 호출을 하게 되어 결국 오류를 발생시키기 때문이다.

순환 호출의 내부

• 하나의 함수가 자기 자신을 다시 호출하는 것은 다른 함수를 호출하는 것과 동일

• 복귀주소가 시스템 스택에 할당되고, 호출되는 함수를 위한 매개변수(parameter)와 지역 변수를 스택으로부터 할당 받음

• 호출된 함수의 코드의 시작 위치로 점프(만약, 호출된 함수가 자기 자신이라면 자기 자신의 시작 주소로 점프)

• 호출된 함수가 끝나게 되면 시스템 스택에 복귀 주소를 호출하여 호출한 함수로 되돌아가게 됨

순환의 원리

분할 정복(divide and conquer): 주어진 문제를 더 작은 동일한 문제들로 분해하여 해결하는 방법

순환 예제

팩토리얼 계산

int factorial(int n)
{
    if (n <= 1) return(1);
    else return (n * factorial(n - 1));
}

거듭제곱값 계산

지수법칙을 이용하여 효율적으로 작성하였다. 위의 지수의 덧셈 성질을 이용하여

2^8 = 2^4 + 2^4 2^9 = 2^4 + 2^4 + 2^1

a^n = a^(n / 2) + a^(n / 2)

double power(double x, int n)
{
    if(n == 0) return 1;
    else if((n % 2) == 0) return power(x * x, n / 2);
    else return x * power(x * x, (n - 1) / 2);
}

거듭제곱값을 계산하는 프로그램은 반복적인 방법보다 순환적인 방법으로 구현하는 것이 효과적이다. 입력 값이 알고리즘의 반복마다 반씩 줄기 때문에 시간복잡도는 O(log n)이다.

피보나치 수열의 계산

int fib(int n)
{
    if(n == 0) return 0;
    if(n == 1) return 1;
    return (fib(n - 1) + fib(n - 2));
}

피보나치 수열은 정의 자체가 순환적으로 되어있다. 따라서 구현 시에 순환 호출을 사용하는 것이 자연스러운 방법이다. 위 코드는 매우 단순하고 이해하기 쉽지만 매우 비효율적이다. 이유는 중간에 이미 계산되었던 값을 기억하지 않고 다시 계산하기 때문이다. 시간 복잡도도 O(2^n)으로 실질적으로 피보나치 수열은 순환적인 방법으로 계산하는 것이 불가능하다. 따라서 반복적인 방법으로 계산해야 한다.

하노이탑 문제

void hanoi(int n, char from, char tmp, char to)
{
    if(n == 1)
    {
        printf("원판 1을 %c에서 %c로 옮긴다.\n", from, to);
    }
    else
    {
        hanoi(n - 1, from, to, tmp);
        printf("원판 %d를 %c에서 %c로 옮긴다.\n", n, from, to);
        hanoi(n - 1, tmp, from, to);
    }
}

int main()
{
    hanoi(4, 'A', 'B', 'C');

    return 0;
}

반복적인 형태로 바꾸기 어려운 순환

대부분의 순환적인 형태의 코드는 반복적인 형태로도 변환이 가능하다.

• 꼬리 순환(tail recursion)은 쉽게 반복적인 형태로 변환이 가능하다.

• 머리 순환(head recursion)이나 여러 군데에서 순환호출을 하는 경우 반복적인 형태로 바꾸는 것이 쉽지 않다.

만약 알고리즘을 꼬리 순환과 머리 순환 양쪽으로 모두 표현이 가능하다면 꼬리 순환으로 작성하여야 한다.

알고리즘 복잡 분석은 코드를 직접 구현하지 않고도 모든 입력을 고려하는 방법이다. 실행 하드웨어나 소프트웨어 환경과는 관계 없이 알고리즘의 효율성을 평가할 수 있다.

시간 복잡도 함수

알고리즘의 수행 시간 분석을 시간 복잡도(time complexity) 라고 한다.

연산의 수를 입력의 개수 n의 함수로 나타낸 것을 시간복잡도 함수라고 하고 T(n) 이라고 표기한다.

시간 복잡도 함수에서는 차수가 가장 큰 항만을 고려하면 충분하다.

T(n) = n^2 + n + 1

여기서 n = 1000 일 때 T(n) 의 값은 1,001,001이고 이중에서 첫 번째 항이 전체의 약 99.9%를 차지한다.

따라서 입력 자료의 개수가 큰 경우에는 차수가 가장 큰 항이 전체의 값을 주도함을 알 수 있다.

따라서 시간 복잡도 함수에서 중요한 것은 n이 증가하였을 때에, 연산의 총횟수가 n에 비례하여 증가하는지, 아니면 n^2의 비례하여 증가하는지, 아니면 다른 증가추세를 가지는지가 더 중요하다.

빅오 표기법

시간 복잡도 함수에서 불필요한 정보를 제거하여 알고리즘 분석을 쉽게 할 목적으로 시간 복잡도를 표시하는 방법을 빅오 표기법이라고 한다.

빅오 표기법은 n의 값에 따른 함수의 상한값을 나타내는 방법이다.

다음은 빅오 표기법에 의한 알고리즘의 수행시간을 비교한 것이다.

O(1) < O(log n) < O(n) < O( n * log n) < O(n^2) < O(2^n) < O(n!)

여기서 알고리즘이 지수형이나 팩토링얼형의 시간복잡도를 가진다면 사실상 사용할 수 없는 알고리즘이다. 그 이유는 입력의 개수가 30을 넘으면 현재의 가장 강력한 super computer를 동작시켜도 우주가 탄생되어 지금까지 흘러온 시간보다 더 많은 수행 시간을 요구 하기 때문이다.

그 외 시간복잡도 표기법

Big-Ω(빅 오메가) 표기법 : 알고리즘 최상의 실행 시간을 표기한다. Big-θ(빅 세타) 표기법 : 알고리즘 평균 실행 시간을 표기한다.

알고리즘의 성능을 분석하고자 할 때 동일한 조건의 컴퓨터에서의 동일한 조건에서 수행시간을 측정하는 방법을 알아보자.

실제 사용할 수 있는 경우는 제한적이지만 대단히 정확하고 확실한 방법이다.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main()
{
    clock_t start, stop;
    float duration;
    start = clock(); //측정 시작

    // 측정하고자 하는 프로그램

    stop = clock(); // 측정 종료
    duration = (float)(stop - start) / CLOCK_PER_SEC;
    printf("수행시간 : %f\n", duration);

    return 0;
}

clock() 함수는 호출 프로세스에 의하여 사용된 CPU 시간을 계산한다. 또 한 호출 되었을 때의 시스템 시각을 CLOCK_PER_SEC 단위로 반환한다.

이 방법을 사용하여 알고리즘을 비교하려면 반드시 똑같은 하드웨어를 사용하여 알고리즘들의 수행시간을 측정하여야 한다.

그 외에도 프로그래밍 언어, 동일한 데이터 사용 등 고려해야 할 사항이 있다.