이것저것 공부 기록하기

문제링크 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 문제풀이 주어진 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 문제이므로 투포인터로 풀이가 가능한 문제이다. 수열의 길이 N과 타겟으로 봐야할 S의 범위는 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000) 이므로 시간초과에 유의해야한다. 처음에는 아무 생각 없이 주어진 수열 arr의 길이를..

문제링크 https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 문제풀이 에라토스테네스의 체 기반으로 풀었다. m, n이 1부터 입력될 수 있기 때문에 sieve의 0, 1을 False로 초기값을 설정해야 한다. m, n = map(int, input().split()) x = int(n**0.5) sieve = [False,False] + [True] * (n-1) for i in range(2, x+1): if sieve[i] == True: for j in range(2*i, ..

문제링크 https://www.acmicpc.net/problem/2960 2960번: 에라토스테네스의 체 2, 4, 6, 8, 10, 3, 9, 5, 7 순서대로 지워진다. 7번째 지워진 수는 9이다. www.acmicpc.net 문제풀이 n, k = map(int, input().split()) sieve = [True] * (n+1) m = int(n**0.5) chk = [] for i in range(2,m+1): if sieve[i] == True: chk.append(i) for j in range(2*i, n+1, i): sieve[j] = False if j not in chk: chk.append(j) chk += [i for i in range(m+1,n+1) if sieve[i] =..

문제링크 https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 문제는 일정 범위 내의 연속된 소수의 합을 찾아야하므로 에라토스테네스의 체로 소수의 리스트를 구하고, 구한 소수 리스트에서 투포인터로 그 합을 구하는 것이 포인트이다. 이 부분을 인지해서 풀이했지만, 처음에는 시간초과가 났고 투포인터 부분에서 시간복잡도 문제가 있다고 생각했다. val = sum(tmp[left:right])에서 (O(right-left) 만큼의 공간을 만드는 시간) + (sum 함수 시간복잡도)가 소요된다. (이 부분은 감으로 고치고 풀이 통과 후에 이왜맞과 맞왜틀을 동시에 시전하며 질문해..

https://www.acmicpc.net/problem/10814 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 www.acmicpc.net n = int(input()) tmp = [] for i in range(n): tmp.append(input().split()) tmp = [[int(x[0]),x[1]] for x in tmp] tmp.sort(key=lambda x:x[0]) for i in range(n): print(*tmp[i]) 정렬문제인데 나는 그냥 sort 써서 했다보니 채점시간이 4000ms이 걸렸다. 이후에 좀 더 ..

오늘부터 나도 1일1문제 시작. 오늘의 문제 : https://www.acmicpc.net/problem/18258 18258번: 큐 2 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net # sys.stdin.readline() 을 사용해야 시간초과 안 나고 통과됨 (같은 풀이일 때 input() 으로 받면 시간초과남) import sys from collections import deque n = int(sys.stdin.readline()) q = deque() for i in range(n): tmp =..

교차검증이란? 머신러닝을 돌리기 전에 train test로 나눠 머신을 훈련한다. 하지만 이 훈련 때 학습 데이터에 과도하게 초점을 맞춰 머신이 훈련될 수가 있다. 이 같은 경우에는 훈련시에는 점수가 잘 나오지만 실제 테스트를 할 때는 점수가 잘 나오지 않는다. 이걸 과적합(overfitting)이라고 한다. 우리는 훈련시에 이 같은 과적합을 막아야 한다. 이걸 위해 교차검증 이란 것 을 사용한다. 교차검증이란 훈련 데이터 세트를 바꿔가면 훈련하면서 나온 평균을 정확도로 보는 방법을 뜻한다. 이렇게 훈련 데이터 세트를 교차하면서 검증을 하기에 교차 검증이라고 한다. # K-fold 교차검증 학습세트와 검증 세트를 나눠 반복해서 검증한다. 이걸 k값만큼의 폴드 세트에 k번의 학습과 검증을 한다. 이러한 방..

References https://brunch.co.kr/@mathian/32