간단한 스택 구현 문제. k = int(input()) lst = [] for i in range(k): n = int(input()) if n == 0: lst.pop() else: lst.append(n) print(sum(lst))

import sys N = int(sys.stdin.readline()) stack = [] def push(n): stack.append(n) def pop(): if len(stack) != 0: a = stack[0] stack.pop(0) print(a) else: print("-1") def size(): print(len(stack)) def empty(): if len(stack) == 0: print("1") else: print("0") def front(): if len(stack) == 0: print("-1") else: print(stack[0]) def back(): if len(stack) == 0: print("-1") else: print(stack[-1]) func_dic..

이 포스팅은 유클리드 호제법을 공부하고 나서 백준문제를 해결하고 정리를 위해 올리는 글입니다. 유클리드 호제법은 최대공약수,최소공배수를 쉽게 구할 수있는 공식들 중에 하나이다. 방법은 또 매우 간단한데, 최대공약수를 구하기 위해서 예를들어 A와 B라는 수가 각각 주어진다면 최대공약수를 구하기 위해서는 AxB를 Bx(A%B)로 나눠주고 나온 나머지를 r이라고 할때 r이 0이 아니라면, 이를 다시 두번째 항 (Bx(A%B))과 나머지 연산을 해서 r을 또 구하고.. 이게 다시 0이 아니라면 또 다시 두번째 항과 나눠주고.. 이것을 반복해서 나머지가 0인 값이 최대공약수가 된다. 최소공배수는 여기서 구한 최대공약수를 이용해서 아주 쉽게 구할 수 있다. a와 b의 최소공배수는 a와 b의 곱을 a와 b의 최대공약..

import math n,n2 = map(int,input().split()) a = math.gcd(n,n2) b = math.lcm(n,n2) print(a) print(b) MATH 라이브러리로 해결하긴 했는데 문제가 원하는 방향은 유클리드 호제법을 이용한 해결이기 때문에 이를 이용한 방법으로도 해결한 뒤 다시 포스팅 해볼 예정

n = int(input()) dp = [0 for _ in range(n+1)] #[0,1,0,0,0] dp[0] = 0 dp[1] = 1 def dynamic(n): for i in range(2, n+1): dp[i] = dp[i-1] + dp[i-2] return dp[n] print(dynamic(n)) 기초적인 dp문제이다. 피보나치 수를 재귀로 구현하면 배열에서 입력받은 i의 함수 [i-2] + [i-1] 를 재귀적으로 호출해서 계산해야한다. 이는 매우 비효율적이며 구해야하는 값이 커질수록 시간도 오래 걸린다. 따라서 dp를 이용하여 값을 저장하며 진행하면 시간이 더욱 단축된다.

동적계획법을 배우고 나서 백준에서 문제를 풀어보았고 어느정도 머리에 지식이 생긴것 같아서 생각도 정리 할 겸 포스팅 하기로 했다. 예제로 풀 문제가 필요하여 chatGPT에게 간단한 문제를 받아보았다. 우선 해당 코드를 재귀함수로 풀어보자면 재귀함수를 이용한 코드 def count_ways(n): if n == 0: return 1 elif n < 0: return 0 else: return count_ways(n-1) + count_ways(n-2) + count_ways(n-3) n = 4 result = count_ways(n) print(result) # 7 return 문을 보면, count_way() 내부에서 다시 해당 함수를 호출한다. 이 코드는 재귀적으로 호출을 하기 때문에 시간 복잡도를 ..