개발 공부 블로그

트리 트리는 노드와 노드 사이를 연결하는 에지를 이용하여 계층을 구성한다. 트리이 계층 구조를 화면에 도식적으로 나타내려면 말 그대로 나무 형태로 나타낼 수 있으며, 이때 에지는 나뭇가지처럼 표현된다. 트리의 중심이 되는 노드를 루트 노드라고 부르고, 이 노드는 보통 가장 맨 위에 나타낸다. 즉, 트리 구조를 그림으로 나타낼 때는 실제 나무와는 정 반대로 뿌리 모양처럼 생기게 된다. 그 외에도 다양한 트리 모양이 있다. 연습 문제 : 조직도 구조 만들기 #include #include struct node { std::string position; node* first; node* second; }; struct org_tree { node* root; // 새로운 트리를 만드는 정적 함수로 트리 구조를..

컨테이너 어댑터 이번 게시글에서는 이미 존재하는 컨테이너를 기반으로 만들어진 컨테이너를 알아볼 것이다. 기존 컨테이너를 감싸는 래퍼를 제공하는 데에는 몇 가지 이유가 있다. 코드에 좀 더 의미를 부여하고 싶거나, 또는 특별한 인터페이스를 새롭게 제공하고 싶은 경우가 대표적이다. 이러한 자료 구조 중의 하나가 스택이다. 스택은 데이터 처리와 보관을 위해 LIFO(Last In First Out, 후입선출) 구조를 사용한다. 기능적인 측면에서 스택은 컨테이너의 한족 끝에서만 데이터를 삽입하거나 삭제할 수 있으며, 한쪽 끝이 아닌 위치에 있는 데이터는 접근하거나 변경할 수 없다. 벡터나 덱은 이러한 기능을 기본적으로 지원하기 때문에 스택을 구현하기 위한 용도로 사용할 수 있다. 그러나 벡터나 덱을 직접 스택처..

그리디 - 분할 가능 배낭 문제 그리디 방법으로 풀 수 있는 문제로 널리 알려진 배낭 문제에 대해 알아보겠다. 먼저 0-1 배낭 문제(0-1 knapsack problem)이라고도 부르는 일반 배낭 문제는 NP-완전 문제로 알려져 있어 다항 시간 솔루션을 사용할 수 없다. 그러나 0-1 배낭 문제를 조금 변경한 분할 가능 배낭(fractional kanpsack problem)은 그리디 방식으로 해결할 수 있다. 이 두 가지 문제를 살펴보면서, 문제 정의의 작은 차이가 문제 해결 방법에 큰 변화를 가져올 수 있다는 점을 확인하자. 0-1 배낭 문제 물건들의 집합 O = { ... }이 있고, 여기서 i번째 물건 O[i]의 무게는, W[i]이고, 가격은 V[i]이다. 그리고 최대 무게를 T까지 견딜 수 있..

그리디 알고리즘 그리디 알고리즘은 매 단계에서 '가장 좋아 보이는' 해답을 선택하는 알고리즘이다. 즉, 그리디 방법은 지역적인 최적의 해결 방법으로부터 전역적인 최적의 해결 방법을 구성하는 방식이다. 예를 들어, 네비게이션이 인천국제공항에서 강남역까지 차로 이동하는 최단 경로를 보여주는 것 처럼 말이다. 이 경로상에 있는 임의의 두 지점을 선택할 경우, 이 두 지점의 최단 이동 거리는 처음에 구한 전체 최단 경로를 따라 이동함으로써 구할 수 있다. 전체 최단 경로는 사실상 이 경로상에 존재하는 다수의 지점 사이를 최단 거리 경로로 모두 연결시켜 놓은 것이라고 볼 수 있다. 그러므로 어느 두 지점 사이의 최단 경로를 구하기 위하여 다음과 같은 방법을 사용할 수 있다. 즉, 출발 지점에서 아직 방문하지 않은..

