우선순위 큐란? 우선순위의 개념을 큐에 도입한 자료 구조 데이터들이 우선순위를 가지고 있고 우선순위가 높은 데이터가 먼저 나간다. 우선순위 큐는 배열, 연결리스트, 힙 으로 구현이 가능하다. 이 중에서 힙(heap)으로 구현하는 것이 가장 효율적이다. 힙이란? 완전이진트리 구조 최댓값과 최솟값을 뽑아낼 때 사용하기 좋은 자료구조이다. 힙은 완전히 정렬된 상태를 유지하는 것이 아닌 Level에 따른 정렬만 이루어져 느슨한 정렬상태를 유지한다. (Max Heap인 경우 부모가 자식보다 큰 값을 가지고 있고, Min Heap인 경우 부모가 자식보다 작은 값을 가지고 있어야 함) 힙의 종류 Max Heap 루트 노드에는 항상 가장 큰 값이 위치하고 있으며, 부모 노드가 자식 노드들보다 무조건 값이 커야한다. M..

다익스트라 알고리즘이 뭘까? 다익스트라 알고리즘이란 하나의 출발점에서 도달할 수 있는 모든 도착점에 대한 최단 경로를 구할 수 있는 알고리즘이다. 대신 조건이 있는데 다익스트라 알고리즘은 간선들의 비용이 모두 양수여야만 적용이 가능하다. 만약 음의 비용을 가진 간선이 존재한다면 최단 경로를 구할 수 없다. 다익스트라 알고리즘과 다이나믹 프로그래밍 다익스트라 알고리즘의 메인 아이디어는 다이나믹 프로그래밍(DP)이다. 다익스트라 알고리즘은 기존에 구해놓은 최단 거리를 이용하여 최단 거리를 갱신해나가는 메인 아이디어를 가지고 있다. (최단 경로는 최단 경로들의 집합으로 이루어져 있다) 다익스트라 알고리즘의 복잡도 (좀 더 자세히 알아볼 것) 원래 다익스트라 알고리즘은 O(V^2)의 시간 복잡도를 가지고 있었지..

테이블에 대해 정규화를 해야하는 이유는 Anomaly(이상 현상)이 나타나기 때문이다. 삽입 이상 불필요한 정보를 함께 저장하지 않고서는 어떤 정보를 저장하는 것이 불가능한 경우 Faculty and Courses 테이블에 Course Code가 없는 Faculty인 경우 어떻게 삽입해야 할까? → 없음을 표시하는 불필요한 정보가 삽입 되어야함! 갱신 이상 일부만 변경하여, 데이터가 불일치 하는 경우 김사랑 → 김소연으로 바꾸는 경우 모든 김사랑이 김소연으로 바뀌어야만 한다. → 첫번째 튜플과 세번째 튜플 간의 데이터 불일치 발생 삭제 이상 튜플 삭제로 인해 꼭 필요한 데이터까지 함께 삭제되는 경우 ENG-206 강의를 제거하려고 389번 튜플을 제거했더니 Dr.Giddens의 정보도 삭제되었다. → 꼭..

기수 정렬이란? 낮은 자리수부터 비교하여 정렬해가는 알고리즘이며 비교 연산이 불필요한 정렬이다. 자릿수에 해당되는 값에 따라 버킷에 데이터들을 삽입하기 때문에 비교 연산이 불필요하지만 자릿수만큼의 추가적인 메모리 공간이 필요하다. (또한 자릿수만큼의 추가적인 로직도 필요하다) 자릿수가 비정상적으로 큰 데이터가 존재한다면 쓸데없는 메모리의 크기를 차지하게 된다. 구현과 시간 복잡도 자바를 이용한 구현 public static void main(String[] args) { RadixSort radixSort = new RadixSort(); for(int i=0; i

최대 공약수 구하기 유클리드 알고리즘이란? 최대 공약수(GCD)를 구할 수 있는 알고리즘으로, gcd(a,b)와 (r=a%b라고 할 때), gcd(b,r)의 최대 공약수는 같다. 즉, gcd(a,b) == gcd(b,r)이다. 이 성질에 따라 gcd(a,b) == gcd(b, a%b) == gcd(a%b, (a%b)%b).... 반복하여 나머지가 0이 되었을 때 나뉘어지는 수가 a와 b의 최대공약수가 된다. 정리하자면 gcd(a,b) -> cdg(a, a%b) .... -> gcd(x, 0)이면 a와 b의 최대 공약수는 x이다. 구현 private static int gcd(int a, int b) { if(b == 0) return a; return gcd(b, a%b); } 최소 공배수를 구하는 방법..