반응형

알고리즘 16

[프로그래머스/python3] 하샤드 수

문제 설명 양의 정수 x가 하샤드 수이려면 x의 자릿수의 합으로 x가 나누어져야 합니다. 예를 들어 18의 자릿수 합은 1+8=9이고, 18은 9로 나누어 떨어지므로 18은 하샤드 수입니다. 자연수 x를 입력받아 x가 하샤드 수인지 아닌지 검사하는 함수, solution을 완성해주세요. 제한 조건 x는 1 이상, 10000 이하인 정수입니다. 입출력 예 arr return 10 true 12 true 11 false 13 false 입출력 예 설명 #1) 10의 모든 자릿수의 합은 1입니다. 10은 1로 나누어 떨어지므로 10은 하샤드 수입니다. #2) 12의 모든 자릿수의 합은 3입니다. 12는 3으로 나누어 떨어지므로 12는 하샤드 수입니다. #3) 11의 모든 자릿수의 합은 2입니다. 11은 2로 ..

[프로그래머스/python3] x만큼 간격이 있는 n개의 숫자

문제 설명 함수 solution은 정수 x와 자연수 n을 입력 받아, x부터 시작해 x씩 증가하는 숫자를 n개 지니는 리스트를 리턴해야 합니다. 다음 제한 조건을 보고, 조건을 만족하는 함수, solution을 완성해주세요. 제한 조건 x는 -10000000 이상, 10000000 이하인 정수입니다. n은 1000 이하인 자연수입니다. 입출력 예 x n answer 2 5 [2,4,6,8,10] 4 3 [4,8,12] -4 2 [-4, -8] 풀이 def solution(x, n): answer = [] for i in range(n): answer.append(x+i*x) return answer

[자료형 라이브러리] collections.deque (데크)

collections 모듈에는 파이썬의 범용 내장 자료형인 dict, list, set, tuple에 대한 대안으로 특수 컨테이너 데이터형이 구현되어있다. 그중 deque는 양방향으로 빠르게 추가 및 삭제를 할 수 있는 리스트류의 객체이다. 개념 일반 큐(queue)는 선입선출으로 FIFO방식으로 작동하지만, deque는 양방향 큐로써 앞과 뒤에서 데이터를 추가, 삭제할 수 있다. 따라서 deque는 스택처럼 써도 되고, 큐처럼 쓸 수도 있다. collections.deque 모듈은 이러한 deque 자료형을 생성하는 모듈이다. class collections.deque([iterable[,maxlen]]) from collections import deque #iterable로 부터 왼쪽에서 오른쪽 순..

Python 2021.07.28

[탐욕 알고리즘] 개념과 응용 문제(거스름돈 문제, 프로그래머스 체육복)

탐욕 알고리즘은 동적 프로그래밍 사용 시 지나치게 많은 일을 한다는 것에서 착안한 알고리즘이다. 동적 계획법과 마찬가지로 최적화 문제를 푸는데 주로 사용한다. 동적 계획법은 재귀관계식을 세워서 입력 사례를 더 작은 입력 사례로 분할한다. 그런데 탐욕 알고리즘은 입력사례를 분할하지 않는다. 탐욕 알고리즘은 순서대로 답을 모아서 최종 답을 구축하는데, 답을 모으는 당시의 가장 좋은 최적해를 선택해 모은다. 그래서 탐욕 알고리즘은 어떤 선택이든지 선택할 당시의 최적해를 구한다고 하여 locally optimal choice를 구한다고 한다. 전체적으로 최적인 해(globally optimal choice)를 구하고 싶지만 항상 최적해를 구한다는 보장이 없기 때문에, 반드시 최적인 해답을 얻는지 확인하는 절차를..

반응형