C++ Standard Library 의 deque deque deque란? 덱(deque)은 양방향 큐(double-ended queue)의 약자이다. 벡터는 가변 길이 배열이고, push_front() 또는 pop_front() 같은 함수는 비용이 많이든다. std::deque를 사용하면 이러한 단점을 극복할 수 있다. 덱의 구조 C++ 표준은 어떤 기능의 동작만을 정의할 뿐이며, 어떻게 구현해야 하는지는 정의하지 않는다. deque는 list 혹은 vector보다 구현이 약간 복잡한데, deque는 다른 컨테이너만큼 단순하지는 않기 때문에 실제 구현은 좀 더 다른 형태일 수 있고, 많은 최적화 기법이 적용되었을 수 있다. 그러나 기본 개념은 같다. 즉, 이러한 컨테이너를 구현하려면 연속된 메모리 청..

C++ Standard Library 의 list std::list list란? std::forward_list는 아주 기본적인 형태로 구현된 연결리스트이다. std::forward_list는 다른 유용한 기능 중에서도 리스트 끝에 원소 추가, 역방향 이동, 리스트 크기 반환 등의 기능은 제공하지 않는다. 이는 메모리를 적게 쓰고 성능을 유지하기 위함이다. 이외에도 std::forward_list의 반복자는 매우 적은 기능만 지원한다. 컨테이너의 크기를 얻어오거나 자료 구조 맨 뒤에 새로운 데이터를 추가하는 등의 기능은 매우 유용하고 빈번하게 사용되지만, std::forward_list에서는 지원되지 않는다. 그러므로 std::forward_list의 단점을 보완하기 위해 std::list를 C++에서 ..

1. 우선순위 큐 1.1 우선순위 큐란? 큐(Queue)는 먼저 들어오는 데이터가 먼저 나가는 FIFO(First In First Out) 형식의 자료구조이다. 우선순위 큐 (Priority Queue)는 먼저 들어오는 데이터가 아니라, 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조이다. 우선순위 큐는 일반적으로 힙(Heap)을 이용하여 구현한다. 1.2힙이란? 힙(Heap)은 우선순위 큐를 위해 고안된 완전이진트리 형태의 자료구조이다. 여러 개의 값 중 최댓값 또는 최솟값을 찾아내는 연산이 빠르다. 힙의 특징 완전이진트리 형태로 이루어져 있다. 부모노드와 서브트리간 대소 관계가 성립된다. (반정렬 상태) 이진탐색트리(BST)와 달리 중복된 값이 허용된다. 힙의 종류 최대 힙(Max Heap) 부..

자료구조와 알고리즘이란? 자료구조는 데이터의 구조이고,알고리즘은 작업 과정의 묘사이다. 시간 복잡도 정의하기 실제 시간 복잡도를 정의하는 3가지 유형은 다음과 같다. 시간 복잡도 유형빅 - 오메가 (Ω(n)) : 최선일 때 (best case)의 연산 횟수를 나타낸 표기법빅 - 세타 (Θ(n)) : 보통일 때 (average case)의 연산 횟수를 나타낸 표기법빅 - 오 (O(n)) : 최악일 때 (worst case)의 연산 횟수를 나타낸 표기법코딩 테스트에서 어떤 시간 복잡도 유형을 사용해야 할까? 코딩 테스트에서는 빅 - 오 표기법 (O(n))을 기준으로 수행 시간을 계산하는 것이 좋다.실제 테스트에서는 1개의 테스트 케이스로 합격, 불합격을 결정하지 않는다.응시자가 작성한 프로그램으로 다양한 테..

1. istringstream과 ostringstream과 stringstream 은 무엇인가? 문자열을 다룰 때 유용하게 사용 가능한 Class이다. 1) istringstream - 문자열 포맷을 parsing 할 때 사용한다. 2) ostringstream - 문자열 format을 조합하여 저장할 때 사용합니다. 3) sstringstream - 문자열에서 내가 원하는 자료형의 데이터를 추출할 때 사용한다. 2. 헤더 정보 #include 를 include 하면 사용 가능하다. 3. 기본 사용법 1) istringstream로 문자열 format을 분해하기 - 다음 예제에서 space 또는 tap으로 구분된 "test 123 123 hah ahha" 를 각 변수에 알맞게 넣은 예제이다. #inclu..