본문 바로가기

코딩테스트/알고리즘6

주요 알고리즘 설명 및 문제 모음 냅색(knapsack) 알고리즘 Dynamic Programming: 배낭 채우기 문제 (Knapsack Problem) 도둑이 보석가게에 배낭을 메고 침입했다. 배낭의 최대 용량은 W이며, 이를 초과해서 보석을 담으면 배낭이 찢어질 것이다. 각 보석들의 무게와 가격은 알고 있다. 배낭이 찢어지지 않는 선에서 gsmesie692.tistory.com 12865: 평벙한 배낭 2021. 7. 7.
[알고리즘] 최단경로 - 다익스트라 알고리즘 (Dijkstra's algorithm) 동빈나님의 이코테 강의를 보고 제 생각을 더해 정리해 보았습니다. 풀이 언어는 파이썬을 사용했습니다. 목차 최단 경로 문제 다익스트라 알고리즘 우선순위 큐를 사용한 다익스트라 알고리즘 최단 경로 문제 최단 경로 문제 중 한 시작점으로 부터 다른 노드 까지 가는데 비용이 얼마나 걸리는 지를 구할 때 사용하는 알고리즘이 다익스트라 알고리즘 입니다. 기본적으로 최단 경로 문제는 방향이 있고 가중치가 있는 그래프가 주어집니다. 따라서 위의 그래프는 다음과 같이 입력을 받습니다. 6 11 1 1 2 2 1 3 5 1 4 1 2 3 3 2 4 2 3 2 3 3 6 5 4 3 3 4 5 1 5 3 1 5 6 2 코드에선 다음과 같은 2차원 배열로 구현 됩니다. [[], [(2, 2), (3, 5), (4, 1)], .. 2021. 3. 10.
[알고리즘] 파이썬에서 순열 조합 구하기 - itertools, permutations, combinations 파이썬에선 itertools 모듈의 permutations 함수를 이용해 쉽게 순열을 구할 수 있습니다. 다음의 코드로 리스트의 순열을 구할 수 있습니다. import itertools numbers = '123' p = list(map(''.join, itertools.permutations(numbers))) # p -> ['123', '132', '213', '231', '312', '321'] pools = ['a', 'b', 'c'] p = list(map(''.join, itertools.permutations(numbers))) # p -> ['abc', 'acb', 'bac', 'bca', 'cab', 'cba'] p = list(itertools.permutations([1,2,3]) #.. 2021. 2. 27.
[알고리즘] 에라토스테네스의 체 에라토스테네스의 체는 소수(prime number)를 구할 때 가장 기본적으로 사용되는 알고리즘 입니다. 소수를 구하는 것은 기본적으로 완전탐색을 사용하는데, 이미 검사한 수는 스킵하여 효율성을 높였습니다. + 소수는 0과 1을 제외한 2부터 시작됩니다. 코드에서 prime[0], prime[1]이 True여도 이는 소수가 아니므로 사용할 때 주의해야 합니다. 파이썬 코드 N = 10000 # N-1번까지의 소수 구하기 prime = [True]*(N+1) for i in range(2, int(N**0.5)): # 2 부터 N-1의 제곱근 까지 검사 if prime[i]: for j in range(i+i, N+1, i): prime[j] = False 매우 간단하지만 막상 사용하려고 하면 쉽게 떠오르.. 2021. 2. 26.

티스토리툴바