개발하는 멍정이야기

[c++] std container2. 연관 컨테이너(Associative Container)

* 잘못된 내용에 대한 피드백은 언제나 환영입니다. * 멍하멍정이에요.오늘은 STL컨테이너 두번째 시간!연관 컨테이너(Associative Container)에 대해 알아보아요! 연관 컨테이너에서 요소는 미리 정의된 순서(예: 오름차순 정렬)로 삽입됩니다. 순서가 지정되지 않은 연관 컨테이너도 사용할 수 있습니다. 연관 컨테이너를 맵 및 집합의 두 하위 집합으로 그룹화할 수 있습니다.Microsoft Learn - STL 컨테이너 문서  말 그대로 컨테이너에 값을 넣을 때 정의된 순서를 따라서 삽입한다고 할 수 있습니다.하나하나 천천히 살펴보아요. map container각 요소가 정렬 키와 데이터 값을 갖고 있는 쌍으로 삽입됩니다.키 값은 고유하며(이미 값이 있는 경우에는 다시 삽입 불가) 키 값을 기..

* 잘못된 내용에 대한 피드백은 언제나 환영입니다. *  멍하멍정이에요.오늘은 STL컨테이너에 대해 정리해보아요. STL 컨테이너란 무엇인가?표준 라이브러리는 관련 개체 컬렉션을 저장할, 형식이 안전한 다양한 컨테이너를 제공합니다. 컨테이너는 클래스 템플릿입니다. 컨테이너 변수를 선언할 때 컨테이너가 보유할 요소의 형식을 지정합니다. 컨테이너는 이니셜라이저 목록을 사용하여 생성할 수 있습니다. 요소를 추가 및 제거하고 다른 작업을 수행하기 위한 멤버 함수가 있습니다.https://learn.microsoft.com/ko-kr/cpp/standard-library/stl-containers?view=msvc-170 C++ 표준 라이브러리 컨테이너자세한 정보: C++ 표준 라이브러리 컨테이너learn.mic..

멍하멍정이에요.티스토리 정말 오랜만이네요.티스토리 편집툴이 너무 구려서 요즘은 노션을 자주 이용했는데 아무튼앞으로 열심히 할 수 있길 바라며. 오늘은 c++ 을 조금 준비하려고 합니다.저번학기에 1일 1백준을 했었는데c++은 처음이라 처음 보는 개념 같은걸 깃허브에 메모했던걸 좀 정리해보려고 합니다.깃허브는 요기https://github.com/258xsw/BaejoonAlgorithm : c++ 표준 입출력 클래스c++은 객체지향이기 때문에 입출력을 담당하는 수단도 객체로 다루게 된다.std::cout- 표준 c 출력 스트림- cout std::setprecision(n)- cout의 출력 포맷을 지정한다.- cout의 기본 정밀도는 6이기 때문에 원하는 소수점을 늘리고 싶을 때 사용!-> 포맷을 변경..

멍하멍정이에요나름 바빴던 4학년 1학기를 끝내고 이제 정말로 취준을 준비하면서..git/github에 대해 다시 한 번 정리해보려고 해요깃허브 계정은 오백년 전에 만들었는데 아직도 기본 기능만 사용하는 것 같아서천천히 git부터 배워가려고 해요그런 의미에서 오늘은 간단하게 많이들 헷갈리는 Git/Github에 대해서 짚고 가려고 해요. 들어가기에 앞서..잘못된 정보는 언제든지 알려주시면 수정하겠습니다 0Git과 Github란?저도 처음에 그랬듯이 많은 분들이 git과 github에 대한 개념을 헷갈리시는데 간단하게 짚고 넘어가자면 Git : 내 컴퓨터(local)에서 진행 상황 정리GitHub : 내 컴퓨터(local)에서 저장한 진행 상황을 온라인(global)으로 올려서 관리간단하게 닌텐도 게임 젤다..

