컴굥일지

문제 https://www.acmicpc.net/problem/11047 문제 내용 동전을 적절히 사용해서 K원을 만드는 문제이다. 이때 동전의 최소화하여 사용하는 것이 이 문제의 핵심이다. 문제 풀이 이 문제는 greedy한 성격이 있다. 4200원을 만들 때, (1원짜리 4200개) / (100원짜리 420개) / (1000원짜리 4개 + 100원짜리 2개) 등 여러 방법으로 만들 수 있다. 이 경우 (1000원짜리 4개 + 100원짜리 2개)로 4200원을 만드는 것이 동전의 개수를 최소화할 수 있다. 그럼 이 문제를 풀 때 어떻게 해야 할까? 동전의 가치가 큰 것부터 사용하는 방식을 선택하면 된다. 만들려는 K원보다 가치가 작은 동전들 중에서, 그나마 가치가 큰 동전부터 사용하면 된다. 코드 #i..

문제 https://www.acmicpc.net/problem/2231 문제 내용 자연수 N을 입력받아, N의 가장 작은 생성자를 구하는 문제이다. 즉, 우리의 결과값의 분해합을 구하였을 때 N이 만들어지면 된다. 문제 풀이 이 문제의 경우, 완전탐색 알고리즘(brute force)을 사용하여 문제를 해결했다. 이 문제의 결과값은 항상 1 이상, N 미만이다. (생성자가 없는 경우는 0) 따라서 for 반목문을 1~N-1까지 돌면서 각 숫자의 분해합을 구해보면 된다. 만들어진 분해합이 N과 같으면 종료하면 되고, for문이 끝날 때까지 결과가 나오지 않는다면 생성자가 없는 경우이므로 0을 출력하면 된다. 특정 숫자의 분해합을 구하는 과정은 while문을 통해 구현했다. 10으로 나누었을 때의 나머지를 차..

문제 https://www.acmicpc.net/problem/6996 문제 내용 테스트 케이스별로 단어 2개를 입력받아서 애너그램인지 아닌지를 판단하는 문제이다. 문제 풀이 애너그램이란 단어 2개가 주어졌을 때, 두 단어를 이루고 있는 알파벳이 같은 것을 의미한다. 즉, 순서를 바꿔서 동일해지면 애너그램이다. 이 문제는 sort() 함수를 통해 정말 간단하게 해결할 수 있다. 입력받은 문자열 2개를 모두 정렬하고, 그 뒤에 같은지 비교하면 된다. 코드 #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); //입력 int test; cin >> test..

문제 https://www.acmicpc.net/problem/8892 문제 내용 입력받은 문자열들 중 2개를 골라 연결했을 때, 팰린드롬인지 아닌지 확인하는 내용이다. 가능한 팰린드롬들 중에 1가지만 출력하면 되며, 만들 수 없을 경우 0을 출력하면 된다. 문제 풀이 1. check_palindrome(string str) 함수 매개 인자로 전달받은 문자열이 팰린드롬인지 아닌지를 확인하는 함수이다. 문자열의 양 끝에서부터 가운데로 진행하며, 대칭인지 아닌지를 확인하면 된다. 2. solution() 함수 함수 안에서 먼저 주어지는 단어의 개수와, 단어들을 입력받는다. 이중 for문을 돌며, 단어 두 개를 골라 결합하여 check_palindrome()에 넘긴다. 반환된 값이 false이면 새로 단어를 ..

문제 https://www.acmicpc.net/problem/11091 문제 내용 한 줄을 입력받아서 알파벳 a~z가 모두 최소 한 번씩 사용되었는지 확인하는 문제이다. 문제 풀이 먼저 알파벳 a~z가 들어있는 문자 배열을 선언해 두고 시작했다. 테스트 케이스별로 문제를 해결하기 위해 for문을 사용했다. 입력받는 문자열에 공백이 포함될 수 있기 때문에 getline()을 사용했다. 입력을 받고 나서는 tolower() 함수를 사용하여 문자열에 포함된 대문자를 소문자로 만들었다. 이후 find()함수를 통해 입력받은 문자열에 각각의 알파벳이 있는지 없는지를 확인했다. find() 함수로 찾는 대상이 없다면 -1을 반환하기 때문에, 반환 값이 -1이면 해당 알파벳을 저장했다가 이후에 출력했다. 코드 #i..

