개발 공부 블로그

특정 언어에선 배열(이 경우엔 종종 리스트라 불리지만)의 크기를 자동으로 조절할 수 있습니다.즉, 데이터를 덧붙일 때마다 배열 혹은 리스트의 크기가 증가한다.하지만 자바 같은 언어에서는 배열의 길이가 고정되어 있다.이런 경우에는 배열을 만들 때 배열의 크기를 함께 지정해야 한다. 동적 가변 크기 기능이 내재되어특정 언어에선 배열(이 경우엔 종종 리스트라 불리지만)의 크기를 자동으로 조절할 수 있습니다. 즉, 데이터를 덧붙일 때마다 배열 혹은 리스트의 크기가 증가한다.하지만 자바 같은 언어에서는 배열의 길이가 고정되어 있다.이런 경우에는 배열을 만들 때 배열의 크기를 함께 지정해야 한다. 동적 가변 크기 기능이 내재되어 있는 배열과 비슷한 자료구조를 원할 때는 보통 ArrayList를 사용한다.Arra..

해시테이블은 효율적인 탐색을 위한 자료구조로서 키를 값에 대응시킨다.해시테이블을 구현하는 방법은 여러 가지가 있다.하지만, 간단하면서도 흔하게 사용되는 구현 방식에 대해서 설명하고자 한다. 간단한 해시테이블을 구현하기 위해선, 연결리스트와 해시 코드 함수만 있으면 된다.키와 값을 해시테이블에 넣을 때는 다음의 과정을 거친다. 1. 처음엔 키의 해시 코드를 계산한다.키의 자료형은 보통 int 혹은 long이 된다.키의 개수는 무한한데 반해 int의 개수는 유한하기 때문에서로 다른 두 개의 키가 같은 해시 코드를 가리킬 수 있다는 사심을 명심하자. 2. 그 다음엔 hash(key) % array_length 와 같은 방식으로 해시 코드를 이용해 배열의 인덱스를 구한다.물론 서로 다른 두 개의 해시 코드가 같..

N-항 트리란 무엇인가? 이번 포스팅에서 살펴볼 N-항 트리(N-ary tree)는 각 노드가 N개의 자식을 가질 수 있다.N은 임의의 양수이므로 n개의 자식 노드는 벡터를 이용하여 저장할 수 있다.그러므로 N-항 트리는 다음과 같이 구현할 수 있다. struct nTree{ int data; std::vector children;}; 위 코드에서 각각의 노드는 임의 개수의 자식을 거느릴 수 있다.그러므로 전체 트리도 임의의 형태를 가지게 된다.평범한 이진 트리를 많이 사용하지 않는 것처럼 평범한 N-항 트리도 그다지 유용하지 않다.그러나 응용 프로그램의 요구 사항에 맞는 형태의 트리를 만들어 사용해야 한다. N항 트리의 예시와 컴퓨터 분야에서의 쓰임회사의 조직도와 같은 경우를 N-항 트리..

