Computer Science
-
[SQL] SQL OverviewComputer Science/데이터베이스 2021. 7. 9. 04:55
SQL Overview SQL(Structured Query Language)은 데이터베이스에서 데이터를 저장, 조작 및 조회하기 위한 standard language입니다. Oracle, MySQL, Postgres 등의 다양한 데이터베이스에서 표준으로서 사용됩니다. 본 포스팅은 자세히보다는 가볍게 SQL 용법들을 정리하려고 합니다. Demo DB 예시로 사용하는 DB는 Northwind 데이터베이스입니다. 해당 데이터베이스에는 여러 table이 존재하는데, 그중 Customers 데이터베이스는 다음 표와 같은 모습을 가집니다. 1. SQL basic SELECT SELECT 구문은 데이터 조회를 위해 사용합니다. Syntax SELECT column1, column2, ... FROM tabl..
-
[알고리즘] 투 포인터 (Two Pointers)Computer Science/자료구조 & 알고리즘 2021. 3. 8. 00:33
# 투 포인터 (Two Pointers) 알고리즘 투 포인터(Two Pointers) 알고리즘은 리스트에 순차적으로 접근해야 하는 경우에, 두 개의 점의 위치를 기록하면서 처리하는 방식을 말한다. 시작점과 끝점을 사용해 순차적으로 접근할 데이터의 범위를 표현할 수 있다. 투 포인터를 활용하면 유용한 다음 문제를 살펴보자. 위 문제는 전체 수열이 주어지면, 그 수열의 부분 수열 중 특정한 합을 가지는 연속하는 부분 수열을 찾는 문제이다. 이 문제를 해결하는 가장 심플한 방법은 완전탐색으로 각 인덱스마다 해당 인덱스로 시작하는 부분 연속 수열을 모두 찾아보는 방법이다. 다만, 이 완전탐색은 시간 복잡도가 O(N²)이 걸리므로 비효율적이다. 이 때, 투 포인터 알고리즘을 활용하면 선형 시간 복잡도 O(N)으로..
-
[OS] 9-2. Virtual MemoryComputer Science/운영체제 2021. 3. 4. 02:05
# Page replacement - 다양한 캐슁 환경 - 캐슁 기법 한정된 빠른 공간(=캐쉬)에 요청된 데이터를 저장해 두었다가 후속 요청시 캐쉬로부터 직접 서비스하는 방식이다. 즉, 한 번 썼던 데이터는 빠른 접근이 가능한 캐쉬 메모리에 저장해두었다가 가까운 시기에 해당 데이터에 대한 접근이 요청되면 빠르게 제공해준다. Paging system과 더불어 cache memory, buffer caching, Web caching 등 다양한 분야에서 사용되는 방식이다. - 캐슁 기법의 운영상 시간 제약 다만, 이러한 캐슁 기법은 운영상 시간 제약이 존재한다. 교체 알고리즘이 삭제할 항목을 결정하는 일에 지나치게 많은 시간을 소요하지 않아야 한다. 예를 들어, Buffer caching이나 Web cach..
-
[OS] 9-1. Virtual MemoryComputer Science/운영체제 2021. 3. 3. 19:26
※ 이번 챕터부터는 메모리 관리 기법 중 paging 기법을 사용하는 것을 가정한다. 실제로도 대부분의 시스템은 paging 기법을 채택하고 있다. # Demand Paging 실제로 특정 page에 대한 요청이 있을 때 해당 page를 메모리에 올리는 것을 말한다. 프로그램에는 안정적인 실행을 위해 방어적으로 넣은 자주 쓰이지 않는 코드 영역들이 매우 많이 존재한다. 그렇기에 실제로 쓰이는 코드들만 메모리에 올리면, I/O 양과 메모리 사용량을 크게 감소시킬 수 있고 더 많은 사용자들이 멀티 프로세싱할 수 있는 환경이 만들어진다. Demand Paging에서 페이지 테이블의 entry에 존재하는 valid/invalid bit의 역할을 살펴보자. Invalid는 주소 영역에서 사용되지 않는 부분이나 페..
-
[알고리즘] 소수 판별 알고리즘 - 에라토스테네스의 체Computer Science/자료구조 & 알고리즘 2021. 3. 3. 18:06
# 소수 (Prime Number) 판별 알고리즘 소수란 1보다 큰 자연수 중 1과 자기자신을 제외한 자연수로는 나누어떨어지지 않는 자연수를 말한다. 코딩 테스트에서는 어떠한 자연수가 소수인지 아닌지 판별해야 하는 문제가 자주 출제되므로 알고리즘을 기억해두면 좋다. 다음은 기본적인 소수 판별 알고리즘을 파이썬으로 구현한 것이다. # 소수 판별 함수 정의 (2이상의 자연수에 대하여) def is_prime_number(x): # 2부터 (x - 1)까지의 모든 수를 확인하며 for i in range(2, x): # x가 해당 수로 나누어떨어진다면 if x % i == 0: return False # 소수가 아님 return True # 소수임 print(is_prime_number(4)) print(is..
-
[OS] 8-2. Memory ManagementComputer Science/운영체제 2021. 2. 25. 18:29
# Allocation of Physical Memory 메모리는 일반적으로 Interrupt vector와 함께 낮은 주소 영역을 사용하는 OS 상주 영역과 높은 주소 영역을 사용하는 사용자 프로세스 영역 둘로 나뉜다. # 사용자 프로세스 영역의 할당 방법 1. Contiguous allocation (연속 할당) 각각의 프로세스가 메모리의 연속적인 공간에 적재되도록 하는 것이다. 연속 할당 방식은 두 가지가 존재한다. - 고정 분할 방식 프로그램이 들어갈 사용자 메모리 영역을 미리 파티션(partition)으로 나눠놓는 것을 말한다. 이 경우, 동시에 메모리에 load되는 프로그램의 수가 제한되고 최대 수행 가능 프로그램 크기도 제한된다. 위 그림을 예시로 보면 메모리 영역은 이미 고정되어 나뉘어져 ..
-
[OS] 8-1. Memory ManagementComputer Science/운영체제 2021. 2. 24. 18:17
# Symbolic Address VS Logical Address VS Physical Address 1. Symbolic Address - 프로그래머 입장에서 메모리를 다룰 때, 숫자가 아닌 변수명, 함수명 등으로 메모리를 조작하는 상징적 주소 - Symbolic Address가 compile되면 숫자로 된 Logical Address가 됨 2. Logical Address (=Virtual Address) - 프로세스마다 독립적으로 가지는 주소 공간 - 각 프로세스마다 0번지부터 시작 - CPU가 보는 주소 3. Physical Address - 실제 메모리에 올라가는 위치 - 프로그램이 실행될 때, Logical Address를 Physical Address로 주소 변환 (주소 바인딩) # 주소 ..
-
[알고리즘] 기타 그래프 이론 - 최소 신장 트리 (MST, Minimum Spanning Tree)Computer Science/자료구조 & 알고리즘 2021. 2. 20. 00:03
# 신장 트리(Spanning Tree)란? 신장 트리(Spanning Tree)란 원본 그래프의 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 뜻한다. 위의 가운데 그림처럼 간선들이 모든 노드를 잇고 있지만, 사이클은 생기지 않는 부분 그래프가 신장 트리의 예시가 된다. 반면, 오른쪽 그림처럼 모든 노드를 잇지도 않고 사이클마저 생기는 것은 신장 트리에 해당되지 않는다. 이 개념을 트리라고 부르는 이유는 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건이 트리의 조건에 해당하기 때문이다. 이러한 트리의 특성으로 인해, 신장 트리가 가지는 총 간선의 개수는 노드의 개수 - 1이 된다. # 최소 신장 트리(MST, Minimum Spanning Tree) 최소 신장 트리(..