컴굥일지

문제 https://www.acmicpc.net/problem/1158 문제 내용 이 문제는 예전에 한 번 푼 적이 있었다. (https://gyong0117.tistory.com/5?category=1050636) 이번에는 queue를 이용해 문제를 풀고자 한다. 문제는 별로 어렵지 않다. 1~N번까지의 사람이 원을 이루며 앉아있고, 계속해서 K번째 사람을 지워나가면 된다. 문제는 이 지워지는 사람의 순서를 출력하면 된다. 문제 풀이 이 문제를 큐로 어떻게 푼다는 것일까? 생각보다 간단하다. 처음에 1~n을 담은 queue를 만든다. 이후, 앞에서부터 k-1명을 pop()하고 다시 뒤에 push()하면 된다. 그러면 이제 queue의 front()에는 우리가 제거해야 할 k번째 사람이 남게 되어있다. ..

문제 https://www.acmicpc.net/problem/5525 문제 내용 Pn은 (n+1)개의 I와 n개의 O가 번갈아 나오는 문자열을 의미한다. 이 문제는, 입력받은 문자열 S에 Pn이 몇 군데에 포함되어 있는지를 확인하는 문제이다. 문제 풀이 이 문제를 맨 처음에는 find()함수를 여러 번 써서 풀었는데, 이렇게 하면 50점만 받을 수 있었다. 그렇기 때문에 시간을 좀 더 단축시킬 수 있는 방법이 필요했다. 밑의 코드에서, k는 IOI의 개수를 의미한다. 문자열을 한글자씩 읽어나가며 문제를 해결한다. 현재 읽는 문자가 I이고, 이어지는 문자열이 OI 일 경우에 k의 값을 증가시킨다. k가 n과 같아지게 되면, 문자열에 Pn이 존재하는 것이므로 ans(결괏값)을 증가시키면 된다. 코드가 잘 ..

문제 https://www.acmicpc.net/problem/11727 문제 내용 2 * n 크기의 직사각형을 1 * 2, 2 * 1, 2*2 타일로 채우는 가지 수를 구하는 문제이다. 2*n 타일링 문제에서 2*2 타일이 하나 늘어난 경우이다. https://gyong0117.tistory.com/73 [BOJ/백준 11726][C++] 2xn 타일링 문제 https://www.acmicpc.net/problem/11726 문제 내용 2 * n 크기의 직사각형을 1 * 2, 2 * 1 타일로 채우는 가지 수를 구하는 문제이다. 문제 풀이 문제를 읽어보면 느껴지겠지만, dynamic programming 문제이.. gyong0117.tistory.com 문제 풀이 2*n 타일링 문제와 같이 dynami..

문제 https://www.acmicpc.net/problem/1932 문제 내용 위에서부터 내려올 때, 아래 또는 오른쪽 아래 방향으로만 내려올 수 있다. (예제 입력 기준) 내려오면서 합이 최대가 되는 경로를 구하면 된다. 문제 풀이 이 문제도 역시 dp를 사용한다. 이 문제에서 dp를 채워나갈 때, 첫 번째 열은 무조건 위에서 내려오는 방법만 있다. 더불어, i==j인 곳은 무조건 대각선 방향으로만 내려올 수 있다. 위 두가지 경우를 제외하면, 아래 또는 오른쪽 아래 방향 중에서 더 큰 쪽을 선택하면 된다. dp를 채우면서 max값을 따로 파악해주어야지 나중에 결과를 출력할 수 있다. 코드 #include #include #include using namespace std; int dp[505][5..

문제 https://www.acmicpc.net/problem/11048 문제 내용 (1,1)에서 (n,m)으로 가면서, 사탕을 최대한 많이 얻을 수 있도록 하면 된다. 이동할 수 있는 방향은 왼쪽/아래쪽/왼쪽아래 대각선 총 3가지이다. 문제 풀이 dp를 사용하여 문제를 풀면 된다. arr배열에 각 위치의 사탕개수를 입력받고, for 반복문을 통해 dp배열을 채워나가면 된다. 어떤 특정한 위치는, 오른쪽/위쪽/오른쪽 위 대각선 방향으로부터 올 수 있다. 따라서 내가 구하려는 dp[i][j]의 값은 오른쪽(dp[i-1][j]) / 위쪽(dp[i][j-1]) / 오른쪽 위(dp[i-1][j-1])의 값 중에 가장 큰 값과 그 위치에 있는 사탕의 개수(arr[i][j])을 더하여 구할 수 있다. 코드 #inc..

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