목록알고리즘/알고리즘 (7)
어디까지 갈 수 있을까?
목적 시작노드에서 각 노드까지 최단거리를 구하는 알고리즘 O(ElogV)의 시간 복잡도를 갖는다 우선순위 큐로 거리가 짧은 노드를 우선적으로 탐색한다 BFS는 가중치가 같은(없는) 그래프에서, 다익스트라는 가중치가 서로 다른 그래프에서 사용한다 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 import heapq import sys input = sys.stdin.readline INF = int(1e9) n, m = map(int, input().split()) start=int(input()) graph = [[] for i in range(n + 1)] ..
문제링크 programmers.co.kr/learn/courses/30/lessons/72410 처음에는 함수 여러개를 만들어서 다 비교하다가 정규표현식으로 풀면 깔끔하길래 풀어봤다 [답코드] import re def solution(new_id): st=new_id st=st.lower() st=re.sub('[^a-z0-9-_.]','',st) st = re.sub('[.]+', '.', st) st = re.sub('^[.]|[.]$', '', st) if len(st)==0: st = 'a' else: st=st[0:15] st = re.sub('^[.]|[.]$', '', st) if len(st)
문제링크 www.acmicpc.net/problem/1463 처음 풀어본 DP 문제이다. Bottom-up 방식으로 풀었는데 해당 방식이 함수를 재귀호출하지 않아 시간과 메모리를 줄일 수 있다고 한다 [답코드] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 import sys input=sys.stdin.readline n=int(input()) dp=[0 for _ in range(n+1)] for i in range(2, n+1): dp[i]=dp[i-1]+1 if i%3==0 and dp[i]>dp[i//3]+1: dp[i]= dp[i//3]+1 if i%2==0 and dp[i]>dp[i//2]+1: dp[i]= dp[i // 2] + 1 print(dp[-1]) cs DP 문제..
문제 링크 www.acmicpc.net/problem/6588 에라토스테네스의 체를 이용하라는 말도 있던데 사용 안 해도 통과 가능하다 해당 수가 소수인지 아닌지는 1과 자기자신을 제외한 수로 나누어지는 지를 보면 된다 10 = 2*5 = 5*2 이기 때문에 소수가 아니다. 이와 같이 약수는 대칭되기 때문에 10의 경우 2까지만 검사해도 소수인지 아닌지 검사할 수 있다. [풀이법] ① n의 가장 작은 약수는 sqrt(n) 이하이므로 2부터 sqrt(n) 이하까지 루프를 돌린다 ② 두 수 중 하나라도 소수가 아니면 수를 증감하고 다시 소수인지 검사한다 [답코드] 123456789101112131415161718192021import sysinput=sys.stdin.readline def prime_num..
GCD는 greatest common divisor의 약자로 최대공약수를 뜻한다 유클리드 알고리즘은 최대공약수를 쉽게 구하는 방법으로 "비교대상의 두 개의 자연수 a와 b에서(단 a>b) a를 b로 나눈 나머지를 r이라고 했을때 GCD(a, b) = GCD(b, r)과 같고 r 이 0이면 그때 b가 최대공약수이다."라는 원리를 활용한 알고리즘" 이다 ex) GCD(24,16) -> GCD(16,8) -> GCD(8,0) : 최대공약수 = 8 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 import sys input=sys.stdin.readline for _ in range(int(input())): a, b=map(int, input().split()) #최소공배수 ..
1. 투포인터 알고리즘 특정합을 가지는 부분연속 수열 찾기 start와 end 포인터를 움직여가며 빨간 네모 안의 합을 찾아가는 알고리즘 *빨간네모의 합은 코드의 summary #데이터의 개수 n, 부분 연속 수열의 합 m n, m=5,5 data=[1,2,3,2,5] result=0 summary=0 end=0 for start in range(n): while summary