본문 바로가기

코딩테스트19

[알고리즘] 최단경로 - 다익스트라 알고리즘 (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.
[백준] 6236: 용돈 관리 파이썬 리뷰 6236번: 용돈 관리 현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로 www.acmicpc.net 풀이는 해당 블로그를 참고했습니다. 전형적인 이분 탐색 문제입니다만... 고려하지 못한 부분과 실수한 부분이 많아 이를 되짚어 보려합니다. 문제 풀이는 적절한 금액(조건을 만족하면서 최소가 되는)을 이분탐색으로 찾는 것입니다. 처음에 제가 잘못 생각한 것은 하루 소비 금액 > 뽑을 수 있는 금액(설정 금액) 이어도 하루에 여러번 돈을 뽑으면 된다는 것이었습니다. 문제에서 돈을 뽑을 때는 가지고 있는 돈을 모두 반환하고 뽑기 때문에 잘못된 생각입니다. 이 때문에 설정 .. 2021. 2. 23.

티스토리툴바