정화 코딩

5/12. 바이러스 (백준 2606번) https://www.acmicpc.net/problem/2606 //C++#include #include #include using namespace std;vector visited;vector> g;int n;int bfs(int start) { queue q; int cnt = 0; q.push(start); visited[start] = true; while (!q.empty()) { int cur = q.front(); q.pop(); for (int nxt: g[cur]) { if (!visited[nxt]) { q.push(nxt); ..

A. 1, 2, 3 더하기 (백준 9095번) https://www.acmicpc.net/problem/9095 #pythonimport sysinput = sys.stdin.readlinet = int(input())dp = [0] * 12dp[1] = 1dp[2] = 2dp[3] = 4for i in range(4, 12): dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]for _ in range(t): n = int(input()) print(dp[n])n을 1, 2, 3의 합으로 나타내려면 다음과 같은 경우의 수가 있다. (여기서 주의할 점은 1+2와 2+1가 다른 경우라는 것이다.)1) (n-1)까지 만들고 1을 더하기2) (n-2)까지 만들고 2를 더..

거리의 합 2 (백준 23330번) https://www.acmicpc.net/problem/23330문제 해석이런식으로 n개의 점이 수직선 위에 놓여 있고, 모든 점들의 쌍에 대해 두 점 사이의 거리의 합을 구하는 문제이다. 첫번째 풀이우선 가장 직관적인 풀이로 풀어보자. //C++#include #include #include using namespace std;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; vector data(n); for (int i = 0; i > data[i]; } long long sum = 0; for (int i ..

1. LCS 알고리즘 설명어떤 두 문자열이 얼마나 유사한지를 수치화하기 위해 longest common subsequence(LCS)를 구한다. LCS란 공통 문자열 중 길이가 가장 긴 문자열을 말한다. 이 때 공통 문자열을 이루는 문자들 사이에 다른 문자열이 있어도 상관없으며 공통 문자열을 이루는 문자들의 순서만 동일하면 된다. LCS가 길수록 두 문자열이 유사도가 높다고 할 수 있다. 이 LCS의 길이와 LCS를 구하는 알고리즘이 LCS 알고리즘이며, 이를 직접 코드로 구현해보고자 한다. 2. LCS 알고리즘 구현 코드 (python)입력: 첫번째 줄에 문자열 X를 입력하고 두번째 줄에 문자열 Y를 입력한다. (문자열을 입력할 때는 문자와 문자 사이에 공백을 두고 입력한다.) 출력: 첫번째 줄에 LC..

087. 2×n 타일링 (백준 11726번) https://www.acmicpc.net/problem/11726 import sysinput = sys.stdin.readlinem = 10007n = int(input())# dp: 순열dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]dp[0][0] = 1for i in range(1, n + 1): dp[i][0] = dp[i][i] = 1 for j in range(1, i): dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]ans = 0i = nj = 0while i >= j: ans = (ans + dp[i][j]) % m i -= 1 ..

5/3. 랜선 자르기 (백준 1654번) https://www.acmicpc.net/problem/1654 //C++#include #include using namespace std;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int k, n; cin >> k >> n; vector data(k); for (int i = 0; i > data[i]; } long long l = 0; long long r = data[0] + 1; while (l = n) l = m + 1; else if (cnt 전형적인 매개변수탐색 문제인 것 ..

A. 돌 게임 (백준 9655번) https://www.acmicpc.net/problem/9655 #python import sys input = sys.stdin.readline n = int(input()) if n % 2 == 0: print("CY") else: print("SK") 규칙을 찾으려고 몇 개 적어봤는데, 한 8까지 적어보니까 그냥 n이 홀수인 경우에는 상근이가 이기고 n이 짝수인 경우에는 창영이가 이기는 것 같은데..?? 라는 생각이 들었다. 뭔가 아닐 것 같지만 일단 한번 제출해봤는데 이왜진... (정답) B. 수열 (백준 2491번) https://www.acmicpc.net/problem/2491 #python import sys input = sys.stdin.readlin..

4/9. 통계학 (백준 2108번) https://www.acmicpc.net/problem/2108 //C++ #include #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, sum = 0; cin >> n; vector data(n); for (int i = 0; i > data[i]; sum += data[i]; } sort(data.begin(), data.end()); int maxCnt = 0; vector cnt(8001, 0); for (int x: data) { cnt[x + 4000]++..