나그네

9251번: LCS 문제 https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 풀이 입력된 두 문자열을 비교하면서 LCS(최장 공통 부분 수열)의 길이를 찾는 문제. 가능한 모든 경우의 수를 확인하면 시간초과가 나기 때문에 dp를 이용해 풀어야 한다. 예제를 통해 설명을 해보자. 비교하는 두 문자열은 "ACAYKP"와 "CAPCAK"다. 최장 공통 부분 수열은 "ACAK"로 길이는 4다. 0 A C A Y..

1269번: 대칭 차집합 문제 https://www.acmicpc.net/problem/1269 1269번: 대칭 차집합 첫째 줄에 집합 A의 원소의 개수와 집합 B의 원소의 개수가 빈 칸을 사이에 두고 주어진다. 둘째 줄에는 집합 A의 모든 원소가, 셋째 줄에는 집합 B의 모든 원소가 빈 칸을 사이에 두고 각각 주어 www.acmicpc.net 풀이 C++ STL인 map을 사용하여 쉽게 풀 수 있다. A, B 집합을 입력받고 A집합에 없는 B집합의 원소의 수, B집합에 없는 A집합의 원소의 수를 구해 더한다. 코드 #include using namespace std; int main() { // 입력 int n, m, cnt = 0, x; cin >> n >> m; map A, B; for (int ..

1267번: 핸드폰 요금 문제 https://www.acmicpc.net/problem/1267 1267번: 핸드폰 요금 동호가 저번 달에 이용한 통화의 개수 N이 주어진다. N은 20보다 작거나 같은 자연수이다. 둘째 줄에 통화 시간 N개가 주어진다. 통화 시간은 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 30초 미만이거나 60초 미만이어도 요금이 나오므로 나눈 후 1을 더하고 요금을 곱하면 된다. 코드 #include using namespace std; int main() { int n, time, y = 0, m = 0; cin >> n; for (int i = 0; i > time; y += 10 * (time / 30 + 1); m..

14622번: 소수 게임 문제 https://www.acmicpc.net/problem/14622 14622번: 소수 게임 인하대학교에 다니는 대웅이는 정수론을 정말 좋아한다. 정수론을 광적으로 좋아하는 대웅이는 어느 순간부터 소수를 외우기 시작했고 어떤 수를 말하면 그 수가 소수인지 아닌지 판별할 수 있 www.acmicpc.net 풀이 에라토스테네스의 체로 미리 500만 이하의 소수를 구해놓은 다음, 입력 범위를 주의하며 차례대로 조건에 따라 구현하면 되는 문제다. 입력받은 수에 따라 조건을 나누어보겠다. 1. 이미 등장한 소수인 경우 이미 등장한 소수인 경우엔 자신이 -1000점을 얻는다. 2. 처음 등장하는 소수인 경우 처음 등장한 소수인 경우엔 해당 소수를 방문처리하고 정렬이 오름차순인 우선순위..

14490번: 백대열 문제 https://www.acmicpc.net/problem/14490 14490번: 백대열 n과 m이 :을 사이에 두고 주어진다. (1 ≤ n, m ≤ 100,000,000) www.acmicpc.net 풀이 N, M을 입력받아 최대한 약분하여 출력하는 문제다. 당연 최대공약수로 나누어주면 그만이다. 입력이 100:10 같은 형태로 입력되기 때문에 cin이 아닌 scanf로 입력을 받았다. 코드 #include using namespace std; // 유클리드 호제법 int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } int main() { int n, m; scanf("%d:%d", &n, &m); int g = gcd(n, m..

1071번: 소트 문제 https://www.acmicpc.net/problem/1071 1071번: 소트 N개의 정수가 주어지면, 이것을 연속된 두 수가 연속된 값이 아니게 정렬(A[i] + 1 ≠ A[i+1])하는 프로그램을 작성하시오. 가능한 것이 여러 가지라면 사전순으로 가장 앞서는 것을 출력한다. www.acmicpc.net 풀이 N개의 수를 입력받아 A[i]+1 ≠ A[i+1]를 만족하게 정렬하여 사전순으로 가장 앞서는 것을 출력하는 문제다. 그리디 알고리즘으로 풀면 된다. 두 시간 정도 들여서 AC 받았다. 가장 중요한 두가지가 있는데 첫 번째는 사전순으로 가장 앞서는 것이기 때문에 수를 정렬해 주고 시작해야 한다. 둘째는 남아있는 수의 (최댓값 - 최솟값)이 1이면 큰 수를 먼저 모두 출력..

17609번: 회문 문제 https://www.acmicpc.net/problem/17609 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net 풀이 문자열을 입력받아 이 문자열이 회문인지, 유사 회문인지, 둘 다 아닌지를 판단하여 각 0, 1, 2를 출력하는 문제다. 여기서 유사 회문이란 문자열에서 한 글자를 제거하여 회문이 되는 문자열을 말한다. 투 포인터(two pointer)를 사용해 풀었다. 문자열을 s라 하면, left는 0번 index부터 차례로 증가, right는 문자열의 마지막 문자 index부터 차례로 감소하며 left < r..

1264번: 모음의 개수 문제 https://www.acmicpc.net/problem/1264 1264번: 모음의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있으며, 각 줄마다 영어 대소문자, ',', '.', '!', '?', 공백으로 이루어진 문장이 주어진다. 각 줄은 최대 255글자로 이루어져 있다. 입력의 끝에는 한 줄 www.acmicpc.net 풀이 getline 함수를 사용해 줄 단위로 입력을 받고 모음(a, e, i, o, u)의 개수를 세는 문제다. 대/소문자 모두 세어야 함에 주의하자. 코드 #include using namespace std; int main() { string str; char arr[] = {'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I..

1260번: DFS와 BFS 문제 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 풀이 dfs와 bfs의 기본 사용 방법을 연습할 수 있는 문제다. 간선이 양방향이므로 x, y를 입력받아 graph[x][y] = 1, graph[y][x] = 1로 해준다. 시작 정점부터 dfs를 돌리면 방문처리를 한 후 정점에서 연결된 위치가 아직 방문하지 않았다면 해당 정점으로 dfs를 다시 진행한다. 이를 반복하여 계속..

1259번: 팰린드롬수 문제 https://www.acmicpc.net/problem/1259 1259번: 팰린드롬수 입력은 여러 개의 테스트 케이스로 이루어져 있으며, 각 줄마다 1 이상 99999 이하의 정수가 주어진다. 입력의 마지막 줄에는 0이 주어지며, 이 줄은 문제에 포함되지 않는다. www.acmicpc.net 풀이 문자열 S를 입력받고 왼쪽 끝과 오른쪽 끝에서부터 차례대로 문자가 같은지 확인하며 같은 개수를 센다. 하나라도 틀리다면 "no"를 출력한다. 아니라면 탐색을 모두 끝내면 "yes"를 출력한다. 오래전에 푼 문제라 너무 어렵게 푼 것 같다. 그냥 문자열을 복사해 두고 헤더의 reverse() 함수를 사용해 뒤집어서 같은지 비교만 하면 풀 수 있는 간단한 문제다. 코드 #includ..