TWpower Reading time ~1 minute

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;

}


참고자료

TWpower Reading time ~1 minute

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]);
	}

}


TWpower Reading time ~2 minutes

업데이트(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;
}


참고자료

TWpower Reading time ~1 minute

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

업데이트(2019.03.02): 그래프(방향, 무방향) 이미지 추가

C++에서 그래프를 구현하는 방법을 알아보자.


환경 및 선수조건

  • C++
  • 그래프의 기본 개념(정점, 간선 등등)


그래프의 구현

  • 행렬을 이용한 구현
  • List를 이용한 구현(vector를 Linked List처럼 사용)


행렬

개념

  • 행렬: 정점
  • 행렬값: 가중치 값(연결만 되었으면 1)
  • 행과열은 정점을 나타내고 [i][j]값은 정점 i로부터 j가 연결되어있으면 1 아니면 0으로 표시
  • 가중치가 있다면 [i][j]에 가중치를 저장


방향 그래프

  • 방향 그래프 예시


무방향 그래프

  • 무방향 그래프 예시
  • 무방향 그래프는 행렬이 대칭임을 알 수 있습니다.


코드

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

using namespace std;

int main(){
    int n,m;
    cin >> n >> m; // 정점과 간선의 개수를 입력받음

    int graph[n+1][n+1];

    // Visual Studio의 경우
    /* 변수를 통해서 배열을 동적으로 생성할 때
    int ** graph = new int * [n];
    for (int i = 0; i <= n; ++i)
        graph[i] = new int[m];
    */

    // 정적으로 선언했기 때문에 값들을 전부 -1로 초기화
    for(int i=0; i<=n; i++){
        for(int j=0; j<=n; j++){
            graph[i][j] = -1;
        }
    }

    for(int i=0; i<m; i++){
        int u,v;
        scanf("%d %d", &u, &v);
        graph[u][v] = graph[v][u] = 1;
        // 단방향의 경우 graph[u][v] = 1;
        // 가중치가 있는 경우 단방향의 경우 graph[u][v] = 가중치값;
    }
}


리스트(vector를 Linked List처럼 사용)

개념

  • vector: 정점
  • vector의 요소: 연결된 정점
  • 정점의 수만큼 리스트를 생성하고 해당 정점 리스트에다가 연결된 정점들을 추가


방향 그래프

  • 방향 그래프 예시


무방향 그래프

  • 무방향 그래프 예시


코드

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

using namespace std;

int main(){
    int n,m;
    cin >> n >> m; // 정점과 간선의 개수를 입력받음

    vector<int> graph[n+1];

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

    for(int i=0; i<m; i++){
        int u,v;
        scanf("%d %d", &u, &v);
        graph[u].push_back(v);
        graph[v].push_back(u);
        // 단방향의 경우 graph[u].push_back(v);만 작성
        // 가중치가 있는 경우 vector<pair<int,int>> graph[n+1];로 만들거나 구조체를 만들어서 가중치와 함께 저장
        // graph[u].push_back(make_pair(v,w)); u->v 가중치: w
    }
}


참고자료

TWpower Reading time ~1 minute

C++에서 헤더 파일에 있는 sort와 stable_sort를 통해서 정렬하는 방법을 알아보자.


환경 및 선수조건


sort() 사용하기

  • 배열의 경우
#include <iostream>
#include <algorithm>

using namespace std;

int main (){

    int a[100];

    // 초기화를 했다고 가정

    // 정렬
    // 첫번째 인자는 시작지점 = 배열의 포인터
    // 두번째 인자는 끝나는지점 + 1 = a(배열의 포인터) + 배열의 크기
    sort(a, a+100);
}
  • 벡터의 경우
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main (){

    vector<int> a(100);

    // 초기화를 했다고 가정

    // 정렬
    // 첫번째 인자는 시작지점 = iterator의 begin()
    // 두번째 인자는 끝나는지점 + 1 = iterator의 end()
    sort(a.begin(), a.end());    
}


sort() 사용하기(비교함수 이용하기)

  • 때로는 직접 비교함수를 추가해줘야하는 경우가 있다 사용법은 위와 동입하며 함수만 3번째 인자로 추가해주면 된다.
  • Point라는 구조체를 정렬한다고 가정해보자.
#include <iostream>
#include <algorithm>

using namespace std;

struct Point{
    int x;
    int y;
};

// const와  &를 통해서 레퍼런스로 받아오는걸 잊지말자!
// x순으로 정렬하고 x값이 같으면 y순으로 각각 오른차순으로 정렬
bool cmp(const Point &p1, const Point &p2){
    if(p1.x < p2.x){
        return true;
    }
    else if(p1.x == p2.x){
        return p1.y < p2.y;
    }
    else{
        return false;
    }
}

int main (){

    Point a[100];

    // 초기화를 했다고 가정

    // 정렬
    // 첫번째 인자는 시작지점 = 배열의 포인터
    // 두번째 인자는 끝나는지점 + 1 = a(배열의 포인터) + 배열의 크기
    sort(a, a+100, cmp);
}


stable_sort() 사용하기

  • stable_sort()는 구조체처럼 여러 값들이 묶여 있을 때 하나의 요소로 정렬을 했을 때 다른 요소들의 정렬 순서도 정렬 전과 같이 그대로 유지 될 수 있도록 하는 정렬이다.
#include <iostream>
#include <algorithm>

using namespace std;

struct Point{
    int x;
    int y;
};

// const와  &를 통해서 주소값을 받아오는걸 잊지말자!
// x순으로 정렬하고 x값이 같으면 y순으로 각각 오른차순으로 정렬
bool cmp(const Point &p1, const Point &p2){
    if(p1.x < p2.x){
        return true;
    }
    else if(p1.x == p2.x){
        return p1.y < p2.y;
    }
    else{
        return false;
    }
}

int main (){

    Point a[100];

    // 초기화를 했다고 가정

    // 정렬
    // 첫번째 인자는 시작지점 = 배열의 포인터
    // 두번째 인자는 끝나는지점 + 1 = a(배열의 포인터) + 배열의 크기
    stable_sort(a, a+100, cmp);
}


참고자료