Warm Developer

그리디 알고리즘(Greedy Algotirhm) 이란? 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 말한다. 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 한다. Q. 거스름 돈 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한으로 존재한다. 손님에게 거슬러 주어야 할 돈이 N원일 때 거슬러 주어야 할 최소의 동전 개수를 구하라. 단, 거슬러 줘야 할 돈N은 항상 10의 배수이다. A. n = 1260 count = 0 array = [ 500, 100, 50, 10 ] for coin in array: count += n // coin n %= coin print(count) -> 거스름 돈이 1,260원일 때, array리스트(동..

등차수열의 합을 구해보자. 등차수열 이란? 연속하는 두 항의 차이가 모두 일정한 수열을 뜻한다. Q. 1 × 20 + 2 × 19 + 3 × 18 + ⋯ + 20 × 1 = ? A. def summation(n): s = 0 for i in range(1, n+1): s += i * (n+1 - i) return s print(summation(20)) Q. 재귀를 통해 수열의 합 구하기 A. def sumOfArray(array, i): end = len(array) - 1 if end == i : return array[end] else: return array[i] + sumOfArray(array, i+1) print(sumOfArray([1,2,3,4,5,6,7,8,9,10],0)) 이외에도 재..

2차원 배열을 생성하여 마방진을 만들어보자. 마방진(Magic Square) 이란? 일정한 칸 안에 있는 중복을 허용하지 않은 숫자들의 가로, 세로, 대각선의 합이 같은 것을 말한다. 대표적으로 마방진을 활용한 알고리즘 게임으로 스도쿠가 있다. Warming up. 간단하게 이차원 배열을 출력해보자. magicSquare = [ [1, 14, 14, 4], [11, 7, 6, 9], [8, 10, 10, 5], [13, 2, 3, 15] ] for i in range(len(magicSquare)): print(magicSquare[i]) 1. 배열 중 행의 합을 출력하는 함수를 만들자. def checkRow(square): for row in range(len(square)): sum = 0 for ..

계란을 낙하시켜 계란이 깨지는 높이를 찾아보자 Q1. 계란을 땅에 낙하하는 실험을 할 때, 계란이 깨지는 최소 높이(H)를 구하시오. 단, 계란은 1개 있음. A. # 계란 낙하실험 문제 n = 100 # 횟수 answer = random.randint(1, n) # 높이 # 계란이 깨지는지 안깨지는지 판별 def isSafe(h): if h 높이 1부터 100까지 순차적으로 확인한..

질문을 통해 답을 맞추는 놀이를 해보자 Q. 1,000 이하의 자연수 n을 생각할 테니 맞춰보시오. A. # 임의의 수 : 난수 (random 모듈 사용 : randint(a,b)) import random def guess(answer, start, end): print(answer) while start 1. 임의의 난수, 범위 시작 수, 마지막 수를 받는다. 2. 범위의 중간을 계산하여 mid 변수에 넣고 임의의 난수와 비교한다. 3. ..

로마 숫자 표기법 로마 숫자는 위와 같이 표기하며 python dict 형태로 표현하면 아래와 같다. romanDict = {'M':1000, 'D':500, 'C':100, 'L':50, 'X':10, 'V':5, 'I':1} Q. 로마 문자 'MDCLXVI' 를 아라비아 숫자로 변경해보자. A. # 감산표기법(IV=4, IX=9, XL=13, XC=19,,,) 추가 및 함수로 변경 def romatoArabic(roman): arabic = 0 for i in range(len(roman)): val = romanDict[roman[i]] # 총 길이의 마지막을 제외하고 and 현재 roman[i]와 뒤의 roman[i+1]을 비교하여 감산 if (i 감산표기법은 뒤 문자의 숫자가 더 클 경우 (뒤 ..

콜라츠의 추측이란? 1937년 Collatz란 사람에 의해 제기된 추측으로 주어진 수가 짝수이면 2로 나누고, 홀수이면 곱하기3을 한 다음 1을 더하는 작업을 반복하면 모든 수를 1로 만들 수 있다고 제시한 수학적 명제이다. 1. python 코드로 구현 def collatz(n): seq = [n] while (n > 1): # 주어진 수 n이 1보다 클 때까지 반복 if n % 2 == 0 : # 짝수인 경우 n = n // 2 else: # 홀수인 경우 n = 3 * n + 1 seq.append(n) return seq -> seq 리스트에 append 함으로써 콜라츠의 수열을 볼 수 있다. 마지막은 1이 나온다. Q. 콜라츠의 수열 길이가 100인 숫자들 중에서 가장 작은 수는? A. n = 1..

Q. 2021-5-10부터 1000일 후의 날짜는? A. 1. python 코드를 함수화하여 구현 year = 2021 month = 5 day = 10 n = 1000 # 윤년, 그레고리력 근거하여 구함 def leapyear(y): # 4의 배수이며 100의 배수가 아닐 때 and 400의 배수일 때 if ((y%4 == 0 and y%100 !=0) or y % 400 == 0): return True else: return False def invalidDay(y,m,d): num = 31 if m in [4,6,9,11]: # 4,6,9,11월은 30일 num = 30 if m == 2: # 2월은 윤년 판별에 따라 29일 28일로 나눈다. if leapyear(year): num = 29 el..

공배수란? 두 개 이상의 자연수 중에서 공통인 배수 최소공배수(Least Common Multiple)란? 공배수 중 가장 작은수를 말하며, x와 y가 주어졌을 때 두 수를 곱한 수에서 두 수의 최대공약수를 나누면 최소공배수가 된다. import math def lcm(n,m): return (n*m) // math.gcd(n,m) Q. 1에서 10까지의 최소공배수를 구하라. A. import math def lcm(n,m): return (n*m) // math.gcd(n,m) def lcmFromTo(start, end): l = start for i in range(start+1, end+1): l = lcm(l,i) return l # 1에서 10까지 최소공배수 -> 2520 print(lcmFr..

소인수란? 어떤 자연수의 인수(약수)중에서 소수인 것 소인수분해란? 1보다 큰 자연수를 소인수만의 곱으로 나타낸 것 ex) 30 -> 2 x 3 x 5 1. n까지의 소수를 찾은 후 소수를 나누어서 소인수 분해하기 # 소수 판별 def isPrime(num): for i in range(2, math.floor(math.sqrt(num))+1): if num % i == 0 : return False return True # 소수 찾기 def findPrimes(n): primes = [] for i in range(2, n+1): # for i in range(2, (n//2)+1) 로 개선 가능 if isPrime(i): primes.append(i) return primes print('소수 리스트..