공순이의 블로그

문제 출처 [문제 요약] 분해합이란 어떤 자연수 N이 있으면 N의 각 자릿수와 N을 더한 값이다. ex) 어떤 자연수 N이 245라고 하면, N의 분해합은 2+4+5+245 = 256 수식으로 나타내면 N(분해합) = M(생성자) + int(str(M)[0]) + … + int(str(M)[len(M-1)]), 간단하게 아래처럼 된다. 생성자란 분해합을 만드는 수이다. 위에서 말하던 어떤 자연수 N이 생성자다. 생성자는 여러개가 있기도, 없기도 한데 분해합이 입력으로 들어오면 가장 작은 생성자를 출력하는게 목표이다. 생성자가 없으면 0을 출력한다. [풀이] 분해합은 생성자의 각 자릿수와 생성자를 더하기 때문에 생성자보다 크다. 이 점을 이용해 분해합을 구하는 함수를 간단히 만든다음 룹을 생성자 - 1 만..

파이썬 2023. 8. 16. 16:10

문제 출처 [문제 요약] 원형 테이블에 n명의 사람들이 순서대로 앉아있다. 양의 정수 k가 주어지면 k번째에 앉은 사람을 제거하고, 재거한 사람 이후부터 다시 k번째에 앉아있는 사람을 제거한다. 이와 같은 방식으로 모두를 제거할때 제거하는 순서를 적으면 된다. 입력은 n k로 주어진다. 예를들어 입력이 7 3이라고 하자. 그리고 어떤 사람을 지울지 가리키는 변수를 편의상 idx(index 인덱스)라고 정의했다. 총 7명의 사람들이 원형으로 앉아있고, 스탭(step)은 3이어서 idx는 3씩 더해진다. 움직이는 칸을 편의상 스탭이라고 불렀다. 위 그림과 같은 상황에서 1부터 3칸을 세어보자. 그러면 처음으로 제거되는 숫자는 3이다. 제거된 수 이후부터 3칸을 더 가면 6, 또 3칸을 세어 원형 테이블의 마..

파이썬 2023. 8. 14. 20:11

문제 출처 [문제 요약] 길이가 제각각인 랜선 k개가 주어진다. 이를 길이가 동일한 n개의 랜선으로 잘라야 할때 가장 크게 자를 수 있는 길이를 출력하면 된다. * 자를때 손실되는 길이 없음 ** 기존 주어진 k개의 랜선으로 n개의 랜선을 만들 수 없는 경우는 없다고 가정 (답이 항상 있다) *** 단위는 정수 [풀이] 이분 탐색 문제이다. 간단하게 1부터 아직 어딘지 모를 최대 길이 limit가 있다고 가정을 하자. 보통 수열에서의 이분탐색은 범위를 가리키는 시작점(start)과 끝점(end)가 있고 찾아야 하는 수 정답(ans)이 있다면 start와 end의 딱 절반 지점인(이 문제에서는 중앙값인) half가 ans보다 큰지 작은지를 비교하면서 점점 그 범위를 좁혀 나가는 방식이다. half가 ans..

파이썬 2023. 7. 21. 15:35

문제 출처 [문제 요약] 입력을 n을 받는다. 그러면 n!에서 0 이외의 다른 수가 나오기 전까지의 0의 개수 (오른쪽 끝에 있는 0의 개수) 를 출력으로 내보내면 된다. [풀이] 1부터 n까지 곱할때 나오는 2와 5의 개수를 세서 10이 몇개인지 알아내면 된다. 2*5가 10이니 2가 나온 갯수, 5가 나온 갯수중 작은 수를 돌려주면 된다. [유의할점] 100같은 수는 10이 두번 곱해진 형태이다. 이처럼 어떤수의 최대공약수가 2^x * 5^y인 경우 (2 혹은 5의 몇승인 경우) 1번만 세는게 아니라 x와 y개만큼 전부 세어주어야한다. [파이썬 3 코드] def mul5(n): num5 = 0 while n % 5 == 0: n = n // 5 num5 += 1 return num5 def mul2(..

파이썬 2023. 6. 12. 14:57

