출처 : Programmers(https://programmers.co.kr/learn/courses/30/lessons/42627) 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러는 여러 가지 방법으로 구현할 수 있습니다. 먼저, CPU 프로세스 스케줄링의 여러 가지 방법을 알아보려면 -> https://junboom.tistory.com/13 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 방법(FIFO: First In First Out, A -> B -> C)입니다. 이때, 각 작업의 요청으로부터 종료까지 걸린 시간의 평균은 (3 + 11 + 16) / 3 = 10ms입니다. 하지만 하드디스크 작업이 끝난 후 가장 짧은 작업 먼저 처리할 경우(SJF: Short Jo..

2020 상반기 삼성전자 SW 역량테스트 문제 출처 : BOJ(https://www.acmicpc.net/problem/19236) 4 x 4 공간 안에 물고기 16마리가 존재하고, 상어가 (0, 0) 지점의 물고기부터 먹기 시작해 먹은 물고기 방향으로 나아가며 먹기를 반복하는 문제입니다. BFS로 4 x 4 공간인 map과 물고기의 정보를 단계마다 저장할 수 있도록 HashMap과 Key인 cnt를 활용해 문제를 풀었습니다. 사이클마다 계속해서 map이 변하고, 물고기의 이동 방향이 변하기 때문에 HsahMap에 저장하는 방법을 선택했습니다. 우선, 상어가 (0, 0) 자리에 들어오고, (0, 0) 자리에 있던 물고기의 번호(num)를 섭취하고, 방향(d)을 가지게 됩니다. 이후 그 방향에 있는 모든 ..

합병 정렬은 주어진 array를 지속적으로 쪼개어 최소 array에서 값을 비교해 다시 합치고 정렬하는 방식으로 최소, 최대, 평균 시간 복잡도가 O(n*log n)으로 비교적 가장 빠른 정렬 방법입니다. 쪼개진 array를 정렬하여 저장하기 위한 별도의 copy array가 필요하기 때문에 공간복잡도는 n입니다. 자바와 벡터를 이용해 합병 정렬을 구현해 보겠습니다. Java 코드 package sort; import java.util.Vector; public class MergeSort { static void merge(Vector v, int s, int e, int m) { Vector ret = new Vector(); int i = s; int j = m + 1; while (i