🥕 [ 백준 11403 ] 경로 찾기 문제 링크 url : https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 참고: https://callmescone.tistory.com/150?category=1097465 [알고리즘] 최단 경로 플로이드 워셜 알고리즘 [플로이드 워셜 알고리즘] 모든 노드에서 다른 모든 노드 까지 최단 경로를 모두 계산한다. 매번 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾을 필요가 없게 됐다. 각 단계마다 \( O(N^2 callmescone.tistor..
[최대 공약 문자열] def solution(s1, s2): if len(s1)>=len(s2): # word1에 더 긴 문자열 저장 word1, word2 = s1,s2 else: word1, word2 = s2,s1 s3 = "" # 찾고자 하는 s3 초기화 for i in range(len(word2),0,-1): # word2 전체 문자열 부터 해서 뒤부터 한칸 씩 줄여가며 word1의 시작 문자열인지 체크 if word1.startswith(word2[:i]): s3 = word2[:i] break return s3 startswith 함수가 뭔지 알 수 있었다. ( 쉽게 검사가 되더라 ) endswith 라는 함수도 있다. 완전한 코드는 아니다. 왜냐면 구한 s3가 word1과 word2에 대..
🥕 [ 백준 2294 ] 동전 2 문제 링크 url : https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 🍒 문제 분석 n 가지 종류의 동전이 있다. 이 동전들을 적당히 사용해 가치의 합이 k원이 되도록 만들고 싶다. 그러면서 동전의 갯수를 최소로 하고 싶다. 이때 사용하는 최소의 동전 갯수를 구하여라. 🥑 코드 def sol(k): d = [10001]*10001 for coin in coin_list: for i..
🥕 [ 백준 2293 ] 동전 1 문제 링크 url : https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 🍒 문제 분석 동전의 종류 n과 이를 이용해 만들어야하는 k원이 주어진다. 그리고 각 동전의 단위가 몇인지 알려준다. 이를 통해 k원을 만드는 경우의 수를 구해야한다. 가령 n = 3, k = 5 , 동전의 종류가 [1, 2, 5] 라면 1원 짜리 5개 1원 짜리 3개, 2원 짜리 1개 1원 짜리 1개, 2원 짜리 2개 5원 짜리 1개 하여 4..
