업데이트(2019.04.22): iterator를 이용한 for문 예제 추가

C++에서 vector 사용법을 간단하게 알아보자


환경 및 선수조건

  • C++


벡터 기본 함수

iterator(반복자)

  • begin(): beginning iterator를 반환
  • end(): end iterator를 반환

추가 및 삭제

  • push_back(element): 벡터 제일 뒤에 원소 추가
  • pop_back(): 벡터 제일 뒤에 원소 삭제

조회

  • [i]: i번째 원소를 반환
  • at(i): i번째 원소를 반환
  • front(): 첫번째 원소를 반환
  • back(): 마지막 원소를 반환

기타

  • empty(): 벡터가 비어있으면 true 아니면 false를 반환
  • size(): 벡터 원소들의 수를 반환

배열과의 차이

  • 동적으로 원소를 추가할 수 있으며 크기가 자동으로 늘어난다.


구현 코드

#include <iostream>
#include <vector>

using namespace std;

int main(){

	vector<int> v;


	// push_back
	// 1-2-3-4-5
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5);


	// pop_back
	v.pop_back();


	// back and front
	cout << "vector front value: " << v.front() << '\n';
	cout << "vector end value: " << v.back() << '\n';


	// [i] and at(i)
	cout << "vector opeartor[]: " << v[3] << '\n';
	cout << "vector at: " << v.at(3) << '\n';


	// size
	cout << "vector size: " << v.size() << '\n';


	// empty
	cout << "Is it empty?: " << (v.empty() ? "Yes" : "No") << '\n';


	// iterator
	vector<int>::iterator begin_iter = v.begin(); // auto begin_iter = v.begin()도 가능
	vector<int>::iterator end_iter = v.end(); // auto end_iter = v.end()도 가능

	// get value by iterator
	cout << "vector begin value: " << *begin_iter << '\n';

	// for statement iteration using iterator
	for(vector<int>::iterator iter = v.begin(); iter != v.end(); iter++){
		cout << *iter << ' ';
	}
	cout << endl;

	return 0;

}


참고자료

C++에서 queue 사용법을 간단하게 알아보자


환경 및 선수조건

  • C++


큐 기본 함수

추가 및 삭제

  • push(element): 큐에 원소를 추가(뒤에)
  • pop(): 큐에 있는 원소를 삭제(앞에)

조회

  • front(): 큐 제일 앞에 있는 원소를 반환
  • back(): 큐 제일 뒤에 있는 원소를 반환

기타

  • empty(): 큐가 비어있으면 true 아니면 false를 반환
  • size(): 큐 사이즈를 반환


구현 코드

#include <iostream>
#include <queue>

using namespace std;

int main(){

	// 큐 생성
	queue<int> q;


	// push
	q.push(1);
	q.push(2);
	q.push(3);
	q.push(4);
	q.push(5);
	q.push(6);


	// pop
	q.pop();
	q.pop();
	q.pop();


	// front
	cout << "front element: " << q.front() << '\n';


	// back
	cout << "back element: " << q.back() << '\n';


	// size
	cout << "queue size: " << q.size() << '\n';


	// empty
	cout << "Is it empty?: " << (q.empty() ? "Yes" : "No") << '\n';

	return 0;

}


참고자료

C++에서 stack 사용법을 간단하게 알아보자


환경 및 선수조건

  • C++


스택 기본 함수

추가 및 삭제

  • push(element): top에 원소를 추가
  • pop(): top에 있는 원소를 삭제

조회

  • top(): top(스택의 처음이 아닌 가장 끝)에 있는 원소를 반환

기타

  • empty(): 스택이 비어있으면 true 아니면 false를 반환
  • size(): 스택 사이즈를 반환


구현 코드

#include <iostream>
#include <stack>

using namespace std;

int main(){

	// 스택 생성
	stack<int> s;


	// push
	s.push(3);
	s.push(2);
	s.push(1);


	// top
	cout << "top element: " << s.top() << '\n';


	// pop
	s.pop(); // 1이 삭제
	s.pop(); // 2가 삭제


	// size
	cout << "stack size: " << s.size() << '\n';


	// empty
	cout << "Is it empty?: " << (s.empty() ? "Yes" : "No") << '\n';

	return 0;

}


참고자료

C와C++에서 숫자가 문자열처럼 연속으로 되어있을 때 하나씩 받아보자


환경 및 선수조건

  • C, C++


구현

숫자가 문자열처럼 연속되어서 입력이 주어졌을 때 scanf("%1d", &변수);를 통해 하나씩 받는법을 알아보자

  • 입력
123412314123
  • 코드
#include <iostream>
#include <stdio.h>

using namespace std;

int main (){

    int a[12]; // 위에 입력이 12개

    for(int i=0; i<12; i++){
        // "%1d"를 사용
        scanf("%1d", &a[i]);
	}

}


업데이트(2020.07.12): GIF 이미지 변경

업데이트(2020.06.14): 배열의 크기를 변수로 받아서 동적으로 그래프를 생성하는 예시 추가

업데이트(2019.03.02): DFS, BFS 이미지 추가

업데이트(2018.04.07): Stack을 이용한 DFS 방식 추가

