A L I D A
1 Introduction
본 포스트에서는 알고리즘 문제 풀이에 관련된 내용을 포스팅한다. 대부분의 문제들은 백준에서 풀었으며 검색창에 boj.kr/{#} 를 입력하여 검색할 수 있다. 이 때, # 부문에 문제 번호를 입력하면 된다.
ex) boj.kr/2751
코드에서 사용한 #include <bits/stdc++.h> 헤더는 모든 표준헤더를 포함하는 헤더로써 필자가 테스트한 Ubuntu 18.04 환경에서 정상적으로 컴파일되었다.
ios_base::sync_with_stdio(false);
cin.tie(0);
위 코드는 시간초과 구문을 피하기 위해 C++의 출력속도를 높이는 코드이다. 또한 속도를 높이기 위해 std::endl 대신 '\n' 를 통해 새 라인을 추가한다.
2 Basic
2.1 2751 수 정렬하기2
#include <bits/stdc++.h>
using namespace std;
int main(int argc, char **argv){
ios_base::sync_with_stdio(false);
cin.tie(0);
// N을 입력받는다.
int N;
cin >> N;
vector<int> v;
// 숫자들을 입력받는다.
for(int i=0; i<N; i++) {
int num;
cin >> num;
v.push_back(num);
}
// vector를 오름차순으로 정렬한다.
sort(v.begin(), v.end());
// 정렬한 vector를 출력한다.
for(auto it : v) {
cout << it << '\n';
}
return 0;
}2.2 10989 수 정렬하기3
#include <bits/stdc++.h>
using namespace std;
int arr[10001];
int main(int argc, char **argv){
ios_base::sync_with_stdio(false);
cin.tie(0);
int N;
cin >> N;
// 문제 조건 상 N의 값이 매우 크므로 이를 전부 vector에 넣고 정렬하기에는 시간이 오래걸린다
// 따라서 arr 배열에 카운트를 추가하는 방식으로 변경한다
for(int i=0; i<N; i++) {
int tmp;
cin >> tmp;
arr[tmp]++;
}
// 루프를 돌면서 카운트가 추가된 배열들만 카운트 개수만큼 출력한다
for(int i=1; i<=10000; i++) {
for(int j=0; j<arr[i]; j++) {
cout << i << '\n';
}
}
return 0;
}2.3 11650 좌표 정렬하기
#include <bits/stdc++.h>
using namespace std;
int main(int argc, char **argv){
ios_base::sync_with_stdio(false);
cin.tie(0);
// N을 입력받는다.
int N;
cin >> N;
vector<pair<int,int>> coords;
// 좌표를 입력받는다.
for(int i=0; i<N;i++){
int x,y;
cin >> x>>y;
coords.push_back(make_pair(x,y));
}
// 좌표를 정렬한다. 이 때, lambda 함수를 사용하여 정렬한다.
sort(coords.begin(), coords.end(), [](const pair<int,int> &a,
const pair<int,int> &b) {
if(a.first != b.first) {
return a.first < b.first;
}
else {
return a.second < b.second;
}
});
// 정렬한 좌표를 출력한다.
for(auto it : coords) {
cout << it.first << " " << it.second << '\n';
}
return 0;
}2.4 11651 좌표 정렬하기2
#include <bits/stdc++.h>
using namespace std;
int main(int argc, char **argv){
ios_base::sync_with_stdio(false);
cin.tie(0);
// N을 입력받는다.
int N;
cin >> N;
vector<pair<int,int>> coords;
// 좌표를 입력받는다.
for(int i=0; i<N;i++){
int x,y;
cin >> x>>y;
coords.push_back(make_pair(x,y));
}
// 좌표를 정렬한다. 이 때, lambda 함수를 사용하여 정렬한다.
sort(coords.begin(), coords.end(), [](const pair<int,int> &a,
const pair<int,int> &b) {
if(a.second != b.second) {
return a.second < b.second;
}
else {
return a.first < b.first;
}
});
// 정렬한 좌표를 출력한다.
for(auto it : coords) {
cout << it.first << " " << it.second << '\n';
}
return 0;
}2.5 10814 나이순 정렬
#include <bits/stdc++.h>
using namespace std;
int main(int argc, char **argv){
ios_base::sync_with_stdio(false);
cin.tie(0);
int N;
cin>>N;
vector<pair<int, string>> members;
// 멤버를 입력받는다.
for(int i=0; i<N;i++) {
int age;
string name;
cin >> age >> name;
members.push_back(make_pair(age, name));
}
// 멤버를 정렬한다. 이 때, stable_sort함수를 사용하면 변경되지 않는 항목들은 움직이지 않는다.
stable_sort(members.begin(), members.end(), [](const pair<int,string> &a,
const pair<int, string> &b) {
return a.first < b.first;
});
// 정렬한 멤버를 출력한다.
for(auto it : members) {
cout << it.first << " " << it.second << '\n';
}
return 0;
}
2.6 10825 국영수
#include <bits/stdc++.h>
using namespace std;
// 학생의 구조체 선언
typedef struct _Student {
string name;
int kor, eng, math;
} Student;
int main(int argc, char **argv){
ios_base::sync_with_stdio(false);
cin.tie(0);
int N;
cin >> N;
vector<Student> students;
// 각 필드를 입력으로 받은 다음 벡터에 넣는다
for(int i=0; i<N; i++) {
string name;
int kor, eng, math;
cin >> name >> kor >> eng >> math;
Student s;
s.name = name;
s.kor = kor;
s.eng = eng;
s.math = math;
students.push_back(s);
}
// 문제에서 요구하는 순서대로 비교함수를 작성한다
sort(students.begin(), students.end(), [](const Student &a, const Student &b) {
if(a.kor != b.kor) {
return a.kor > b.kor;
}
else if(a.eng != b.eng) {
return a.eng < b.eng;
}
else if(a.math != b.math) {
return a.math > b.math;
}
else {
return a.name < b.name;
}
});
for(auto it : students) {
cout << it.name << '\n';
}
return 0;
}
2.7 2004 조합 0의 개수
#include <bits/stdc++.h>
using namespace std;
// total을 소인수분해했을 때 num의 개수를 출력하는 함수
int solve(int total, int num) {
int cnt = 0;
while(total >= num) {
cnt += total / num;
total /= num;
}
return cnt;
}
int main(int argc, char** argv) {
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);
int N, M, five, two;
cin >> N >> M;
// mCn = m! / n! (m-n)! 이므로 m!에서 특정 수가 몇개 있는지 계산하는 알고리즘을 통해 mCn에 2와 5가 몇개 있는지 계산한다
five = solve(N, 5) - solve(N-M, 5) - solve(M, 5);
two = solve(N, 2) - solve(N-M, 2) - solve(M, 2);
// 2 또는 5의 개수 중 더 적은 개수만큼 0이 존재한다
if(five >= two)
cout << two << '\n';
else
cout << five << '\n';
return 0;
}3 Graph (DFS, BFS)
3.1 1260 DFS와 BFS
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> vec;
queue<int> q;
int check[1001];
void dfs(int now) {
check[now] = 1;
cout << now << ' ';
// 재귀적으로 그래프를 탐색한다.
for(int i=0; i<vec[now].size(); i++) {
int next = vec[now][i];
if(check[next]==0) {
dfs(next);
}
}
}
void bfs(int now) {
q.push(now);
check[now] = 1;
// queue가 빌 때까지 그래프를 탐색한다.
while(!q.empty()) {
now = q.front();
q.pop();
cout << now << ' ';
// 현재 위치에서 갈 수 있는 모든 곳을 queue에 담는다.
for(int i=0; i<vec[now].size(); i++) {
int next = vec[now][i];
if(check[next] == 0) {
q.push(next);
check[next] = 1;
}
}
}
}
int main(int argc, char **argv){
ios_base::sync_with_stdio(false);
cin.tie(0);
int N,M,V;
cin >>N>>M>>V;
vec.resize(N+1);
// 그래프에 데이터를 넣는다.
for(int i=0; i<M; i++) {
int a,b;
cin>>a>>b;
vec[a].push_back(b);
vec[b].push_back(a);
}
// 문제에서 방문할 수 있는 정점이 여러개일 경우 정점번호가 작은 것부터 방문하기 위해 정렬해준다.
for(int i=1; i<=N; i++) {
sort(vec[i].begin(), vec[i].end());
}
dfs(V);
cout << '\n';
// 방문 정보 초기화
memset(check,0,sizeof(check));
bfs(V);
return 0;
}3.2 11724 연결 요소의 개수
#include <bits/stdc++.h>
using namespace std;
bool check[1001];
vector<vector<int>> graph;
void dfs(int now) {
if(check[now]) return;
// DFS를 수행하면서 방문하는 노드에 방문 표시를 기록한다.
check[now] = 1;
for(int i=0; i<graph[now].size(); i++) {
int next = graph[now][i];
if(!check[next]) {
dfs(next);
}
}
}
int main(int argc, char **argv){
ios_base::sync_with_stdio(false);
cin.tie(0);
int N,M;
cin>>N>>M;
graph.resize(N+1);
// 그래프에 데이터를 입력한다.
for(int i=0;i<M;i++) {
int u,v;
cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}
int count=0;
// 모든 노드에 대해 DFS를 수행한다. 한 번의 루프가 끝났음에도 check[i]==0인 곳이 존재하면 연결되어 있지 않다는 뜻이므로 카운트를 증가시킨다.
for(int i=1; i<=N; i++) {
if(check[i]==0) {
count++;
}
dfs(i);
}
cout << count << '\n';
return 0;
}3.3 2178 미로 탐색
#include <bits/stdc++.h>
using namespace std;
// 상하좌우 이동 변수 설정
const int roff[4] = {-1,1,0,0};
const int coff[4] = {0,0,-1,1};
int main(int argc, char **argv){
int R, C;
cin >> R >> C;
int world[100][100];
int visited[100][100];
memset(world, 0, sizeof(world));
memset(visited, 0, sizeof(visited));
// 맵을 입력받는다
for(int r=0; r<R; r++) {
for(int c=0; c<C; c++) {
scanf("%1d", &world[r][c]);
}
}
visited[0][0] = 1;
// 시작 지점(0,0)을 큐에 담는다
queue<int> Q;
Q.push(0);
int ans=1;
while(true) {
int qsize = Q.size();
for(int i=0; i<qsize; i++) {
int r = Q.front() / 100;
int c = Q.front() % 100;
Q.pop();
// 큐에 담긴 r,c가 맵의 마지막에 도달하면 프로그램을 종료한다
if(r == R-1 && c == C-1) {
cout << ans << '\n';
return 0;
}
// 상하좌우 움직이면서 이동가능한 곳이 있으면 큐에 담는다. 이 때 해시를 사용하여 담는다.
for(int d=0; d<4; d++) {
int nr = r + roff[d];
int nc = c + coff[d];
// 맵 밖을 벗어난 경우
if(nr<0 || nr >= R || nc<0 || nc >= C) continue;
// 맵 위치가 0인 경우
if(world[nr][nc]==0) continue;
// 이미 방문한 곳인 경우 스킵
if(visited[nr][nc]) continue;
visited[nr][nc] = 1;
Q.push(nr*100 + nc);
}
}
ans++;
}
return 0;
}
3.4 1707 이분 그래프
#include <bits/stdc++.h>
using namespace std;
// 입력 그래프가 이분 그래프로 나뉘면 true를 리턴하고 나뉘지 않으면 false를 리턴하는 함수
bool IsBipartite(vector<vector<int>> &graph) {
vector<int> color(graph.size(),0);
queue<int> Q;
for(int i=0; i<graph.size(); i++) {
if(color[i] != 0) continue;
Q.push(i);
while(!Q.empty()) {
for(int j=0; j<Q.size(); j++) {
int curr = Q.front();
Q.pop();
int adj_color = 0;
// 현재 그래프와 연결된 다음 레벨의 노드들을 탐색하면서
for(int next : graph[curr]) {
// 색상이 없으면 큐에 추가하고 해당 loop을 탈출하면 색상을 추가한다
if(color[next] == 0) Q.push(next);
else {
if(adj_color==0) {
adj_color = color[next];
}
// 인접색깔과 다음 레벨 노드의 색깔이 다른 경우 이분그래프 조건에 위배하므로 false를 리턴한다
else if(adj_color != color[next]) {
return false;
}
}
}
color[curr] = (adj_color==0) ? 1 : -1*adj_color; // 큐 loop이 넘어갈 때마다 색상을 -1, 1로 반전시킨다
}
}
}
return true;
}
int main(int argc, char **argv){
ios_base::sync_with_stdio(false);
cin.tie(0);
int K;
cin >> K;
// 테스트 케이스만큼 루프를 돈다
for(; K>0; K--) {
int V,E;
cin >> V >> E;
vector<vector<int>> graph(V);
for(int i=0; i<E; i++) {
int start,end;
cin >> start >> end;
// index는 보통 0부터 시작하므로 1씩 빼준다
graph[start-1].push_back(end-1);
graph[end-1].push_back(start-1);
}
if(IsBipartite(graph)) cout << "YES\n";
else cout << "NO\n";
}
return 0;
}
4 Binary Search
4.1 2805 나무 자르기
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> trees;
int main(int argc, char **argv){
ios_base::sync_with_stdio(false);
cin.tie(0);
int N, M;
cin>>N>>M;
// 나무의 크기를 입력한다.
for(int i=0; i<N; i++) {
int tree;
cin >> tree;
trees.push_back(tree);
}
ll lo=0;
ll hi=1000000000;
ll mid;
// 루프를 돌면서 이분탐색
while(lo < hi) {
mid = (lo+hi) >> 1;
ll result=0;
for(int i=0; i<trees.size(); i++) {
int cut = trees[i] - mid;
if(cut > 0) {
result += cut; // 잘린 값이 양수일 경우에만 result에 저장한다.
}
}
if (result >= M) {
lo = mid + 1;
}
else {
hi = mid;
}
}
cout << lo - 1 << '\n';
return 0;
}
4.2 2110 공유기 설치
#include <bits/stdc++.h>
using namespace std;
int N,C;
vector<int> v;
// 현재 갭(mid) 크기로 공유기를 원하는 만큼(C) 설치할 수 있는지 확인하는 함수
bool Solve(int mid) {
int count=1;
int curr = v[0];
for(int i=1; i<N; i++) {
// 공유기 사이의 거리가 갭(mid)보다 큰 경우
if(v[i] - curr >= mid) {
count++; // 공유기 1개를 설치할 수 있다.
curr = v[i];
}
}
// 공유기가 원하는 개수 이상 설치되면 true를 반환한다
if(count >= C) {
return true;
}
return false;
}
int main(int argc, char **argv){
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>N>>C;
for(int i=0; i<N; i++) {
int num;
cin >> num;
v.push_back(num);
}
// 공유기 좌표를 정렬한다
sort(v.begin(), v.end());
int left = 1;
int right = v[v.size()-1] - v[0];
int ans=0;
// 공유기 간 갭을 mid로 설정하여 이분탐색으로 문제를 푼다
while(left <= right) {
int mid = (left + right) / 2;
// 현재 갭(mid) 크기로 공유기를 원하는 개수(C) 이상 설치할 수 있는 경우
if(Solve(mid)) {
ans = max(ans, mid);
left = mid + 1;
}
else { // 없는 경우
right = mid-1;
}
}
cout << ans << '\n';
return 0;
}
5 Dynamic Programming
5.1 1463 1로 만들기
#include <bits/stdc++.h>
using namespace std;
int D[1000001];
int main(int argc, char **argv){
ios_base::sync_with_stdio(false);
cin.tie(0);
int N;
cin >> N;
D[0] = 0;
D[1] = 0;
// D[N] = min(D[N-1], D[N/2], D[N/3]) + 1
// 위 수식을 코드로 구현한다
for(int i=2; i<=N; i++) {
D[i] = D[i-1] + 1;
if(i%2 == 0) {
D[i] = min(D[i], D[i/2] + 1);
}
if(i%3 == 0) {
D[i] = min(D[i], D[i/3] + 1);
}
}
cout << D[N] << '\n';
return 0;
}
5.2 11726 2xn 타일링
#include <bits/stdc++.h>
using namespace std;
int D[1001]= {0,1,2};
int main(int argc, char **argv){
ios_base::sync_with_stdio(false);
cin.tie(0);
int N;
cin >> N;
D[0] = 0;
D[1] = 1;
D[2] = 2;
// D[i] = D[i-1] + D[i-2] 식을 코드로 구현한다. 문제의 조건에 맞게 10007로 나누는 코드 또한 적용한다.
for(int i=3; i<=N; i++) {
D[i] = (D[i-1]%10007 + D[i-2]%10007) % 10007;
}
cout << D[N] << '\n';
return 0;
}
5.3 11727 2xn 타일링 2
#include <bits/stdc++.h>
using namespace std;
int main(int argc, char** argv) {
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);
int N;
cin >> N;
int d[1001];
d[0] = d[1] = 1;
// 점화식 d[n] = d[n-1] + 2*d[n-2]을 구현한 코드
// 문제의 조건에 따라 10007로 나눈 나머지를 저장한다
for(int i=2; i<=N; i++) {
d[i] = d[i-1] + 2*d[i-2];
d[i] %= 10007;
}
cout << d[N] << '\n';
return 0;
}6 References
'Software' 카테고리의 다른 글
| Emacs 에디터 사용법 설명 및 C++/Python 개발환경설정 (0) | 2022.01.06 |
|---|---|
| Vim 에디터 사용법 설명 및 C++/Python 개발환경설정 (0) | 2022.01.06 |
| cmake 사용법 및 다양한 옵션 정리 (0) | 2022.01.06 |
| x11vnc 원격 접속 서버 설치 및 사용법 정리 (0) | 2022.01.04 |
| TI-Nspire-CX-CAS 계산기 사용법 및 다양한 기능 설명 (3) | 2022.01.03 |