문제 https://www.acmicpc.net/problem/15904 문제 내용 문자열을 입력받아 임의의 문자를 적절히 제거하여 UCPC를 만들 수 있는지 없는지를 판단하는 문제이다. 가능하다면 I love UCPC를, 불가능하다면 I hate UCPC를 출력하면 된다. 문제 풀이 공백이 포함된 문자열을 입력받기 위해 getline() 함수를 사용한다. 이후 find() 함수를 사용하여 U C P C의 위치를 받는다. 참고로 find() 함수는 대상문자열.find(찾는 대상, 시작 위치)의 방식으로도 쓸 수 있다. (찾는 대상이 존재하지 않으면 -1을 반환한다.) 앞의 문자의 위치를 뒤의 문자의 시작 위치로 주면, find() 함수가 반환하는 위치가 U

문제 https://www.acmicpc.net/problem/4583 문제 내용 입력받은 문자열이 거울상 문자열인지 확인하고, 맞으면 거울에 비춰지기 전 모습을, 그렇지 않으면 INVALID를 출력하는 문제이다. 문제 풀이 일단 거울상 문자에 해당하는 'b', 'd', 'p', 'q', 'i', 'o', 'v', 'w', 'x'를 미리 배열로 만들어둔다. #이 입력될 때까지 문자열을 계속 입력받기 때문에, while 반복문 안에서 문자열을 입력받고 #인지 아닌지 확인하는 과정이 필요하다. 위 과정이 끝나면, 문자열의 각각의 문자에 대해서 거울상 문자인지 아닌지를 판단하는 과정을 거치면 된다. find()를 통해 문자가 reflect 배열 안에 존재하지 않으면 결과는 INVALID가 된다. 문자가 거울상..

문제 https://www.acmicpc.net/problem/9009 문제 내용 하나의 양의 정수를 최소한의 피보나치 수들의 합으로 나타내면 된다. 문제 풀이 일단 먼저 피보나치 배열을 만들어두었다. 입력이 1,000,000,000 이하의 수로 들어오기 때문에, 피보나치 수를 45 정도까지 구해두면 문제를 푸는데 문제가 없었다. 숫자를 입력받고 나서는, 반복문을 통해 문제를 해결해 나갔다. 하나의 테스트 데이터에 대해, 역순으로 피보나치 수와 비교하며 진행했다. (코드를 보면 이해가 갈 것이다.) 코드 #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0..

문제 https://www.acmicpc.net/problem/1026 문제 내용 정수 배열 A와 B의 원소의 곱이 최소가 되도록 하는 함수 S를 만드는 문제이다. 문제 풀이 문제에는 배열 B를 재배열하지 말라고 되어있다. 하지만 굳이 문제를 그렇게 풀 필요는 없어 보인다. (B를 기준으로 A를 맞추는 건 너무 일이 많아 보인다....) 배열 A와 B 모두 정렬하여, A는 앞에서부터, B는 뒤에서부터 곱하여 더한다면 S의 값이 최소가 된다. 코드 #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); //입력 int n,tmp; cin >> n; vect..

문제 https://www.acmicpc.net/problem/1448 문제 내용 입력받은 빨대들 중에서 3개를 뽑아 삼각형을 만드는 문제이다. 삼각형으로 만들 수 없다면 -1 출력하고, 만들 수 있다면 세 변의 길이의 합의 최댓값을 출력한다. 문제 풀이 삼각형을 이루기 위해서는 (가장 긴 변의 길이) >..