그래프 구조를 이용해 문제를 해결하기 위해필요한 기본적이고 대표적인 그래프 알고리즘에서BFS,DFS를 빼놓고 논하기는 쉽지 않을 것이다.일단, 그래프 알고리즘을 말하기 전에 그래프에 대해서 말해보자. 그래프란? 그래프는 정점의 집합과 정점들을 서로 잇는 에지의 집합으로 구성된다.수학적으로 표현하면 그래프 G = 형태로 표현하고,여기서 V는 정점의 집합, E는 에지의 집합을 나타낸다. 그래프에는 크게 방향 그래프, 무방향 그래프, 가중 그래프, 비가중 그래프가 있다. 만약 에지가 특정 정점에서 다른 정점으로 향하는 방향있다면 방향 그래프라고 한다.특정 방향을 가리키지 않으면 무방향 그래프라고 한다.에지에 가중치가 있으면 가중 그래프,가중치가 없으면 비가중 그래프라고 한다. (추가적으로 그래프를 다룰 때 ..

DFS 구현 재귀 호출 코드#include #include using namespace std;const int MAX_N = 10;int N, E;int Graph[MAX_N][MAX_N];bool Visited[MAX_N];void dfs(int node) { Visited[node] = true; cout > N >> E; // 배열 초기화 memset(Visited, 0, sizeof(Visited)); memset(Graph, 0, sizeof(Graph)); for (int i = 0; i > u >> v; Graph[u][v] = Graph[v][u] = 1; } dfs(0); return 0;}  스택 코드#include #include #include using namespace st..

비선형 자료구조는 선형 자료구조를 기반으로 만들어진다.비선형 자료구조는 경우에 따라어떠한 선형 자료구조로 구현하느냐에 따라성능과 메모리 공간 차지에 영향을 미친다.따라서 선형 자료구조의 이해는 아주 중요한 기반지식이다.배열은 연속된 메모리 구조를 가지고 크기가 정해져있다.리스트는 노드와 노드로 연결된 메모리 구조를 가지고크기가 가변적이다.배열의 대표적인 stl은 벡터이다.배열은 연속된 메모리 구조를 가지기 때문에,캐시 공간적 지역성을 만족하여 주변 접근이 빠르다.또한 인덱스를 이용한 임의접근이 가능하여,데이터 접근 속도는 O(1)의 속도를 가진다.벡터는 원소 삽입 삭제 시 사이즈를 넘어선 경우,중간에 삽입 삭제가 일어나는 경우삭제되고 재할당 된다.이는 성능에 영향을 끼친다.때문에 속도면에서 리스트에 비해..

유전자 관련 생명의학 응용 프로그램에서대용량 데이터셋을 처리하는 경우를 가정해보겠다.유사성을 계산하려면 정렬된 DNA 순위가 필요하다. 그러나 데이터셋이 너무 방대하기 때문에 단일 머신에서 처리할 수 없다.그러므로 분산 클러스터에서 데이터를 처리하고 저장하며,각각의 노드는 일련의 정렬된 값이 있다. 주 처리 엔진은 이들 데이터를 모아서 정렬된 단일 스트림으로 변환해야 한다.다수의 정렬된 배열을 합쳐 하나의 정렬된 배열을 만드는 기능을 벡터로 제작해보자. 각각의 리스트는 이미 정렬되어 있기 때문에각 리스트의 최소 원소는 맨 앞에 위치한다.힙에서 최소 원소를 가져온 후 이를 제거하고,최소 원소가 있던 리스트에서 그 다음으로 작은 원소를 선택해 힙에 추가한다. 힙의 노드는 이 원소를 어느 리스트에서 가져왔는지..

힙을 이용한 중앙값 구하기중앙값 먼저 해보자 이번 게시글에서는머신 러닝, 데이터 분석 응용 프로그램에서 접할 수 있는 문제를 풀어보고자 한다. 어떤 소스로부터 한 번에 하나의 데이터를 연속적으로 받는다고 가정하자.그리고 매번 데이터를 받을 때마다지금까지 받은 데이터의 중앙값을 계산한다고 가정하겠다. 간단한 방법은 매번 데이터를 받을 때마다 모든 데이터를 정렬하고,그 중에서 가운데 원소를 반환하는 것이다.그러나 이러한 작업은 정렬 연산 때문에 O(N log N)의 시간 복잡도를 가진다.들어오는 데이터양이 늘어날수록 이 방식은 매우 많은 리소스를 사용하게 된다.여기서는 힙을 이용해서 최적화하는 방법을 알아보자! 1. 먼저 필요한 헤더 파일을 포함하고두 개의 힙을 사용해서 데이터를 저장할 것이다.하나는 최대힙..

힙은 다음과 같은 시간 복잡도를 만족해야 한다. O(1) : 최대 원소에 즉각적으로 접근할 수 있어야 한다.O(log N) : 원소 삽입에 대한 시간 복잡도O(log N) : 최대 원소 삭제에 대한 시간 복잡도 원소 삽입 또는 삭제에 대하 O(log N)의 시간 복잡도를 만족하기 위해 트리 구조를 사용해야 한다.이 경우 완전 이진 트리를 사용해야 한다.완전 이진 트리는 마지막 레벨의 노드를 제외하고 모두 두 개의 자식 노드가 있고,마지막 레벨에서는 왼쪽 부터 차례대로 노드가 있는 트리이다.  완전 이진 트리는 새로운 원소를 트리의 마지막 레벨에 추가하는 방식으로 구성할 수 있다.만약 마지막 레벨의 모든 노드가 채워져 있다면 새로운 레벨을 하나 더 만들고,맨 왼쪽에 위치에 노드를 추가한다.완전 이진 트리는..

1. FileSystemDataStrcut.h에 필요한 헤더 파일을 포함한다.#pragma once#include #include #include  2. 디렉터리/파일 정보를 저장할 노드 구조체를 작성한다.// 파일 시스템의 노드를 나타내는 구조체 정의typedef struct nArrNode {    string name;  // 파일 또는 디렉토리의 이름    bool isDir;  // 이 노드가 디렉토리인지 여부 (true: 디렉토리, false: 파일)    vector children;  // 자식 노드들을 가리키는 포인터들의 벡터 (파일 또는 서브디렉토리)} nArrNode; 3. 사용하기 편하도록 nArrNode를 사용하여 트리를 구성한다.그리고 현재 디렉터리를 저장할 변수를 추가한다. s..