Algorithm2 [프로그래머스/Python] Level1. 숫자 짝꿍 프로그래머스에서 간만에 새로운 문제가 나와서 풀었다. 문제 입출력 예 풀이 짝꿍이라는 말 때문에 똑같은 숫자가 있으면 제거하면서 세볼까 생각했는데, 귀찮고 번거로워서 가장 간단한 방법을 생각했다. 1. 배열 선언 # 자릿수마다 초기화 (0~9) Xs = [0] * 10 Ys = [0] * 10 for x in X: Xs[int(x)] += 1 for y in Y: Ys[int(y)] += 1 0~9의 한자리 정수로만 파악하기 때문에 크기 10인 배열을 선언했다. 그리고 X, Y에 대해 개수만큼 더해주었다. 2. 같은 숫자가 있으면 추가 (짝짓기) # X, Y 비교하여 짝지을 수 있는 만큼 answer에 추가 for i in range(10): if Xs[i] > 0 and Ys[i] > 0: for j .. 2022. 10. 28. [Algorithm] 탐욕 알고리즘 (Greedy Algorithm) 안타깝고 당연하지만 이제는 코테를 무작정 풀 수는 없으니 모르는 척 그만하고 알고리즘을 하나씩 정리해야겠다. 알고리즘 수업을 2년 전 수강했지만 남은건 거의 없는 백지에서부터 채우기 목표 탐욕 알고리즘 (Greedy Algorithm) Greedy (탐욕적인, 욕심 많은) 알고리즘 최적해를 구하는 데 사용하는 근사적인 방법 선택의 순간마다 가장 최선이라고 생각하는 것을 선택해 최종 해답에 도달하는 방식 하지만, 순간(Local)의 최적해가 최종해(Global)의 최적이라는 것을 보장 불가능 탐욕 알고리즘은 말 그대로 욕심 많은 사람을 생각하면 된다. 모든 순간마다 가장 최적의 해를 선택하지만, 결국 최종적으로는 최적의 답이 될 수도 아닐 수도 있다. 단, 탐욕 알고리즘을 사용하면 최적해를 보장하진 못해도.. 2022. 6. 21. 이전 1 다음
