본문 바로가기

Base18

효율성을 위한 메모리의 계층적 구조 (메모리 계층 구조) 앞선 글에서는 컴퓨터가 어떻게 우리가 프로그래밍 언어로 작성한 코드를 알아듣고 처리하는지 알아보았다. 메모리와 구조에 대해서도 잠시 언급했는데, 이번 글에서는 메모리에 정보들을 더 효율적으로 저장하고 가져오기 위해 어떤 방법들을 사용했는지에 대한 이야기를 해보려고 한다. 컴퓨터에 있는 메모리들의 종류는 생각보다 훨씬 다양한데, 이 메모리들은 아래 피라미드 그림처럼 계층적인 구조를 이루고 있다. 지금은 낯설게 보일 수 있지만, 이 글을 다 보고나면 각 계층이 무슨 역할을 하고, 왜 이런 구조로 이루어지는지 알게될 것이다. 하나씩 차근차근 알아보도록 하자. 프로세서(CPU)-메모리(RAM) 격차 CPU는 어떤 명령어가 주어지면 내부 자체 메모리 셀인 레지스터에 데이터를 저장하고, 그 데이터들을 가지고 연산을.. 2021. 6. 13.

컴퓨터가 코드를 실행하기까지 (feat. 메모리, 프로세서, 컴파일러) 컴퓨터 컴퓨터는 한마디로 명령에 따라 데이터를 조작하는 기계이다. 조작을 위해서는 '프로세서'와 '메모리'의 역할이 중요하다. 메모리는 무슨 명령을 수행해야하는지, 명령을 수행하려면 어떤 데이터가 필요한 지를 적어두는 공간이고, 프로세서는 메모리에서 명령과 데이터를 꺼내와서 실제로 명령을 수행하는 부품이다. 메모리(RAM) = 수행할 명령들, 명령 수행을 위한 데이터들을 보관 프로세서(CPU) = 메모리에서 명령과 데이터를 꺼내와서 실제로 명령을 수행 메모리 메모리는 왜 필요할까? 예를들어 누군가 우리한테 500에서 600까지의 합을 구하라고 했다고 생각해보자. 500 + 501 를 먼저 계산하고 1001이라는 숫자를 어딘가 적어둘 것이다. 다음에는 1001에 다음 수인 502을 더해 적어두고... 이런.. 2021. 6. 6.

컴퓨터가 실수를 표현하는 방법 (고정소수점, 부동소수점, IEEE 754) 언어 언어는 여러 사람들이 편하게 의사를 전하기 위해 생긴 수단이다. 같은 언어를 사용하는 사람들이 서로의 말을 이해하기 위해서는 같은 기호를 사용했을 때, 같은 뜻으로 받아들여야 한다. 사람이 사용하는 언어든 컴퓨터가 사용하는 언어든 모든 언어는 각 언어만의 기호로 이루어진다. 컴퓨터의 언어 컴퓨터의 언어는 기본적으로 2진수라는 방법을 사용해서 모든 기호를 나타낸다. 2진수는 어떤 기호를 오직 0 과 1 이라는 두가지 종류의 숫자로만 나타내는 방식이다. 선택지가 0, 1 두 가지이기 때문에 2진수 혹은 비트(bit = binary + digit)라고 부른다. 우리는 보통 0~9의 10가지 숫자를 가지고 다른 숫자를 나타낸다. 이 경우에는 선택지가 열 가지나 되기 때문에 10진수라고 부른다. 2진수, 1.. 2021. 6. 3.

퀵 정렬(Quick Sort) 퀵 정렬은 이름처럼 굉장히 빠른 정렬 알고리즘이라고 알려져 있다. 이번 글에서는 이런 퀵 정렬을 어떻게 구현할 수 있는지, 항상 빠르게 작동하는지, 어떤 장단점이 있는지 알아보고자 한다. 퀵정렬? 퀵 정렬은 우선 한 원소를 무작위로 골라 기준으로 삼고, 배열을 분할한다. 그리고 고른 원소보다 작은 것들은 앞쪽으로, 큰 것들은 뒤로 보낸다. 이렇게 배열을 계속해서 분할하고 또 분할하면, 결국 배열은 정렬된 상태가 된다는 것이 퀵정렬의 기본적인 아이디어이다. 배열을 분할하는 기준값을 보통 pivot이라고 하는데, 이 pivot값이 무엇이냐에 따라 시간복잡도가 달라지기도 하기 때문에 이 값은 굉장히 중요하다. 보통은 첫번째 원소를 pivot값으로 설정하지만, 상황에 따라서는 중앙값이나 마지막값으로 두기도 하고.. 2021. 6. 1.

