개발 공부 블로그

그리디 - 분할 가능 배낭 문제 그리디 방법으로 풀 수 있는 문제로 널리 알려진 배낭 문제에 대해 알아보겠다. 먼저 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..