컴퓨터공학기초 및 이론(21)
-
컴퓨터 구조 분야의 8가지 아이디어
1. 무어의 법칙을 고려한 설계 2. 설계를 단순화 하는 추상화 - 설계시간을 줄이고 생산성을 높이기 위하여 추상화 개념을 사용 - 하위 수준의 상세한 사항을 안보이게 함으로써 상위 수준 모델을 단순화 ex) 고급언어(c,java,python)가 추상화의 대표적인 예 3. Common case fast - 자주 발생하는 일을 빠르게 처리하여 성능 향상 도모 - 자주 일어나는 일에 대한 최적화 및 단순화 - 무엇이 커먼케이스인가? - 세심한 실험과 측정 필요 4. 병렬성을 통한 성능개선 - 같은 작업(큰 문제)를 여러 개의 작은 문제로 나누어서 해결하는 방법 - 병렬처리의 예 : 쓰레드 5. 파이프라이닝을 통한 성능개선 - 파이프라이닝은 병렬성의 특별한 형태 - 처음단계 출력이 다음단계 입력으로 이어지는 ..
2019.10.27 -
정지문제
정지문제란 "프로그램과 초기 입력값이 주어졌을 때, 이 프로그램에 입력값을 넣고 실행한다면 이 프로그램이 계산을 끝내고 멈출지 아니면 영원히 계속 계산할지 판정하라" 라는 엘런 튜링이 제시한 문제로 유명하다. 이런 문제를 고안한 이유는 기계적인 방식으로 모든 수학적인 증명이 가능한지를 묻는 결정문제로부터 출발한다. 결정문제를 실제 기계로 구현하기 위해 튜링머신이라는 것을 고안했는데, 튜링 머신은 1. 테이프에 기록될 수 있는 기호 및 튜링 머신의 상태와 행동표의 개수는 모두 유한해야 하며 서로 구분되어야 한다. 2. 현재 상태가 1인데 기호 A를 읽었다면 C를 기록하고 정지 3. 현재 상태가 1인데 기호 B를 읽었다면 오른쪽으로 한 칸 이동하고 상태 2로 변경 4. 현재 상태가 2인데 기호 C를 읽었다면..
2019.10.27 -
스택(stack)
스택은 데이터를 일시적으로 저장하기 위해 사용하는 자료구조이다. 데이터는 후입선출로 이뤄진다는 점이 큐와의 차이점이라고 할 수 있다. 따라서 큐에서의 프론트/리어와 다르게 스택은 탑과 바텀으로 표현하는데, 이것은 후입선출 특징상 꼭대기(탑)에 가까운 데이터만 나가고 들어오기 때문이다. 흔히 '스택을 쌓는다'라는 말이 있는데, 쌓는다는 표현이 바로 정확하게 표현한다고 볼 수 있다. 바닥부터 쌓아올리는 형식을 생각하면, 자료를 넣을때도 뺄 때도 후입선출을 할 수 밖에 없기 때문이다. 스택에서 데이터를 넣는 작업을 푸시(push)라 하고, 데이터를 꺼내는 작업을 pop 이라고 한다. Java에서는 메서드를 호출하고 실행하는 것을 스택방식으로 처리한다. 스택 역시 데이터의 집합이기 때문에 배열로 구현할 수 있다..
2019.05.27 -
큐(queue)와 링 버퍼(ring buffer) 연결 리스트 (Linked list)
큐 형태의 자료구조는 데이터를 쌓아두는 자료구조로, 선입선출(FIFO)인 점이 특징이다. 주로 일시적인 자료의 저장에 많이 사용된다. 큐의 경우 가장 먼저 들어간 데이터를 먼저 꺼내고, 나중에 들어간 데이터를 나중에 꺼내게 되는데 이를 배열로 만들게 될 경우 하나의 데이터를 꺼낼 때 마다 모든 데이터의 위치를 이동해야하는 문제가 있다. 따라서 보통 큐를 만들 때는 Linked list를 이용하거나, ring buffer 형태를 많이 사용한다. 큐에 데이터를 넣는 작업은 인큐(enqueue), 꺼내는 작업은 디큐(dequeue)라고 한다. 데이터를 꺼내는 쪽은 프론트(front)라고 하고 데이터를 넣는 쪽을 (rear)라고 한다. 배열로 큐를 생성할 경우, 인큐의 복잡도는 O(1)이 되지만 디큐의 복잡도는..
2019.05.27 -
복잡도와 점근표기법(빅오표기법)
본래 점근표기법은 수학적 개념으로, 임의의 함수에 대하여 정의역의 원소가 커짐에 따라 그 원소의 상이 얼마나 빠르게 커지는지를 표현하는 것이다. 그러나 컴퓨터의 경우, 1의 연산과 100, 1000의 연산에 거의 차이가 없다. 이 말은, 컴퓨터가 연산하는 과정을 1의 단위까지 세세하게 고려하더라도 명확한 성능 차이를 드러내지는 않는다는 것이며, 따라서 프로그래밍 과정에서 점근표기법을 통해 프로그램 알고리즘의 복잡도을 표현하는 것은 근사값에 대한 정의를 나타내는 것이다. 즉, 프로그램에 있어서 점근표기법이란, 한 프로그램이 실행되는 과정에 소요되는 시간(단계)를 나타내며, 그 과정에서 계수와 상수를 제거한다. 이는 컴퓨터의 연산속도가 사람과 다르기 때문에 계수와 상수로 이뤄지는 횟수의 차가 실제 차이만큼 ..
2019.05.21 -
이진 탐색 (binary-search)
오름차순, 혹은 내림차순으로 이미 정렬이 되어있는 배열에서 특정한 값을 찾아내는 것. 방식은 배열 중간의 임의의 값을 선택하여 찾고자 하는 키 값과 비교하는 것을 반복하는 방식으로 진행되며, 크기가 작고 큰지에 대해 이후 탐색해야할 배열의 영역을 정해 다시 탐색한다. 해당 값을 찾을 때 까지 이러한 과정을 반복하게 되며, 따라서 탐색 배열은 한 번 탐색이 끝날 때 마다 배열의 크기가 절반씩 줄어든다고 볼 수 있다. 가령 N개 크기의 배열을 이진 탐색하면 N은 *1/2, *1/4 식으로 줄어들 것이다. 여기서 몇 번 탐색했느냐가 시간복잡도를 나타내게 된다. 따라서 이를 수식으로 세운다면 시간복잡도는 log2N이 된다고 볼 수 있다(2^X(실행탐색회수)=N) public class BinSearch { //..
2019.05.21