DFS(깊이우선탐색) / BFS(너비우선탐색) 그래프를 탐색하는 방법에 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) 두 가지가 있다. 말 그대로 '깊이'를 우선시해서 탐색을 하는지, '너비'를 우선시해서 탐색하는 지에 차이가 있다. 아래 그림을 보며 어떻게 달라지는지 한번 비교해보자! DFS (Depth-First Search, 깊이 우선 탐색) 우선 DFS는 기본적으로 최대한 깊이 내려간 뒤에, 더 이상 갈 곳이 없을 때 옆으로 이동하는 탐색 방식이다. 스택(Stack)이나 재귀(Recurse)를 이용해서 구현 가능하다. 스택으로 구현할 때는 모든 노드가 중복없이 딱 한 번씩만 담겨야 하고, 재귀로 구현할 때도 노드 방문 여부를 반드시 체크해서 무한재귀에 빠지지 않게 주의해야 한다. DFS는 모든 노드를 방문하고자 할 때 주로 사용한다. 탐.. 2021. 1. 24.

Data Structure(5) Tree(트리), Binary Search Tree(이진검색트리) Tree (트리) 트리는 노드(node)들을 선(edge)으로 연결한 계층형 자료구조이다. 제일 위에 root(뿌리) 노드 하나가 있고, 그 아래 나머지 자식 노드들이 선으로 연결되고 또 연결되는 구조이다. 나무를 거꾸로 한 모양같다고 해서 트리라는 이름이 붙여졌다고 한다. 관련 용어 루트노드(root node) : 최상위 노드 리프노드(leaf node) : 자식이 없는 노드 부모 노드(parent node) : 노드에 연결된 한단계 상위 레벨 노드 자식노드(child node) : 서브트리의 루트노드들 ex. A의 자식 : B, C 형제노드(sibling) : 같은 부모 + 같은 depth에 있는 노드들 노드의 차수 : 한 노드의 서브트리의 수 트리의 차수 : 트리노드 차수들 중 최대 차수 트리의 높.. 2021. 1. 22.

Data Structure(4) Graph(그래프) Graph (그래프) Graph(그래프)는 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료 구조이다. 지하철 노선도처럼 서로 연결된 데이터들이 어떤 관계인 지 표시할 때 주로 사용한다. let subway = { '교대': ['동대문운동장','사당','충무로'], '동대문운동장': ['교대','을지로3가','충무로'], '사당': ['교대','서울역', '신도림'], '서울역': ['사당','시청','신도림','충무로'], ...} Graph 종류 그래프는 방향성을 가졌는지 여부에 따라 방향 그래프(Directed Graph), 무방향 그래프(Undirected Graph)로 구분할 수 있다. 1. 방향 그래프(Directed Graph) 방향 그래프는 말 그대로 방향을 나타내는 화살표가 있는 그래.. 2021. 1. 22.

