Python/알고리즘
파이썬(python) 알고리즘 - 최단 경로 (다익스트라, 벨만포드, 플로이드 워셜)
양의 그래프에서 최소 비용 찾는 문제를 만났을 때 무슨 알고리즘을 쓸 지 판단이 어려운데요. 고민할 필요 없이 정확히 판단할 수 있도록 정리해 보았습니다. 판단 척도 항목 판단 척도 사용 알고리즘 가중치 +(방향), +(양방향), -(방향) 가능 -(양방향) 불가능 → -사이클 발생 플로이드 워셜, 벨만포드 +(방향), +(양방향) 가능 -(방향), -(양방향) 불가능 다익스트라 입력 최대 범위 V정점 200개 이하 (너무 작은 범위인 경우 무조건 플로이드 의심) 플로이드 워셜 (V+E)*log(V) 계산해서 2천만 이하 다익스트라 (V+E) 계산해서 2천만 이하 벨만포드 필요한 정보 한 노드에서 다른 모든 노드로의 최단 경로 비용 다익스트라, 플로이드 워셜, 벨만 포드 모든 노드에서 다른 모든 노드로의..
파이썬(python) 알고리즘 - 최단 경로 (플로이드 워셜)
플로이드 워셜 개요 항목 내용 언제 쓰는가? 양방향이면서 음/양 가중치 그래프에서 최단 경로 찾기 모든 노드에서 다른 모든 노드 까지의 최단 경로의 길이 계산 ex) A→B로 가는 경로가 있는지 확인 ex) A→??지점을 거쳐서 B,C로 각각 갈때 최소비용 노드 개수가 500개 이하 그래프 유형 양방향, 가중치 (음의 사이클 x) 가중치 양(o), 음(o) 시간 복잡도 O(V^3), (V
파이썬(python) 가장 긴 증가하는 부분수열 (LIS)
가장 긴 증가하는 부분수열 (LIS) 알고리즘 분류 : 동적계획법 설명 [3,5,7,9,2,1,4,8] 과 같은 하나의 수열은 여러 부분수열로 나눌 수 있다. ex) [3,5], [5,7], [9,2,1,4], [1,4,8] 그 부분수열의 처음~끝까지 증가하는 횟수가 몇번이 되는지 count 하였을때 가장 횟수가 많은 부분수열을 구하는 문제다. [3,5] = 2회 [3,5,7] = 3회 [3,5,7,9] = 4회 [2,1,4] = 2회 아이디어 [3,5,7,1] 라는 수열의 LIS를 구해보자. 무지성 야생의 힘으로 덤벼보자. 모든 부분수열을 구해서 그 중에서 LIS를 구한다. [3], [5], [7], [1], [3,5], [5,7], [7,1] [3,5,7], [3,5,1], [5,7,1], [3,5,..
파이썬(python) 투 포인터
투 포인터 리스트에 순차적으로 접근해야할 때 두개의 포인터를 이용하여 합을 구하는 기법 O(N)으로 해결가능 1) a+b = k 시작점은 첫번째, 끝점은 마지막 원소를 가리킨 상태에서 시작. 이 경우는 정렬된 상태에서 진행이 필요하다. start, end, result = 1, n-1, 0 while start x: end-=1 elif total < x: start+=1 else: start+=1 result+=1 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을..
파이썬(python) 알고리즘 - 최단 경로 (다익스트라)
최단 경로 찾기 (다익스트라) 개요 항목 내용 언제 쓰는가? 양의 가중치가 있는 방향/양방향 그래프에서 최단경로 찾기 하나의 노드에서 출발하여 다른 모든 노드로 가는 최소/최대 비용 계산 (노드+간선)*log(간선) 이 2천만 이하 (python 기준) 그래프 유형 방향/양방향, 가중치 가중치 양(o) 음(x) 시간 복잡도 O((V+E)logV), ((V+E)logV cost : distance_arr[next] = cost heapq.heappush(heap,(cost,next)) 문제 예시 & 코드 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 ..
파이썬(python) 알고리즘 - 동적 계획법 푸는 방법
DP문제를 풀어나가는 순서 1. 문제의 조건대로 손으로 그려보며 반복되는 부분을 찾습니다. 2. dp테이블 dp[i]는 무엇을 의미하는지 정의해봅니다. dp[i] = ??? 3. 디테일한 점화식을 세웁니다. dp[i] = dp[i-1] + dp[i-2] 4. 필요하다면 dp 테이블을 확장합니다. dp[i] → dp[i][j] 5. 중복되는 부분을 어떻게 활용할 수 있을지 생각합니다. 어떤 방법으로도 점화식 세워지지 않으면 계산 과정이나 정의의 순서를 뒤집어서 생각해봅니다. 예를 들면 계산 과정을 완전히 거꾸로 뒤집어보는 발상을 해봅니다. 즉 1+1=2 이 아니라 2=1+1 이라는 발상을 하는 것입니다. 1번으로 되돌아가서 다시 진행합니다. DP문제 유형이라고 어떻게 판단하는가? 문제만 보면 완전 탐색과 ..
파이썬(python) 알고리즘 - DFS, BFS
DFS (깊이 우선 탐색) 깊이를 우선으로 탐색하는 알고리즘 시작 노드에서 방문하지 않은 인접 노드를 큐에 삽입 (방문 했음을 표시) 더 이상 방문할 수 없는 경우 탐색 중단하고 이전 상태로 되돌아옴 특징 스택 or 재귀함수 사용 한 방향으로 최대한 깊게 접근해본다 (경고) 파이썬 최대 재귀 횟수는 1000번까지 가능하다. 재귀를 많이 호출하는 문제는 제한횟수에 걸려서 런타임 에러가 발생할 수도 있다. sys.setrecursionlimit(제한횟수) 로 제한을 늘릴 수 있다. import sys sys.setrecursionlimit(제한횟수) 기본 형태 def dfs(arr, cur, visited): visited[cur] = True for i in arr[cur]: if not visited[i..
파이썬 (python) 알고리즘 - 그리디 알고리즘
그리디 알고리즘 현재 상황에서 최적의 값을 탐욕적으로 취하는 알고리즘 그리디 알고리즘으로 얻은 해가 최적의 해를 보장할 수 없는 때가 많지만, 코딩 테스트에서는 최적의 해를 보장하도록 나오므로 걱정하지 않아도 됨. 특징 몇 가지 선택지가 주어짐. 각각의 선택지를 최소한의 선택으로 조건을 만족하도록 하는 해를 구하기 이때 선택지A 보다 B가 더 최적이라는 것에 대한 정당성을 설명할 수 있어야 함. 백준 단계별로 문제 풀어보기 - 그리디 알고리즘 그리디 알고리즘 단계 동전의 조건이 특별해서 동적 프로그래밍보다 빠르게 답을 찾을 수 있는 문제 www.acmicpc.net 문제 풀이 파이썬(python) 백준 1541 : 잃어버린 괄호 백준 1541 : 잃어버린 괄호 문제 내용 시간 제한 : 2 초 메모리 : ..
파이썬(python) 알고리즘 - 팩토리얼
백준 10872 : 팩토리얼 10872번: 팩토리얼 0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오. www.acmicpc.net 속도 : math.factorial > for > 재귀 1. math 라이브러리 사용 import sys import math n = int(sys.stdin.readline()) print(math.factorial(n)) 2. for문으로 구하기 import sys n = int(sys.stdin.readline()) ans = 1 for a in range(1,n+1): ans*=a print(ans) 3. 재귀함수 사용 import sys def factorial(n): if n == 0: return 1 return factori..