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)을 구현하는 방법을 알아보자.
#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;
}
#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;
}
#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;
}
업데이트(2020.05.26): 배열의 크기를 변수로 받아서 동적으로 그래프를 생성하는 예시 추가
업데이트(2019.03.02): 그래프(방향, 무방향) 이미지 추가
C++에서 그래프를 구현하는 방법을 알아보자.
#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] = 가중치값;
}
}
#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
}
}
C++에서
헤더 파일에 있는 sort와 stable_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());
}
#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);
}
#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);
}
소수를 구할 때 가장 빠른 시간에 구할 수 있는 에라토스테네스의 체의 방법을 알아보자
2부터 n까지의 소수를 구할 때 에라토스테네스의 체를 이용한 방법은 아래와 같다.
O(n*log(log(n)))example.cpp
bool c[1000001]= {false,};
int p[1000000];
int count = 0;
//0~1000000까지 소수 구하기
for(int i=2; i<=1000000; i++){
if(c[i] == false){
// 추가
p[count++] = i;
// i의 배수 지우기
for(int j=i+i; j<=1000000; j+=i){
c[j]=true;
}
}
}