C++에서 그래프 탐색(DFS와 BFS)을 구현하는 방법을 알아보자.


환경 및 선수조건


탐색

개념

  • DFS(깊이우선탐색): 현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색
  • BFS(너비우선탐색): 현재 정점에 연결된 가까운 점들부터 탐색
  • 위의 이미지를 참고하시면 비교가 쉽습니다. 해당 번호 순서대로 탐색을 합니다.

방법

  • DFS: 스택 또는 재귀함수로 구현
  • BFS: 큐를 이용해서 구현


구현

  • List(여기서는 vector)를 통해서 구현
  • https://www.acmicpc.net/problem/1260 풀이와 관련된 구현
  • graph[]: List를 통해서 구현한 그래프
  • check[]: 탐색을 했으면 true 아니면 false로 구분

DFS

Recursion 이용

#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

// dfs에 들어오면 '방문'한거로 판단
// 해당 위치에 check true로 해준다.
void dfs(int start, vector<int> graph[], bool check[]){
	check[start]= true;
	printf("%d ", start);

	for(int i=0; i < graph[start].size(); i++){
		int next = graph[start][i];
		// 방문하지 않았다면
		if(check[next]==false){
			// 재귀함수를 호출한다.
			dfs(next, graph, check);
		}
	}
}

int main (){

	int n, m, start;
	cin >> n >> m >> start;

	vector<int> graph[n+1];
	// Visual Studio의 경우
	/* 변수를 통해서 배열을 동적으로 생성할 때
	vector<int> * graph = new vector<int>[n+1];
	*/
	bool check [n+1];
	fill(check, check+n+1, false);

	for(int i=0; i<m; i++){
		int u,v;
		cin >> u >> v;

		graph[u].push_back(v);
		graph[v].push_back(u);
	}

	// Sorting은 왜 한거지?
	// 나중에 하나의 정점에서 다음을 탐색할 때 node 값에 순차적으로 접근해야하기 때문
	for(int i=1; i<=n; i++){
		sort(graph[i].begin(), graph[i].end());
	}

	//dfs
	dfs(start, graph, check);
	printf("\n");

	return 0;
}

Stack 이용

#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
#include <stdio.h>
#include <queue>

using namespace std;


// stack에 들어가면 방문한거로 판단
// 해당 위치를 true로 해준다.
void dfs(int start, vector<int> graph[], bool check[]){

	stack<int> s;
	s.push(start);
	check[start] = true;
	printf("%d ",start);

	while(!s.empty()){

		int current_node = s.top();
		s.pop();
		for(int i=0; i<graph[current_node].size(); i++){

			int next_node = graph[current_node][i];

			if(check[next_node]==false){
				printf("%d ", next_node);
				check[next_node] = true;
				// pop()을 했었기 때문에 현재 current_node도 넣어줘야한다.
				s.push(current_node);
				s.push(next_node);
				break;
			}
		}
	}

}

int main (){


	int n, m, start;
	cin >> n >> m >> start;

	vector<int> graph[n+1];
	// Visual Studio의 경우
	/* 변수를 통해서 배열을 동적으로 생성할 때
	vector<int> * graph = new vector<int>[n+1];
	*/
	bool check [n+1];
	fill(check, check+n+1, false);

	for(int i=0; i<m; i++){
		int u,v;
		cin >> u >> v;

		graph[u].push_back(v);
		graph[v].push_back(u);
	}

	// Sorting은 왜 한거지?
	// 나중에 하나의 정점에서 다음을 탐색할 때 node 값에 순차적으로 접근해야하기 때문
	for(int i=1; i<=n; i++){
		sort(graph[i].begin(), graph[i].end());
	}

	//dfs
	dfs(start, graph, check);
	printf("\n");

	return 0;
}


BFS

#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

void bfs(int start, vector<int> graph[], bool check[]){
	queue<int> q;

	q.push(start);
	check[start] = true;

	while(!q.empty()){
		int tmp = q.front();
		q.pop();
		printf("%d ",tmp);
		for(int i=0; i<graph[tmp].size(); i++){

			// 방문하지 않았다면
			if(check[graph[tmp][i]] == false){
				// 큐에 넣어주고 방문했음을 표시한다.
				q.push(graph[tmp][i]);
				check[graph[tmp][i]] = true;
			}
		}
	}

}

int main (){

	int n, m, start;
	cin >> n >> m >> start;

	vector<int> graph[n+1];
	// Visual Studio의 경우
	/* 변수를 통해서 배열을 동적으로 생성할 때
	vector<int> * graph = new vector<int>[n+1];
	*/
	bool check [n+1];
	fill(check, check+n+1, false);

	for(int i=0; i<m; i++){
		int u,v;
		cin >> u >> v;

		graph[u].push_back(v);
		graph[v].push_back(u);
	}

	// Sorting은 왜 한거지?
	// 나중에 하나의 정점에서 다음을 탐색할 때 node 값에 순차적으로 접근해야하기 때문
	for(int i=1; i<=n; i++){
		sort(graph[i].begin(), graph[i].end());
	}

	//bfs
	bfs(start, graph, check);
	printf("\n");

	return 0;
}


참고자료