이것저것 공부 기록하기

문제링크 https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 문제설명 [아이디어1] N x M 판을 전체 경우의 수로 돌려야 한다. 그러기 위해서는 인덱스가 8을 넘지 않도록 조정을 해줘야 한다. 9x9에서 움직여서 조사할 수 있는 경우의 수는 2x2 = 4개이며, 10x10에서 움직여서 조사할 수 있는 경우의 수는 3x3 = 9개이고, 11x11에서 움직여서 조사할 수 있는 경우의 수는 4x4 = 16개이다. 따라서 i는 N-7의 범위에서..

문제링크 https://www.acmicpc.net/problem/7568 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩 www.acmicpc.net 문제설명 n명 집단에서 각 사람의 덩치 등수는 자신보다 더 '큰 덩치'의 사람의 수로 정해진다. 또한, 가장 큰 덩치의 사람은 키와 몸무게가 모두 어떤 사람보다도 더 커야하며 그 등수는 1이다. 따라서 자신보다 더 큰 덩치의 사람이 k명이면 그 사람의 덩치 등수는 k+1이다. 이 때, 같은 덩치 등수를 가진 사람은 여러 명도 가능하므로, 2중으로 for문을 돌면서 요소 간 완..

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

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이 걸렸다. 이후에 좀 더 ..