개발일지

문제설명 입출력 예제 개념 연속된 문자가 나타났을 때, 그 사이에 교차되는 문자가 있는지 확인하는 문제다. 이를 그림으로 나타내면 다음과 같다. 따라서 반복되는 문자열을 모두 지웠을 때 같은 문자가 존재한다면 그룹단어가 아니게 된다는 것을 이용하면 된다. 풀이 #include #include #include using namespace std; int main() { int num = 0; cin >> num; int cnt = 0; 단어의 개수를 num으로 받고, 그룹 단어 개수를 출력할 cnt를 초기화한다. for (int i = 0; i > str; bool check = true; str.erase(unique(str.begin(), str...

문제설명 입출력 예제 개념 문자열을 크로아티아 알파벳의 규칙에 맞게 변경한 후, 그 개수를 카운팅 하는 문제다. 크로아티아 문자가 생성되는 규칙은 다음과 같다. 문자 =가 있는 경우 이전 문자가 c거나 s인 경우 카운트를 2개가 아닌 하나로 한다. 이전 문자가 z인 경우 카운트를 2개가 아닌 하나로 한다. 이전 문자가 z이며 d인 경우 카운트를 3개가 아닌 하나로 한다. 문자 -가 있는 경우 이전 문자가 c거나 d인 경우 카운트를 2개가 아닌 하나로 한다. 문자 j가 있는 경우 이전 문자가 l이거나 n이 경우 카운트를 2개가 아닌 하나로 한다. 풀이 #include #include using namespace std; int main() { string str; cin >> str; int count =..

문제설명 입출력 예제 개념 생성자가 없는 숫자인 셀프 넘버를 출력하는 문제다. 문제에서 알 수 있듯이 x라는 숫자가 있을 때, x의 각 자릿수들의 숫자와 x를 더한 숫자는 셀프 넘버가 아니게 된다. 따라서 bool 배열은 만들어 1부터 10000까지 상술한 규칙을 적용해, 해당하는 자리의 숫자를 true로 바꾼 후 false만 출력하면 된다. 풀이 풀이(1) string 이용하기 #include #include using namespace std; int main() { int num = 10000; bool selfnum[10000] = { false }; max 숫자인 10000을 num으로 초기화하고, selfnum를 체크할 bool 배열 selfnum[]을 초기화한다. for (int i = 1;..

문제 설명 제한 사항 및 입출력 예제 알고리즘 개념 알고리즘(1) 정해진 규칙에 의해 생성되는 배열의 일부분을 출력하는 문제다. 제한사항을 보면 n과 left, right의 값이 상당히 크므로 시간 초과를 주의해야 한다. 즉, 배열을 초기화하려면 시간 복잡도가 O(n^2)이 될 텐데, O(n)으로 줄이는 것을 목표로 하자. 그렇다면 우리는 배열의 규칙성을 찾아 left와 right 사이의 인덱스 값을 통해 바로 배열의 값을 구해야 한다. 이를 구하기 위해 예제에 나와 있는 n = 3의 배열을 시각화해 보자. 어떤 규칙성이 보이는가? 먼저 확인할 수 있는 것은 다음과 같다. 행이 바뀔 때마다 첫 번째 행을 기준으로 일련의 규칙에 따라 값이 바뀐다. 다음 사진에서 기준인 값은 1, 2, 3이다. 이 값을 기..

문제 설명 제한 사항 및 입출력 예제 알고리즘 개념 괄호 문자의 규칙을 찾으면 되는 문제다. 내가 알고 있는 기존의 괄호 규칙은 총 3가지다. 왼쪽 괄호의 개수와 오른쪽 괄호의 개수가 같아야 한다 같은 타입의 괄호에서 왼쪽 괄호는 오른쪽 괄호보다 먼저 나와야 한다 서로 다른 타입의 왼쪽 괄호와 오른쪽 괄호쌍은 서로 교차하면 안 된다 상당히 복잡해보이지만, 이 규칙을 자료 구조를 이용하여 한 번에 적용하여 해결할 수 있다. 바로 stack인데, 값을 push하기 전에 마지막 값과 비교하여 괄호 문자의 규칙을 만족하면 제거하거나 푸시하면 풀린다. 예를 들어 "()[]{}"와 "([]){}", "({)}[]"가 각각 stack에서 어떻게 처리되어야 할지 생각해보자. 어느정도 감이 오는가? 그렇다. 왼쪽 괄호 ..

