Algorithm

[백준 11724번] 연결 요소의 개수 (C++)

https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 연결 요소의 개수 문제는 BFS 또는 DFS를 이용하여 부분 그래프의 개수를 계산하여 해결할 수 있습니다. 간선 정보를 입력 받아 인접 리스트를 만들고, 각 정점에 대해 BFS 또는 DFS를 수행하면 부분 그래프의 개수를 구할 수 있습니다. 아래는 전체 코드입니다. #include using namespace std; #define u..

[백준 1931번] 회의실 배정 (C++)

https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 회의실 배정 문제는 그리디 알고리즘을 이용하여 해결할 수 있습니다. 만약 시작 시간이 가장 빠른 것을 선택하고, 이후 종료 시간보다 시작 시간이 크거나 같은 회의 중 시작 시간이 가장 작은 것을 선택한다면, 시작 시간이 가장 빨라도 회의 시간이 긴 경우 사용 가능한 회의의 수가 최대가 되지 않을 수 있습니다. 따라서 종료 시간이 가장 빠른 것을 선택하고, 종료 시간 이후 시작하는 것 중 가장 빨리 끝나는 것을 선택하면 됩니다. 즉, 종료 시간을 기준으로 정렬한 다음, 시작 시간이 전 회의가 종료 시간보다 같거나 ..

[백준 2606번] 바이러스 (C++)

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 바이러스 문제는 네트워크 상에서 연결되어 있는 컴퓨터의 쌍을 입력 받아 인접 리스트에 저장하고, 인접 리스트를 이용하여 BFS를 수행하여 해결할 수 있습니다. 아래는 전체 코드입니다. #include using namespace std; bool vis[101]; int main(){ ios::sync_with_stdio(0); cin.tie(0); int n, m; cin >> n >> m; vect..

[백준 1620번] 나는야 포켓몬 마스터 이다솜 (C++)

https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 나는야 포켓몬 마스터 이다솜 문제는 N이 최대 100,000이 될 수 있으므로, for문 이용하여 하나씩 탐색하면 시간초과가 발생할 수 있기 때문에 이분탐색을 이용하여 해결할 수 있습니다. 또한, 문자열과 숫자의 이분탐색을 나누어서 하기 위해 두 개의 벡터를 사용하고, 각각 번호와 이름을 기준으로 정렬한 다음 이분탐색을 수행해주면 됩니다. 아래는 전체 코드입니다. #i..

[백준 9095번] 1, 2, 3 더하기 (C/C++)

https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 1, 2, 3 더하기 문제는 백트래킹 또는 다이나믹 프로그래밍을 이용하여 해결할 수 있습니다. th번째에서 1, 2, 3 중에 선택하고, th + 1번째를 선택하도록 하면 됩니다. 아래는 백트래킹을 이용한 코드입니다. #include using namespace std; int selected[11]; int n, m, ans = 0; void back(int th){ int s = 0; for(int i = 0; i < th - 1; i++) s += selected[i]; // 현재까지 선택..

[백준 1463번] 1로 만들기 (C/C++)

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 1로 만들기 문제는 BFS 또는 다이나믹 프로그래밍을 이용하여 해결할 수 있습니다. ⚠️ 주의! N의 최대 값인 10의 6승도 방문 표시 할 수 있도록 방문 표시 배열의 크기를 충분히 주어야 합니다. 아래는 BFS를 이용한 코드입니다. #include using namespace std; int vis[1000001]; void bfs(int n){ queue q; q.push(n); vis[n] = 1; while(!q.empty()){ int cur = q.front(); q.pop(); if(cur < 1..

[백준 11723번] 집합 (C++)

https://www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 집합 문제는 set container를 사용하면 시간 초과가 발생합니다. 따라서 x가 S에 존재하는 지 나타내는 bool 배열을 이용하면 문제를 해결할 수 있습니다. 삽입 할 때는 해당 위치를 true로, 제거할 때는 false로 만들어주면 됩니다. 아래는 전체 코드입니다. #include using namespace std; int main(){ ios::sync_with_stdio(0); cin.tie(0); int n; cin..

[백준 17837번] 새로운 게임 2 (C/C++)

https://www.acmicpc.net/problem/17837 17837번: 새로운 게임 2 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하 www.acmicpc.net 새로운 게임은 게임 규칙에 따라 코드를 작성해주시면 되며, 각 칸 위에 놓인 말들을 저장하는 벡터의 2차원 배열로 구현하였습니다. 단, 주의할 점이 몇가지 있습니다. ⚠️ 주의할 점 다음 칸이 파란색인 경우, 방향을 반대로 바꾼 후, 이동하려는 칸이 파란색이거나 체스판을 벗어나는 경우 움직이지 않아야 한다. 다음 칸이 파란색인 경우 방향을 반대로 바꾼 후, 이동하려는 칸이 빨간색인 경우 말을 ..