Simple Explain

#1463번 1로 만들기 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 수학과 관련된 문제를 모두 해결하고 나니 다이나믹 프로그래밍이라는 새로운 분야를 만나게 됐다. 바로 다이나믹 프로그래밍. 동적 계획법이라고도 표현되는 이 문제는 기존에 내가 애용해왔던 재귀함수와 유사한 부분이다. def : 큰 문제를 작은 문제로 나누어 푸는 방법. 분할 정복과 비슷하지 않냐는 의견을 낼 수도 있지만, 분할 정복은 같은 형태의 계산을 반복해서 수행하지만 다이나믹 프로그래밍은 작은 문제를 해결한 결과를 재사용하는 형태이다. 동적 프로그래밍을 진행하기 위한 충분조건은 다음과..

#2089번 https://www.acmicpc.net/problem/2089 2089번: -2진수 -2진법은 부호 없는 2진수로 표현이 된다. 2진법에서는 20, 21, 22, 23이 표현 되지만 -2진법에서는 (-2)0 = 1, (-2)1 = -2, (-2)2 = 4, (-2)3 = -8을 표현한다. 10진수로 1부터 표현하자면 1, 110, 111, 100, 101, 11010, 110 www.acmicpc.net -2 진수로 변환하는 문제이다. 기본적인 2진법은 자리수 마다 2의 제곱수를 해주는데 -2진법은 -2의 제곱수를 자리해주는 방식이다. 때문에 1,3,5,7 번째 자리 즉 홀수번 째 자리에서는 양수가 나오고, 짝수번 째 자리에서는 음수가 나온다. 이를 잘 조합해서 변환해주면 된다. 처음엔 ..

#17087 https://www.acmicpc.net/problem/17087 17087번: 숨바꼭질 6 수빈이는 동생 N명과 숨바꼭질을 하고 있다. 수빈이는 현재 점 S에 있고, 동생은 A1, A2, ..., AN에 있다. 수빈이는 걸어서 이동을 할 수 있다. 수빈이의 위치가 X일때 걷는다면 1초 후에 X+D나 X-D로 이 www.acmicpc.net 최소공약수가 필요한 문제인데, 난 여태 최소공약수 연산을 다음처럼 했었다. def get_gcd(num1, num2): for i in range(max(num1, num2), 0, -1): if num1%i == 0 and num2%i == 0: return i 공약수를 구하는 상황인 만큼 두 수의 약수가 아닌 수까지 loop를 돌리는 위 코드는 무조..

괜찮은 아이디어가 하나 있다. #1676번 팩토리얼 0의 개수 https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 입력된 수의 팩토리얼을 구하고, 뒤에서부터 0이 아닌 수가 나올 때 까지 0의 개수를 구하는 문제이다. 어떻게 보면 비교적 순진하게 풀었다. #1676번 #파이썬 num = int(input()) if num == 0: print(0) else: for i in range(2, num): num *= i loop = str(num) answer = 0 for s in range(len(loop)-1, -1, -1): if..

#6588 골드바흐의 추측 https://www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net 정말 피곤한 문제였다. 소수는 에라토스테네스의 체를 이용해서 구해야한다. 이건 매번 이해만 하고 외워지지가 않는다. 멍청한걸까? bool_prime = [False, False] + [True]*(1000000-1) prime = [] for i in range(2, 1000000 + 1): if bool_prime[i]: prime.append(..

#10820 https://www.acmicpc.net/problem/10820 문자열 분석을 진행하는 문제인데, 입력 값의 개수(보통 N으로 주는데)를 주지않아서 난감한 문제이다. 파이썬에서는 이를 단순하게 해결할 수 있는데 바로 EOFerror 내장예외를 활용해 예외처리를 해주면 된다. EOF = End Of File 이라는 의미인데, 말 그대로 입력값이 없어지는 상황을 받아준다. 때문에 위 문제를 해결하는 기본적인 구조는 while True: try: s = input() func(s) except EOFerror: break 가 될 수 있다. func는 쉬우니까 그냥 짜보면 된다!

#1935 https://www.acmicpc.net/problem/1935 1935번: 후위 표기식2 첫째 줄에 피연산자의 개수(1 ≤ N ≤ 26) 가 주어진다. 그리고 둘째 줄에는 후위 표기식이 주어진다. (여기서 피연산자는 A~Z의 영대문자이며, A부터 순서대로 N개의 영대문자만이 사용되며, 길이 www.acmicpc.net 후위표기식이라는 새로운 개념을 만났다. 기존의 수학 표기법은 중위표기식 이라고 하는데 A + (B*C) - D/E 이렇게 연산자(기호)가 피연산자(수) 사이에 위치한다. 반면에 후위 표기식은 연산자가 피연산자 뒤에 위치하는데, 위 식과 동일한 형태의 식이 ABC*+DE/- 이다. 어떻게 처리하나 고민을 많이 했지만, 역시나 Stack을 사용하면 됐다. 기호가 나오기 전 까지 ..

리스트에 있는 원소의 개수를 각각 카운팅 해야하는 상황이 있다. 내가 택했던 방법은 nums = list(map(int, input().split())) num_set = set(nums) counts = dict() for num in num_set: counts[num] = nums.count(num) set을 구한 뒤, list에서 set을 count하는 형태였다. 근데 자꾸 시간초과가 나서 설마 이것 때문인가 하고 찾아보니 def list_to_set(l): s = set() # Repeat n times --> O(n) for x in l: # Add element to set --> O(1) s.add(x) return s 리스트 -> set으로 변환을 할 때에는, 일단 set을 선언한 뒤 리..