문제설명 입출력 예제 개념 N이 주어졌을 때, 주어진 3kg 봉지와 5kg 봉지를 이용해 3x + 5y = N을 만족하는 최소의 정수쌍의 합을 구하는 문제다. 이때 이러한 해를 만족하는 정수쌍이 존재하지 않을 때는 -1을 출력해야 하며, x나 y에 0이 들어갈 수 있다는 것을 유념해야 한다. 알고리즘 필자의 경우엔 3x + 5y = N을 y에 대해 정리하여 y = -3x/5 + N/5로 표현한 뒤, 다음과 같은 과정으로 문제를 풀었다. x = 0부터 y = -3x/5 + N/5가 정수가 되는 (x,y)의 값을 찾고, 배열에 x + y를 넣음 (개수를 묻는 문제이므로) 만약 -3x/5 + N/5 < 0이 되면 더이상 0을 넘는 값을 찾을 수 없음 일련의 과정을 통해 x + y의 값을 배열에 넣은 후, 배열..

문제설명 입출력 예제 개념 주어진 자연수 중 소수의 개수를 출력하는 문제다. 여기서 소수란 약수가 1과 자기 자신밖에 없는 수를 의미한다. 알고리즘 1부터 입력된 수까지 순회하며 나눠지는 수가 존재한다면 소수가 아니므로 break를 건 후 다음 반복으로 넘어가고, 나눠지는 수가 없다면 소수의 개수를 늘리는 식으로 접근하면 되는 간단한 문제다. 풀이 #include using namespace std; int N, cnt; int check; int main() { cin >> N; while (N--) { int num; check = 0; cin >> num; for (int i = 1; i < num; i++) { if (num % i == 0 && i != 1) break; check++; } if..

문제 설명 제한 사항 및 입출력 예제 알고리즘 개념 예제에서 주어진 원형 수열을 기준으로 연속 부분 수열을 구하면 다음과 같다. 따라서 이 합들을 저장할 벡터를 초기화한 후에 중복되는 값을 지워주면 해결된다. 여기서 첫 번째 문제는 연속된 합을 반복문을 이용해 하나 하나 저장하고 비교하려니 시간 초과가 걸린다. 두 번째 문제는 끝이 연결되어 끊기는 부분이 없다는 것이다. 이러한 문제를 해결하기 위해 특정 구간의 합을 구할 수 있는 구간합(Prefix sum) 개념을 이용하여 풀었다. 주어진 예제의 구간합을 표현해보면 다음과 같다. sum이 초기화되는 과정을 보면 다음과 같다. 여기서 구간합은 특정 구간의 합을 구할 수 있다고 했는데, 만약 내가 elements의 인덱스 n부터 k까지의 합을 구하고 싶다면..

문제 설명 제한 사항 및 입출력 예제 알고리즘 개념 - 개념 자체는 간단하다. 두 정수 배열 중 한 배열을 골랐을 때, 그 배열의 공약수 집합들 중 남은 배열의 원소와 나누어 떨어지지 않는 최댓값 원소를 찾는 문제다. 여기서 얼마나 시간을 줄이느냐가 관건이다(즉, 알고리즘을 맞게 작성하였어도 시간 초과가 뜰 수 있다). 필자는 풀이에서 언급할 반복의 횟수를 줄이는 방식을 통해 시간 초과 문제를 해결하였다. 풀이 풀이(1) 최초의 풀이 방법 #include #include using namespace std; int getGCD(int& min, vector& a, vector& b) { bool check = true; int max = 0; for (int i = 2; i

문제 설명 입출력 예제 풀이 #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); // 입출력 시간 절약 int num; cin >> num; int Result = num; int count = 0; while (true) { int tens = num / 10; int units = num % 10; num = 10 * units + (tens + units) % 10; count++; if (num == Result) break; } cout