Berom's Blog

백준 1699 제곱수의 합문제어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=2^2+2^2+1^2+1^2+1^2(5개 항)도 가능하다. 이 경우, 수학자 소크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다. 주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 프로그램을 작성하시오 풀이처음 문제를 접근할 땐 주어진 숫자보다 작은 가장 큰 제곱 수부터 차례대로 구하면서 풀었다.하지만 가장 큰 제곱 수부터 차례대로 구하는 방식이 항의 갯수를 최소한으로 한단 보장을 하지 못한다.즉 DP 문제이다. 핵심아래는 1부터 7까지의 최소 제곱 항의 수이다 ...

문제첫째 줄에 저장된 사이트 주소의 수 N(1 ≤ N ≤ 100,000)과 비밀번호를 찾으려는 사이트 주소의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 두번째 줄부터 N개의 줄에 걸쳐 각 줄에 사이트 주소와 비밀번호가 공백으로 구분되어 주어진다. 사이트 주소는 알파벳 소문자, 알파벳 대문자, 대시(‘-‘), 마침표(‘.’)로 이루어져 있고, 중복되지 않는다. 비밀번호는 알파벳 대문자로만 이루어져 있다. 모두 길이는 최대 20자이다. N+2번째 줄부터 M개의 줄에 걸쳐 비밀번호를 찾으려는 사이트 주소가 한줄에 하나씩 입력된다. 이때, 반드시 이미 저장된 사이트 주소가 입력된다. 출력첫 번째 줄부터 M개의 줄에 걸쳐 비밀번호를 찾으려는 사이트 주소의 비밀번호를 차례대로 각 줄에 하나씩 출력한다. 풀이123456789101112import sysn,m = map(int,sys.stdin.readline().split())dic = {}for i in range ...

백준 17299 오등큰수문제크기가 N인 수열 A = A1, A2, …, AN이 있다. 수열의 각 원소 Ai에 대해서 오등큰수 NGF(i)를 구하려고 한다. Ai가 수열 A에서 등장한 횟수를 F(Ai)라고 했을 때, Ai의 오등큰수는 오른쪽에 있으면서 수열 A에서 등장한 횟수가 F(Ai)보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오등큰수는 -1이다. 예를 들어, A = [1, 1, 2, 3, 4, 2, 1]인 경우 F(1) = 3, F(2) = 2, F(3) = 1, F(4) = 1이다. A1의 오른쪽에 있으면서 등장한 횟수가 3보다 큰 수는 없기 때문에, NGF(1) = -1이다. A3의 경우에는 A7이 오른쪽에 있으면서 F(A3=2) < F(A7=1) 이기 때문에, NGF(3) = 1이다. NGF(4) = 2, NGF(5) = 2, ...

문제김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오. 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 둘재 줄부터 순서대로 듣도 못한 사람과 보도 못한 사람의 이름이 순서대로 입력됨 출력듣도 보도 못한 사람의 수와 이름을 출력하라 풀이12345678910111213141516import sysn, m = map(int, sys.stdin.readline().split())nset = set()mset = set()for i in range(n): nset.add(sys.stdin.readline().rstrip())for j in range(m): mset.add(sys.stdin.readline().rstrip())result = list(nset.intersection(mset))print(len(result))for r in sorted(result) ...

백준 1780 종이의 개수문제N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.(1)이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다.이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오. 풀이123456789101112131415161718192021222324252627282930import sysdef solve(x,y,n): num = paper[x][y] for i in range(x,x+n): for j in range(y,y+n): if (paper[i][j]!=num): ...

백준 18870 좌표 압축문제수직선 위에 N개의 좌표 X1, X2, …, XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X’i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, …, XN에 좌표 압축을 적용한 결과 X’1, X’2, …, X’N를 출력해보자. 풀이123456789101112131415import sysn = int(sys.stdin.readline())numbers = list(map(int,sys.stdin.readline().split()))sNumbers = sorted(list(set(numbers)))numDic={}for num in numbers: numDic[num]=0for i in range(len(sNumbers)): numDic[sNumbers[i]]=ifor i in range(n): print(numDic[numbers[i]], e ...

백준 1931 회의실 배정문제한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다. 풀이처음 풀이는 회의실 배정 한 곳을 체크해서, 간 곳은 안 가고, 바로 이어지는 회의 시간을 이어갈 때마다 카운트하는 방식으로 풀었다.하지만 시간 초과 문제를 잘못 이해했었다. 꼭 이어질 필요는 없다. 123456789101112131415161718192021222324import systime = int(sys.stdin.readline())conference = [list(map(int,sy ...

백준 1935 후위 표기식 2문제후위 표기식과 각 피연산자에 대응하는 값들이 주어져 있을 때, 그 식을 계산하는 프로그램을 작성하시오. 입력첫째 줄에 피연산자의 개수(1 ≤ N ≤ 26) 가 주어진다.둘째 줄에는 후위 표기식이 주어진다. (여기서 피연산자는 A~Z의 영대문자이며, A부터 순서대로 N개의 영대문자만이 사용되며, 길이는 100을 넘지 않는다)셋째 줄부터 N+2번째 줄까지는 각 피연산자에 대응하는 값이 주어진다. 3번째 줄에는 A에 해당하는 값, 4번째 줄에는 B에 해당하는값 , 5번째 줄에는 C …이 주어진다, 그리고 피연산자에 대응 하는 값은 100보다 작거나 같은 자연수이다. 후위 표기식을 앞에서부터 계산했을 때, 식의 결과와 중간 결과가 -20억보다 크거나 같고, 20억보다 작거나 같은 입력만 주어진다. 풀이핵심 아이디어 후위 표기식의 계산 방식을 알고 있는가 컴퓨터가 순차적으로 어떻게 계산해 나가도록 할 것인가? 후위 표기식으로 표기를 하게 되면 연산자의 ...

백준 1992 쿼드 트리문제흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다. 흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축하여 간단히 표현할 수 있다. 주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 “0”이 되고, 모두 1로만 되어 있으면 압축 결과는 “1”이 된다. 만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지를 못하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영상으로 나누어 압축하게 되며, 이 4개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현한다 영상을 압축한 결과를 출력하라 풀이12345678910111213141516171819202122232425import syssys.setrecursionlimit(15000)n = int(sys.stdin.readline())tree ...

백준 1929 소수 구하기문제M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오. 풀이 N이하의 소수들을 모두 구한 후 M과 N 사이의 소수를 출력한다 CODE123456789import sysM,N = map(int, sys.stdin.readline().split())arr = [False,False] + [True] * (N-1)for i in range(2,N+1): for j in range(2*i,N+1,i): arr[j] = Falsefor i in range(M,N+1): if arr[i] == True: print(i)