💻 Problem문제 보러 가기 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 5^2과 1 ^ 2의 합이다; 또한 4 ^ 2 + 3 ^ 2 + 1 ^ 2으로 표현할 수도 있다. 역사적으로 암산의 명수들에게 공통적으로 주어지는 문제가 바로 자연수를 넷 혹은 그 이하의 제곱수 합으로 나타내라는 것이었다. 1900년대 초반에 한 암산가가 15663 = 125 ^ 2 + 6 ^ 2 + 1 ^ 2 + 1 ^ 2라는 해를 구하는데 8초가 걸렸다는 보고가 있다. 좀 더 어려운 문제에 대해서는 56초가 걸렸다: 11339 = 105 ^ 2 + 15 ^ 2 + 8 ^ 2 + 5 ^ 2.자연수 n이 주어..

💻 Problem문제 보러 가기  과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.  💡 Approachn * n 배열의 각 칸을 살펴보며 집이 있으면 bfs로 연결 개수를 찾는다.bfs 탐색이 끝나면 연결 개수를 res 리스트에 삽입한다.모든 칸을 탐색한 후에 res의 길이와..

💻 Problem문제 보러 가기 한결이를 도와 k번째 소수를 알려주자.소수의 정의는 다음과 같다.2 이상의 자연수 N이 1과 N을 제외하고 어떤 자연수로도 나누어 떨어지지 않을 때 소수라고 한다. 💡 Approach25점 코드import sysinput = sys.stdin.readlinedef is_prime(target): global k for i in range(2, int(target ** 0.5) + 1): if target % i == 0: return False k -= 1 return Truek = int(input())i = 1while k > 0: i += 1 is_prime(i)print(i)반복문으로 소수 ..

💻 Problem문제 보러 가기  농장에는 N마리의 소가 있다. 농부 존은 소들의 몸무게의 합이 소수(prime)가 되도록 M마리의 소를 선별할 계획이다. 농부 존의 계획에 맞게 소를 선별했을 때 나올 수 있는 몸무게의 합을 모두 출력하시오.  💡 Approach전체 로직조합으로 m마리의 소를 뽑아 후보 리스트에 저장한다.후보를 하나씩 살펴본다.몸무게의 합을 구해 몸무게의 합이 소수이면 정답 리스트에 추가한다.정답 리스트를 정렬해서 출력한다. (비어있으면 -1 출력) 소수 판정 로직target이 1이면 소수가 아니다.target에서 2부터 √ target까지의 값 중 나눠지는 숫자가 있으면 소수가 아니다.1, 2에서 걸리지 않았으면 소수이다.  소수 판정 로직의 2번에서 반복문의 범위가 2 ~ √ t..

💻 Problem문제 보러 가기 에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다.이 알고리즘은 다음과 같다.2부터 N까지 모든 정수를 적는다.아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다.P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.N, K가 주어졌을 때, K번째 지우는 수를 구하는 프로그램을 작성하시오. ✏️ Solution 1import sysinput = sys.stdin.readlinen, k = map(int, input().split())num = [i for i in range(2, n + 1)]while num: p = num.pop..

💻 Problem문제 보러 가기 케빈 베이컨의 6단계 법칙에 의하면 지구에 있는 모든 사람들은 최대 6단계 이내에서 서로 아는 사람으로 연결될 수 있다. 케빈 베이컨 게임은 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임이다.예를 들면, 전혀 상관없을 것 같은 인하대학교의 이강호와 서강대학교의 민세희는 몇 단계만에 이어질 수 있을까?천민호는 이강호와 같은 학교에 다니는 사이이다. 천민호와 최백준은 Baekjoon Online Judge를 통해 알게 되었다. 최백준과 김선영은 같이 Startlink를 창업했다. 김선영과 김도현은 같은 학교 동아리 소속이다. 김도현과 민세희는 같은 학교에 다니는 사이로 서로 알고 있다. 즉, 이강호-천민호-최백준-김선영-김도현-민세희 와 같이 5단계만..

💻 Problem문제 보러 가기 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다.X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해 보자.1 ≤ N ≤ 1,000,000-109 ≤ Xi ≤ 109 💡 Approach이 문제는 처음에 이해하기 힘들었다..좌표 압축이 무슨 말인지,,, 왜 하는 건지,,친구한테 설명을 듣고 나서야 이해했다. x[i]를 압축한 값은 x[i]`이다 x[i]` 값은 X[i] > x[j]를 만족하는 x[j]의 개수이다 => x[i]` 값은 x[i]보다 작은 수의 개수이다 왜 ..

💻 Problem문제 보러 가기 여러 개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다. 전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 의 I, II, III, IV와 같이 똑같은 크기의 네 개의 N/2 × N/2색종이로 나눈다. 잘라진 종이가 모두 하얀색 또는 모두 파란색으로 칠해져 있거나, 하나의 정사각형 칸이 되어 더 이상 자를 수 없을 때까지 반복한다. 입력으로 주어진 종이의 한 변의 길이 N과 각 정사각형칸의 색(하얀색 또는 파란색)이 주어질 때 잘라진..