Computer Science

1. Merge sort 분할 정복기법을 활용하여 정렬시키는 정렬 알고리즘이다. 재귀를 활용하여 큰 문제를 작은 문제로 쪼개서 풀이한 다음 return하면서 값을 합쳐서 도출해낸다. 정렬 로직 수행 간 초기 정렬상태를 보장하는 안정 정렬 방식이다 시간복잡도 : O(NlogN) // 공간복잡도 : O(N) Merge sort의 로직 동작 과정 1. 정렬할 배열의 처음과 끝 인덱스를 함수의 인자로 넘겨준다. 2. 처음과 끝 인덱스를 2로 나눈, 즉 mid = (left + right)/2. mid를 기준으로 재귀함수를 호출하여 범위가 1이 될 때 까지 나눠준다. 3. 정렬한 후 값을 복사해서 return 한다. mid를 기준으로 나눴을 때 왼쪽 부분의 범위 : left~mid mid를 기준으로 나눴을 때 오..

1-1. Bubble sort / 버블 정렬 인접한 두 원소를 비교해서 정렬이 잘못되어 있으면 서로 바꾸는 방식으로 정렬한다. 한번 큰 for문을 돌 때마다 탐색 범위 중에서 가장 큰 값을 가지는 원소가 뒤로 이동한다(오름차순 정렬일 경우) 돌 때마다 큰 숫자 하나는 무조건 정렬되기 때문에 (전체 원소의 갯수 - 큰 for문을 돈 횟수)만큼 돌아주면 된다. 시간복잡도 : O(N^2) 1-2. Code #include using namespace std; int n; vector arr; void Print() { for (int a : arr) { cout

1. CPU scheduling이란? CPU는 한번에 하나의 프로세스만을 수행할 수 있다. 여러개의 프로세스가 있어도 현재 CPU가 실행하고 있는 프로세스가 끝날때 까지 기다려야한다. 또한 I/O요청이 들어올 경우 CPU는 들어온 I/O요청이 끝날 때 까지 기다린 후 I/O가 끝나면 다시 실행된다. 즉, 다른 프로세스들을 실행하지 못하고 무한 대기하고 있기 때문에 대시 시간만큼 CPU를 낭비하는 것이다. 이를 해결하기 위해 멀티 프로그래밍 환경에서 CPU를 효율적으로 사용하기 위해 I/O요청이 오면 다른 프로세스한테 CPU를 양도하고 I/O가 끝나면 다시 Ready-queue에 들어가서 실행을 준비하고 실행하고 이런 CPU를 효율적으로 사용하기 위한 방법을 Scheduling이라고 한다. 2. CPU I..

1. Implicit Threading이란? 스레드를 개발자가 명시적으로 생성하거나 제어하지 않고 언어나 프레임워크에게 스레드의 생성과 관리 책임을 넘기는 것. 개발자는 따로 스레딩을 생성할 필요없이 병렬로 실행해야 할 프로그램을 걸러내어 함수형으로 실행만 시켜주면 된다. 2. Implicit Threading의 종류 2-1. Thread pool / 스레드 풀 프로세스 사용? 스레드 사용? 프로세스를 스케줄링 하는 것보다 스레드를 만들어 사용하는 게 자원 소비, 오버헤드 관점에서 훨씬 효율적인 방법이긴 하다. 이유는 프로세스 간 통신을 할 경우 shared-memory또는 Message passing같은 IPC방식을 사용해야 하기 때문에 오버헤드가 크고 context switch를 할 때 프로세스는 레..

오늘 백준에서 문제를 풀다가 vector정렬 시 내가 원하는 순서대로 커스텀해서 정렬하는 compare함수를 만들어서 사용하다가 Runtime Error를 만나서 구글링으로 알아낸 결과를 정리하려고 한다. 결론은 벡터를 정렬하기 위해 sort로 넘겨준 cmp 함수가 잘못돼서 발생한 문제였다. 1. C++ 공식 문서에서 알아보는 Sort C++ STL의 sort함수는 수학적으로 strict weak ordering 조건을 만족해야 한다. 1. cmp(a, a) == false 2. cmp(a, b) == true이면 cmp(b, a) == false. 두 비교체를 바꾸면 참/거짓 값도 변경되어야한다. 3. cmp(a, b) == true이고 cmp(b, c) == true이면 cmp(a, c) == tru..

