분류 전체보기

[백준 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차원 배열로 구현하였습니다. 단, 주의할 점이 몇가지 있습니다. ⚠️ 주의할 점 다음 칸이 파란색인 경우, 방향을 반대로 바꾼 후, 이동하려는 칸이 파란색이거나 체스판을 벗어나는 경우 움직이지 않아야 한다. 다음 칸이 파란색인 경우 방향을 반대로 바꾼 후, 이동하려는 칸이 빨간색인 경우 말을 ..

[백준 17779번] 게리맨더링 2 (C/C++)

https://www.acmicpc.net/problem/17779 17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름 www.acmicpc.net 게리맨더링 문제는 기준점, d1, d2의 모든 경우의 수에 대해 각 선거구의 인구 수를 계산하여 문제를 해결할 수 있습니다. 알고리즘의 기본 틀은 아래와 같습니다. 각 기준점, d1, d2에 대해 2번부터 수행 경계선인 경우 board 배열에 5를 표시한다. 각 칸에 대해 3-1부터 수행 3-1. 경계선이고, 경계선의 왼쪽 부분인 경우, 오른쪽으로 이동하며 5를 저장한다. (단, 다른 경계선을 만난 경..

[백준 16986번] 인싸들의 가위바위보 (C/C++)

https://www.acmicpc.net/problem/16986 16986번: 인싸들의 가위바위보 두 사람이 같은 손동작을 내어 무승부가 발생할 경우 경기 진행 순서상 뒤인 사람이 이긴 것으로 간주함에 다시 한 번 유의한다. 구체적으로, 경기 진행 순서는 지우, 경희, 민호 순으로 고정되 www.acmicpc.net 인싸들의 가위바위보 문제는 백트래킹을 이용하여 해결할 수 있습니다. 백트래킹은 next_permutation 함수를 사용하여 수행할 수 있습니다. 손동작 수가 N개일 때, 1 ~ N으로 이루어진 순열의 각 경우의 수에 대해 게임을 진행하면 됩니다. 아래는 전체 코드입니다. #include using namespace std; int table[9][9]; int b[20], c[20]; ..