CS

[CS - 운영체제] 스레드와 멀티 스레드 (Feat. 멀티 프로세스 vs 멀티 스레드)

스레드 (Thread) 개념 한 프로세스에서 실행되는 동작(기능 function)의 단위 하나의 프로세스 내부에 스레드가 한 개일 수도, 여러 개일 수도 있음. 이때 여러 개인 경우를 멀티 스레드(Multi Thread) 예) 유튜브라는 하나의 프로세스를 진행할 때 동영상 렌더링(스레드1), 댓글 조회(스레드2), 추천 동영상 탐색(스레드3) 등 각 스레드는 프로세스에 할당된 메모리 영역 중 코드, 데이터, 힙 영역을 공유 각 스레드는 스택 메모리 영역을 독립적으로 사용 독립적인 스택 메모리 필요 스레드는 하나의 실행 단위 → 함수를 호출함 함수를 호출하기 위해 인자 전달, return address 저장, 함수 내 지역 변수 저장 등을 위한 독립적인, 개별적인 공간 필요 독립적인 공간이 필요하다는 건 ..

[CS - 운영체제] 프로세스와 멀티 프로세스 (Process, Multi Process)

프로세스 (Process) 개념 일종의 명령어 리스트 또는 실행 파일인 프로그램이 하드 디스크에서 메모리로 적재되어, CPU에게 할당받아 실행(연산)되는 프로그램 흐름 우리가 코딩을 해서 프로그램을 작성 컴파일 하드디스크(HDD)에 프로그램 저장 RAM 메모리에 적재 CPU가 직접 접근해서 CPU에 할당 CPU가 프로그램을 한줄 한줄 읽으며 처리함 명령어 처리가 진행되면 프로그램은 프로세스가 되었음 메모리 메모리 : CPU가 직접 접근할 수 있는 컴퓨터 내부의 기억장치. 우리가 말하는 메모리는 RAM 메모리를 의미한다. 메모리에는 4가지 영역이 존재한다. 코드 : 프로그램의 코드를 저장하는 메모리 영역 데이터 : 프로그램의 전역 변수, static 변수를 저장하는 메모리 영역 힙 : 프로그래머가 직접 공..

[CS - 자료구조] 이진 탐색 트리 (BST, Binary Search Tree), Red-Black Tree

이진 탐색 트리 (Binary Search Tree) 배경 이진 트리에서 데이터를 효과적으로 찾는 방법을 고민함 데이터를 효과적으로 찾기 위해 데이터를 효과적으로 저장하는 것이 더욱 효율적이다는 아이디어를 고안해냄 개념 이진 트리 기반의 데이터 탐색을 위한 자료구조 (이진 트리 + 데이터 저장 규칙) 데이터 저장과 동시에 정렬을 하는 자료구조 이진 트리의 효율적인 탐색 능력을 가지며, 삽입과 삭제 가능 조건 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드 모든 노드에서 위의 조건을 충족 모든 노드는 유일한 키를 가짐 (노드 중복값 없음) operation 시간복잡도 (검색, 저장, 삭제 등) O(logn) worst case : 편향 트리 (skewed tree) → 한쪽으로만 노드가 추가되는 것 이..

[CS - 자료구조] 트리 (Tree), 이진 트리 (Binary Tree)

