본문 바로가기

Language & Technique

 (4)
[자료구조] Pair 와 Map Pair 두 객체를 하나의 객체처럼 다룰 수 있게 해주는 구조체 선언 pair p ( first, second); 생성 p = make_pair( first , secnod ); 데이터 접근 p.first; p.second; Map #include 선언이 필요하다. pair로 된 데이터를 저장, 검색하기 위한 자료 구조이다. map에 있는 요소의 값은 직접 변경할 수 있으나. 키 값은 상수이며 변경할 수 없다. 구문 template class map; Key : map키 데이터 Type : map에 저장되는 요소 데이터 Traits : map내에서의 상대적인 순서를 결정하기 위한 정렬 Allocator : map의 메모리 할당 및 할당 취소에 대한 정보를 저장하는 할당자 개체 생성 map m1; map ..
DFS - 조합과 순열 조합과 순열 조합 nCr (조합) 조합은 순서가 상관이 없는 모임을 의미한다. 순서가 상관 없기 때문에 { 1, 2, 3 }, { 1, 3, 2 } , { 2, 1, 3} 모두 같은 것으로 취급을 한다. (3, 6, 9)에서 숫자 2개로 구성된 조합을 구한다면 -> (3, 6), (3, 9), (6, 9) 순열 nPr (순열) 순열이라는 것은 주어진 수열에서 순서에 따라 결과가 달라지는 방식을 의미한다. 즉 순서가 존재함을 의미한다 즉 순열에서 { 1, 2, 3 } 과 { 1, 3, 2 } , { 2, 1, 3 } 은 모두 다른 결과를 가져온다. (3, 6, 9)에서 숫자 2개로 구성된 순열을 구한다면 -> (3, 6), (3, 9), (6, 3), (6, 9), (9, 3), (9, 6) DFS로 구현..
참조자(레퍼런스)와 포인터 참조자(Reference, 레퍼런스) 변수라고 하는 것은 할당된 메모리 공간에 붙여진 이름이다. 이름을 사용하면 해당 메모리 공간에 접근이 가능해진다. 참조자는 이러한 변수에 다른 이름을 붙이는 것을 말한다. 대상이 이름이 존재하지 않을 경우에는 참조할 수 없다. 선언 방법 int num = 1; int& ref1 = num; // 참조자 선언 int& ref2; // Compile Error: 초기화 필요 포인터 포인터는 변수의 주소를 저장하는 변수이며 포인터, 포인터 변수 다 같은 의미로 쓰인다. 주소만을 저장할 수 있는 변수를 포인터 변수라고 하고 일반적인 변수 선언과는 다르게 자료형에 * 표시를 붙여 선언한다. 포인터가 가리키는 값을 가져오는 것을 역참조라고 한다. 선언 방법 int n = 100..
그래프 - DFS 와 BFS DFS( Depth-First Search / 깊이 우선 탐색) 해당 노드의 자식 노드들을 모두 탐색한 후 형제 노드를 탐색한다. 모든 노드를 방문하고자 할 때 사용 스택 또는 재귀 함수를 사용하여 구현한다. DFS의 장점 단지 현 경로상의 노드들만을 기억하면 되므로 저장공간의 수요가 비교적 적다. 목표 노드가 깊은 단계(트리의 레벨이 높은 곳)에 있을 경우 해를 빨리 구할 수 있다. DFS의 단점 해가 없는 경로에 깊이 빠질 가능성이 있다. 따라서 실제의 경우 임의의 깊이까지만 탐색하고 목표 노드를 발견하지 못하면 다음의 경로를 따라 탐색하는 방법이 유용할 수 있다. 얻어진 해가 최단 경로가 된다는 보장이 없다. 이는 목표에 이르는 경로가 다수인 문제에 대해 깊이우선 탐색은 해에 다다르면 탐색을 끝내버..

티스토리툴바