백준8 그리디 알고리즘(Greedy algorithm)이란? Goal 1. 그리디 알고리즘에 대해 알아보기 2. 예시 문제 풀어보기 그리디 알고리즘이란? 그리디(Greedy)란 단어는 탐욕이란 뜻을 가지고 있다. 그래서 그냥 쉽게 생각해서 코딩 문제를 풀 때 욕심쟁이처럼 지금 현재 가장 좋은 선택, 가장 최적의 선택만 하면 된다! 나중에 어떻게 되든간에 일단은 제일 최선의 선택을 계속 해나가면서 전체적으로도 그냥 최적의 선택이었기를 바라는 것이다. 예제 문제 (백준 5585번) 잔돈을 주는데 거스름돈 개수가 가장 적에 만들어보는 문제이다. 잔돈으로는 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 무한개가 있다고 생각하면 된다. Hint 1. 개수가 가장 적으려면 금액이 큰거부터 주면 될까 작은거부터 주면 될까? 해결 # 문제에서 준 입력값은 내야할 금액이므.. 2023. 5. 12. [백준] 10808번: 알파벳 개수 Hint 1. 알파벳 개수는 총 26개로 정해져 있다. 2. ord()을 사용하면 알파벳을 아스키 숫자로 변환할 수 있다. 3. ord('a')는 97이다. 백준 10808번: 알파벳 개수 (풀어보기) # 알파벳 개수를 셀 수 있게 미리 0으로 된 리스트를 만들어 준다 alphabet = [0 for i in range(26)] for char in input(): # ord('a')는 97이기 때문에 97을 빼면 alphabet 리스트에서 0번째로 값을 추가할 수 있다 alphabet[ord(char) - 97] += 1 # 리스트는 join을 써서 string 형태로 합칠 수 있다. 이때, 리스트에 들어있는 값들은 string이어야 한다 print(' '.join(map(str, alphabet))) 2023. 3. 6. [백준] 1927번: 최소 힙 Hint 1. 힙 자료구조 이용하기 (힙이란?) 2. 힙에서 heappop()을 하면 가장 작은 값이 반환 됨 백준 1927번: 최소 힙 import heapq import sys n = int(sys.stdin.readline()) heap = [] # 힙 만들기(리스트랑 만드는 법은 똑같음) for i in range(n): num = int(sys.stdin.readline()) if num == 0: # input 숫자가 0 이면 현재 힙에 들어있는 최소값 출력하기 print(heapq.heappop(heap) if heap != [] else 0) # 힙이 비어있지 않을 때만 heappop() 하기 else: heapq.heappush(heap, num) # 힙에 숫자 넣기 2023. 2. 28. [백준] 11279번: 최대 힙 Hint 1. 힙 자료구조 이용하기 (힙이란?) 2. 힙에서 heappop()을 하면 가장 작은 값이 반환 됨. 그렇다면 가장 큰 값을 반환하려면..? 3. 힙에 넣은 숫자들을 마이너스 해서 넣는다면 heappop() 했을 때 어떤 숫자가 먼저 뽑힐까? 백준 11279번: 최대 힙 import heapq import sys n = int(sys.stdin.readline()) heap = [] # 힙 만들기(리스트랑 만드는 법은 똑같음) for i in range(n): num = int(sys.stdin.readline()) if num == 0: # input 숫자가 0 이면 현재 힙에 들어있는 최대대값 출력하기 print((heapq.heappop(heap))*(-1) if heap != [] el.. 2023. 2. 26. [백준] 2075번: N번째 큰 수 Hint 1. 우선순위 큐 - 힙(heap) 자료구조 이용하기 (그게 뭐지?) 2. 힙에서 heappop()을 이용하면 작은 수 부터 출력된다! 백준 2075번: N번째 큰 수 (풀어보기) import heapq N = int(input()) heap = []# 새로운 힙 만들기 for i in range(N): for num in map(int, input().split()): heapq.heappush(heap, num)# 힙에 숫자 삽입하기 if len(heap) > N:# 힙의 원소의 개수가 N개를 넘어가면 heapq.heappop(heap)# 힙에서 가장 작은 수 제거하기 print(heapq.heappop(heap))# N번째로 큰 수 출력하기 2023. 2. 24. [백준] 11286번: 절댓값 힙 Hint 1. 힙 자료구조에 튜플을 넣을 수 있다 2. 힙 안의 튜플은 들어있는 순서대로 작은거부터 큰거까지 정렬된다 3. 힙 응용방법 알아보기 (여기) 백준 11286번 (풀어보기) import heapq import sys heap = [] for i in range(int(sys.stdin.readline())): n = int(sys.stdin.readline()) if n == 0: if heap == []: print(0) else: print(heapq.heappop(heap)[1])# 가장 작은 절댓값을 가진 숫자 n 출력하기 else: heapq.heappush(heap, (abs(n), n))# 튜플 형태로 n의 절댓값과 n을 둘 다 넣어줌 2023. 2. 21. [백준] 1929번: 소수 구하기 Hint 1. 1부터 n까지의 숫자가 소수인지 아닌지 확인을 하고, 소수이면 그 숫자의 배수들은 소수일까요? 2. 소수의 배수들은 소수가 아닌게 확실하기 때문에 미리 제거해주면 나중에 소수인지 확인할 필요가 없다! 3. 에라토스테네스의 체 이용하기 (그게 뭐지?) 백준 1929번: 소수 구하기 (풀어보기) import sys M, N = map(int, sys.stdin.readline().split()) # N까지의 숫자의 소수인지 아닌지에 대한 여부를 판단하는 배열 만들기 # 이것이 에레스토스테네스의 체! is_prime = [True] * (N+1) is_prime[0], is_prime[1] = False, False # 2부터 N까지의 숫자의 배수는 모두 소수가 아니라고 False로 바꿔주기 f.. 2023. 2. 18. [백준] 1463번: 1로 만들기 Hint 1. n에서 2나 3을 나누거나 1을 뺄 생각하지 말고 1부터 고려하는 코드로 짜야함 2. 1부터 n까지의 숫자를 각각 만들기 위해선 몇번의 연산 횟수가 필요한지 생각해봐야 함 3. Memoization 기법 활용 백준 1463번: 1로 만들기 (풀어보기) n = int(input()) ans = [0] * (n+1) # ans[i] = i가 1이 되기 위한 연산 횟수 for i in range(2, n+1): ans[i] = ans[i-1] + 1 # 디폴트로는 그 전 숫자에서 +1 한거니까 횟수도 그 전 숫자의 횟수에 +1 한것임 if i % 3 == 0: ans[i] = min(ans[i], ans[i // 3] + 1) # 디폴트와 x3 하기 전의 숫자의 횟수에서 +1 한거 중에 더 작은.. 2023. 2. 17. 이전 1 다음
