CS

알고리즘 - 최소 편집 거리(Minimum Edit Distance)

문자열 S를 다른 문자열 T로 변환하고자 할 때 필요한 최소의 편집 연산 횟수를 구하는 문제. 1회의 연산에는 삽입(insert), 삭제(delete), 대체(substitute)중 한 가지만 할 수 있다. 문자열 S = strong 문자열 T = stone S를 T로 변환하기 위해서는 총 4회의 편집 연산이 필요하다. s t r o n g s t o n e 1. o 삽입 2. r 삭제 3. o 삭제 4. g -> e 대체 총 4회의 편집 연산이 필요하다.

알고리즘 - 플로이드 와샬 알고리즘(Floyd Warshall Algorithm)

다익스트라 알고리즘 하나의 정점에서 출발했을 때 다른 모든 정점으로의 최던 경로를 구하는 알고리즘. 가장 적은 비용을 하나씩 선택을 해서 그 노드의 인접한 노드로 가는 길을 하나씩 계산해서 푼다. 1에서 3으로 가는 비용이 바로가는것보다 2을 거쳐간다면 거쳐가는 만큼의 비용으로 1에서 3으로 가는 비용을 수정한다. 플로이드 와샬 알고리즘 모든 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘 거쳐가는 정점을 기준으로 한다. 아예 반복문의 중심에 거쳐가는 노드가 있다. 에초에 거쳐가는 노드를 하나씩 설정해서 확인한다. 그래프가 있을 경우 2차원 배열의 형태로 유지한다. 1번 2번 3번 4번 1번 0 7 무한 무한 2번 5 0 9 6 3번 2 무한 0 4 4번 무한 무한 3 0 왼쪽 번호에서 상단 번호로..

운영체제(OS) - 데드락(Deadlock)

Deadlock - 어떤 프로세스 집단 내의 각 프로세스가 그 집단 내의 또 다른 프로세스에 의해서만 발생할 수 있는 이벤트를 기다리고 있으면, 그 프로세스 집단은 deadlock상태에 있다. 이 그림처럼 차량이 또다른 차량의 앞을 막고, 또 그 차량이 또 다른 차량의 앞을 막아 아무도 빠져나갈 수 없는 상태가 되었을 때 Deadlock상태라고 할 수 있다. 프로세스가 후진을 할 일은 없기 때문에 deadlock이 발생하면 손해없이 복구할 수 없다, deadlock에 관련된 프로세스중 누군가는 rollback또는 사라져야 한다. 위의 사진에서도 차량중 한 개의 차량만 사라져도 Deadlock은 풀리게 된다. Deadlock 발생 4가지 필요조건 1. 상호 배제(mutual exclution) - 각 자원..

운영체제(OS) - Segmentation

세그먼트 - 완전히 독립적인 주소 공간이다. - 각 세그먼트는 0부터 시그템에서 허용된 최대 크기까지 값을 갖는 선형 주소로 구성된다. 세그먼트는 서로 다른 크기이다.(page는 모두 동일한 크기) 세그먼트 크기 는 다른 세그먼트에 영향을 주지 않으면서 독립적으로 증가하거나 감소할 수 있다. 조건 페이징(paging) 세그멘테이션(segmentation) 프로그래머는 어떤 기술이 사용되고 있는지 알고 있어야 하는가? no yes 주소 공간의 크기의 종류가 몇개나 있는가 1 many 총 주소공간의 크기가 실제 메모리의 크기보다 클 수 있는가 yes yes 절차와 데이터를 구분하고 보호할 수 있는가? no yes 공간의 크기를 쉽게 변경할 수 있는가? no yes 사용자와의 절차 공유를 하게 되는가 ? no..

알고리즘 - 모든 쌍 최단 경로 문제(All Pairs Shortest Paths)

각 쌍의 점 사이의 최단 경로를 찾는 문제 다익스트라의 최단 경로 알고리즘 - 한 정점에서 모든 정점으로의 최단경로를 구함 - 각 점을 시작점으로 정하여 다익스트라 알고리즘 수행 - 시간 복잡도는 O(n^3) - 가장 적은 비용의 정점을 기준으로 하나씩 선택해 가며 구해냄. 플로이드-워샬(Floyd_Warshall) 알고리즘 - 모든 정점에서 모든 정점으로의 최단 경로를 구함. - 거쳐가는 정점을 기준으로 알고리즘 수행

알고리즘 - 동적 계획 알고리즘(Dynamic Programming)