1. 스레드란? 스레드의 정의는 프로세스 내부에서 실행되는 실행 흐름의 단위이다. 정의는 위와 같지만 어렵기 때문에 스레드는 한 프로세스 내부의 자원을 공유하면서 프로세스를 여러개로 쪼개서 실행시키는 것을 말한다. 프로세스끼리는 서로 자원 공유를 못하지만 스레드는 한 프로세스 내에 여러개가 존재하기 때문에 한 프로세스의 자원을 공유할 수 있다. 이처럼 한 프로세스 내에 여러개의 스레드가 존재하는 것을 멀티 스레드라고 한다. 싱글 스레드는 일반적인 프로세스 구조이기 때문에 이 포스팅에서는 멀티스레딩에 대해서 설명할 것이다. 2. 멀티 스레드(Multi Thread)란? 위에서 설명한 것과 같이 한 프로세스 내에서 여러개의 스레드가 존재하는 것을 멀티 스레드라고 한다. 스레드 입장에서 보면 프로세스는 스레드..

동기(Synchronous) & 비동기(Asynchronous) 동기와 비동기는 작업 순서에 관점을 둔다. 동기(Synchronous)는 작업 완료 여부에 따라 순차적으로 처리하는 것을 말한다. 프로세스 처리 순서가 A > B > A라고 했을 때 A가 완료된 후 B가 실행되고, B가 완료된 후 A가 순차적으로 처리된다.즉 작업의 순서가 보장되어야 한다. (동시성 - Concurrency) 비동기(Asynchronous)는 작업 완료 여부가 새로운 작업을 실행하는데 영향을 미치지 않는다. 프로세스가 A, B, C순서대로 시작한다고 해도 프로세스가 종료되는 순서는 A, B, C순서대로 종료된다는것을 보장하지 못한다. 즉 작업의 순서가 보장되지 않는다. (병렬성-Parallelism) 블로킹(Blocking)..

1. IPC 란? 프로세스는 스레드와 다르게 독립적으로 실행된다. 이처럼 독립적인 자원을 가진 프로세스끼리 통신에 사용되는 기법을 IPC 라고 한다. 2. 생산자-소비자 문제(Producer-Consumer Problem) 생산자란 말 그대로 정보를 생산하는 역할, 소비자란 정보를 소비하는 역할이다. 이렇게 들으면 이해가 잘 안가기 때문에 예시를 들어보자면 1. 생산자 : compiler > 어셈블리 코드 생성 // 소비자 : assembler > 어셈블리 코드를 소비하여 기계어 변환 2. 생산자 : 웹 서버 > request시에 웹 페이지 HTML코드 생성 // 소비자 : 브라우저 > HTML코드를 소비해서 화면에 랜더링 함. 이정도가 대표적인 생산자-소비자에 대한 예시가 될 것 같다. 그래서 다시 생..

1. 이중 연결 리스트란? 이중 연결 리스트란 단일 연결리스트와 다르게 양방향으로 노드가 이어진 리스트이다. 이중 연결 리스트는 이전 노드와 이후 노드가 이어져 있기 때문에 삽입 삭제 연산 시 이전, 이후 노드를 저장하지 않아도 되기 때문에 훨씬 유연하게 사용할 수 있다. 2. 이중 연결 리스트 구현 이번 이중 연결 리스트 구현은 Head와 Tail에 data가 들어있지 않은 더미(dummy)노드를 사용해서 구현했다. 2-1. 구조체 및 클래스 선언부 이중 연결 리스트는 노드 두개가 서로 연결 되어있기 때문에 이전 노드와 다음 노드를 포인팅하는 prev, next 구조체 포인터를 선언해줬다. struct Node { Node* prev; Node* next; int data; }; class Doubly..

프로세스가 운영체제로부터 메모리를 할당받게 되면 위와 같은 구조로 생성된다. 각 계층별 데이터를 주소가 낮은 순서대로 코드와 함께 보면서 살펴보자 Text section(.code) - 코스 코드를 실행 가능한 기계어 코드로 변환되어 저장돼 있는 영역. 함수나 명령문이 기계어로 변환되어 저장된다. - CPU는 이 부분에 있는 명령들을 하나씩 가져가서 처리한다. - 흔히 코드영역(Code Segment)라고도 한다. Data section 데이터 섹션은 전역변수와 정적변수(static)가 할당되는 공간이다. 또한 Data section은 초기화 된 변수(.data)와 초기화 되지 않은 변수(.bss) 영역으로 나뉜다. 초기화된 변수는 다시 상수를 보관하는 rodata부분과 초기화 된 전역변수를 저장하는 ...