.compare Graph Algorithms .MST(Minimum Spanning Tree), 최소신장트리 정점 -1개의 간선으로 이루어진 신장트리 중에서 가중치의 합이 가장 작은 것고르는 간선은 사이클을 만들지 않아야 하고, 가중치가 작은 것들부터 골라져야 함 * 절대적이진 않지만, 간선이 적으면 KRUSKAL, 간선이 많으면 PRIM 알고리즘이 유리 .KRUSKAL (간선을 고르는 간선 중심)MST 의 목적을 이루기 위해 간선들을 가중치 오름차순으로 정렬해두고,사이클을 만들지 않는 간선이라면 골라나가서 N-1 개를 고르면 완료참고 ㅇ Use edgeList12345678910111213141516171819202122232425262728293031323334353637383940414243444..
[Math] 순열, 조합, 부분집합 비교
. 순열 서로 다른 n개의 원소 중에서 "중복을 허락하지 않고", "순서를 생각"하며 r개를 일렬로 나열하는 수열 123456789101112131415161718192021// 지정된 자리에 순열 뽑기// cnt : 현재까지 뽑은 순열의 수private static void permusation(int cnt) { // R개를 모두 골랐다면 if(cnt == R) { System.out.println(Arrays.toString(numbers)); return; } for (int i = 0; i
[Math] 코딩테스트에 나오는 수학 정리(정수론 : 공약수/공배수, 에라토스테네스의 체..)
.#ㅇ 대표적으로 코딩테스트에 나오는 수학.- 정수론(소수, 약수, 배수 등의 관계)- 기하(피타고라스 정리, 점 사이의 거리, 직선의 방정식, 삼각형의 넓이 등)* 기하의 CCW(Counter Clock WIse), Convex Hull, 좌표 기하는 높은 난이도로 코딩테스트보다 대회에서 자주 빈출 .정수론1. 최대공약수/최소공배수2. 에라토스테네스의 체를 사용한 소수3. 거듭제곱의 연산(C, Java 필수 알고리즘) ㅇGCD와 LCMㅇ최대공약수, GCD(Greatest Common Divider)12345678910111213141516171819# 1. 단순한 반복문def gcd_naive(a, b): for i in range(min(a,b), 0, -1): if a % i== 0 and b % ..
[Algorithm] 위상정렬(그래프 정렬)
#. Problemhttps://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98* The copyright in this matter is in Inflearn #. Solveㅇ위상정렬- 어떤 일을 하는 순서를 찾는 알고리즘- 각각의 일의 선후관계가 복잡하게 얽허있을 때 각각 일의 선후관계를 유지하면서 전체 일의 순서를 짜는 알고리즘 (그래프를 이용하여 일의 순서를 정할 때 주로 사용)- 순서가 지켜져야하므로 인접행렬 방향 그래프 사용 입력이 다음과 같을 때,6 61 4 (1번 작업 수행 후 4번 작업 진행)5 4 4 3 2 5 2 3 6 2아래와 같은 그래프가 그려진다.위상정렬에서는 진입차수, 들어오는 간선이 중요한데(차수 : 연결된 간선의 ..
[Algorithm] 가방문제(냅색 알고리즘, knapsack algorithm)
#. Problem https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98 * The copyright in this matter is in Inflearn #. Resolution Process 1. Read and understand problem 2. Redefine the problem + abstract 3. Create solution plan (select Algorithm, Data structure) 4. Prove the plan (check performance time and usage memory) 5. Carry out the plan 6. Look back on the plan and find a way to ..
#. Problemhttps://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98* The copyright in this matter is in Inflearn #. Resolution Process 1. Read and understand problem 2. Redefine the problem + abstract 3. Create solution plan (select Algorithm, Data structure) 4. Prove the plan (check performance time and usage memory) 5. Carry out the plan 6. Look back on the plan and find a way to im..
#. 동적 계획법? ㅇ 동적계획법 = 다이나믹 프로그래밍(Dynamic Programming), DP- 벨만-포드 알고리즘을 개발한 벨만이 만들어낸 알고리즘- 알고리즘 이름을 어떻게 지으면 기억에 잘 남고, 간지(?)가 날지 생각하다가 다이나믹이라는 단어가 좋아서 이렇게 되었다는.. ㅇ 특징- 다음 상태를 구하기 위해, 이전 상태를 저장하고, 사용(Memoization)- 무엇을 어떻게 저장할지 정하는 것이 중요- 많이 풀어보고, 생각 과정을 연습하는 것이 중요.. ㅇ 적용 순서1. 상태 정의- dp배열을 만들었을 때, index값이 의미하는 상태- 문제의 초기상태를 정의(직관적인 작은 문제의 해)2. 점화식 구하기- 다음 상태를 나타내기 위한 표현식3. 시간복잡도 계산4. 구현 ㅇ 적용 방법1. Top..
#. Problemhttps://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98* The copyright in this matter is in Inflearn #. Resolution Process 1. Read and understand problem 2. Redefine the problem + abstract 3. Create solution plan (select Algorithm, Data structure) 4. Prove the plan (check performance time and usage memory) 5. Carry out the plan 6. Look back on the plan and find a way to im..