다익스트라 알고리즘이 뭘까? 다익스트라 알고리즘이란 하나의 출발점에서 도달할 수 있는 모든 도착점에 대한 최단 경로를 구할 수 있는 알고리즘이다. 대신 조건이 있는데 다익스트라 알고리즘은 간선들의 비용이 모두 양수여야만 적용이 가능하다. 만약 음의 비용을 가진 간선이 존재한다면 최단 경로를 구할 수 없다. 다익스트라 알고리즘과 다이나믹 프로그래밍 다익스트라 알고리즘의 메인 아이디어는 다이나믹 프로그래밍(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); } 최소 공배수를 구하는 방법..

프로세스 vs 프로그램 프로그램 : 특정 작업을 수행하기 위한 코드들의 모음 프로세스 : 프로그램이 커널에 등록된 상태를 프로세스라고 한다. 성능 향상을 위해 커널이 프로세스를 관리한다. JOB : 프로그램 + 데이터 프로세스란? 커널에 등록된 커널의 관리하에 있는 프로그램 각종 자원을 요청하고 할당받을 수 있는 동적 개체 PCB를 할당 받은 개체 PCB란? 커널내에 존재하며, 프로세스의 정보를 가지고 있다. PCB에는 다음과 같은 필드가 존재한다. 스케줄링 정보 프로세스 상태 메모리 관리 정보 입출력 상태 정보 문맥 저장 영역 계정 정보(다중 시스템인 경우를 위한 정보) 프로세스 상태 Created State (-> ready or suspended ready) 프로그램을 커널에 등록한 상태, PCB를..