개발일지

문제 설명 제한 사항 및 입출력 예제 개념 id_list에 포함된 사용자가 신고 결과 이메일을 얼마나 많이 받았는지 파악하는 문제다. 각 신고 처리 내역은 "신고자 신고할 사람"의 형식으로 제시된다. 단, 본 문제에서 핵심적인 고려 사항은 동일한 사용자에 대한 중복 신고가 단 한 번의 신고로만 처리된다는 점이다. 따라서, 동일한 대상에 대한 다수의 신고가 있더라도 이를 단일 신고로 간주하며, 이는 신고 결과 이메일의 수를 결정하는 데 중요한 요소가 된다는 점을 놓치면 안 된다. 따라서 map 자료구조를 활용하여 "신고자" "신고한 사람"의 형태의 쌍을 받아 처리할 수 있다. 각 신고자를 키로 설정하고, 신고한 사람을 값으로 설정한다. 동일한 신고자가 동일한 신고한 사람을 여러 번 신고하더라도, map 구..

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

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

문제 설명 제한 사항 및 입출력 예제 알고리즘 개념 예제에서 주어진 원형 수열을 기준으로 연속 부분 수열을 구하면 다음과 같다. 따라서 이 합들을 저장할 벡터를 초기화한 후에 중복되는 값을 지워주면 해결된다. 여기서 첫 번째 문제는 연속된 합을 반복문을 이용해 하나 하나 저장하고 비교하려니 시간 초과가 걸린다. 두 번째 문제는 끝이 연결되어 끊기는 부분이 없다는 것이다. 이러한 문제를 해결하기 위해 특정 구간의 합을 구할 수 있는 구간합(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