DFS (Depth First Search)
-
깊이 우선 탐색, 트리에서 깊이를 기준으로 하나씩 정복해 나간다.
-
Stack 자료구조를 사용, 컴퓨터는 내부적으로 스택 구조를 활용하므로 재귀함수를 통해 구현 가능.
-
순열, 조합의 개념과 연관되는 것이 많으므로 아래 링크를 통해서 개념을 이해하고 먼저 구현 해보기.
https://yabmoons.tistory.com/99
BFS (Breadth First Search)
-
너비 우선 탐색, 트리에서 너비를 기준으로 하나씩 정복해 나간다.
-
Queue 자료구조를 사용
백트래킹이란?
-
쉽게 DFS + 가지치기라 생각할 수 있다.
-
대표적 예제 (N-Queen). 모든 경우의 수를 생각하지 않고 미리 조건을 확인하며 제외 해 나간다.
https://www.youtube.com/watch?v=_hxFgg7TLZQ
위 영상 내용을 통해 깔끔하게 개념 정리 가능.
[C++ 벡터 구조 이해해기]
https://jhnyang.tistory.com/230
벡터는 배열과 매우 유사하지만, 길이 변화가 비교적 자유로운 동적 배열 구조라고 생각하자.
[벡터의 단점]
중간값 삭제, 검색, 중간 추가가 어려움.
[벡터의 장점]
마지막값 추가, 삭제가 쉬움.
구현이 쉬움.
주소를 알 경우 접근이 쉬움.
사진 출처 : http://myblog.opendocs.co.kr/archives/1347
[벡터는 언제 사용하나요?]
저장하려는 데이터의 갯수가 가변적이고, 마지막에서 추가 삭제가 이루어지며
데이터가 적거나, 많으면 검색이 잦지 않으며, 랜덤하게 데이터 접근을 허용할 때.
[벡터 사용법]
벡터는 C++의 표준(Standard) 템플릿(Template) 라이브러리(Library) 줄여서 STL!
STL에서 제공되는 컨테이너는 일반적으로 헤더 파일 이름이 컨테이너 이름과 같다.
즉, #include <vector>
[iterator(반복자)의 개념]
컨테이너에 저장된 원소를 순회, 접근하는 일반화된 방법을 제공하는 것은 Iterator!
Iterator가 컨테이너에 범용적으로 사용되기 때문에 종속적이지 않고, 독립적으로 운용 가능.
일반적으로 begin(), end()를 활용해 반복자를 사용한다. 해당 element를 반환하는 것이 아닌 반복자의 위치를 설정하는 개념
벡터 예제 연습 코드.
|
#include <iostream> #include <vector> using namespace std; int main(void) {
//벡터 생성. vector<자료형> 이름. vector<int> v1; vector<char> v2; vector<string> v3;
//개수를 넣어 생성자 활용해 디폴트(char 빈값, int 0)값 선언 초기화. vector<char>v4(3); vector<int>v5(5); //vector for loop for(char x: v4) cout<< x; cout<<endl; for(int x : v5) cout<< x; cout<<endl;
//다른 값으로 초기화 하고 싶다면? vector<자료형>이름(갯수, 초기화값)으로. vector<int> v6(5, 10); for(int x : v6) cout<< x<<","; cout<<endl;
//여러값을 다르게 초기화 하고 싶다면? 배열처럼{}를 이용. 단, c++ 11이상 vector<char>v7 = {'a', 'b', 'c', 'd'}; for(char x : v7) cout<< x << " "; cout<<endl; //벡터의 제일 뒤에 값을 추가하고 싶다면? push_back 사용. vector<string>v8; v8.push_back("a11"); v8.push_back("b11"); v8.push_back("c11"); for (string x : v8 ) cout << x << " "; cout<<endl;
//응용버전. int size = 10; vector<int> v9; for(int i=0; i<size; i++) v9.push_back(i+1); cout<<endl; for(int x: v9) cout<< x << "!"; cout<<endl;
//벡터 복사하기 v9을 v10으로 복사. vector<int> v10(v9); for(int x : v10) cout<< x << " ?"; cout<<endl;
//컨테이너에 저장된 원소를 순회, 접근하는 일반화된 방법을 제공하는 것은 Iterator! //Iterator가 컨테이너에 범용적으로 사용되기 때문에 종속적이지 않고, 독립적으로 운용 가능. //일반적으로 begin(), end()를 활용해 반복자를 사용한다. 해당 element를 반환하는 것이 아닌 반복자의 위치를 설정하는 개념 vector<int> v11(v10.begin(), v10.end()); // 전체 복사. vector<int> v12(v10.begin(), v10.begin()+5); // 앞에서 다섯 개 복사. for(int x : v11) cout<< x << "@"; cout<<endl; for(int x : v12) cout<< x << "#"; cout<<endl; } |
'Developer > Algorithm' 카테고리의 다른 글
| 알고리즘 공부하기 (Step 3, Dynamic Programming 이론) (0) | 2020.04.30 |
|---|---|
| 알고리즘 공부하기 (Step 2, 백준 입출력 문제 30문제 풀기) (0) | 2020.04.19 |
| 자료구조(Data Structure) 입문을 위한 개요 정리 (0) | 2020.03.30 |
| 알고리즘 공부하기 (Step 1, 뭐부터 어떻게 공부해야 하지?) (0) | 2020.03.13 |