Dynamic Programming(DP) 동적 계획 알고리즘은 그리디 알고리즘과 같이 최적화 문제를 해결하는 알고리즘이다. - 입력 크기가 작은 부분 문제들을 해결한 후, 그 해를 이용하여 큰 크기의 부분 문제들을 해결... - 최종적으로 주어진 입력의 문제를 해결 - 작은 부분 문제의 해가 보다 큰 부분 문제를 해결하는데 사용되는 관계가 있다. 각 단계의 부분문제의 답을 기반으로 전체 문제의 답을 구하는 방법

알고리즘 - 작업 스케줄링 알고리즘(JobScheduling)

작업의 수행 시간이 중복되지 않도록 모든 작업을 가장 적은 수의 기계에 배정하는 문제 대학 수업에서 강의실을 배정하는 문제와 같다. 강의실 = "기계" 강의 = "작업" 주어진 요소 - 작업의 수 - 각 작업의 시작시간과 종료시간 - 작업의 길이 알고리즘 다음과 같은 그리디 알고리즘이 존재한다. - 빠른 시작시간 작업 우선(Earliest start time first)배정 - 빠른 종료시간 작업 우선(Earliest finish time first)배정 - 짧은 작업 우선(Shortest job first)배정 - 긴 작업 우선(Longest job first)배정 위 4가지중 첫 번째 알고리즘을 제외하고 나머지 3가지는 항상 최적해를 찾지 못한다. 빠른 시작시간 작업 우선(Earliest start ..

알고리즘 - 집합 커버 문제(Set Cover)

집합 F에서 선택하는 집합들의 수를 최소화하는 문제 신도시를 계획하는데 있어서 학교 배치의 예) 10개의 마을이 신도시에 만들어질 계획이다. 조건이 만족되어야 한다. 조건 1. 학교는 마을에 위치해야 한다. 조건 2. 등교 거리는 걸어서 15분 이내이어야 한다. 2번 마을에 학교를 만들면 1, 2, 3, 4 ,5 마을이 커버된다. 6번 마을에 학교를 만들면 5, 6, 7, 9, 19 마을이 커버된다. 최소 학교의 수 = 2개 전체 마을의 수 U = {1, 2,3 ,4, 5, 6, 7, 8, 9 ,19} 한 마을에 배치했을때 커버되는 마을의 집합 S1 = {1, 2, 3, 8} S2 = {1, 2, 3, 4, 8} S3 = {1, 2, 3, 4} S4 = {2, 3, 4, 5, 7, 8} S5 = {4, ..

알고리즘 - 부분 배낭 문제(Fractional Knapsack)

문제 n개의 물건이 각 무게와 가치를 가지고 있을 때, 한정된 용량의 배낭에 최대 가치를 갖도록 배낭에 넣을 물건들을 정하는 문제. 물건의 전체를 넣지 못한다면 물건을 부분적으로 담는 것을 허용된다. 해결 방법 단위 무게당 가장 값나가는 물건을 배낭에 넣고 계속해서 그 다음으로 값나가는 물건을 넣는다. 만일 물건을 통째로 배낭에 넣을 수 없으면 배낭에 넣을 수 있을 만큼만 물건을 부분적으로 배낭에 담는다. 수행 과정 배낭의 최대 용량 = 40 단위 무게당 가치로 정렬 물건 가치 무게 단위 그램당 가치 백금 60만원 10g 6만원 금 75만원 15g 5만원 은 10만원 25g 4천원 주석 1만원 10g 1천원 백금을 통째로 담는다. 배낭의 무게 = 10/40 가치 = 60만원 금을 통째로 담는다. 배낭의 ..

알고리즘 - 다익스트라 알고리즘(Dijkstra Algorithm)

다익스트라 알고리즘은 다이나믹 프로그래밍을 활용한 대표적인 최단경로(Shortest Path)탐색 알고리즘이다. 흔히 최소비용으로 선로 또는 파이크 네트워크, 인공위성 GPS 소프트웨어에서 가장 많이 사용된다. 다익스트라 알고리즘은 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다. 이 떄 음의 간선을 포함할 수 없는데 현실 세계엔 음의 간선이 존재하지 않기 때문에 현실 세계에 사용하기 매우 좋은 알고리즘이라고 한다. 다익스트라 알고리즘이 다이나믹 프로그래밍 문제인 이유는 최단 거리는 여러개의 최단 거리로 이루어져 있기 떄문이다. 하나의 최단거리를 구할 때 직전까지 구했던 최단거리를 이용한다. 1. 출발 노드를 정한다. 2. 출발 노드를 기준으로 각 노드의 최소 비용을 저장한다. 3...