컴굥일지

문제 https://www.acmicpc.net/problem/2607 문제 내용 기준이 되는 단어와 비교했을 때, 비슷한 단어가 몇 개인지 출력하면 된다. 먼저 같은 구성을 갖는 기준은 아래와 같다. 1. 두 문자열이 같은 종류의 문자로 이루어져 있다. 2. 같은 문자는 같은 개수만큼 있다. => 즉, 문자열을 정렬했을 때 두 문자열이 일치해야 한다. 그럼 비슷한 단어의 기준을 알아보겠다. 1. 두 문자열이 서로 같은 구성일 경우 2. 한 문자열에서 한 글자를 삭제하거나, 추가하거나, 다른 문자로 바꾸었을 때, 다른 문자열과 같은 구성이 될 경우 문제 풀이 처음에는 문제가 약간 헷갈렸다. 문제를 풀 때 그냥 풀지 말고 생각하고 구현해야 하는 문제 같다. 일단, 기준 문자열과 비교 대상이 되는 문자열은 ..

문제 https://www.acmicpc.net/problem/1463 문제 내용 할 수 있는 연산은 3가지이다. 3으로 나누거나, 2로 나누거나, 1을 빼는 것 위 3가지 연산을 최소한으로 사용해서 입력받은 수를 1로 만들면 된다. 문제 풀이 문제를 보면 dynamic programming이라는 것은 짐작이 올 것이다. dp이긴 한데 조건을 어떻게 새워야 할까? 2나 3으로 나누어 떨어지면 그냥 나누는 것을 선택하는게 좋을까? => 아니다 문제에서 준 힌트를 보니 10의 경우 10 -> 9 -> 3 -> 1의 순서가 가장 연산이 적다고 되어있었다. 10의 경우 2로 나누어 떨어지지만, 1을 먼저 뺀 경우가 더 연산 숫자가 적다. 이를 적용해보자면, 1) 2 또는 3으로 나누어지지 않는다 => 1을 뺀다..

문제 https://www.acmicpc.net/problem/1427 문제 내용 숫자를 입력받아서 각 자릿수를 내림차순으로 정렬하면 된다. 문제 풀이 문제는 함수 몇개만 알면 매우 쉽다. 먼저 입력받은 숫자를 문자열로 바꾸어준다. 이때, to_string() 함수를 사용한다. (string헤더) 그리고 각각의 문자를 vector에 집어넣고, 이를 sort()하면 된다. 출력 시에는 정렬한 vector를 역순으로 출력해주면 끝난다. 코드 #include #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); //입력 int n; cin >> n; //문제..

문제 https://www.acmicpc.net/problem/2798 문제 내용 카드 n개를 입력받아 3장을 뽑는다. 뽑은 카드를 다 합했을 때, m보다는 작거나 같으면서 만들 수 있는 최대의 값을 만들면 된다. 문제 풀이 완전 탐색으로 문제를 풀면 된다. 3장의 합이 m보다 작을 때, mmax의 값을 계속 갱신해가면서 확인하면 된다. 코드 #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); //입력 int n, m; cin >> n >> m; vectorarr(n); for (int i = 0; i > arr[i]; //..

문제 https://www.acmicpc.net/problem/10773 문제 내용 숫자를 입력받아 0이면 이전 숫자를 지우고, 그렇지 않다면 계속 추가해주면 되는 문제이다. 문제에서는 마지막에 남아있는 수들의 합을 구하기를 바란다. 문제 풀이 크게 어려울 것이 없다. 스택을 쓸 줄 아는지 묻는 문제라고 보면 될 것 같다. 입력으로 0이 들어오면 pop(), 다른 수가 들어오면 push()를 해준다. 입력이 전부 끝나면 스택에 남아있는 수를 전부 더해주면 끝이다. 코드 #include #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); //입력 int n,num; cin >> n; ..

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