Algorithm/개념 정리14 Sorting Algorithms 재밌는 소팅 알고리즘 영상 퍼왔어요~S2 우하하 https://youtu.be/kPRA0W1kECg 2023. 4. 3. 순열,중복순열/조합,중복조합 구현 순열(Permutation) 요소 n개 중 r개를 뽑아 정렬하는 경우의 수로 요소의 순서를 구분한다. e.g. [1,2]와 [2,1] 은 순서가 다르기 때문에 다른 경우의 수로 판단 구현 pubilc class Solution{ public static void permutation(int arr[],int[] out,boolean[] visited,int depth,int r){ if(depth==r){ for(int num:out) System.out.print(num); System.out.println(); return; } for(int i =0; i 2022. 8. 1. Greedy 개요 그리디 알고리즘은 매 선택에서 현재 당장 최적인 답을 선택하여 적합한 결과를 도출하도록 한다. 다시 말해 현재 조건에서 최적의 선택을 했다면 더 이상 다른 가능 케이스는 검증하지 않는 것이다. 그 결과 그리디 알고리즘은 전체에서 최적값을 보장할 수 없다. 그럼에도 불구하고 그리디 알고리즘은 처리 속도가 매우 빠르기 때문에 특정 조건을 만족할 경우 자주 사용될 수 있다. 최적의 해를 보장하는 조건 탐욕 선택 속성(Greedy Choice Property) 이전의 선택이 이후의 선택에 영향을 주지 않아야 한다. 최적 부분 구조(Optimal Substructure) 부분 문제의 최적 결과가 전체에도 그대로 적용될 수 있어야 한다. 2022. 7. 28. 우선순위 큐(Priority Queue) 개요 우선순위 큐는 일반적인 큐의 구조를 가지지만 결정된 우선순위에 따라 데이터를 꺼낼 수 있다. 일반적으로 Heap을 이용하여 구현하며 이진트리 구조로 구성되어있다. 데이터를 삽입할 때 우선순위를 기준으로 최대 혹은 최소 힙을 구성하고 데이터를 꺼낼 때 루트 노드를 얻어낸다. 루트 노드를 삭제할 때는 빈 루트 노드 위치에 맨 마지막 노드를 삽입한 후 아래로 내려가면서 적절한 자리를 찾아서 옮기는 방식으로 진행된다. 우선순위 큐 사용법 Priority Queue 선언 import java.util.PriorityQueue; //우선순위 : 낮은 숫자순 PriorityQueue q1 = new PriorityQueue(); //우선순위 : 높은 숫자순 PriorityQueue q2 = new Priorit.. 2022. 7. 26. Dynamic Programming 개요 동적 계획법(DP)은 하나의 큰 문제를 작은 문제로 나누어서 그 결과를 저장 후 다시 재활용하는 방식으로 특정된 알고리즘이 아니라 하나의 문제 해결 방법론이며, 아래 조건을 만족할 때 사용할 수 있다. 최적 부분 구조(Optomal Substructure) 겹치는 부분 문제(Overlapping Subproblems) 동작 원리 DP는 일반적인 재귀 방식과 매우 유사하다. 만약 피보나치 수열을 재귀 방식으로 푼다면 작은 문제들이 여러번 반복되어 비효율적인 계산이 될 수 있지만 한 번 구한 작은 문제의 결과 값을 저장하여 재사용한다면 앞서 계산된 값을 다시 반복할 필요가 없어 보다 더 효율적으로 문제를 해결할 수 있다. 시간복잡도 기준 O(n^2) -> O(f(n))으로 개선 가능하다.(문제 별 상이.. 2022. 7. 20. 그래프 탐색(DFS&BFS) 그래프 탐색 개요 DFS,BFS 모두 그래프를 탐색하는 방법이다. 그래프 탐색 : 하나의 정점으로부터 시작하여 모든 정점들을 한 번씩 방문하는 것 DFS 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식 형제 정점을 탐색하기 전에 자식 정점부터 탐색 모든 노드를 방문하고자 하는 경우 사용한다.(완전탐색) 예) 미로찾기를 할 때 최대한 한 방향으로 갈 수 있을 때까지 쭉 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 그 갈림길부터 다시 다른 방향으로 탐색을 진행하는 방식 구현 : 스택 또는 재귀 함수로 구현 *참고로 재귀 함수는 내부 스택이 구현되어있음 BFS root 노트에서 시작하여 인접한 노드를 먼저 탐색하는 방법으로.. 2022. 6. 15. 이전 1 2 3 다음
