컴굥일지

문제 https://www.acmicpc.net/problem/14425 문제 내용 n개의 문자열로 이루어진 집합에, 그 뒤로 주어지는 문자열들이 몇 개나 포함되어있는지를 구하는 문제이다. 위 사진에서 빨간색으로 묶여있는 문자열들 안에, 그 뒤로 이어지는(파란색) 문자열의 포함 여부를 판단하면 된다. 문제 풀이 문제 자체는 간단하다. 다만 n의 입력 범위가 1~10000, m의 입력 범위가 1~10000이라는 점에서 단순하게 탐색하면 안 된다. m개 입력되는 문자열을 n개의 집합에서 처음부터 매번 찾을 수는 없기 때문이다. (시간 초과 난다) 그렇기 때문에 이 문제에서는 이진 탐색을 사용했다. binary_search()는 정렬된 상태에서 사용이 가능하기 때문에, n개의 문자열 집합을 입력받고 나서 so..

문제 https://www.acmicpc.net/problem/1431 문제 내용 시리얼 번호는 숫자와 알파벳 대문자로 이루어져 있다. 시리얼을 입력받아서 기준대로 출력하는 프로그램을 짜면 된다. 이때 A가 먼저 올 기준은 아래와 같다. 1. A와 B의 길이가 다르면, 짧은 것이 먼저 온다. 2. 만약 서로 길이가 같다면, A의 모든 자리수의 합과 B의 모든 자리수의 합을 비교해서 작은 합을 가지는 것이 먼저온다. (숫자인 것만 더한다) 3. 만약 1,2번 둘 조건으로도 비교할 수 없으면, 사전순으로 비교한다. 숫자가 알파벳보다 사전순으로 작다. 문제 풀이 문제에서 원하는 기준대로 정렬해주기 위해 sorting()함수를 새로 만들어주었다. 코드와 주석을 읽으면 이해가 될 것이다. 코드 #include #..

문제 https://www.acmicpc.net/problem/11726 문제 내용 2 * n 크기의 직사각형을 1 * 2, 2 * 1 타일로 채우는 가지 수를 구하는 문제이다. 문제 풀이 문제를 읽어보면 느껴지겠지만, dynamic programming 문제이다. dp 문제의 핵심은 규칙 찾기이다. 이 문제의 규칙을 찾아보자. dp[1]=1 이다. // I dp[2]=2 이다. // II, = dp[3]=3 이다. // III,I=,=I dp[4]부터 확인해 보자. dp[3]왼쪽에 I추가하는 경우 => IIII,II=,I=I dp[2]왼쪽에 =추가하는 경우 => =II,== 따라서 dp[4]=5이다. dp[5]도 확인해 보자. dp[4]왼쪽에 I추가하는 경우 => IIIII,III=,II=I,I=II,..

문제 https://www.acmicpc.net/problem/2309 문제 내용 9명의 키가 주어지고, 이들 중 2명을 제외하여 키의 합을 100으로 맞추는 문제이다. 문제 풀이 전형적인 완전 탐색 문제이다. 일단 입력받은 키들의 합을 구하고, 이중 for문을 돌며 두 명을 골라 제외시키며 키의 합이 100이 되는지 아닌지를 확인하면 된다. 만약 키의 합이 100이 되면, 나머지 수들을 바로 출력해주고 프로그램을 종료하면 된다. 코드 #include #include #include //accumulate() 들어있다. using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); //입력 int arr[9]..

문제 https://gyong0117.tistory.com/ 문제 내용 후위 표기식과 피연산자들에 해당하는 값들이 주어졌을 때 식을 계산하여 소수점 둘째 자리까지 출력하는 문제이다. 1. 중위 표기식이란? 중위 표기법은 우리가 흔히 사용하는 표기법으로 피연산자 사이에 연산자를 두는 방식이다. 3*5, 4+7, 5/2 등이 중위 표기식에 해당한다. 2. 후위 표기식이란? 후위 표기법은 연산자를 피연산자 뒤에 놓는 방법이다. 위의 중위 표기식을 후위 표기식으로 바꾸면 35*, 47+, 52/ 과 같은 형태로 적을 수 있다. 문제 풀이 후위 표기식을 계산하기 위해는 stack을 사용하는 것이 좋다. 더불어, 식의 결과와 중간 결과가 -20억보다 크거나 같고, 20억보다 작거나 같다고 했기 때문에 double ..

문제 https://www.acmicpc.net/problem/9012 문제 내용 테스트 케이스별로 괄호 문자열을 입력받아 VPS인지 아닌지를 확인하는 문제이다. 문제 풀이 괄호 문자열을 입력받아서, 문자열의 앞부터 한 글자씩 읽으며 스택에 추가하거나 빼면 된다. 읽은 글자가 '(' 라면, 스택에 push( '(' ) 한다. 읽은 글자가 ')' 라면, 스택에서 하나를 pop() 하면 된다. 이때 만약 스택이 비어있다면, 문자열은 절대 VPS가 될 수 없으므로 바로 false를 return 한다. 문자열을 전부 읽은 후에 스택이 비어있으면 괄호의 쌍이 제대로 맞는다는 것을 의미하므로 true를 return 한다. 스택이 비어있지 않다면 false를 return 한다. 코드 #include #include ..

문제 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이면 새로 단어를 ..