트리 (Tree) 개념 선형 구조인 큐, 스택과 달리, 비선형 구조로 계층적 관계(Hierarchiral Relationship)를 표현하며 데이터를 저장하는 자료구조 그래프의 한 종류이며, 사이클이 허용되지 않는 그래프 (자기 자신으로 돌아오지 않는) 용어 노드 (Node) : 트리를 구성하는 각각의 요소 간선 (Edge) : 노드를 연결하는 선 루트 노드 (Root Node) : 트리 구조에서 최상위에 있는 노드 단말 노드 (Leaf Node 또는 Terminal Node) : 하위에 다른 노드가 없는 노드 (맨 끝에 있는 노드) 내부 노드 or 비단말 노드 (Internal Node) : 단말 노드를 제외한 모든 노드 (루트 노드도 포함) 레벨 (Level) : 노드가 몇 층인지 나타냄 (루트 노드..

[CS - 자료구조] 그래프 (Graph)

그래프 (Graph) 개념 요소들이 서로 복잡하게 얽혀있는 연결 관계를 정점(vertex)과 간선(edge)으로 표현한 자료구조 스택, 큐처럼 CS의 대표적인 자료구조 중 하나 현실 세계의 많은 것들을 그래프로 나타낼 수 있어서 알고리즘 문제에 그래프 유형이 많음 cf) 트리 또한 그래프의 한 종류이며, 사이클이 허용되지 않는 그래프를 의미함 용어 정점 (Vertex, Node) 데이터가 저장되는 기본 원소 간선 (Edge, Link) 정점간의 관계를 나타내는 선 인접 정점 (Adjacent Vertex) 하나의 정점에서 간선으로 직접적으로 연결된 정점 차수 (degree) 각 정점에 연결되어 있는 간선의 수 진입 차수 (in-degree) : 방향 그래프에서 해당 정점으로 외부에서 오는 간선의 수 진출..

[CS - 자료구조] 해시 테이블 (Hash Table)

해시 테이블 (Hash Table) 배경 직접 주소화 테이블 (Directed Address Table) 의 단점을 보완하기 위해 직접 주소화 테이블 (Directed Address Table) key, value를 저장할 때 key값으로 k를 갖는 원소는 index k에 저장하는 방식 (key를 그대로 인덱스로 쓰는 테이블) key가 적절(배열의 인덱스로 쓰기 적절)하면 상관이 없음 ex) (2,”노정호”), (1,”배준석”), (4,”정재헌”) 만약 (학번, 이름)이나 (아이디, 닉네임) 등의 key, value를 저장하는 상황에 문제가 발생 (201622528, 박강욱) → 배열의 201622528 번째 공간에 value 저장 → 메모리 공간 낭비 발생 (syunxttm, 박강욱) → 배열의 syu..

[CS - 자료구조] 큐 vs 스택 (Queue vs Stack)

Queue 개념 시간 순서상 먼저 들어온 데이터가 먼저 추출되는 선입선출(FIFO, First In First Out) 방식으로 데이터를 저장하는 자료구조 선형 (Linear) 자료구조 Queue Overflow : Queue의 용량보다 데이터를 더 추가하려는 경우 발생 Queue Underflow : Queue가 비었음에도 데이터를 삭제하려는 경우 발생 단순 투 포인터로만 구현하게 되면, push/pop 연산 시 포인터가 증가만 하기 때문에 메모리 공간 낭비 발생 (계속 뒤쪽으로만 추가된다는 의미) 코드 struct Queue { // Property private var array: [Int] private var f: Int private var r: Int private var capacity: ..

[CS - 네트워크] HTTP와 HTTPS

HTTP와 HTTPS HTTP에는 3가지 문제점이 있다. 각각에 대한 보완점이 있는데, HTTPS는 이 3가지 문제점을 모두 보완할 수 있다. HTTP의 3가지 문제점이 어떤 것이며, HTTPS의 개념 및 구조와 어떻게 문제점들을 보완할 수 있는지 알아보자. HTTP의 3가지 문제점 첫번째로, HTTP는 TCP/IP 통신을 하고, 이는 평문 통신이라 도청 가능한 네크워크라는 점이다. TCP/IP 구조의 통신은 경로 상에서 엿볼 수 있고, 암호화가 되지 않았기 때문에 의미를 파악할 수 있다. 또한 패킷을 수집하는 것만으로도 도청 가능성이 있다. 때문에 암호화가 필요하다. 보완 방법으로는, 통신 자체를 암호화된 통신을 사용할 수 있다. SSL(Secure Socket Layer) 또는 TSL(Transpor..