출처 : https://www.acmicpc.net/problem/19235 19235번: 모노미노도미노 모노미노도미노는 아래와 같이 생긴 보드에서 진행되는 게임이다. 보드는 빨간색 보드, 파란색 보드, 초록색 보드가 그림과 같이 붙어있는 형태이다. 게임에서 사용하는 좌표 (x, y)에서 x는 행, www.acmicpc.net 해당 문제는 빨간색 보드에서 파란색 보드와 초록색 보드로 좌표에 따라 블록이 이동하는 게임입니다. 블록의 종류는 1x1, 1x2, 2x1이 있습니다. 해당 문제의 마지막 테스트케이스인 예제 7번을 수행하게 되면 다음 그림과 같이 배치됩니다. 파란색 보드에서 열 부분이 모두 채워지거나 초록색 보드에서 행 부분이 모두 채워지면 점수를 획득합니다. 열이나 행 부분이 모두 채워지지 않은 ..

출처 : 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..

1. OOP(Object Oriented Programming) : 객체지향 프로그래밍 OOP란? 캡슐화, 다형성, 상속성, 추상화 4가지 특징을 이용해 코드의 재사용을 증가시키고 유지보수 빈도를 감소시키는 장점을 얻기 위해 객체들을 연결시켜 프로그래밍하는 것입니다. 캡슐화(Encapsulation) : 객체의 필드, 메서드를 하나로 묶고 실제 구현 내용을 감추는 것 다형성(Polymorphism) : 같은 이름으로 실행 결과가 다양한 객체를 이용하는 것 ex) 오버로딩(Overloading) : 이름은 같지만 다른 매개변수와 다른 리턴 타입을 갖는 것 오버라이딩(Overriding) : 부모의 함수를 상속받아 메서드를 재정의하는 것 상속성(Inheritance) : 상위 개념의 특징을 하위 개념이 물려..

QuickSort는 주어진 array를 분할 정복하고, pivot을 설정해 pivot과 비교하며 정렬하는 방법입니다. pivot 설정은 개발자에 따라 다르게 설정할 수 있지만, 보통은 중앙값을 pivot으로 설정합니다. 분할 정복을 하기 때문에 최소, 평균 시간복잡도가 O(n*log n)이지만, pivot과 비교되는 값이 항상 조건에 충족되어 pivot을 지속해서 바꿔주어야 하는 경우(최악의 경우) O(n^2)이 됩니다. 기존의 array에서 값을 변경하기 때문에 공간복잡도는 1입니다. 자바와 벡터를 이용해 QuickSort를 구현해 보겠습니다. Java 코드 import java.util.Vector; public class QuickSort { static void quickSort(Vector v,..

합병 정렬은 주어진 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