-- 1. 모든 레코드 조회하기
SELECT * from animal_ins order by animal_id asc
-- 2. 역순 정렬하기
SELECT Name, datetime from animal_ins order by animal_id desc
-- 3. 아픈 동물 찾기
SELECT animal_id, name from animal_ins where intake_condition = "Sick" order by animal_id asc ;
-- 4. 어린 동물 찾기
SELECT animal_id, name from animal_ins where not intake_condition = "aged" order by animal_id ASC
-- 5. 동물의 아이디와 이름
SELECT animal_id, name from animal_ins order by animal_id asc
-- 6. 여러 기준으로 정렬하기
SELECT animal_id, name, datetime from animal_ins order by name asc, datetime desc
-- 7. 상위 n개 레코드
SELECT name from animal_ins order by datetime asc limit 1
-- 1. 최댓값 구하기
SELECT datetime from animal_ins order by datetime desc limit 1
-- 2. 최솟값 구하기
SELECT min(datetime) from animal_ins
-- 3. 동물 수 구하기
SELECT count(animal_id) from animal_ins;
-- 4. 중복 제거하기
SELECT distinct(name) from animal_ins
-- 1. 고양이와 개는 몇마리 있을까
SELECT animal_type, count(animal_id) as count from animal_ins group by animal_type order by animal_type asc
-- 2. 동명 동물 수 찾기
SELECT name, count(name) as count from animal_ins group by name having count(name) >= 2 order by name asc
-- 3. 입양 시작 구하기 (1)
select HOUR(datetime) as hour, count(datetime) as count
from animal_outs
group by hour having hour >= 9 and hour < 20
order by hour asc
-- 4. 입양 시각 구하기 (2)
SET @h = -1;
SELECT (@h := @h + 1) as hour,
(select count(hour(datetime)) from animal_outs where hour(datetime) = @h) as count
from animal_outs where @h < 23
-- 1. 이름이 없는 동물의 아이디
SELECT animal_id from animal_ins where name is NULL
-- 2. 이름이 있는 동물의 아이디
SELECT animal_id from animal_ins where name is not null order by animal_id asc
-- 3. NULL 처리하기
SELECT animal_type, ifnull(name, "No name") as name, sex_upon_intake from animal_ins;
-- 1. 없어진 기록 찾기
SELECT outs.animal_id, outs.name from animal_outs outs
left outer join animal_ins ins
on outs.animal_id = ins.animal_id
where ins.animal_id is null
order by outs.animal_id asc
-- 2. 있었는데요 없었습니다
SELECT ins.animal_id, ins.name from animal_ins ins
join animal_outs outs on ins.animal_id = outs.animal_id
where ins.datetime > outs.datetime
order by ins.datetime asc
-- 3. 오랜 기간 보호한 동물 (1)
select ins.name, ins.datetime from animal_ins ins
left join animal_outs outs
on ins.animal_id = outs.animal_id
where outs.animal_id is null
order by ins.datetime asc
limit 3
-- 4. 보호소에서 중성화한 동물
SELECT ins.animal_id, ins.animal_type, ins.name from animal_ins ins
left join animal_outs outs
on ins.animal_id = outs.animal_id
where (outs.sex_upon_outcome like '%Spayed%' or outs.sex_upon_outcome like '%Neutered%')
and ins.sex_upon_intake like '%Intact%'
order by ins.animal_id asc
-- 1. 루시와 엘라 찾기
SELECT animal_id, name, sex_upon_intake from animal_ins
where name="Lucy" or name="Ella" or name="Pickle" or name="Rogan" or name="Sabrina" or name="Mitty"
order by animal_id asc
-- 2. 이름에 el이 들어가는 동물 찾기
SELECT animal_id, name from animal_ins
where lower(name) like "%el%" and animal_type = "Dog"
order by name asc
-- 3. 중성화 여부 파악하기
SELECT animal_id, name,
case when (SEX_UPON_INTAKE LIKE '%NEUTERED%' OR SEX_UPON_INTAKE LIKE '%SPAYED%')then 'O' else 'X' end
from animal_ins
order by animal_id asc
-- 4. 오랜 기간 보호한 동물 (2)
SELECT ins.animal_id, ins.name from animal_ins ins, animal_outs outs
where ins.animal_id = outs.animal_id
order by datediff(outs.datetime, ins.datetime) desc
limit 2
-- 5. DATETIME에서 DATE로 형 변환
SELECT animal_id, name, DATE_FORMAT(datetime, '%Y-%m-%d') as 날짜 from animal_ins
order by animal_id asc
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
void func_1260_dfs_recursion(int n, vector<int> * graph, bool* visited) {
visited[n] = true;
cout << n << " ";
for (auto node : graph[n]) {
if (!visited[node]) {
func_1260_dfs_recursion(node, graph, visited);
}
}
}
void func_1260_bfs_queue(int n, vector<int> * graph, bool* visited) {
queue<int> q;
int now_node;
visited[n] = true;
q.push(n);
while (!q.empty()) {
now_node = q.front();
q.pop();
cout << now_node << " ";
for (auto node : graph[now_node]) {
if (!visited[node]) {
visited[node] = true;
q.push(node);
}
}
}
cout << "\n";
}
int main() {
int n, m, start_node, u, v;
cin >> n >> m >> start_node;
vector<int> *graph = new vector<int>[n+1];
bool *visited = new bool[n+1];
memset(visited, 0, sizeof(bool) * (n+1));
for (int i = 0; i < m; i++) {
cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}
for (int i = 1; i <= n; i++) {
sort(graph[i].begin(), graph[i].end());
}
func_1260_dfs_recursion(start_node, graph, visited);
cout << "\n";
memset(visited, 0, sizeof(bool) * (n + 1));
func_1260_bfs_queue(start_node, graph, visited);
return 0;
}
문제 2. 바이러스
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
static int func_2606_cnt;
void func_2606_dfs(int start, vector<int> *graph, bool* visited) {
visited[start] = true;
func_2606_cnt++;
for (auto node : graph[start]) {
if (!visited[node]) {
func_2606_dfs(node, graph, visited);
}
}
}
int main() {
int n, m, u, v;
cin >> n >> m;
vector<int> *graph = new vector<int>[n+1];
bool* visited = new bool[n+1];
memset(visited, 0, sizeof(bool) * (n+1));
func_2606_cnt = 0;
for (int i = 0; i < m; i++) {
cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}
for (int i = 1; i <= n; i++) {
sort(graph[i].begin(), graph[i].end());
}
func_2606_dfs(1, graph, visited);
cout << func_2606_cnt -1 << "\n";
return 0;
}
문제 3. 단지 번호 붙이기
#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
#include<algorithm>
#include<utility>
using namespace std;
int func_2667_bfs(int cnt, int n, queue<pair<int, int>> q, int **map, int ** v) {
int _x, _y, a=0;
pair<int, int> now, tmp;
int** direc = new int* [4];
for (int i = 0; i < 4; i++) {
direc[i] = new int[2];
if (i == 0) {
_x = 0;
_y = -1;
}
else if (i == 1) {
_x = 1;
_y = 0;
}
else if (i == 2) {
_x = 0;
_y = 1;
}
else if (i == 3) {
_x = -1;
_y = 0;
}
direc[i][0] = _x;
direc[i][1] = _y;
}
while (!q.empty()) {
now = q.front();
q.pop();
if (v[now.first][now.second] != 1) {
v[now.first][now.second] = 1;
a++;
}
for (int i = 0; i < 4; i++) {
_x = now.first + direc[i][0];
_y = now.second + direc[i][1];
if (_x < 0 || _x >= n) {
continue;
}
if (_y < 0 || _y >= n) {
continue;
}
if (map[_x][_y] == 0) {
continue;
}
if (v[_x][_y] == 1) {
continue;
}
// 방문한적 없는 좌표인데 값이 1보다 크면 현재 카운트로 덮어쓰기 및 방문처리
if (map[_x][_y] >= 1) {
v[_x][_y] = 1;
map[_x][_y] = cnt;
q.push({_x, _y});
//cout << _x << ", " << _y << "\n";
a++;
}
}
}
for (int i = 0; i < 4; i++) {
delete direc[i];
}
return a;
}
int main() {
int n, cnt =0;
string str;
queue<pair<int, int>> q;
vector<int> m;
int tmp_m;
cin >> n;
int** v = new int* [n];
for (int i = 0; i < n; i++) {
v[i] = new int[n];
for (int j = 0; j < n; j++) {
v[i][j] = 0;
}
}
int** _map = new int* [n];
for (int i = 0; i < n; i++) {
str = "";
_map[i] = new int[n];
cin >> str;
for (int j = 0; j < n; j++) {
_map[i][j] = str[j] - '0';
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (_map[i][j] == 1) {
q.push({ i, j });
tmp_m = func_2667_bfs(cnt+1, n, q, _map, v);
if (tmp_m != 0) {
m.push_back(tmp_m);
cnt++;
}
}
}
}
sort(m.begin(), m.end());
cout << cnt << "\n";
for (int i = 0; i < cnt; i++) {
cout << m[i] << "\n";
}
return 0;
}
문제 4. 유기농 배추
#include <iostream>
#include <utility>
#include <cstring>
#include <queue>
using namespace std;
int main() {
int test_case;
int n, m, k;
int u, v;
int _x, _y;
pair<int, int> dir[4] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} }; // 상, 우, 하, 좌
pair<int, int> tmp_q;
int graph_count = 0;
int** _map;
int** _visit;
queue<pair<int, int>> q;
cin >> test_case;
for (int a = 0; a < test_case; a++) {
cin >> m >> n >> k;
// Map 생성 및 초기화
_map = new int* [n];
_visit = new int* [n];
for (int i = 0; i < n; i++) {
_map[i] = new int[m];
_visit[i] = new int[m];
memset(_map[i], 0, sizeof(int) * m);
memset(_visit[i], 0, sizeof(int) * m);
}
// Map 업데이트
for (int i = 0; i < k; i++) {
cin >> u >> v;
_map[v][u] = 1;
}
graph_count = 0;
// Map 탐색
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// 지도에서 현재 좌표가 1이고 방문한 적이 없으면 현재 좌표를 q에 등록하고 방문 처리
if (_map[i][j] == 1 && _visit[i][j] != 1) {
q.push({i, j});
_visit[i][j] = 1;
graph_count++;
}
// q에 값이 있으면
while (!q.empty()) {
tmp_q = q.front();
q.pop();
// 현재 좌표에서 인접한 4방향 좌표를 검사, 위부터 시계방향
for (int i = 0; i < 4; i++) {
_x = tmp_q.first + dir[i].first;
_y = tmp_q.second + dir[i].second;
// 경계선 검사
if (_x >= n || _x < 0)
continue;
if (_y >= m || _y < 0)
continue;
// 값 검사
if (_map[_x][_y] == 0)
continue;
// 방문여부 검사
if (_visit[_x][_y] == 1)
continue;
// 방문기록 남기고 다음 작업대상에 추가
_visit[_x][_y] = 1;
q.push({_x, _y});
}
}
}
}
cout << graph_count << "\n";
// 메모리 해제
for (int i = 0; i < n; i++) {
free(_map[i]);
free(_visit[i]);
}
}
return 0;
}
문제 5. 미로 탐색
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
// 노드 정보 저장용 클래스
class func_2178_node {
public:
int x;
int y;
int value;
int visited;
};
int func_2178_BFS(int n, int m, func_2178_node **_map, int *start_node, int *end_node) {
// BFS 탐색을 위한 큐 생성 현재 노드 저장
queue<func_2178_node> q;
func_2178_node tmp_node, now_node;
// 상0, 우1, 하2, 좌3
int** direction = new int*[4];
for (int i = 0; i < 4; i++) {
direction[i] = new int[2];
if (i == 0) {
direction[i][0] = 0;
direction[i][1] = -1;
}
if (i == 1) {
direction[i][0] = 1;
direction[i][1] = 0;
}
if (i == 2) {
direction[i][0] = 0;
direction[i][1] = 1;
}
if (i == 3) {
direction[i][0] = -1;
direction[i][1] = 0;
}
}
// 시작노드의 방문 여부 변경
_map[start_node[0]][start_node[1]].visited = 1;
// 시작노드 넣기
q.push(_map[start_node[0]][start_node[1]]);
// 큐에 값이 있으면 탐색 시작
while (!q.empty()) {
// 현재 큐의 값 가져오기 + pop
now_node = q.front();
q.pop();
// 인접 노드 탐색 (시계방향으로 탐색)
for (int i = 0; i < 4; i++) {
// 현재 좌표가 좌우를 넘어가는지 확인
if (now_node.x + direction[i][0] <= 0 || now_node.x + direction[i][0] > n) {
continue;
}
// 현재 좌표가 상하를 넘어가는지 확인
if (now_node.y + direction[i][1] <= 0 || now_node.y + direction[i][1] > m) {
continue;
}
// 이동한 값이 맵 안에 있으면 노드 이동
tmp_node = _map[now_node.x + direction[i][0]][now_node.y + direction[i][1]];
// 값이 1이 아닌지 검사, 아니면 continue;
if (tmp_node.value == 0) {
continue;
}
// 방문 여부가 없는지 검사 (방문했으면 다음거)
if (tmp_node.visited) {
continue;
}
_map[tmp_node.x][tmp_node.y].visited = _map[now_node.x][now_node.y].visited + 1;
q.push(_map[tmp_node.x][tmp_node.y]);
}
}
return _map[n][m].visited;
}
int main() {
int n, m;
int* start_node = new int[2];
int* end_node = new int[2];
string str_input;
cin >> n >> m;
start_node[0] = 1;
start_node[1] = 1;
end_node[0] = n;
end_node[1] = m;
func_2178_node** map = new func_2178_node*[n+1];
for (int i = 1; i <= n; i++) {
map[i] = new func_2178_node[m+1];
}
for (int i = 1; i <= n; i++) {
cin >> str_input;
for (int j = 1; j <= m; j++) {
map[i][j].x = i;
map[i][j].y = j;
map[i][j].value = str_input[j-1] - '0';
map[i][j].visited = 0;
}
}
cout << func_2178_BFS(n, m, map, start_node, end_node) << "\n";
return 0;
}
문제 6. 토마토
#include <iostream>
#include <queue>
using namespace std;
class func_7576_tomato {
public:
int x;
int y;
int visited;
int value;
};
void func_7576_bfs(int n, int m, func_7576_tomato** box, queue<func_7576_tomato> q) {
func_7576_tomato now_tomato, tmp_tomato;
// 방향 정의 (시계방향)
int** direc = new int*[4];
int _x, _y;
for (int i = 0; i < 4; i++) {
direc[i] = new int[2];
// 상
if (i == 0) {
_x = 0;
_y = -1;
}
// 우
if (i == 1) {
_x = 1;
_y = 0;
}
// 하
if (i == 2) {
_x = 0;
_y = 1;
}
// 좌
if (i == 3) {
_x = -1;
_y = 0;
}
direc[i][0] = _x;
direc[i][1] = _y;
}
// bfs 탐색 시작
while (!q.empty ()) {
now_tomato = q.front();
q.pop();
// 각 방향별 탐색
for (int i = 0; i < 4; i++) {
// 이동한 범위가 토마토 상자 내부인지 검사 (x축)
if (now_tomato.x + direc[i][0] < 0 || now_tomato.x + direc[i][0] >= n) {
continue;
}
// 이동한 범위가 토마토 상자 내부인지 검사 (y축)
if (now_tomato.y + direc[i][1] < 0 || now_tomato.y + direc[i][1] >= m) {
continue;
}
tmp_tomato = box[now_tomato.x + direc[i][0]][now_tomato.y + direc[i][1]];
// 해당 위치가 벽인지 검사
if (tmp_tomato.value != 0) {
continue;
}
// 해당 위치에 숙성되지 않은 토마토가 있으면 숙성 시키고 몇 일차에 숙성시켰는지 입력 후 큐에 등록
box[tmp_tomato.x][tmp_tomato.y].value = 1;
box[tmp_tomato.x][tmp_tomato.y].visited = now_tomato.visited + 1;
q.push(box[tmp_tomato.x][tmp_tomato.y]);
}
}
}
int main() {
int m, n, tmp, max;
queue<func_7576_tomato> q;
// 노드 개수
cin >> m >> n;
// 노드 생성
func_7576_tomato** box = new func_7576_tomato*[n];
for (int i = 0; i < n; i++) {
box[i] = new func_7576_tomato[m];
}
// 초기화
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
box[i][j].x = i;
box[i][j].y = j;
box[i][j].visited = 0;
box[i][j].value = 0;
}
}
// 입력값 받기, 입력에 따른 값 설정
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> tmp;
box[i][j].value = tmp;
//입력 값이 1이면 큐에 등록
if (tmp == 1) {
q.push(box[i][j]);
}
}
}
func_7576_bfs(n, m, box, q);
max = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// 숙성안된 토마토가 있으면 -1
if (box[i][j].value == 0) {
max = -1;
break;
}
// 최대값 찾아서 갱신
if (max < box[i][j].visited) {
max = box[i][j].visited;
}
}
if (max == -1) {
break;
}
}
cout << max << "\n";
return 0;
}
문제 7. 토마토
문제 8. 숨바꼭질
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
void func_1697_bfs(int k, queue<int> q, int *visited) {
int now;
while (!q.empty()) {
now = q.front();
q.pop();
if (now == k) {
break;
}
if (visited[now - 1] == 0 && (now - 1) >= 0) {
visited[now - 1] = visited[now] + 1;
q.push(now-1);
}
if ( (now+1) < 100000 && visited[now + 1] == 0) {
visited[now + 1] = visited[now] + 1;
q.push(now+1);
}
if ( (now * 2) <= 100000 && visited[now * 2] == 0) {
visited[now * 2] = visited[now] + 1;
q.push(now * 2);
}
}
}
int main() {
int n, k;
cin >> n >> k;
int* visited = new int[100000];
memset(visited, 0, sizeof(int) * 100000);
queue<int> q;
q.push(n);
visited[n] = 1;
func_1697_bfs(k, q, visited);
cout << visited[k]-1 << "\n";
return 0;
}
탐색 알고리즘인 DFS(Depth First Search, 깊이 우선 탐색) 알고리즘에 대해 이해하고 직접 구현
탐색 알고리즘인 BFS(Breadth First Search, 너비 우선 탐색) 알고리즘에 대해 이해하고 직접 구현
인접리스트와 인접 행렬
그래프
위 와 같은 그래프가 있을 때, 이 그래프를 표현하는 방식은 크게 2가지(인접리스트, 인접행렬)가 있다.
각 표현 방식을 구현해보면 다음 코드와 같다.
1) 간선을 인접리스트로 변환
#include<iostream>
#include<cstring>
#include<vector>
#include<map>
using namespace std;
// 만들어진 그래프를 출력
void print_adjacency_list(map<int, vector<int>> graph) {
for (auto node : graph) {
cout << node.first << " : ";
for (auto ns : node.second) {
cout << ns << " ";
}
cout << "\n";
}
}
int main() {
int n, m, u, v;
// 최초 입력 받기
cin >> n >> m >> start_node;
// 그래프를 인접리스트 형식으로 표현
map<int, vector<int>> graph;
// 간선의 개수만큼 노드에 추가
for (int i = 0; i < m; i++) {
cin >> u >> v;
// 각 노드별로 연결된 간선을 서로 추가(무방향 또는 양방향 그래프)
graph[u].push_back(v);
graph[v].push_back(u);
}
// 생성된 인접리스트 출력
print_adjacency_list(graph);
return 0;
}
출력 결과
2) 간선을 인접행렬로 변환
#include<iostream>
using namespace std;
int main() {
int n, m, u, v;
cin >> n >> m;
// 인접행렬 생성
int** graph = new int* [n];
for (int i = 0; i < n; i++) {
graph[i] = new int[n];
}
// 인접행렬 초기화
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
graph[i][j] = 0;
}
}
// 간선 입력
for (int i = 0; i < m; i++) {
cin >> u >> v;
u--;
v--;
// 무방향 그래프
graph[u][v] = graph[v][u] = 1;
}
// 인접행렬 출력
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << graph[i][j] << " ";
}
cout << "\n";
}
return 0;
}
출력 결과
3) 인접행렬을 문자열로 입력받기
#include<iostream>
using namespace std;
int main() {
int n;
string str;
cin >> n;
int** map = new int* [n];
for (int i = 0; i < n; i++) {
str = "";
map[i] = new int[n];
cin >> str;
for (int j = 0; j < str.length(); j++) {
map[i][j] = str[j] - '0';
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j< n; j++) {
cout << map[i][j];
}
cout << "\n";
}
return 0;
}
출력 결과
4) 인접행렬을 인접리스트로 변환
#include<iostream>
#include<vector>
using namespace std;
vector<int> *Convert_adjMatrix_to_adjList(int n, int** matrix) {
vector<int> * adjlist = new vector<int>[n+1];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == 1 && i != j) {
adjlist[i+1].push_back(j+1);
}
}
sort(adjlist[i+1].begin(), adjlist[i+1].end());
}
return adjlist;
}
int main() {
int n;
string str;
cin >> n;
int** map = new int* [n];
for (int i = 0; i < n; i++) {
str = "";
map[i] = new int[n];
cin >> str;
for (int j = 0; j < str.length(); j++) {
map[i][j] = str[j] - '0';
}
}
vector<int> *adl = Convert_adjMatrix_to_adjList(n, map);
for (int i = 1; i <= n; i++) {
cout << i << " : ";
for (auto node : adl[i]) {
cout << node << " ";
}
cout << "\n";
}
return 0;
}
출력 결과
DFS (깊이 우선 탐색)
1 2 4 3 5
재귀로 DFS 구현
#include<iostream>
#include<cstring>
#include<vector>
#include<map>
using namespace std;
void dfs_recursion(int n, vector<int>* graph, bool* visited) {
cout << "start\nCurrent Node : " << n << "";
// 시작노드의 방문 여부를 체크
visited[n] = true;
for (auto node : graph[n]) {
cout << "\nN : " << n << ", Node : " << node << ", Visited : " << visited[node] << " ";
// 노드가 방문이 되어있는지 확인
if (!visited[node]) {
cout << "-> Next node : " << node << "\n";
// 방문 안된 노드의 키값을 넣음
func_1260_dfs_recursion(node, graph, visited);
}
}
cout << "\nend";
}
int main() {
int n, m, start_node, u, v;
cin >> n >> m >> start_node;
vector<int> *graph = new vector<int>[n+1];
bool *visited = new bool[n+1];
memset(visited, 0, sizeof(bool) * (n+1));
for (int i = 0; i < m; i++) {
cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}
/*
// 오름차순으로 각 벡터를 정렬시킴 (이부분 주석 해제 시 1 2 3 4 5 순서로 진행)
for (int i = 1; i <= n; i++) {
sort(graph[i].begin(), graph[i].end());
}
*/
dfs_recursion(start_node, graph, visited);
return 0;
}
재귀 방식 코드 결과
스택으로 DFS 구현
//
BFS (너비 우선 탐색)
1 2 5 3 4
큐로 BFS 구현
#include<iostream>
#include<cstring>
#include<vector>
#incldue<queue>
using namespace std;
void bfs_queue(int n, vector<int> * graph, bool* visited) {
queue<int> q;
int now_node;
visited[n] = true;
q.push(n);
while (!q.empty()) {
now_node = q.front();
q.pop();
cout << now_node << " ";
for (auto node : graph[now_node]) {
if (!visited[node]) {
visited[node] = true;
q.push(node);
}
}
}
cout << "\n";
}
int main() {
int n, m, start_node, u, v;
cin >> n >> m >> start_node;
vector<int> *graph = new vector<int>[n+1];
bool *visited = new bool[n+1];
memset(visited, 0, sizeof(bool) * (n+1));
for (int i = 0; i < m; i++) {
cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}
for (int i = 1; i <= n; i++) {
sort(graph[i].begin(), graph[i].end());
}
bfs_queue(start_node, graph, visited);
return 0;
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows;
using System.Windows.Controls;
using System.Windows.Data;
using System.Windows.Documents;
using System.Windows.Input;
using System.Windows.Media;
using System.Windows.Media.Imaging;
using System.Windows.Navigation;
using System.Windows.Shapes;
// OpenCV 사용을 위한 using
using OpenCvSharp;
using OpenCvSharp.WpfExtensions;
// Timer 사용을 위한 using
using System.Windows.Threading;
namespace WPF
{
// OpenCvSharp 설치 시 Window를 명시적으로 사용해 주어야 함 (window -> System.Windows.Window)
public partial class MainWindow : System.Windows.Window
{
// 필요한 변수 선언
VideoCapture cam;
Mat frame;
DispatcherTimer timer;
bool is_initCam, is_initTimer;
public MainWindow()
{
InitializeComponent();
}
private void windows_loaded(object sender, RoutedEventArgs e)
{
// 카메라, 타이머(0.01ms 간격) 초기화
is_initCam = init_camera();
is_initTimer = init_Timer(0.01);
// 초기화 완료면 타이머 실행
if(is_initTimer && is_initCam) timer.Start();
}
private bool init_Timer(double interval_ms)
{
try
{
timer = new DispatcherTimer();
timer.Interval = TimeSpan.FromMilliseconds(interval_ms);
timer.Tick += new EventHandler(timer_tick);
return true;
}
catch
{
return false;
}
}
private bool init_camera() {
try {
// 0번 카메라로 VideoCapture 생성 (카메라가 없으면 안됨)
cam = new VideoCapture(0);
cam.FrameHeight = (int)Cam_1.Height;
cam.FrameWidth = (int)Cam_1.Width;
// 카메라 영상을 담을 Mat 변수 생성
frame = new Mat();
return true;
}catch{
return false;
}
}
private void timer_tick(object sender, EventArgs e)
{
// 0번 장비로 생성된 VideoCapture 객체에서 frame을 읽어옴
cam.Read(frame);
// 읽어온 Mat 데이터를 Bitmap 데이터로 변경 후 컨트롤에 그려줌
Cam_1.Source = OpenCvSharp.WpfExtensions.WriteableBitmapConverter.ToWriteableBitmap(frame);
}
}
}
#include<iostream>
using namespace std;
int main(){
int n, m, sum, min, res = 0;
cin >> n >> m;
int* card = new int[n];
bool is_flag;
for (int i = 0; i < n; i++) {
cin >> card[i];
}
sum = 0;
min = m;
is_flag = true;
for (int i = 0; i < n - 1 && is_flag; i++) {
for (int j = i + 1; j < n && is_flag; j++) {
for (int k = j + 1; k < n && is_flag; k++) {
sum = card[i] + card[j] + card[k];
if (sum == m) is_flag = false;
if (min > m - sum && m >= sum) {
min = m - sum;
res = sum;
}
}
}
}
cout << res << endl;
return 0;
}
문제 2. 분해합 (브론즈 2)
#include <iostream>
#include <string>
#include <cmath>
#include <map>
using namespace std;
int func_2231_create_decompose(int a) {
int len, res = a;
len = to_string(a).length();
for (int i = len; a > 0; i--) {
res += a / pow(10, i);
a %= (int)pow(10, i);
}
return res;
}
int main() {
int a, key;
cin >> a;
map<int, int> m;
for (int i = 1; i < a; i++) {
key = func_2231_create_decompose(i);
if(!m[key])
m[key] = i;
}
cout << m[a];
return 0;
}
문제 3. 덩치 (실버 5)
/*
* 문제 내용 이해가 중요한 문제였음.
* map을 사용해서 구현한 버전
*/
#include <iostream>
#include <map>
using namespace std;
int main() {
int int_case;
int cnt, grade;
int* bulk;
cin >> int_case;
map<char, int *> m_input;
// 입력
for (int i = 0; i < int_case; i++) {
bulk = new int[2];
cin >> bulk[0] >> bulk[1];
m_input['a' + i] = bulk;
}
// 등수 : 나보다 덩치가 큰 사람의 수 + 1
for (int i = 0; i < int_case; i++) {
cnt = 1;
for (int j = 0; j < int_case; j++) {
// 덩치 : 키도 크고, 몸무게도 무거운 사람 수
if (m_input['a' + i][0] < m_input['a' + j][0] && m_input['a' + i][1] < m_input['a' + j][1]) {
cnt++;
}
}
// 등수 출력
cout << cnt << " ";
}
for (int i = 0; i < int_case; i++) {
delete m_input['a' + i];
}
return 0;
}
/*
* 문제 내용 이해가 중요한 문제였음.
* 2차원 Array를 사용해서 구현한 버전
*/
#include <iostream>
using namespace std;
int main() {
int int_case, cnt;
cin >> int_case;
int** arr = new int*[int_case];
int* bulk;
for (int i = 0; i < int_case; i++) {
bulk = new int[2];
cin >> bulk[0] >> bulk[1];
arr[i] = bulk;
}
for (int i = 0; i < int_case; i++) {
cnt = 1;
for (int j = 0; j < int_case; j++) {
if (arr[i][0] < arr[j][0] && arr[i][1] < arr[j][1]) {
cnt++;
}
}
cout << cnt << " ";
}
return 0;
}
문제 4. 체스판 다시 칠하기 (실버 5)
#include <iostream>
#include <cstring>
using namespace std;
int func_1018_bitmask(char **_map) {
int cnt_1 = 0, cnt_2 = 0;
char filter_1[8][8] = {
{0, 1, 0, 1, 0, 1, 0, 1},
{1, 0, 1, 0, 1, 0, 1, 0},
{0, 1, 0, 1, 0, 1, 0, 1},
{1, 0, 1, 0, 1, 0, 1, 0},
{0, 1, 0, 1, 0, 1, 0, 1},
{1, 0, 1, 0, 1, 0, 1, 0},
{0, 1, 0, 1, 0, 1, 0, 1},
{1, 0, 1, 0, 1, 0, 1, 0}
};
char filter_2[8][8] = {
{1, 0, 1, 0, 1, 0, 1, 0},
{0, 1, 0, 1, 0, 1, 0, 1},
{1, 0, 1, 0, 1, 0, 1, 0},
{0, 1, 0, 1, 0, 1, 0, 1},
{1, 0, 1, 0, 1, 0, 1, 0},
{0, 1, 0, 1, 0, 1, 0, 1},
{1, 0, 1, 0, 1, 0, 1, 0},
{0, 1, 0, 1, 0, 1, 0, 1}
};
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
if ( !(_map[i][j]^filter_1[i][j]) ) {
cnt_1++;
}
if (!(_map[i][j] ^ filter_2[i][j])) {
cnt_2++;
}
}
}
if (cnt_1 >= cnt_2) return cnt_2;
else return cnt_1;
}
int main() {
int n, m;
int min, cnt;
string tmp;
cin >> n >> m;
char** tmp_map = new char* [8];
for (int i = 0; i < 8; i++) {
tmp_map[i] = new char[8];
}
char** bwmap = new char* [n];
for (int i = 0; i < n; i++) {
bwmap[i] = new char[m];
}
for (int i = 0; i < n; i++) {
cin >> tmp;
for (int j = 0; j < m; j++) {
if (tmp[j] == 'B') {
bwmap[i][j] = 1;
}
else {
bwmap[i][j] = 0;
}
}
}
cnt = 0;
min = 64;
for (int i = 0; i <= n - 8; i++) {
for (int j = 0; j <= m - 8; j++) {
for (int a = i, aa = 0; a < i + 8; a++, aa++) {
for (int b = j, bb = 0; b < j + 8; b++, bb++) {
tmp_map[aa][bb] = bwmap[a][b];
}
}
cnt = func_1018_bitmask(tmp_map);
if (cnt < min) {
min = cnt;
}
}
}
cout << min << "\n";
return 0;
}
문제 5. 영화감독 숌 (실버 5)
#include <iostream>
#include <cstring>
using namespace std;
int main() {
int n, cnt=0;
string tmp;
cin >> n;
for (int i = 666; i < 2100000000; i++) {
tmp = to_string(i);
if (tmp.find("666") != string::npos) {
cnt++;
if (cnt > 10000) break;
if (cnt == n) {
cout << tmp << "\n";
}
}
}
}
