haejun IT

백준 파도반 수열 풀이 백준 사이트 특성상 알고리즘의 분류가 되어 있어 DP 문제라는 것을 알 수 있지만 실전같은 경우는 어떻게 DP 문제라는 것을 유추할 수 있을까? 위의 문제에서 제시한 예시를 보면 이 전의 연산 결과에 따라서 다음의 연산 결과를 저장한다. 고로 작은 것을 통해 큰 것의 최적해를 찾는 것이기 때문에 DP를 사용하면 된다는 것을 유추할 수 있다. 또한 입력 N의 범위가 1

문제 백준 1로 만들기 풀이 과정 그리디 알고리즘과 구분하기. 그리디 알고리즘은 각 단계에서 최적의 해를 보장해야하지만, 이 문제는 무엇으로 나눌지에 따라서 최적의 해가 달라지기 때문에 DP로 풀어야한다. 또한 입력 갯수와 시간 제한이 빡빡하기 때문에 이를 보고 유추했을 때, DP를 떠올릴 수 있다. 각 단계별로 네가지의 연산이 가능하기때문에 이 중에서 최솟값을 구해주면 된다. 따라서 이 문제의 점화식은 다음과 같다. min(ai-1, ai/2, ai/3 ai/5). 나머지를 구하는 연산은 각 조건에 해당할 때만 수행할 수 있어야 한다. (a의 i-1번째, a의 i를 2로 나눔, a의 i를 3으로 나눔, a의 i를 5로 나눔의 의미) 이를 코드로 구현하면 다음과 같이 구현할 수 있다. +1을 해주는 것은..

백준 숫자카드2 풀이 일단 처음에 문제를 보고 입력이 500,000까지의 범위에 시간 제한이 1초인 것을 보고 문제를 최소한 O(n^2) 이하의 알고리즘으로 구현해야겠다고 생각했다. 입력을 보고 이런 생각을 하는 것을 연습중인데 꽤나 도움이 되는 것 같다. 시간 내에 몇개의 원소가 있는지 확인하려면 Hash를 사용하여 숫자를 Counting하여 비교하면 되겠다고 생각했다. 이를 구현하기 위해서 collections.Counter 라이브러리를 사용했다. Counter 라이브러리의 결과값을 타겟 리스트(m_list)와 비교하여 타겟 리스트의 요소가 Counter 결과값에 존재하면 counting 한 value 값을 프린트 해주면 된다. from collections import Counter import s..

1978. 소수 찾기 풀이 소수란 1과 자신만을 약수로 갖는 수를 뜻한다. 따라서 1 이상의 수에서, 나누기를 했을 때 나머지가 0일 때마다 카운팅을 해 주는데 이때 카운팅이 1이라는 것은 1을 제외하고 자기 자신뿐이라는 뜻이다. 따라서 이때 결과를 카운팅해주면 된다. import sys sys.stdin = open("1978_소수찾기_input.txt", "r") n = int(sys.stdin.readline()) nums = list(map(int, sys.stdin.readline().split())) result = 0 for num in nums: cnt = 0 # 숫자마다 카운팅을 해야하기 때문에 초기화 if num > 1: for i in range(2, num+1): if num % i..