숫자 카드 묶음의 개수 N 카드 묶음 각각의 크기가 N번 주어짐 묶음을 합칠 때는 a + b 만큼의 비교가 필요함 즉 a b c 가 있는 묶음에서는 ( a + b ) + ( ( a + b ) + c ) 번의 비교가 필요하다 그리디 알고리즘으로 heap 의 top, top + 1을 더한다. 이때 heap은 mean heap으로 구성돼 가장 작은 수가 top에 위치한다. 해당 차례의 최소 값 만을 더하고 다시 heap에 추가해서 반환한다. 처음 제출 시 n = 1일 경우의 예외처리를 진행하지 않아 시간 초과 문제가 발생했다 if(pq.size() == 1){ cout > n; for(int i=0; i> tmp; pq.push(tmp); } int sum = 0;..
분류 전체보기
문제 링크 : https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 함께 올려주신 파일 합치기 문제와 유사해 금방 해결할 수 있었습니다! 양옆의 두 원소를 합치기 때문에 N - 1번의 연산을 수행해야 하는데요, 따라서 마지막 끝의 두 원소를 합치는 경우가 아닌 이상 더했던 요소를 언젠간 추가로 더하게 되므로 제일 작은 값 둘을 합치는 연산을 반복해야 합니다. 이를 구현하는 데에 수만 개의 원소가 존재해도 원소를 추가하고 빼는 동작이 O..
지난번에 풀어본 적이 있었던 문제였는데 오랜만에 보니까 확실히 까먹게 되네요. 우선순위 큐를 사용해서 풀었습니다. 우선순위 큐를 선언할 때 greater를 같이 넣어줌으로서 내림차순 정렬(queue내부에서 내림차순, 따라서 순서대로 top을 출력보면 가장 마지막에 나온 숫자가 가장 크다)이 되게 해주었습니다. 은 greater를 사용하기 위해 선언해주었습니다. 입력을 받으면서 우선순위 큐에 바로바로 push를 합니다. while문에서 pq.size()가 1보다 클 때까지 반복을 해줍니다. 1보다 클 때까지로 조건을 정한 이유는 큐에서 두 개의 수를 뽑아 더한 뒤에 마지막에 push를 해주기 때문에 result에 최종 답이 담기게 되어도 pq에는 하나의 값이 더 남게됩니다. #include #include..
이번 문제는 투포인터를 개념을 적용해서 바로 풀 수 있었던 문제였던 것 같습니다. 에라토스테네스의 체를 통해서 MAXNUM까지의 소수를 구해주었습니다. 입력받은 n까지의 소수 개수 세고, 소수를 배열에 담아주었습니다. 투포인터 코드를 적용하여 마지막에 경우의 수를 출력해주었습니다. 소스코드 #include #define MAXNUM 4000000 using namespace std; bool check[MAXNUM]; int arr[MAXNUM]; int main(void) { int n; for (int i = 2; i n; int num=0; int idx=0; for (int i = 2; i = n) sum -= arr[lo++]; else if (hi == num) break; else sum +..
참고자료와 강의를 들으니 바로 풀리는 문제였다. 에라토스테네스의 체로 소수를 모두 구한 뒤 two pointer를 사용해 구하면 되는 문제였다. MAX 값을 4000000으로 고정 시킨 후 4000000까지의 소수를 구한 후 해당 소수들을 vector에 저장시켰다. 그 후 vector안의 값의 합이 입력 값과 같은지 two pointer를 사용해 확인한다. #include #include #include #include using namespace std; const int MAX = 4000000; int main(){ ios::sync_with_stdio(false); cin.tie(NULL); vector prime; bool isPrime[MAX+1]; fill(isPrime+2, isPrime+..
문제 링크 : https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 풀이가 매우 직관적이어서 개인적으로 좋다고 생각했던 문제입니다. 코알라 투 포인터 강의영상 에서 나온 2003번 문제에 에라토스테네스의 체를 덧댄 버전입니다. 해결 방법은 정말 깔끔합니다. 1부터 N 사이에 있는 소수들의 배열(리스트)을 미리 만들어 두고, 해당 테이블에 대해 투 포인터 방법을 사용해 인덱스를 움직여가며 부분합이 N이 되는지 검사하기만 하면 됩니다. 저의 경우에는 소수들의 배열을 그냥 문제에서 주어진 범위인 4백만개로 초기화했지만, 그래도 시간 복잡도는 체를 만들 때 O(NlogN) +..
가희의 로그 N개의 로그 Q개의 임무 시작시간 - 종료시간 로그 레벨 lv 이상인 로그가 몇번 발생했는지 시작시각과 종료시간에 발생한 로그 포함 생각 문자열로 그대로 비교해보기 입력 받은 대로 파싱 진행 - : # 제거해서 문자열로 저장 처음에는 1 ≤ N ≤ 2×105 1 ≤ Q ≤ 2×105 이 조건을 생각하지 않고 마지막에 for문을 사용해 비교했다가 시간초과가 계속 생겼다. 이분 탐색을 사용한 후에도 시간초과가 나길래 혹시 몰라 ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 를 추가해보니 바로 해결됐다. 다음 부턴 그냥 기본으로 ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);를 박고 코드를 짜야겠..
백준에 제출을 할 경우 런타임 에러(Seg Fault)가 계속 뜨는데요. 찾아보니까 Seg fault 에러가 할당하지 않은 메모리 영역에 접근할 경우 뜨는 에러라고 하더라구요. 테스트 케이스를 이것저것 넣어봤을 때 결과는 제대로 나오는데 어떤 부분 때문에 SegFault 에러가 계속 뜨는지 잘 모르겠습니다.. #include #include #include #include using namespace std; vector vec[7]; int main(void) { ios_base::sync_with_stdio(false); cin.tie(NULL); int n, q; cin >> n >> q; getchar(); for (int i = 0; i < n; i++) { string s, temp; getl..
입력값의 최대 범위가 4,000,000이므로 숫자 하나하나 소수 판정을 하였다가는 시간초과가 날 것이 분명하므로 에라토스테네스의 채를 이용해 입력받은 수 범위 이내의 소수들을 배열에 저장해놓고 그 값들과 포인터 두 개로 더했다 뺐다를 반복해주며 n과 같은 경우가 발생한 횟수를 기록해주기만 하면 되는 문제일 것입니다. prime=[1 for i in range(n+1)] # n까지 수의 범위 for i in range(2,int(n**0.5)+1): # 소수 판정을 위해 사용할 수의 범위 sqrt(n) if prime[i]==1: for j in range(i*2,n+1,i): # i 의 배수들 지워나가기 prime[j]=0 prime=[i for i in range(2,n+1) if prime[i]==1..
처음 문제를 읽고 든 생각은 탐색 문제라는 것이고 for문 2개로 하기에는 입력값이 너무 크므로 다른 방법을 사용해야 된다고 생각했습니다. 시간이 정렬되어 들어오고 중복된 값도 존재하는 것을 보고 이분 탐색을 써야겠다고 생각했습니다. 그리고 입력들어오는 형태 그대로 대소비교를 해도 괜찮은 형태로 들어오므로 그대로 사용하기로 결정했습니다.((2021-04-05 17:17:11end or arr[i][-1]
먼저 입력의 형태를 한눈에 봤을 때, 주어진 시간을 초 단위로 파싱하는 로직을 짜야겠다는 생각이 들어 파싱을 진행했습니다. 2 2 2021-04-05 17:17:11#1 2021-04-05 17:18:11#2 2021-04-05 17:17:11#2021-04-05 17:18:11#1 2021-04-05 17:18:11#2021-04-05 17:19:11#3 def parseYearToSecond(year): if year == 2000 or year == 2004 or year == 2008 or year == 2012 or year == 2016 or year == 2020: return year * 60 * 60 * 24 * 366 else: return year * 60 * 60 * 24 * 365..
힌트 1 더보기 약 21년의 시간을 초 단위로 나타내어 대소 비교를 할 수 있습니다. 힌트 2 더보기 로그에 대한 시간들이 순서대로 정렬되어 있을 때, 어떤 시간 A보다 크거나 같은 수가 처음 발견되는 위치는 O(logn) 시간에 찾을 수 있습니다. 힌트 3 더보기 종료 시각보다 큰 수가 처음 발견되는 위치 - 시작 시각보다 크거나 같은 수가 처음 발견되는 위치 번외 힌트 더보기 사실 문제처럼 연, 월, 일, 시, 분, 초로 되어있는 로그는 숫자만 모두 모아두면 그 자체로 대소비교가 가능합니다. 예를 들어 2000-01-02 12:12:12 -> 20000102121212 , 2021-04-05 17:17:11 -> 20210405171711 이 부분은 long long 형으로 변환해도 되지만, 그냥 s..
