Just code it

문제자연수 N의 분해합은 N과 N의 각 자리수를 더한 값이다. 예를 들어, 245의 분해합은 다음과 같다.245 + 2 + 4 + 5 = 256이때, 245는 256의 생성자가 된다. 생성자는 여러 개일 수 있으며, 생성자가 없는 경우도 있다.우리의 목표는 주어진 자연수 N에 대해 가장 작은 생성자를 찾는 것이다.배경지식이 문제는 브루트 포스 알고리즘 단계에 들어가 있다. 브루트 포스 알고리즘에 대해 간단히 알아보자면, 브루트(Brute)는 무식한 이라는 뜻이다. 한마디로 무식하게 다 해보는 알고리즘을 브루트 포스 알고리즘이라고 한다.논리 및 아이디어1. 값을 입력받는다.(입력받은 값: n)2. 1부터 n-1까지 해당 숫자와 자릿수를 모두 더해 생성자인지 확인한다.3. 생성자가 맞다면 반복문을 깨고 나온..

문제배경지식이 문제의 경우 소수를 찾는 문제이기 때문에 우선 수가 주어졌을 때, 그 수가 소수인지부터 확인하는 판별법을 알고 구현해야 한다.소수 판별법에는 여러 방법이 있지만 에라토스테네스의 체와 직접 나누어보는 방법이 가장 널리 알려져 있다. 관련된 이론적 배경은 이 단계 내에서 많이 사용되기에 따로 다루어 보았다.https://aaaaaaaaaaayowooji.tistory.com/31 [파이썬과 알고리즘] 소수 판별 알고리즘(에라토스테네스의 체, 직접 나누기)소수 찾기백준에 있는 문제들을 해결하면서 소수와 관련된 많은 문제들을 접했다.소수를 판별하는 방법으로 잘 알려진 에라토스테네스의 체와 직접 나누어서 판별하는 방법을 이번에 간단히aaaaaaaaaaayowooji.tistory.com  논리 및 ..

오늘은 백준 13909번 창문닫기를 풀어보았다.문제논리 및 아이디어먼저 짠 나의 코드먼저 든 생각은 '에라토스테네스의 체 알고리즘에서 했던 것처럼 배수 인덱스에 접근하여 창문의 상태를 바꿔주면 되겠다 '였다.딕셔너리를 통해 창문의 이름(즉, n의 배수)과 창문의 상태(0 또는 1)를 만들어준다.1부터 N까지 숫자를 증가시키면서 N의 배수에 접근하여 창문을 열고 닫는다.열려있는 창문의 갯수를 센다.시간초과 실패 후 찾은 최적의 코드1의 배수는 모든 창문을 연다.창문은 열고 닫는다. 즉, 해당 숫자에 짝수 번 접근하면 창문은 닫혀있다. 반대로 홀수 번 접근하면 창문은 열려있다.숫자에 접근하는 횟수는 약수와 관련된다. 가령, 4는 1번째 사람, 2번째 사람, 4번째 사람이 열고 닫으므로 마지막에 열려있을 것이..

오늘은 백준 2485번 가로수를 풀어보았다.문제 배경지식최대공약수 알고리즘.(유클리드 호제법)2개의 자연수 a, b(a> b)에 대하여 a를 b로 나누었을 때, 나머지를 r이라 하면 a와 b의 최대공약수는 b와 r의 최대공약수와 같다반복해서 b를 r로 나눈 나머지를 r'이라 하면 r과 r'의 최대공약수가 b와 r의 최대공약수와 같다.나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수다. 파이썬 구현def gcd(m,n): while n! = 0: if m math모듈 내의 gcd 함수의 인자에는 자연수 두 개는 물론, iterable 자료형 (요소가 자연수로 이루어진) 도 가능했다.(찾아보니 파이썬 3.9부터 임의의 개수 인자에 대한 지원이 추가되었다고 한다. 출처에 링크 참고)[2,..

안녕하세요!Wooji입니다.오늘은 백준 2903번 중앙 이동 알고리즘을 풀어보았습니다. 배경지식이 문제는 배경지식이라고는 필요 없고 규칙을 어떻게 간단하게 찾느냐가 관건입니다.논리 및 아이디어단순히 문제를 풀기 전 논리일 뿐입니다. 틀릴 확률이 다분합니다.N 단계에서 N-1 단계의 점은 영향을 주지 않으므로 그대로 더하면 되겠다.한 단계가 더해질 때마다 사각형 하나에 점이 5개씩 생긴다.겹치는 점은 N단계에서 (2^(N-1))× (2^(N))×2 개다.최종 식은 [(N-1) 단계의 점의 개수] + 5 × (4^N) - (2^(N-1))× (2^(N))×2나의 코드num=int(input())new=4for i in range(num):    new=new+5*4**(i)-(2**(i)-1)*(2**(i)..

안녕하세요!Wooji 입니다.오늘은 백준 11653번 소인수분해를 풀어보았습니다.여러 가지 풀이를 비교해보고 최적의 답을 찾아보았는데요 해답만 필요하다면 해답 파트로 내려서 보시면 될 것 같습니다! 배경지식소인수분해란?합성수를 소수의 곱으로 나타내는 방법예를 들면, 21＝3×7와 같은 방식으로 나타내는 것을 말합니다. 논리 및 아이디어해당 파트는 코드로 구현하기 전 생각해본 논리일 뿐입니다. 틀릴 확률이 다분합니다.코드를 짜기 전에 우리가 소인수분해하는 방식을 코드로 구현해내면 되겠죠. 그래서 소인수분해하는 방법을 떠올려봅니다.18을 소인수분해한다고 생각해보면 먼저 2로 나눕니다. 9는 2로 안나눠지기 때문에 3으로 넘어가서 3으로 나누어 봅니다.3으로 나누면 3이 남고 마지막으로 3은 더 이상 나눌 수..

안녕하세요! Wooji입니다.파이썬을 다시 복습 겸 공부를 진행하고 있는데 그의 일환으로 백준 문제들을 조금 풀어볼까 합니다. 몇 문제를 풀어봤는데 문제 푸는 거 같고 재밌네요.사실 해답을 티스토리에 올려봤자 이미 해답을 작성해서 올려놓으신 분이 많아서 제 글이 읽힐지는 모르겠습니다.그럼에도 작성하고자 하는 이유는 처음에 문제를 풀 때 저의 논리(틀리든 맞든), 그리고 여러 사람들의 풀이를 비교해 보고 최적의 답을 찾아가는 과정을 남겨보고 싶어서입니다. 모든 문제의 해답을 작성하기 보다 저에게 의미가 있는 문제들만 골라서 할 겁니다. 그럼 많은 관심 부탁드립니다!!