메붕이의 개발쉼터

연관 컨테이너(associate container) 연관 컨테이너 컨테이너의 종류 중 하나로 키와 값을 쌍으로 저장한다. 원소들의 위치를 정할 수 없다. 다음과 같은 종류가 있다. 맵(map) 셋(set) 맵(map) 맵은 키와 값으로 데이터를 관리한다. 삽입시 정렬이 되기 때문에 검색 속도가 매우 빠르다. 키는 유일하므로 하나의 키에 하나의 값만 가질 수 있다. (단, 멀티맵(multimap)은 은 키 중복이 가능하다.) 코드 #include #include int main(){ std::map mp; mp.insert({"철수", 20});// 원소 추가 mp.insert({"영희", 30}); mp["바둑이"] = 100;// 이렇게도 가능 mp.erase("철수");// 키를 이용해 데이터 삭제 ..

시퀀스 컨테이너(sequence container) 시퀀스 컨테이너 컨테이너의 종류 중 하나로 원소를 선형으로 저장한다는 특징이 있다. 수정하지 않는 한 원소들의 순서는 삽인된대로 유지된다. 다음과 같은 종류가 있다. 벡터(vector) 덱(deque) 리스트(list) 순방향 리스트(forward_list) 벡터(vector) 벡터는 동적배열로 구현된 클래스 템플릿이다. 원소들을 연속적인 메모리 공간에 저장하기 때문에 반복자 뿐만아니라 배열처럼 임의접근이 가능하다. (vec[i]) 코드 #include #include int main(){ std::vector vec = {1, 2, 3};// 선언과 동시에 초기화 std::vector::iterator it; vec.push_back(4);// 뒤에 ..

STL : Standard Tamplate Library C++에서 제공하는 표준 템플릿 라이브러리로 다음과 같이 구성되어있다. 컨테이너(Container) 반복자(Iterator) 알고리즘(Algorithm) 컨테이너(Container) 임의의 원소를 담는 객체로 자료구조라고도 한다. 컨테이너는 형태에 따라 다시 다음과 같이 나뉜다. 시퀀스 컨테이너(sequence container) 연관 컨테이너(associate container) 컨테이너 어댑터(container adapter) 반복자(Iterator) 컨테이너 안을 돌면서 특정 위치의 원소를 가리킨다. 알고리즘(Algorithm) 삭제, 검색, 정렬 등을 통해 컨테이너 내 원소를 다룬다. 제공되는 자료구조 Stack Queue Vector Li..

스레드란? 스레드란 프로세스 내의 실행 흐름으로 프로세스보다 작은 단위다. 프로세스에서 제공하는 Protection Domain은 없다. 스레드가 나오게 된 배경 하나의 프로세스에는 하나의 Control만이 존재하기 때문에, 한 번에 하나의 일만 처리할 수 있다. 프로세스에서 할 작업을 여러 개로 쪼갠 뒤 각각을 스레드화하면 작업을 병렬적으로 처리할 수 있다. Cooperative Process와의 비교 Cooperative Process는 IPC가 필요하기 때문에 비용이 많이 든다. 프로세스 내에서 Cooperate하는 스레드를 만든다면 보다 적은 비용으로 Cooperative Process가 하는 일을 동일하게 수행 가능하다. 프로세스와 스레드 프로세스간프로세스 간 메모리 영역은 독립적이므로 서로의 ..

개요 외판원 순회 문제 (Traveling Salesman Problem)는 조합 최적화 문제의 일종으로, NP-난해 집합에 속하기 때문에 계산 이론에서 해를 구하기 어려운 문제의 대표적인 사례로 많이 다룬다. 외판원 문제는 다음과 같이 설명할 수 있다. 어떤 외판원이 n개의 도시를 방문할 계획을 수립하고 있다고 가정하자. 각 도시는 다른 모든 도시와 도로로 연결되어 있다. 출장 비용을 최소로 줄이기 위하여 외판원이 거주하고 있는 도시에서 각 도시를 한 번씩만 방문하고 다시 출발한 도시로 돌아오는 가장 최소 비용의 일주여행 경로를 찾고자 한다. 재귀적 관계식 예시 D[vi][A] Table 알고리즘 void travel(int n, const number W[][], index P[][], number&..