Melody Coding

❓ 플로이드-워셜이란? 음수 사이클이 없는 그래프에서 모든 노드 간에 최단 거리를 구하는 알고리즘 ❓ 플로이드-워셜 import java.io.*; import java.util.*; public class Main { // 플로이드 public static void main(String[] args) throws IOException { BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); StringTokenizer st; int n = Integer.parseInt(bf.readLine(..

❓ LCS 란? 여러 개의 수열 모두의 부분 수열이 되는 수열들 중에 가장 긴 것 ❓ LCS 예를 들어 ABCDE와 ACBDE의 LCS를 찾는다고 가정해 보자 현재 위치가 (x, y)이고 1) 문자가 같다면 (x-1, y-1) +1을 저장한다. 2) 문자가 같지 않다면 (x-1, y)와 (x, y-1) 값 중에서 큰 값으로 저장한다. 배열의 마지막 값이 LCS의 길이가 된다. LCS를 찾기 위해서는 배열의 가장 오른쪽 아래부터 탐색을 시작한다. if) 현재 값과 위의 값이 같다면 위로 이동 else if) 현재 값과 왼쪽 값이 같다면 왼쪽으로 이동 else) 현재 값을 LCS값으로 저장 후 왼쪽 위 대각선으로 이동 ❓ LCS 코드 public class Main { // LCS public static ..

❓ 피사노 주기 피보나치 수를 어떠한 값으로 나누면 항상 같은 수가 나오는 구간이 반복되는 것 ❓ 피사노 주기 구하는 방법 15 x 10^n-1 ex) 만약 1000000으로 나눈 나머지를 출력한다면 주기는 15 x 10^5가 된다.

❓DFS와 BFS - 주어진 그래프에서 모든 노드를 방문하는 알고리즘 ❓DFS - Depth First Search (깊이 우선 탐색) - 임의의 정점에서 시작하여 이웃하는 하나의 정점을 방문하고, 방금 방문한 정점의 이웃 정점을 방문 def dfs(x): visited[x]=True for i in graph[x]: if not visited[i]: dfs(i) ❓BFS - Breadth First Search (너비 우선 탐색) - 임의의 정점에서 시작하여 이웃하는 모든 정점들을 방문하고, 방문한 정점들의 이웃 정점들을 방문 def bfs(x): queue=[] visited[x]=True queue.append(x) while len(queue)!=0: v=queue.pop(0) for i in g..

❓순차 탐색 주어진 목표값을 찾아 리스트를 앞에서부터 순차적으로 탐색 목표가 발견된 첫 번째 위치를 리턴 목표가 발견되지 않으면 음수를 리턴 선형 시간 ❓ 이진 탐색 정렬된 시퀀스를 순차 탐색보다 적은 시간에 목표값 탐색 가능 반복적으로 반으로 나누어가며 목표를 포함하는 반쪽을 찾는 것을 반복 로그 시간

🙄 최대 공약수 GCD(Greatest Common Divisor) 🙄 최소 공배수 LCM(Least Common Multiple) def gcd(a,b): #최대공약수 if b==0: return a return gcd(b,a%b) if __name__=='__main__' : A,B=map(int, input().split()) print(int(A*B/gcd(A,B))) #최소공배수

😊백준_소수 구하기) https://www.acmicpc.net/problem/1929 😊프로그래머스_소수찾기)https://programmers.co.kr/learn/courses/30/lessons/42839 위와 같은 문제들을 풀며 소수 찾기 문제를 풀 때 원래 방식으로 풀면 시간 초과가 발생할 것이라는 생각이 들었다. 🙄 초기 코드) for i in range(M,N+1): #소수찾기 if i==2: #2는 소수 arr.append(i) for j in range(2,i): if i%j==0: #나눠지는 것이 있으면 소수가 아님 break if j==i-1: #나눠지는 것이 없으면 소수 arr.append(i) - 이중 반복문을 사용하여 나눠지는 것이 있는지 없는지 판별한다. 여태 풀었던 문제에서..