이것저것 공부 기록하기

문제링크 https://www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 문제설명 O(nlogn) 알고리즘으로 풀어야하는 문제이다. 따라서 시간복잡도가 O(n^2) 인 insertion sort, bubble sort로는 풀기 어렵고, 최악의 시간복잡도가 O(nlogn)인 merge sort나 heap sort로 풀어야 한다. 또한, python 기본 내장함수인 sort, sorted도 병합정렬을 기반으로 만들어진 함수로, O(nlogn)의 시간복잡..

문제링크 https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 문제설명 맨 아래 이외의 원반들은 목표장대가 아닌 보조장대로 옮기는 것을 재귀적으로 실행한다. 또한, n개의 원반을 이동시키기 위해서는 그 위의 n-1개의 원반을 다른 장대로 이동하고 맨 아래 원반을 도착지로 이동해야 한다. 그리고 다시 n-1개의 원반을 이동해야 하므로 다음과 같은 점화식이 성립한다. a_n = 2a_(n-1) + 1 이를 일반항으로 풀어내면 총 이동횟수는 ..

문제링크 https://www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net 재귀함수로 푸는 문제이다. 규칙파악이 포인트이고, 그 이후에는 재귀로 풀면 된다. 규칙파악 일정하게 가운데가 뚫린 정사각형 패턴이 반복되고 있다. 예를 들어, 3(=3^1)일 때는 가운데에 공백이 있고 1(=3^0)개 씩의 별이 찍히고 있다. 따라서 패턴은 다음과 같다. 3^i일 때 가운데를 공백으로 하고, 3^(i-1) 개 씩의 별 찍는다. 또한, 정사각형의 ..

문제링크 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 함수 시간복잡도)가 소요된다. (이 부분은 감으로 고치고 풀이 통과 후에 이왜맞과 맞왜틀을 동시에 시전하며 질문해..

오늘부터 나도 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 =..