가희의 로그 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);를 박고 코드를 짜야겠..
전체 글
항공대 알고리즘 동아리 Koala 🥰백준에 제출을 할 경우 런타임 에러(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..
1~1000 사이의 n입력받아 길이가 n인 배열을 입력받는다. 한 번에 이동할 수 있는 거리는 0~100 사이의 값이고 1부터 1000까지 최대 이동 횟수는 999회. 각 위치에 해당하는 최소 이동횟수를 저장시켜야 함 -> DP 문제일 것. 입력도 작고 이동 거리도 작으므로 그냥 BFS로 다 넣어서 풀어도 풀리긴 할 것? bfs 풀이 쓸데없는 곳까지 굳이 탐색하여 시간효율도 별로고 배열도 써서 메모리 효율도 별로일 듯.. dp로 예상됨. # 뒤로 가는거 없음. # bfs? 로 풀 수 있을 듯? import sys from collections import deque input=sys.stdin.readline n=int(input()) arr=list(map(int,input().split())) vis..
생각 정리 1. dp[i]를 점프해야 하는 최소 횟수로 정의 2. 횟수가 제일 많은 경우는 n이 1000이고, 입력된 숫자가 모두 1일 때라고 생각(-1이 나오지 않는 범위에서) -> 시간 초과가 나지 않는다고 생각. 3. 점프해야 하는 최소 횟수를 정의하라고 했기 때문에 dp의 모든 인덱스를 아주 큰 수로 초기화 4. a[i]에 입력된 수만큼 떨어진 곳 이하에 점프해야 하는 최소 횟수를 대입하고, 미리 저장되어 있는 최소 횟수와 그 이후 들어온 횟수를 비교해서 min 값을 저장 5. dp[n]이 987654321로 남아있다면 도달하지 못한 것이므로 -1을 출력 소스코드 #include #include #include #define MAXNUM 987654321 using namespace std; in..
문제 링크 : https://www.acmicpc.net/problem/11060 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 www.acmicpc.net DP 문제입니다. 저는 원체 DP에 익숙하질 않아 상태표를 그려가면서 규칙을 파악하려 했는데요, 그 결과 다음과 같은 흐름을 잡을 수 있었습니다. 10 1 2 0 1 3 2 1 5 4 2 위의 기본 테스트케이스를 예로 들어 설명해보겠습니다. 입력받은 값들이 arr 라는 배열에 담겼다 하고, 해당 배열의 순회를 시작합니다. (1번 for문) 조건에 따르면 배열의 요소에 해당..
점프 점프 1*n 크기의 배열 점프는 i번째 칸의 숫자 이하의 횟수만큼 점프 가능 동전 줍기 문제랑 비슷 -> dp? dp로 각 i번째까지 갈 수 있는 방법 중 최소 점프 횟수 확인 #include #include using namespace std; int main(){ int n; cin>> n; int arr[1002], dp[1002]; for(int i=0; i> arr[i]; dp[i] = 100000; } dp[0] = 0; for(int i = 0; i dp[i] + 1){ //다음 자리의 결과 보다 크다 dp[i+j] = d..
생각 정리 1. 4개의 모서리에 최소 하나의 1이 존재 -> 4개의 모서리를 확인 후 1인 경우 건너뛰려고 했다. 2. 최대 넓이가 50x50이고, 회전 하지 않았을 때, 90도, 180도, 270도 총 4가지를 비교하면 50x50(A퍼즐)x50x50(B퍼즐)x4 = 25,000,000가지로 생각(하나의 퍼즐을 고정해야겠다는 생각을 하지 못했다.) 3. 두 개 퍼즐의 행과 열이 다른 경우에 맞춰주려고 함 -> 하나를 고정해야겠다는 생각을 못해서 n1 > n2이고, m1 m2인 경우 0을 채워서 행과 열을 같게 맞춰주려고 했다. 4. 0, 90, 180, 270도 회전을 했을 때 각각 생각 -> swap()을 생각하지 못하고 회전 경우마다 for문을 생성해서 각각을 고려해주려고 했다. 결론 : 중첩된 fo..
짠돌이 호석 1번째 퍼즐 N1 * M1 2번째 퍼즐 N2 * M2 액자 가격 = 행의 개수 * 열의 개수 90도 180도 270도 회전 가능 ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ 큰 퍼즐을 가운데에 기준으로 잡고 사방으로 돌려가면서 붙여보기 1. 큰 퍼즐 / 작은 퍼즐 구분 --> 이 방법은 어차피 어떤 퍼즐을 기준으로 잡고 놓아도 똑같은 방식이기 때문에 첫번째 퍼즐을 기준으로 잡았다 모든 방법 다 해봐야함 0 90 180 270 4가지 방안 확인해야함 비교해볼 때 시작할 위치를 정하는 방법이 2가지 존재 0,0 부터 100,100 까지 다 검색 하거나 or 크기에 맞춰서 a*b 크기면 50-a, 50-b 에서 부터 시작하는 방식이 있다. 그러나 후자의 방법으로 할 시 복잡하거나 헷갈린다는 조언을 듣고 전자 ..