Data Structure(3) Hash Table(해시 테이블) Hash Table (해시 테이블) 해시 테이블은 { 키(key) : 값(value) } 쌍을 저장하고 있는 자료 구조이다. 해시 테이블은 키를 저장할 때에 메모리 공간을 덜 사용할 수 있도록, 키(key)를 '해시 함수'(Hash function)라는 함수를 통해 특정 숫자값의 인덱스(index)로 변환한다. 해시 테이블은 필요할 때에만 메모리 크기를 늘리고, 가능한 작은 크기를 유지한다. 해시테이블 : 키(key) → 해시 함수(Hash function) → 인덱스(index)로 변환해 저장하는 자료구조! 관련 용어 키(key) : 원래의 데이터 값(해시 함수 입력 전) 값(value) : 최종 저장되는 값 해싱(hashing) : key → index로 바꾸는 과정 해시함수(hash function.. 2021. 1. 21.

Data Structure(2) Linked List (연결 리스트) Linked List (연결 리스트) 우선 List(리스트)는 데이터에 순서를 매겨둔 자료구조이다. 데이터들이 순서대로 쭉 늘어진 모양을 하고있다. 아직까지 이 데이터들은 차례대로 줄을 서고 있을 뿐 서로에 대해 모르는 상태이다. Linked List(연결 리스트)는 데이터들이 연락처를 주고받아 자기 뒤에있는 사람에게 연락을 할 수 있게 된 상태이다. 대신 누군가를 건너뛰거나 뒤를 돌아서 앞 사람에게 연락을 할 수는 없다. 오직 자기 뒷사람에게만 연락할 수 있다! 조금만 더 자세히 살펴보자. 연결 리스트에 일렬로 연결된 데이터들을 각각 노드(node)라고 한다. 그리고 이 노드들은 각각 1) 데이터(data)와 2) 다음 노드 정보(next)를 갖는다. ✔️ 노드(node) = 데이터(data) + 다음.. 2021. 1. 21.

Data Structure(1) Stack (스택), Queue (큐) 스택(Stack), 그리고 큐(Queue)는 모두 '자료구조'의 한 종류이다. 처리해야할 데이터가 많아졌을 때, 어떤 순서로 저장하고 처리해야할 지를 정해둔 방식이라고 할 수 있다. 간단히 말하면 스택은 가장 마지막에 쌓인 데이터를 먼저 처리하고, 큐는 가장 먼저 쌓인 데이터를 먼저 처리한다는 점에서 차이가 있다. 이렇게 데이터들을 임시 저장하는 가장 기본적인 자료구조인 스택(Stack), 큐(Queue)에 대해 좀 더 알아보자! 스택(Stack) 스택(stack)은 제한적으로 접근할 수 있는 나열 구조이다. 그 접근 방법은 언제나 목록의 끝에서만 일어난다. 스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO — Last In First Out)으로 되어 있다. 스택(Stack)은 번역.. 2021. 1. 19.

선형 검색, 이진 검색 (단순 검색 알고리즘) 데이터들을 모아둔 곳에서 원하는 값을 가진 원소를 찾아내는 '검색 알고리즘'을 살펴보려고 한다. 먼저 가장 기본적인 접근 방법인 선형 검색, 이진 검색 두 가지를 알아보자. 선형 검색 (linear search) 선형 검색 알고리즘은 여러 개의 데이터가 들어있는 리스트에서 찾고자 하는 값이 나올 때까지, 처음부터 하나씩 차례대로 검색하는 알고리즘이다. 말 그대로 100개의 데이터 중 찾으려는 데이터가 100번째에 있다면 100개의 데이터를 다 확인해봐야 찾을 수 있는 것이다. 데이터 개수가 늘어날수록 시간도 당연히 오래걸리게 된다는 단점이 있다. 종료 조건 ✔️ Success : 검색할 값을 찾은 경우 if (array[index] === 찾는 값) ✔️ Fail : 검색할 값을 찾지 못하고 배열의 맨 .. 2021. 1. 9.

빅오(Big-O) 표기법 before... 복잡도 (Complexity) 복잡도는 알고리즘의 성능을 나타내는 척도인데, 시간 복잡도와 공간 복잡도로 나눌 수 있다. 시간 복잡도는 속도에 해당하는 알고리즘의 수행시간 분석결과를 말한다. 공간 복잡도는 메모리 사용량에 대한 분석결과를 말한다. 쉽게 설명하면 아래와 같다. ✔️ 시간복잡도 = 얼마나 오래 걸리는가 ✔️ 공간복잡도 = 얼마나 메모리를 차지하는가 빅오(Big-O) 표기법? 빅오 표기법은 알고리즘의 효율성을 평가하기 위한 분석 방법이다. 효율성의 판단 기준은 바로 위에서 설명한 시간 복잡도, 공간 복잡도이다. 보통 실행속도가 메모리 사용량보다 중요하기 때문에 성능을 판단할 때는 시간 복잡도에서 가장 영향력이 큰 부분을 따진다. 빅오 표기법은 기본적으로 '최악의 경우'를 가정.. 2021. 1. 9.

이전 1 2 다음

티스토리툴바