Computer Science

1. 프로세스란? 실행중인 프로그램을 프로세스라고 한다. OS에서의 프로세스란 작업의 단위를 의미한다. 컴퓨터 구조상으로 보면 CPU는 Main Memory에 있는 프로세스만 fetch할 수 있기 때문에 프로그램을 실행하기 위해서는 먼저 Storage(HDD, SSD)에 저장되어 있는 프로그램을 Main memory로 가져와야한다. Fetch하기 전 Main memory에 담긴 프로그램의 실행 정보들을 프로세스라고 한다. 이때 OS는 프로세스를 관리하는 일을 한다 컴퓨터에서 연속적으로 실행되고 있는 컴퓨터 프로그램을 말한다. 스케줄링의 대상이 되는 작업이라는 용어와 거의 같은 의미로 쓰인다. Wikipedia 1-1. 프로그램? 프로세스? 프로그램이란 - 컴퓨터에서 어떤 작업을 위해 실행할 수 있는 정적..

1. 단일 연결 리스트란? 각 요소들이 데이터부분과 다음 값 주소를 포인팅하는 노드라는 형태로 이루어져 있으며 체인 형태로 선형으로 이루어진 자료구조이다. 값을 추가할 때 배열은 정해진 사이즈를 넘으면 Overflow가 발생하지만 Linked List는 동적으로 할당해서 노드들을 이어주면 되기 때문에 메모리 사이즈 문제에서 벗어날 수 있다. 하지만 노드들이 서로 체인형태로 이어져 있어 배열처럼 인덱스 개념으로 접근이 불가하기 때문에 순회하여 값을 찾아야 하으로 탐색에 있어서는 배열보다 느리다. 하지만 값을 중간에 넣는 경우 배열은 중간에 값을 삽입하고 한칸씩 뒤로 미뤄줘야 하기 때문에 원소의 갯수에 따라 시간이 차이가 나는 방면, 연결 리스트의 경우 단지 노드의 포인팅만 바꿔주면 되기 때문에 최악의 경우..

1. Queue란? 선입 선출(First In First Out) 즉 먼저 들어간 데이터가 제일 먼저 나오는 성질을 가지는 자료구조이다. 우리의 실생활에서 가장 많이 볼 수 있다. ex) 대기열, 프린터 큐 시간 복잡도 : O(1) 2. Queue 구현 구현해본 기능은 1. Push : 원소를 큐에 넣음 2. Pop : 큐에 가장 먼저 들어간 원소를 제거 3. Front : 큐에 가장 먼저 들어간 원소를 출력 4. Size : 큐에 들어가있는 원소의 갯수를 출력 5. IsEmpty : 큐가 비었는지 확인 6. IsFull : 큐가 다 찼는지 확인 나는 처음에 사용자한테 queue의 사이즈를 입력받아서 구현했고, 원형 큐 형태로 구현했기 때문에 실제로 사용자가 입력한 큐의 사이즈보다 -1만큼 적게 사용한다..

1. Stack이란? 후입선출(Last In First Out) 즉 나중에 들어간 데이터가 제일 먼저 나오는 성질을 가지는 자료구조이다. 시간복잡도 : O(1) 2. Stack구현 Push(int value) : value를 스택의 최상단에 삽입 Pop() : 최상단의 원소를 스택에서 제거. 만약 스택이 비었다면 프로그램 종료 Top() : 스택의 최상위 원소를 반환. 만약 스택이 미었다면 프로그램 종료 Size() : 스택의 원소의 갯수를 반환. isEmpty() : 스택이 비어있는지 여부를 반환. #include #include using namespace std; class Stack{ private: int *arr; int top; int capacity; public: Stack(int siz..

목차 - Internet이란? - 데이터 교환 방식 - Internet Protocol 1. Internet 인터넷은 인터넷 프로토콜 스위트를 기반으로 연결되어 있는 컴퓨터 네트워크 통신망을 말한다. 인터넷 프로토콜 스위트(Internet Protocol Suite)란 인터넷에서 컴퓨터들이 정보를 주고받는 데 쓰는 Protocol의 모음들이다. IP는 Internet Protocol의 이니셜이다. Inter + network는 여러 통신망을 하나로 연결한다는 의미 + Protocol은 규약, 약속이라는 뜻을 가지고 있다. 즉 Internet Protocol은 여러 통신망이 인터넷 환경에서 통신하기 위한 약속을 의미한다. 2. 데이터 교환 방식 1. 회선 교환 방식 회선 교환 방식은 특정 통신 경로를 설정..