Merge Sort Revisited : 잘게 쪼개서 합치면서 비교하며 정렬 worst case time complexity = n lg n + n + 1 -> 합치는 과정에서 2개 이상을 한 번에 처리할 수 있기 때문에 아까보다 좋아짐! - 더욱 개선 할 수 있는 방법? 1. Dynamic programming 2. LInked list 3. More complex merge algorithm merge sort의 자세한 알고리즘은 요기... [알고리즘] Binary Search, Mergesort(DIvide and Conquer) DIvide and Conquer Approach - Divide : 인스턴스가 너무 커서 계산이 힘들다면 작게 쪼개서 계산한다. - Conquer : 작아진 인스턴스를 ..

Two Types of Complexity Analysis Algorithm Analysis : 효율적인 알고리즘을 찾기 위한 접근법 -> time complexity & space complexity problem Analysis : 좀 더 본질적인 문제의 복잡성에 대한 분석 -> matrix multiplication의 경우 n^3이 되는 경우, n^2.81(스트라센) 아무튼 이런저런 방식이 있음 -> 계산 복잡도에 대한 분석을 해보자? (computatuinal complexity analysis) Computational Complexity Objective Ω(f(n))에 대해 Θ(f(n))을 개발하는 방법? -> 하지만 문제의 하한보다 낮은 알고리즘을 개발하는 것은 불가능!! ex. sorti..

The Traveling Salesperson Problem -> 비행기타고 여기저기 출장 다녀오기 (ง˙∇˙)ว + 최소값으로 다녀와야함 Input - 값이 있는 방향 그래프 - 음수 x - 행과 열이 1부터 n까지인 2차원 배열 W - W[i][j] : i번째 정점에서 j번째 정점까지의 간선 위의 가중치 Output - 최적 투어의 길이를 값으로 하는 변수 minlength, 그를 구성하는 행렬 P Dynamic Programming for TSP - Brute force algorithm(전부 찾기) : (n - 1)! - The length of the optimal path(최적 경로 방법?) 아무튼 최단 거리를 찾는게 목표 일반적으로 i가 1이 아니고 vi가 A가 아니라면 a가 0이 아니면(내..

Branch and Bound Algorithm - backtracking을 개선한 알고리즘 - state space tree은 backtracking처럼 그대로 사용됨 - 최적화 문제에 사용 What is a bound? : 바운드는 노드를 넘어 확장하여 얻을 수 있는 해의 값? - 노드의 경계를 계산하여 노드가 유망한지 여부를 확인 - 경계값이 지금까지 발견된 최상의 솔루션의 값보다 크지 않으면 non-promising => k - 1까지의 가장 큰 값이 bound라서 다음 노드의 bound가 Maxprofit보다 작으면 확인 할 필요 없음! -> 내가 찾은 값이 더 크니까! The 0/1 Knapsack Problem Revisited : 가방에 최대한 많은 물건을 훔치자!-> 얼마짜리를 몇키로까지..

Monte Carlo Algorithm - 확률적 알고리즘으로 확률적 분포에 따라 무작위로 결정된다. In backtracking Algorithm - backtracking 알고리즘의 효율성을 추정할 때 사용할 수 있다. - state space tree의 동일한 level에서는 동일한 promising function을 사용 - 동일한 level의 node에는 동일한 수의 자식 노드가 있어야 함. Monte Carlo Algorithm in 4 - queens problem 4-queens problem에서 monte carlo algorithm으로 backtracking algorithm의 효율성 측정하기 -> 실제 방문해야할 노드를 추정 1. i 번째 노드에서 n개 중에 3개정도를 조사하였을 때 ..

Backtracking Technique - dead end를 만나면 뒤로 돌아가서 다른 선택지를 선택함 - Depth First Search(DFS | 깊이 우선 탐색)으로 진행 a modified depth-first-search of a tree (수정된 깊이 우선 탐색) : dead end라는걸 알고 있다면 그 노드는 탐색하지 않음 //유망함수로 판별 promising function(유망 함수) 특정 상태에서 이어진 경로가 해결책이 될 가능성이 있는지 결정 -> 문제의 해결 가능성을 평가하기 위함. -> 트리를 탐색하며 유망함수를 통해 유망한 트리만 탐색함. The Depth First Search(깊이 우선 탐색) //일반적인 방법 1. 루트 방문 2. 하위 노드 방문(왼쪽 -> 오른쪽) //..