코드 깎는 개발자

맵 (Map) 과 해쉬 (Hash) 의 차이는 무엇인가? 일단 먼저 맵과 해쉬는 연관 컨테이너(Associative Container)이며 순서를 유지하는 것이 아닌 빠른 검색하는 과정에 초점을 맞춘 컨테이너이다. 맵 (Map)과 해쉬 (Hash) https://doanhan.tistory.com/28?category=581362 [C++] 연관 컨테이너, 집합과 맵 [C++] 연관 컨테이너, 집합과 맵 연관 컨테이너 (Associative Container) 삽입/제거된 요소의 순서를 유지는 하는 순차컨테이너의 특성을 무시하고 요소를 검색하는 과정을 최대한 빠르게 수행하는데 doanhan.tistory.com 맵은 같은 Key 값을 가지는 Pair들을 저장하는 컨테이너로 같은 Key값을 가지는 Pair..

[OS] 메모리 계층 구조 (Memory Hierarchy) 메모리에 관련 된 용량, 접근 속도, 비용 등의 특성을 필요 관계에 따라 나타낸 구조이다. 빈도(메모리 접근) 속도 가격 용량 레지스터 높음 ↕ 낮음 빠름 ↕ 느림 높음 ↕ 낮음 작음 ↕ 큼 캐시 메모리 하드 디스크 레지스터 (Register) CPU가 요청을 처리하는데 필요한 데이터를 일시적으로 저장하는 기억장치이다. 캐시 (Cache) 데이터나 값을 미리 복사해 높는 임시장소로 시스템의 효율성을 위해서 사용한다. 대부분의 메모리 접근은 특정한 위치의 근방에서 자주 일어나는 경향이 있기 때문에 데이터를 크기는 작지만 속도가 빠른 캐시메모리에 복사해 두면 평균 메모리 접근 시간을 아낄 수 있다. 종류는 외부캐시, 내부캐시, 디스크캐시 등이 있다..

[알고리즘] 이진 탐색 트리 (Binary Search Tree) https://doanhan.tistory.com/49?category=583264 [알고리즘] 이진 트리 (Binary Tree) [알고리즘] 이진 트리 (Binary Tree) 이진트리는 기본적으로 많이 사용되는 비선형 자료구조이다. 기존에 힙에서도 이진트리를 사용했는데 그것은 완전 이진 트리로 배열로 표현이 가능하지만 doanhan.tistory.com 이진 탐색 트리는 특정한 특징을 가지고 있는 이진 트리를 의미한다. - 각 노드에는 중복되지 않는 키가 있다. - 루트 노드의 왼쪽은 루트보다 작은 값이, 오른쪽은 루트보다 큰 값으로 구성되어야 한다. - 서브 트리들도 전부 위와 같은 구성으로 이루어져야 한다. 이진 트리는 전위, 중..

[알고리즘] 에라토스테네스의 체(Sieve of Eratosthenes) 에라토스테네스의 체는 체라는 말처럼 무엇인가를 걸러내는 거나 판별하는 것을 의미하는데, 이것은 소수(PrimeNumber)이다. 소수는 2개의 약수(1과 자기 자신)만을 가지고 있는 수이다. 즉, 에라토스테네스의 체는 소수를 대량으로 빠르게 판별할 수 있는 알고리즘입니다. 먼저 일단 소수를 판별하는 방법을 구현해보겠습니다. #include using namespace std; //소수 판별 bool IsPrimeNumber(int x) { for(int i = 2; i < x; i++) { if(x%i ==0) retur false; } return true; } 위는 간단하게 소수를 구하는 방법이다. 하지만 시간복잡도가 O(N)로..

[자료구조] 원형 연결 리스트 (Circular Linked List) 원형 연결 리스트는 마지막 꼬리(Tail)가 NULL을 가리키지 않고 처음 머리(Head)를 가리키는 구조이다. 단일 연결 리스트와 이중 연결 리스트 둘 다 구현이 가능하다. 원형 연결 리스트는 한 노드에서 모든 노드로 접근이 가능할 수 있다는 장점을 가지고 있다. 하지만 잘못 사용 시 무한 순환이 되는 상황이 발생할 수 있습니다. 소스코드 구현 (C++) #include using namespace std; struct Node { Node(int data) { Data = data; Prev = Next = NULL; } void Destroy() { delete this; } Node* Prev; int Data; Node* N..

