CISC와 RISC ① CISC(Complex Instruction Set Computer) 1. 복잡한 명령어 집합을 가지고 있는 CPU 구조. 2. 명령어의 개수 증가에 따라 프로세서 내부 구조가 매우 복잡해지고, 고속으로 작동되는 프로세서를 만들기 힘듦. 3. 주로 메인프레임이나 펜티엄 시리즈와 같은 CISC CPU도 내부적으로 복잡한 명령어들을 단순한 명령어로 나누어 명령어 파이프라인에서 처리하기 때문에 실제 내부 작동 원리는 RISC와 같음. ex) 복잡한 명령어: 메모리 1의 내용 X 메모리 2의 내용 -> 메모리 3에 삽입 ② RISC(Reduced Instruction Set Computer) 1. CISC에서 실제 쓰이는 명령어가 몇개 되지 않는다는 사실을 바탕으로, 적은 수의 명령어만으..
페이징(Paging) ① 페이징(Paging) 1. 정의: 하나의 프로세스가 사용하는 메모리 공간이 연속적이어야 한다는 제약을 없애는 메모리 관리 방법. 2. 물리 메모리는 Page Frame(페이지 프레임), 논리 메모리는 Page(페이지) 단위로 나눌 수 있음. 3. 논리 메모리는 물리 메모리에 저장될 때, 연속되어 저장될 필요가 없고 물리 메모리의 남는 Page Frame에 적절히 배치됨으로 외부 단편화를 해결 가능함. 4. 외부 단편화를 해소하기 위해 프로세스가 사용하는 공간들을 한쪽으로 몰아 자유 공간을 확보하는 압축 작업보다 효율성이 높음. 5. 단점: 내부 단편화 문제 발생 가능성이 큼. ex) Page 크기가 1000 Byte, Process A의 메모리 요구 크기가 3010 Byte라 가..
스케줄링(Scheduling) 알고리즘 ① FCFS(First Come First Served) * 특징 1. 먼저 온 고객을 먼저 서비스해주는 선입 선처리(First Come, First Served) 방식, 작업 큐(Job Queue)에 먼저 삽입 된 순서대로 처리. 2. CPU burst가 완료될 때까지 CPU를 반환하지 않는다. 할당되었던 CPU가 반환될 때만 스케줄링이 이루어진다. 3. 비선점형(Non-Preemptive) 스케줄링 * 문제점 1. Convoy Effect(호위효과): burst 시간이 긴 하나의 프로세스가 CPU를 반환할 때까지 다른 모든 프로세스들이 기다리는 현상. 2. 소요 시간이 긴 프로세스가 먼저 도달하면 효율성을 낮추는 현상이 발생함. ※ CPU burst: 프로세스의..
스케줄링(Scheduling) ① 스케줄링이란? 1. 스케줄링은 프로세스가 생성되어 실행될 때 필요한 시스템의 여러자원을 해당 프로세스에게 할당하는 작업을 의미함. 2. 프로세스가 생성되어 완료될 때까지 프로세스는 여러 종류의 스케줄링 과정을 거치게 됨. 3. 스케줄링의 종류에는 장기 스케줄링, 중기 스케줄링, 단기 스케줄링이 있음. ※ 프로세스(Process): 일반적으로 CPU에서 처리되는 사용자 프로그램과 시스템 프로그램과 같이 실행중인 프로그램을 의미함. 작업 또는 태스크(Task)라고도 부름. ② 스케줄링의 종류 1) 장기 스케줄링 어떤 프로세스가 시스템의 자원을 차지할 수 있도록 할 것인가를 결정하여 준비상태 큐(Ready Queue)로 보내는 작업. 작업 스케줄링, 상위 스케줄링이라고도 하며..
시작하며삼성전자 SW 역량테스트 B형은 라이브러리를 사용할 수 없는 대신 Reference Code를 제공합니다. 제가 구현한 알고리즘들은 기본적으로 Reference Code를 바탕으로 하며 이해하는 과정에서 주석을 달며 정리했습니다. 구현 코드는 실제 시험에서 사용할 때는 달라질 수 있으며 각자에게 맞는 방식으로 구현하시는 것을 추천합니다. 이진 검색 알고리즘(Binary Search)① 이진 검색 알고리즘(Binary Search)는 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘입니다. 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식입니다. 처음 선택한 중간값보다 찾고자 하는 값이 크면 중간값은 새로운 최댓값이 되며, 작으면 중간값은..
연결 리스트(LinkedList) ① 연결 리스트(LinkedList)는 각 노드(Node)가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조입니다. 아래 소스코드에서 구현한 연결 리스트는 각 노드가 데이터를 가지고 이전 노드와 다음 노드의 주소 값 2개를 저장하는 이중 연결 리스트(Dobly LinkedList) 구조입니다. 여기서 노드는 Node라는 클래스로 선언되어 있고 데이터(data), 이전 노드(prev), 다음 노드(next)로 구성되어 있습니다. ② 아래 소스코드에서 연결 리스트와 관련된 함수들은 다음과 같습니다. addFirst(int data): 리스트의 맨 앞에 data를 추가하는 함수 addLast(int data): 리스트의 맨 뒤에 data를 ..
스택(Stack) ① 스택(Stack)는 가장 마지막에 들어간 데이터가 먼저 나오는 LIFO(Last In First Out) 구조를 가지고 있습니다. 아래 소스코드에서 1차원 배열로 스택을 구현하였고 스택 관련 함수들은 다음과 같습니다. stackIsEmpty(): 스택이 비어있는지 판단하는 함수 stackIsFull(): 스택에 더이상 들어갈 공간이 없는지 판단하는 함수 size(): 스택에 들어가있는 데이터의 개수를 return하는 함수 push(int value): 스택에 value값을 저장하는 함수 peek(): 스택에 가장 마지막에 들어간 데이터를 return하는 함수 pop(): 스택에 가장 마지막에 들어간 데이터를 return하고 삭제하는 함수 ② 아래 소스코드의 맨 아래 주석 부분을 보면..
시작하며 삼성전자 SW 역량테스트 B형은 라이브러리를 사용할 수 없는 대신 Reference Code를 제공합니다. 제가 구현한 자료구조들은 기본적으로 Reference Code를 바탕으로 하며 이해하는 과정에서 주석을 달며 정리했습니다. 구현 코드는 실제 시험에서 사용할 때는 달라질 수 있으며 각자에게 맞는 방식으로 구현하시는 것을 추천합니다. 큐(Queue) ① 큐(Queue)는 먼저 집어넣은 데이터가 먼저 나오는 FIFO(First In First Out) 구조를 가지고 있습니다. 아래 소스코드에서 1차원 배열로 큐를 구현하였고 큐 관련 함수들은 다음과 같습니다. queueIsEmpty(): 큐 안이 비어있는지 판단하는 함수 queueIsFull(): 1차원 배열의 최대 크기를 벗어나면 안 되기에 ..
문제 https://www.acmicpc.net/problem/17780 17780번: 새로운 게임 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하나의 말 위에 다른 말을 올릴 수 있다. 체스판의 각 칸은 흰색, 빨간색, 파란색 중 하나로 색칠되어있다. 게임은 체스판 위에 말 K개를 놓고 시작한다. 말은 1번부터 K번까지 번호가 매겨져 있고, 이동 방향도 미리 정해져 있다. 이동 방향은 위, 아래, 왼쪽, 오른쪽 www.acmicpc.net 문제 이해 백준의 17780번 새로운 게임 문제입니다. 체스판과 말에 대한 정보가 주어지고 하나의 칸에 4개의 말이 쌓이는 턴..
문제 https://www.acmicpc.net/problem/17837 17837번: 새로운 게임 2 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하나의 말 위에 다른 말을 올릴 수 있다. 체스판의 각 칸은 흰색, 빨간색, 파란색 중 하나로 색칠되어있다. 게임은 체스판 위에 말 K개를 놓고 시작한다. 말은 1번부터 K번까지 번호가 매겨져 있고, 이동 방향도 미리 정해져 있다. 이동 방향은 위, 아래, 왼쪽, 오른쪽 www.acmicpc.net 문제 이해 백준의 삼성 SW 역량 테스트 기출문제집에 있는 새로운 게임 2 문제입니다. 체스판과 말에 대한 정보가 주어지고..
- Total