1. Interrupt란? Interrupt의 사전적 정의 : 방해하다, 중단시키다 사전적 정의 그대로 CPU가 일을 수행하는 도중 하드웨어 장치 등에서 발생한 입출력과 같은 예기치 못한 상황을 CPU에게 알려 먼저 예외상황을 처리하도록 하는 것. 2. Interrupt 사용이유 한번에 한가지 일을 수행할 수 있는 CPU를 잠시 중단시키고 급한 Interrupt를 먼저 처리한 후 이전에 수행하던 일을 다시 수행하여 CPU의 효율을 높이기 위해 사용한다. 입출력 연산의 속도는 CPU의 명령 수행 속도보다 현저히 느리다. 하지만 한번에 한가지 일밖에 수행할 수 없는 CPU를 입출력 연산이 끝날 때까지 기다리며 놀게하면(월급루팡) 효율이 떨어지니 연산 결과가 나오기 전에는 CPU가 할 일을 하다가 Interr..

1. 유니온 파인드 알고리즘이란? 대표적인 그래프 알고리즘으로 두개의 노드가 같은 집합에 속하는지 판별하는 알고리즘 서로소 집합 또는 상호배타적 집합(Disjoint-Set) 알고리즘이라고도 불린다 노드를 합치는 Union연산과 루트 노드를 찾는 Find연산으로 이루어져있다. 시간복잡도는 트리의 높이만큼 탐색하는 O(logN)을 가지게 된다. Union을 해주는 과정에서 한쪽으로만 노드들이 달리는 사향트리의 형태를 띄게 되면 O(n)이 되어버린다. 2. Default Logic 현재 7개의 서로 관련이 없는 노드가 존재하고 우리는 1, 2 / 4, 5 / 5, 6 노드를 서로 연결하려고 한다. 현재는 아무런 연관이 없기 때문에 각 노드들에 대한 root node는 자기 자신이다. 1번 노드와 2번 노드를..

1. 이분탐색이란? 이분 탐색 알고리즘은 정렬되어 있는 배열에서 탐색 범위를 절반씩 줄여가며 데이터를 탐색하는 알고리즘이다. 이분탐색은 결정 문제의 답이 이분적일 때 사용할 수 있는데 대표적인 예시로 카드 뽑기 문제가 있다. 결정 문제란 답이 Yes or No인 문제를 의미한다. 시간 복잡도 : O(logN) 카드 뽑기 문제는 1 ~ 50까지 오름차순으로 정렬된 카드묶음에서 28번 카드를 찾는 문제를 예시로 들어보겠다. 첫번째 카드부터 n번째 카드는 card[i], 우리가 찾고자 하는 카드인 28은 val로 가정한다. 이때 문제를 푸는 방법에 v[i] >= val 인가를 잡으면 답은 1~27까지는 False, 28이후로는 True가 나오게된다. 이때 우리가 찾고자 하는 값은 처음으로 card[i] >= ..

1. 위상정렬이란? 순환하지 않고 방향이 정해져있는 그래프의 노드를 거스르지 않은 상태로 정렬하는 방법. 비순환 유향 그래프에서만 사용할 수 있으며 순환이 있거나 양방향 그래프에 대해서는 사용하지 못한다. 모든 간선 (u, v)에 대해 정점 u가 정점 v보다 먼저오는 순서로 정렬이 된다. 시간 복잡도 : O(V+E) {Vertex : 노드의 갯수 / Edge : 간선의 갯수} 2. Default Logic 위상정렬을 하는 방법에는 BFS를 사용하는 방법과 DFS를 사용하는 방법이 있는데 나는 BFS로 설명할 것이다. 먼저 BFS를 사용한 방법을 말로 설명해 보자면 1. 모든 정점의 inDegree를 설정해준다. (inDegree : 정점으로 들어오는 간선 수) 2. 한 간선을 처리한 후 inDegree를..

1. 다익스트라(Dijkstra) 란? 다익스트라 알고리즘이란 하나의 그래프에서의 최단 경로 탐색 알고리즘이며, 우리가 흔히 알고있는 동적계획법 즉 다이나믹 프로그래밍을 활용한 최단경로 탐색 알고리즘이다. 한 정점에서 모든 정점까지의 최단거리를 구할 때 사용하며, 주어진 그래프중에서 음의 가중치가 없는 그래프에서 사용 가능하다. 음의 가중치가 있을 경우 벨만-포드 알고리즘을 사용하여 해결할 수 있다. 2. Default Logic 다익스트라 알고리즘 동작 반복 과정 1. 방문하지 않은 정점 중 가장 가중치 값이 작은 정점을 방문한다. 2. 현재 위치한 정점을 거쳐 다른 노드로 넘어가는 가중치 값을 계산하여 최소 비용을 갱신한다. 3. 위의 과정을 목표한 노드에 도달 할 때까지 반복한다. 이해를 돕기 위해..