나그네

1958번: LCS 3 문제 https://www.acmicpc.net/problem/1958 1958번: LCS 3 첫 줄에는 첫 번째 문자열이, 둘째 줄에는 두 번째 문자열이, 셋째 줄에는 세 번째 문자열이 주어진다. 각 문자열은 알파벳 소문자로 이루어져 있고, 길이는 100보다 작거나 같다. www.acmicpc.net 풀이 9251번 LCS의 확장 버전이다. 아래 문제와 다른 점은 문자열 두개가 아닌 세 개를 비교하는 문제다. https://khyunx.tistory.com/57 [백준 / BOJ] C++ 9251 LCS 9251번: LCS 문제 https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통..

9252번: LCS 2 문제 https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 풀이 9251번 LCS의 확장 버전이다. LCS의 길이를 구하는 풀이는 아래 링크를 참고하길 바란다. https://khyunx.tistory.com/57 [백준 / BOJ] C++ 9251 LCS 9251번: LCS 문제 https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Lon..

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..