본문 바로가기

취업과 기본기 튼튼/빽 투더 기본기

(38)
빽 투더 기본기 [OS 2편]. 쓰레드 이 글에서는 Threaad(쓰레드)에 대해 정리해본다. 1. Thread 란 1.1. Process vs Thread Process : 메모리에 올려져있는 실행중인 프로그램. 프로세스간 메모리 영역은 독립적이다. (stack, heap, data, text) 각 프로세스는 별도의 메모리에 할당되며, IPC 통신이 아니면 서로 접근할 수 없다. Thread : 프로세스 내에서 실행되는 흐름의 단위 프로세스 내에 쓰레드 단위로 stack 만 할당받고, heap, data, text 영역은 공유한다. 즉 쓰레드 간에는 데이터 힙 공간을 통해 IPC 를 거치지 않아도 자원 접근, 수정이 가능하다. 쓰레드는 프로세스 내부의 좀 더 경량화된 프로세스이다. 1.2. 왜 쓰는가? (Multi process vs Mul..
빽 투더 기본기 [OS 1편]. 프로세스 이 글에서는 운영체제의 기초가 되는, Process (프로세스)에 대해 정리해본다. 1. Process 란 1.1. Program vs Process Program : 디스크에 저장된 실행가능한 명령어 파일. 수동적인 개체. Process : 메모리에 올려져있는 실행중인 프로그램. 적극적인 개체. 프로그램이 실행되면 (메모리에 로드되면) 프로세스가 된다. 1.2. Process in Memeory 프로세스는 메모리에서 다음과 같은 독립적인 공간을 할당받는다. Stack : 임시 데이터들을 담는다. ex. 리턴 어드레스, 지역 변수 Heap : 동적 할당 데이터들을 담는다. ex. malloc() Data : 전역 변수를 담는다. Text : 모든 코드를 담는다. 1.3. Process State 프로세스..
빽 투더 기본기 [DB 1편]. 데이터 베이스 기초 핵심 다음 3가지가 가장 핵심 기초라고 생각되어 정리해본다. 기본 개념과 용어 트랜잭션 테이블 설계와 정규화 1. 기본 개념 단어 1.1. 용어 관계형 데이터 모델 릴레이션, 속성(필드, 컬럼), 튜플(레코드, 행) 도메인 각 필드가 가질 수 있는 모든 값들의 집합 원자값(atomic value, 더 이상 분리되지 않는 값)이어야 함 스키마 테이블 정의에 따라 만들어진 데이터 구조 차수 테이블 스키마에 정의된 필드의 수 테이블 인스턴스 테이블 스키마에 현실 세계의 데이터를 레코드로 저장한 형태 기수(cardinality) 테이블 인스턴스의 레코드의 수 2. 트랜잭션 2.1. 정의 데이터베이스의 상태를 변화시키기 위해 수행하는 작업의 단위 '하나의 작업' 에는 하나의 목표를 위해 여러 테스크가 포함된다. 예를 ..
빽 투더 기본기 [알고&자구 7편]. 프림 알고리즘 그래프에서 최소 신장 트리를 만드는 알고리즘 중, 크루스칼과 더불어 유명한 프림(Prim) 알고리즘을 잠깐 정리해볼까 한다. 글 대부분의 내용은 프로그래밍 자료 저장소님의 블로그와 Michael Sambol의 유튜브를 참고하였다. 그래프에서 최소 신장 트리 만들기 프림 알고리즘은, 크루스칼 알고리즘 같이 어떤 그래프가 주어져있을 때, 이 그래프에서 최소 신장 트리 (Minimum Spanning Tree) 를 만드는 알고리즘이다. 최소 신장 트리에 대한 이야기는 이전 글인 크루스칼 알고리즘에 보면 나와있다. 프림 알고리즘을 위해서는, 역시 먼저 그래프가 주어져야 한다. 그리고 이 그래프에서, 우리는 정점과 인접 행렬에 대한 정보가 주어져야 한다. 프림(Prim) 알고리즘 알고리즘 알고리즘을 간단하게 정리..
빽 투더 기본기 [알고&자구 6편]. 크루스칼 알고리즘 그래프에서 최소 신장 트리를 만드는 알고리즘 중, 가장 유명한 크루스칼(Kruskal) 알고리즘을 잠깐 정리해볼까 한다. 글 대부분의 내용은 heejeong Kwon님의 블로그 와 나동빈님의 유튜브를 참고하였다. 그래프에서 최소 신장 트리 만들기 크루스칼 알고리즘은, 어떤 그래프가 주어져있을 때, 이 그래프에서 최소 신장 트리 (Minimum Spanning Tree) 를 만드는 알고리즘이다. 최소 신장 트리란, 어떤 그래프에서 각 정점간 간선을 1개씩만 선택하여, 결과적으로 모든 정점을 잇는 하나의 그래프(트리) 를 말한다. 정점이 n개 있다고 할 때, 간선은 n-1개가 된다. 그럼 이걸 왜하느냐? 대표적인 예로, 여러 도시가 있고, 각 도시간 도로를 깔 수 있는 경로와 비용이 이미 파악되어있다고 하자..
빽 투더 기본기 [알고&자구 5편]. 다익스트라 알고리즘 그래프에서 경로찾는 알고리즘 중, 가장 유명한 다익스트라(Dijkstra) 알고리즘을 잠깐 정리해볼까 한다. 글 대부분의 내용은 Chancethecoder님 블로그 와 허민석님 유튜브를 참고하였다. 한 점에서 다른 정점으로 가는 최단 경로 찾기 위 제목이, 다익스트라 알고리즘이 하는 일이다. 방향 혹은 무방향 그래프에서, 어떤 한 점에서, 다른 모든 점으로 가는 최단 경로와 거리(weight) 을 O(|V||E|) 만에 찾아서 반환한다. 이 때, 거리(weight) 는 모두 양수여야 알고리즘이 제대로 작동한다. 또, 정점(vertex)과, 인접 행렬(adjacent)이 입력으로 주어져야 한다. 알고리즘 알고리즘을 간단하게 정리하면 다음과 같다. 1. 시작점에서 모든 정점까지의 거리를 담는 배열 (dist..
빽 투더 기본기 [알고&자구 4편]. 해시 테이블 기본적인 자료구조들 중, 트리에 이어 또 하나 자세히 살펴볼만한 자료구조가 바로 해시 테이블이다. Ratsgo's blog 님의 정리된 내용을 가지고 간단히 요약해보려고 한다. 정의 key, value 형태로 자료를 저장하는 구조를 해시 테이블이라고 한다. 이 때, 테이블에서 인덱스 역할인 key를 만드는 함수를 해시 함수라고 하고, 본래 값에서 해시 함수를 먹여 해시 값(키)를 만드는 과정을 해싱이라고 한다. 특징 삽입, 삭제, 탐색에서 해시 충돌이 발생하지 않는다면, 시간복잡도 O(1) 을 보인다. 아래 다른 자료구조들과 비교해보았을 때, 매우 극적인 성능을 보이는 자료구조다. 자료구조 삽입 삭제 탐색 배열 O(n) O(n) O(1) 리스트 O(1) O(1) O(n) 트리 O(1) O(1) O(log..
빽 투더 기본기 [알고&자구 3편]. 균형 트리 트리의 구조 특성상 탐색의 시간 복잡도가 '대체로' O(log n) 만에 가능하다. 따라서, 파일 시스템 등, 자료를 저장하거나 관리하는 시스템에서 많이 사용되곤 한다. 아무튼 트리를 사용한다는 것의 핵심은, 빠르게 접근 하기 위함이고, 이를 위해 '그냥 트리' 에서 여러 형태로 변모된다. 2편에서, 트리와 바이너리 서치 트리를 살펴보았다. 하지만 '지금까지의 트리'의 문제점은, 트리가 한 쪽으로 치우쳐져 있는 경우, 탐색의 시간 복잡도가 O(n) 이 된다는 것이다. 따라서, 치우쳐지지 않게, 즉 균형있게 트리를 만드는 것이 트리 구성에 핵심 이슈가 된다. 균형있는 트리. 이를 Balnaced Tree 라고 하며, 기존 트리에서 더 발전된 (균형을 잡아주는) 트리 종류는 다음과 같다. AVL Tree B..