컴굥일지

문제 https://www.acmicpc.net/problem/11399 문제 내용 사람들의 순서를 잘 배치해서, 전체 대기시간이 최대한 줄어들게 하면 된다. 문제 풀이 이 문제는 생각보다 간단하다. 사람들의 인출하는 시간을 입력받아 정렬하고 다 더하면 문제를 해결 할 수 있다. 이때 정렬을 하는 이유는, 앞사람이 빨리 업무를 처리할 수록, 뒤에 남은 사람들이 덜 기다리기 때문이다. 코드 #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); //입력 int n; cin >> n; vectorv(n); for (int i = 0; i < n; i++) c..

문제 https://www.acmicpc.net/problem/11051 문제 내용 정수 n과 k를 입력 받아서 nCk를 구하는 문제이다. 이항계수에 대한 특징을 알면 문제를 쉽게 풀 수 있다. nCk = (n-1)Ck + (n-1)C(k-1) 라는 것을 이용하면 된다. 문제 풀이 dynamic programming (dp)를 사용하여 문제를 풀면 된다. 이항계수의 특성상 k==0 이거나 n==k 일 때는 값이 1이 된다. 그 이외의 경우는 nCk = (n-1)Ck + (n-1)C(k-1) 를 만족한다. 위 점을 고려하여, 이중 반복문을 사용하여 dp값을 하나하나 채워가면 된다. 코드 #include #include #include using namespace std; //이항계수 ////nCk = (n..

문제 https://www.acmicpc.net/problem/1764 문제 내용 듣도 못한 사람 수 n명, 보도 못한 사람 수 m명의 이름이 주어진다. 두 명단에 공통으로 들어있는 사람의 수와 명단을 출력하면 된다. 문제 풀이 이 문제에서 find() 함수를 써서 하면 시간 초과가 난다. n, m의 범위가 모두 500,000 이하의 자연수이기 때문이다. 그렇기 때문에 binary_search()를 사용했다. binary_search()는 정렬된 상태에서 사용 가능하다. 그래서 듣도 못한 사람들의 명단을 sort()한 뒤에 보도 못한 사람이 포함되었는지 binary_search()를 사용해서 확인한다. 만약 듣도 보도 못한 사람이라면 result 벡터에 추가하고 나중에 결과 출력할 때 출력하면 된다. 코..

문제 https://www.acmicpc.net/problem/2841 문제 내용 기타로 멜로디를 연주할 때, 가장 손가락을 적게 움직이는 방법을 찾으면 된다. stack을 사용하여 이 문제를 풀면 좋다. 문제 풀이 1~6번 줄을 각각 스택으로 선언한다. 두 번째 줄부터 입력 형식이 (줄 번호, 프렛 번호) 이므로, 해당 줄 번호 스택에 프렛 번호를 추가하면 된다. 이때 고려할 사항이 몇 가지 존재한다. 1. (이미 누르고 있는 프렛 번호) < (누르려는 프렛 번호) 이 경우 그냥 스택에 새로운 프렛 번호를 추가해주면서, count 개수도 1 증가시키면 된다. 2. (이미 누르고 있는 프렛 번호) == (누르려는 프렛 번호) 별 다른 처리가 필요하지 않다. 손가락을 움직일 필요도, 스택을 변화시킬 이유도..

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