haejun IT

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

11399. ATM 풀이 대기시간이 최소시간이 되기 위해서는 오름차순으로 정렬이 되어야 한다. 또한 이 전의 값을 계속 누적해가며 더해준다면 어렵지 않게 답을 구할 수 있다. import sys sys.stdin = open("11399_ATM_input.txt", "r") n = int(sys.stdin.readline()) waits = list(map(int, sys.stdin.readline().split())) times = 0 result = [] waits.sort() for i in waits: times = i + times result.append(times) print(sum(result))