STL 벡터와 리스트의 차이는 무엇인가? STL 벡터와 리스트는 순차 컨테이너에 속하며 요소들의 보관순서를 유지할 수 있는 특징을 가지고 있다. 벡터 (Vector) https://doanhan.tistory.com/26?category=581362 [C++] 순차 컨테이너와 벡터 [C++] 순차 컨테이너와 벡터 순차 컨테이너 (Sequence Container) 요소들의 보관 순서를 유지할 수 있도록 해주며 어떤 위치든 삽입, 제거가 가능하지만 성능에 있어서는 각각 다른 특성들을 가진다. doanhan.tistory.com 벡터는 배열(Array)처럼 개체들을 연속적인 메모리 공간에 저장한다. 즉, 반복자 외에도 인덱스를 통해서 개체들에 접근할 수 있다. 리스트 (List) https://doanhan..

[자료구조] 이중 연결 리스트 (Doubly Linked List) 이중 연결 리스트는 단일 연결 리스트와는 다르게 Next뿐만 아니라 Previos도 연결되어있는 양방향 리스트이다. 이 연결 리스트의 장점은 양방향으로 연결이 되어있기 때문에 탐색에 유리하다는 점이다. 즉, 단일 연결리스트는 단방향 탐색이지만 이중 연결 리스트는 양방향 탐색이 가능하다는 것입니다. 하지만 그만큼 양방향을 위해 변수를 추가해서 구조가 복잡해지고 메모리를 더 차지한다는 단점을 가지고 있습니다. 소스코드 구현 (C++) #include using namespace std; struct Node { Node(int data) { Data = data; Prev = Next = NULL; } void Destroy() { dele..

[자료구조] 연결 리스트 (Linked List) 연결 리스트는 각 노드가 데이터와 포인터를 가지고 한줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조이며 선형자료구조에 속한다. 종류는 단일 연결 리스트, 이중 연결 리스트, 원형 연결 리스트 등이 있으며 자료의 추가/삭제에 대해 시간 복잡도 O(1)를 갖는다. 하지만 O(N)의 시간이 걸리는 특수한 경우도 존재한다. 일반적으로 리스트의 맨 앞 노드를 헤드(Head), 맨 뒤 노드를 테일(Tail)이라고 부른다. 단일 연결 리스트 (Singly Linked List) 단일 연결 리스트는 각 노드에 자료 공간과 한 개의 포인터 공간이 있고 각 노드의 포인터는 다음 노드를 가리킨다. 즉, 단일 연결 리스트는 한 방향으로만 연결이 되어있으며 연결된 다음 ..

[자료구조] 자료 구조 (Data Structure) 자료구조는 문제해결을 위해 데이터를 조직화하여 저장하는 것과 이를 구현하는 데 필요한 알고리즘에 대해 논하는 기초이론이다. 자료구조는 크게 4가지로 분류할 수 있으며 단순 자료구조, 선형 자료구조, 비선형 자료구조, 파일 자료구조 이다. 단순 구조 (Simple Structure) 흔히들 알고있는 정수, 실수, 문자, 문자열과 같은 자료형을 뜻한다. 선형 자료 구조 (Linear Data Structure) 데이터를 연속적으로 나열한 형태의 자료 구조이다. 리스트, 연결리스트, 스택, 큐, 데큐가 있다. 비선형 자료 구조 (NonLinear Data Structure) 데이터를 여러 관계로 연결한 형태의 자료 구조이다. 대표적인 케이스로는 트리와 그래..

[알고리즘] 다이나믹 프로그래밍 (Dynamic Programming) 하나의 문제를 단 한번만 풀도록 하는 알고리즘이다. 피보나치 수열과 같이 한 번 푼것을 여러번 다시 푸는 비효율적인 알고리즘을 개선시키는 방법으로 사용한다. 그리고 다이나믹 프로그래밍은 두가지 가정하에 사용할 수있는데 1) 큰 문제는 작은 문제로 나눌 수 있다. 2) 작은 문제에서 구한 답은 그것을 포함하는 큰 문제에서도 동일하다. 즉, 다이나믹 프로그래밍은 큰 문제를 해결하기 위해서 그것을 작게 나누어 해결한 뒤 그것을 이용하여 답을 구하는 것이다. 하지만 이 과정이 분할정복과 다른 점은 메모제이션(Memozation)이 사용된다는 점이다. 이미 계산한 것을 저장하는 것으로 나중에 동일한 계산을 할 때는 저장된 값을 반환하여 사용하..