본문 바로가기

알고리즘공부

 (9)
[탐욕법] 난이도1, K 대회 기출 '만들 수 없는 금액' (Python) 동네 편의점의 주인인 동빈이는 N개의 동전을 가지고 있습니다. 이때 N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램을 작성하세요. 예를 들어, N=5이고, 각 동전이 각각 3원, 2원, 1원, 1원, 9원짜리 (화폐 단위) 동전이라고 가정합시다. 이때 동빈이가 만들 수 없는 양의 정수 금액 중 최솟값은 8원입니다. 또 다른 예시로, N=3이고, 각 동전이 각각 3원, 5원, 7원짜리 (화폐 단위) 동전이라고 가정합시다. 이때 동빈이가 만들 수 없는 양의 정수 금액 중 최솟값은 1원입니다. 첫째 줄에는 동전의 개수를 나타내는 양의 정수 N이 주어집니다. (1
[정렬] 프로그래머스 L1 '정수 내림차순으로 배치하기' (Python) https://programmers.co.kr/learn/courses/30/lessons/12933 코딩테스트 연습 - 정수 내림차순으로 배치하기 함수 solution은 정수 n을 매개변수로 입력받습니다. n의 각 자릿수를 큰것부터 작은 순으로 정렬한 새로운 정수를 리턴해주세요. 예를들어 n이 118372면 873211을 리턴하면 됩니다. 제한 조건 n은 1이 programmers.co.kr 1. 정수를 리스트로 바꿔 정렬하고 문자열로 바꾸고 다시 정수로 바꾼다. def solution(n): return int("".join(sorted(str(int(n)), reverse=True))) 1000000000 이상 자연수는 int로 바꿔줘야 함 복습 알고리즘
[기타] 프로그래머스 L1 '최소공약수와 최소공배수' (Python) https://programmers.co.kr/learn/courses/30/lessons/12940 코딩테스트 연습 - 최대공약수와 최소공배수 두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 programmers.co.kr 1. 공식을 이용하여 최대공약수를 구한다. 2. 최대공약수를 이용하여 최대공배수를 구한다. def gcd(a,b): while a!=0: t = b%a (b,a) = (a,t) return b def solution(n, m): answer = [] if m
[알고리즘] 구현 경우의 수가 100,000개 이하면 완전 탐색 가능 8개를 무작위로 나열하는 모든 순열의 개수 구하는 법 : 8!
[알고리즘] - 진법 변환/비트 연산 [진법 변환] 진법이란? 수를 셀 때 자릿수가 올라가는 단위를 기준으로 하는 셈법의 총칭 사용하는 숫자의 개수가 진법의 숫자를 의미 bin(10진수) #2진수로 바꿔주는 함수 oct(10진수) #8진수로 바꿔주는 함수 hex(10진수) #16진수로 바꿔주는 함수 int(2/8/16진수) #10진수로 바꿔주는 함수 [비트 연산] 비트 연산이란? 한 개 혹은 두 개의 이진수에 적용되는 연산 비트 연산의 종류 & (AND) ㅣ (OR) ^ (XOR) : 다르면 1, 같으면 0 ~ (NOT) 음수의 표현을 처리하기 위함 1을 더한 뒤 부호를 바꿔줌 bin(~0b0000) #-0b0001 bin(~0b0001) #-0b0010 bin(~0b0010) #-3 = -0b0011 bin(~0b0011) #-0b0100..
[완전탐색] 프로그래머스 L1 '모의고사' (Python) https://programmers.co.kr/learn/courses/30/lessons/42840 코딩테스트 연습 - 모의고사 수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다. 1번 수포자가 찍는 programmers.co.kr 반복문 사용. 패턴을 answers 길이에 맞춤. 문제가 1개~10,000개일 경우 계산 채점할 수 있는 변수 필요. 가장 많이 맞춘 사람 걸러내기 #1차 시도 --> 몇개의 테스트케이스 실패 def solution(answers): answer = [] a1, a2, a3 = [],[],[] j=1 for i in answers: if i==j: a1.appe..
[알고리즘] 최단경로 - (Dijkstra(다익스트라)/Floyd-Warshall(플로이드-워셜)) 최단 경로 문제 - 최단 경로 문제란 두 노드를 잇는 가장 짧은 경로를 찾는 문제임 - 가중치 그래프 (Weighted Graph) 에서 간선 (Edge)의 가중치 합이 최소가 되도록 하는 경로를 찾는 것이 목적 최단 경로 문제 종류 1. 단일 출발 및 단일 도착 (single-source and single-destination shortest path problem) 최단 경로 문제 - 그래프 내의 특정 노드 u 에서 출발, 또다른 특정 노드 v 에 도착하는 가장 짧은 경로를 찾는 문제 2. 단일 출발 (single-source shortest path problem) 최단 경로 문제 - 그래프 내의 특정 노드 u 와 그래프 내 다른 모든 노드 각각의 가장 짧은 경로를 찾는 문제 > 따지고 보면 굉장..
[Dijkstra] 프로그래머스 L3 '가장 먼 노드' (Python) https://programmers.co.kr/learn/courses/30/lessons/49189 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr 1번 노드에서 가장 멀리 떨어진 노드의 개수를 구해야 하므로 다익스트라 알고리즘을 이용 간선은 양방향이므로 그래프에 노드를 서로 추가 가장 멀리 떨어진 노드를 구해야 하므로 max() 메서드 이용 import heapq def dijkstra(start,distance,graph): q=[] heapq.heappush(q,(0,start)) distance[start]=0 while q: dist,now = heapq.heappop..
LIST

티스토리툴바