문제 출처 [문제 요약] A가 펜케익을 T번 먹을때 남는 펜케익의 부피를 가장 크게 남길때의 부피를 구하는 것이다. 한번 먹을때 1cm 만큼 팬케이크의 한 변이 줄어든다. [풀이] 우선 test case의 개수를 input으로 받는다. 각 test case는 W(width), D(depth), H(height)와 t(먹는 횟수)를 input으로 주는데 가장 남는 부피를 크게 남기려면 W, D, H의 크기를 비슷하게 맞춰주어야한다. 그래서 셋 중 가장 큰 변의 크기를 1cm 씩 iterative 하게 줄이는 풀이가 easy 한 난이도를 통과하기 무난하다. [유의할 점] test case의 개수와 input이 1칸씩 더 띄워져있기 때문에 input을 받을떼 유의할것. [파이썬 3 코드] def max_min..

파이썬 2023. 6. 12. 09:43

문제 출처 [문제 요약] 승환이는 규현이에게 메시지를 받는다. 그런데 그냥 받는게 아닌 비밀 규칙을 적용해서 받는다. 우선 문자 메시지에 들어가는 글자는 알파벳 대문자와 공백으로 이루어져 있다. 글자는 아래처럼 십진수로 바꾼후 5자리 이진수로 바꾼다. 공백 = 0, A = 1, B = 2, ..., Y = 25, Z = 26 바뀐 이진수들은 시계방향의 소용돌이 패턴으로 행렬에 저장한다. 첫 줄에는 해석해야하는 행렬의 개수 (n) 를 받고 그 개수만큼 행렬을 입력을 받는다. 행렬의 행과 열, 그리고 소용돌이 패턴으로 저장된 행렬을 행 우선으로 한 줄로 읽은 것을 입력으로 받는다. 출력으로는 메시지를 프린트하면 된다. 추가적으로 행렬에서 남는칸은 0으로 채우고 만일 해석한 메시지의 끝에 공백이 있으면 공백은..

파이썬 2023. 6. 7. 07:23

문제 출처 [문제 요약] 행렬 두개가 주어지면 행렬 곱 결과를 프린트 하면 된다. 행렬 A = N*M 행렬 B = M*K 참고로 행렬 곱은 아래 이미지처럼 A의 row(열), B의 column(행)에 있는 각각의 원소들을 (순서가 같은것끼리) 곱한 후 더하면 된다. 1*(-1) + 2*0= -1 1*(-2) + 2*0 = -2 1*0 + 2*3 = 6 ... 5*0 + 6*3 = 18 따라 빨간색으로 표시 되어있는 열과 행이 사용되기 때문에 A의 행과 B의 열의 크기는 같다. 입력은 우선 행렬 A의 크기 (n, m)가 주어지고 이후 m개의 줄에 걸쳐 각 줄마다 n개의 원소가 띄어져 입력이 된다. 바로 이어서 행렬 B의 크기 (m, k)가 주어지고 이후 k개의 줄에 걸쳐 각 줄마다 m개의 원소가 띄어져 입..

파이썬 2023. 6. 4. 11:23

문제 출처 [문제 요약] 나이트 투어의 정의는 체스에서의 나이트가 모든 칸을 정확히 한번찍 방문하고 마지막으로 방문하는 칸에서 시작점으로 돌아오는 경로를 의미한다. 아래와 같은 6*6 체스판에서 나이트 투어를 할 때, 36개의 입력이 나이트 투어의 정의를 만족하는지를 판별하면 된다. 가로는 알파벳이, 세로는 숫자로 표기되어 "1A", "2A", ..., "6F"까지 나이트가 방문한 칸을 표기할 수 있다. [풀이] 나이크는 총 3칸을 움직이는데 아래처럼 방향은 자유롭게 아래처럼 움직인다. 가로 1칸 -> 세로 2칸 가로 2칸 -> 세로 1칸 따라서 원래 있던 자리에서 새롭게 간 자리가 나이트 움직임인지를 판별하려면 알파벳 사이의 간격과 숫자 사이의 간격의 합이 3이 되는지를 보면 된다. 그리고 마지막으로 ..

파이썬 2023. 6. 4. 10:00