분류 전체보기

스택이란? 스택은 컴퓨터에서 아주 많이 사용되는 자료구조이다. 휴대폰의 뒤로 가기 기능은 스택을 사용하여 현재 실행되는 앱을 종료하고 이전에 실행되던 앱을 실행한다. 스택(Stack)은 쌓아놓은 더미를 뜻한다. 스택의 가장 큰 특징은 후입선출(LIFO)이다. 가장 가중에 들어온 것이 가장 먼저 나온다. 입력과 출력이 한 방향으로 제한된다는 특징이 있다. 스택의 구조 스택은 자료의 출력 순서가 입력 순서의 역순으로 이루어질 때 사용되는 자료구조이다. 스택 상단(Stack Top) : 스택에서 입출력이 이루어지는 부분 스택 하단(Stack Bottom) : 스택의 바닥 부분 요소(Element) : 스택 자료구조에 저장된 데이터 시스템 스택 함수호출 시스템 스택(System Stack) 운영체제가 사용하는 ..

연결리스트란? 연속된 메모리 위치에 저장되지 않는 선형 데이터 구조 포인터를 사용해서 연결된다. Linked List는 컴퓨터 과학에서 사용하는 기본적인 선형 자료 구조 중 하나 각 노드는 데이터 필드와 다음 노드에 대한 참조를 포함하는 노드로 구성 Linked List는 데이터의 동적 추가, 삭제를 상대적으로 쉽게 할 수 있는 장점이 있다. Linked List의 핵심 요소는 다음과 같다. 노드(Node) : Linked List의 기본 단위, 데이터를 저장하는 필드와 다음 노드를 가리키는 링크 필드로 구성 포인터 : 각 노드 안에서 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간 헤드(Head) : Linked List에서 가장 처음 위치하는 노드. 리스트 전체를 참조하는데 사용 테일(Tail..

Array? 배열은 연속된 메모리 공간에 순차적으로 저장된 데이터 모음이다. 대부분 프로그래밍 언어에서는 동일 타입 데이터를 저장한다. 예를들어 int 타입의 배열에서는 정수 요소만 저장할 수 있다. 배열을 구성하는 각각의 값을 요소(element)라고 한다. 배열에서의 위치를 나타내는 숫자를 인덱스(index)라고 한다. 배열 표현 C언어에서 배열 선언 시 아래와 같다. 위 배열을 그림으로 표현 시 다음과 같다. 그림에서 알 수 있는 사실은 다음과 같다. 연속된 메모리 공간에 데이터가 순차적으로 저장된다. C언어에서 인덱스는 0부터 시작한다. 배열의 크기는 10이므로 10개의 요소를 저장할 수 있다. 각 요소는 인덱스를 통해 엑세스 할 수 있다. 배열의 시간 복잡도 Operation Average Ca..

패리티 비트 정보 전달 과정에서 오류가 생겼는지 검사하기 위해 추가하는 비트를 말한다. 전송하고자 하는 데이터의 각 문자에 1bit를 더하여 전송한다. 패리티 비트를 포함한 데이터에서 1의 개수가 짝수인지 홀수인지에 따라 짝수 패리티, 홀수 패리티라고 한다. 위 그림 처럼 8bit의 데이터를 전송할 때 맨 끝에 패리티 비트를 추가하여 전송한다 짝수 패리티의 경우 100101010 홀수 패리티의 경우 100101011 패리티 비트를 추가하는 위치는 맨 앞이 될 수도 있고, 맨 끝이 될 수 있다. 패리티 비트를 정하여 데이터를 전송하면 데이터를 받는 쪽에서는 수신된 데이터의 전체 비트를 계산하여 패리티 비트를 다시 계산하는 것으로 오류가 발생하였는지 확인할 수 있다. 그러나 패리티 비트로는 오류가 발생하였다..

캐시 메모리란? 속도가 빠른 장치와 느린 장치에서 속도 차이에 따른 병목 현상을 줄이기 위한 메모리 CPU가 주기억장치에서 저장된 데이터를 읽어올 때, 자주 사용하는 데이터를 캐시 메모리에 저장한 뒤, 다음에 이용할 때 주기억장치가 아닌 캐시 메모리에서 먼저 가져오면서 속도를 향상시킨다. 속도라는 장점을 얻지만, 용량이 적기도 하고 비용이 비싼 점이 있다. CPU에는 이러한 캐시 메모리가 2~3개 정도 사용된다. L1, L2, L3 캐시 메모리라고 부른다 속도와 크기에 따라 분류한 것으로, 일반적으로 L1 캐시부터 먼저 사용된다 CPU에서 가장 빠르게 접근하고, 여기서 데이터를 찾지 못하면 L2로 감 듀얼 코어 프로세서에서의 캐시 메모리 각 코어마다 독립된 L1 캐시 메모리를 가지고, 두 코어가 공유하는..

CPU CPU는 인간의 두뇌에 해당하는 컴퓨터에서 가장 핵심적인 부분이다. 크게 연산장치, 제어장치, 레지스터 3가지로 구성된다. 연산장치(ALU) 산술 연산과 논리 연산을 수행 산술논리연산장치라고도 불림 연산에 필요한 데이터를 레지스터에서 가져오고, 연산결과를 다시 레지스터로 보냄 덧샘, 뺄샘 등의 산술연산과 배타적 논리합, 논리합, 논리곱 등의 논리연산을 계산하는 디지털 회로 제어장치 명령어를 순서대로 실행할 수 있도록 하는 제어장치 주기억장치에서 프로그램 명령어를 꺼내 해독하고, 그 결과에 따라 명령어 실행에 필요한 제어 신호를 기억장치, 연산장치, 입출력장치로 보냄 프로그램 수행 순서를 제어하는 프로그램 계수기, 수행중인 명령어를 저장하는 명령 레지스터, 명령을 해독해 제어신호를 보내는 명령 해독..

컴퓨터의 구성 요소 컴퓨터 시스템은 크게 하드웨어와 소프트웨어로 나누어진다. 하드웨어 : 컴퓨터를 구성하는 기계장치 (물리적 장치) 소프트웨어 : 하드웨어의 동작을 지시하고 제어하는 명령어 집합 하드웨어와 소프트웨어가 함께 상호작용을 하며 원하는 일을 수행하게 된다. 컴퓨터는 기본적으로 읽고 처리한 뒤 저장하는 과정으로 이루어진다 READ → PROCESS → WRITE 이 과정을 진행하면서 끊임없이 주기억장치(RAM)과 소통한다 이때 운영체제가 64bit라면, CPU는 RAM으로부터 데이터를 한번에 64비트씩 읽어온다. 하드웨어 메인 보드(Main Board) 마더 보드(Mather Board)라고도 불리며 주회로가 내장된 보드 CPU나 RAM과 같이 시스템이 작동하기 위한 주요 부품 장착과 주변 장치..

https://www.acmicpc.net/problem/8980 8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이 www.acmicpc.net 이 문제는 그리디 알고리즘을 사용해서 해결할 수 있다. 문제에서 각 박스의 정보가 입력으로 들어온다. 박스의 정보는 보내는 마을 번호, 받는 마을 번호, 박스의 개수가 있다. 입력으로 받기 위해 pair 자료형을 사용했다. 또한, 박스 정보를 도착 마을 순서로 정렬하여 탐색 시 가장 작은 도착 마을부터 할 수 있도록 하였다. 그 이유는 보내는 마을과 받는 마을이 가까울수록 많이..