프로세스란?프로세스 : (메모리에 올려져서,) 실행중인 프로그램코드 이미지(바이너리) : 실행 파일응용 프로그램 ≠ 프로세스응용 프로그램은 여러 프로세스로 구성 가능프로세스라는 용어는 작업, task, job 이라는 용어와 혼용ex) 엑셀 프로그램과 엑셀 프로세스excel.exe(코드 이미지, 바이너리)와 엑셀 프로세스해당 파일은 코드로 구현이 되어있을 텐데, CPU가 이해할 수 있는 0과 1로 이루어진 파일로 만들어서 저장(바이너리)이를 실행하면 메모리에 올라감(프로세스)프로세스 스케쥴링프로세스를 언제 실행 시킬 건지1. 배치 처리 시스템(Batch Processing)초기 프로세스 스케쥴링 알고리즘으로 배치 처리 시스템을 채택여러 프로그램을 순차적으로 실행시킬 수 있도록어떤 프로그램은 실행하는데 시간..
문제https://www.acmicpc.net/problem/2805 풀이해당 문제는 높이의 최댓값을 구하는 문제로 매개변수 탐색을 통해 해결했습니다.매개변수 탐색으로 해결한 이유는 최댓값을 구하는 최적화 문제이며 이를 결정 문제로 해결하게되면 답을 도출하는 것이 수월하다고 생각했기 때문입니다. 방법은 다음과 같습니다.1. 수열을 입력받으며 배열에 저장하고, 그 값들 중 최댓값을 저장합니다.2. 매개변수 탐색을 하면서 문제에서 원하는 최댓값을 찾습니다.s = 0, e = 입력값들 중 최댓값, while(e > s)mid 값을 구해줍니다.(이때의 mid 값은 높이 입니다.)mid(높이) 값을 기준으로 들고 갈 나무를 셉니다.(N과 높이의 값이 크기 때문에 long 타입으로 리턴해줍니다.)c에서 구한 값 ≥..
문제https://www.acmicpc.net/problem/2412 풀이시작 위치에서 종료 위치까지 도달하기 위해 그래프 탐색을 이용해서 문제를 해결했습니다.해당 문제는 2차원 배열에 위치를 마킹하거나 방문처리를 하게되면 메모리 초과가 발생합니다.따라서 그래프 탐색을 위해 입력받은 값을 y(열)를 기준으로 list 배열에 x(행)값을 저장해두었고현재 행에서 갈 수 있는 열에 대해서, 다음으로 갈 수 있는 유효한 좌표를 탐색했습니다.최단거리를 구해주는 문제이기 때문에T열에 가장 먼저 도달했을 때의 cnt 값을 리턴해주었습니다.(도달하지 못했다면 -1 리턴) 코드import java.io.*;import java.util.*;public class Main { static int N, T; st..
문제https://www.acmicpc.net/problem/1920 풀이특정 값을 찾는 문제로 시간 복잡도를 고려하여 이분탐색 알고리즘을 활용해 문제를 해결했습니다. 입력 받은 수열을 배열에 넣고 정렬했습니다.타겟 값을 찾기 위해 이분탐색을 진행했습니다.s = 0, e = N-1로 두었습니다.while 조건은 e ≥ s로 두었습니다.(e == s 때 리턴해주기 위해)mid 값이 타겟값 보다 클 경우, (더 커질 필요가 없기 때문에) mid ~ e 까지의 후보군을 제외했습니다.이때 e = mid-1로 e값을 변경했습니다.e = mid로 설정하면 s와 e가 같아지는 상황에서 무한루프에 걸리게 되면서 시간 초과가 발생합니다.mid 값이 타겟값 보다 작을 경우, (더 작아질 필요가 없기 때문에) s ~ mid..
문제https://www.acmicpc.net/problem/1516 풀이선행 조건을 해결해야하는 문제 특성상 위상정렬을 이용해서 문제를 해결했습니다.입력을 받으면서, 정보를 저장했으며(진입차수, 건물 건설시간, 선행 건설 건물정보)진입차수가 0인 건물을 큐에 넣고 그래프 탐색을 진행했습니다. 이때, 건물이 동시에 지어질 수 있기 때문에건물 중 가장 오래걸리는 시간을 찾아서 ans 정답 배열에 저장해주었고진입차수를 1 감소시킨 값이 0이라면 큐에 넣어주었습니다. 그래프 탐색을 마친 후건물을 순회하면서 도출된 정답 배열 값 + 현재 건물을 건설하는 데 걸리는 시간을 더해주어 출력했습니다. 코드import java.io.*;import java.util.*;public class Main { stati..
개념분할 정복을 기반으로 정렬되는 알고리즘이며, 대용량 데이터를 정렬할 때 유리합니다.추가적인 공간 필요 X피벗을 기준으로 나누어진 두 개의 집단 사이에서 요소의 교환이 일어나는 불안정한 정렬입니다. 병합 정렬(Merge Sort)와의 차이점은병합 정렬은 수열의 절반을 나누어 분할 정복을 수행하지만퀵 정렬은 피벗을 기준으로 분할 정복을 수행합니다. 로직피벗을 기준으로 2개의 배열로 분할하고(분할)분할된 배열을 각각 정렬한 다음(정복)정렬된 배열을 합하는 방식으로 동작합니다. (결합)큰 값과 작은 값을 나누어 정렬하는 방식으로 동작합니다. 1. 분할입력 배열을 피벗을 기준으로 2개의 부분 배열로 분할합니다.피벗의 좌측에는 피벗보다 작은 값을 두고피벗의 우측에는 피벗보다 큰 값을 둡니다. 2. 정복부분 배열..
개념요소들 중에서 최대/최소값을 찾아 정렬하는 알고리즘입니다.최대값 선택 시 내림차순 정렬을 진행합니다.(최솟값 선택 시 오름차순 정렬) 로직오름차순 정렬을 기준으로 보자면먼저 0~N-1 요소들 중에서 가장 작은 값을 찾고 0번째 인덱스와 교환해줍니다.그다음 정렬된 0번째를 제외한1~N-1 요소 중에서 가장 작은 값을 찾고 1번째 인덱스와 교환해줍니다.이렇게 총 N-2번(마지막 인덱스 탐색 X) 반복하면 정렬이 완료됩니다.추가 메모리 공간이 필요하지 않는 특징이 있습니다. 코드자바로 작성한 선택정렬 코드는 다음과 같습니다.// 선택 정렬: N^2 순회// 오름차순 정렬for (int i = 0; i arr[j]){ minVal = arr[j]; minIdx = j..
개념정렬을 진행할 원소의 index(a)보다 작은 곳(0~a-1)에 있는 원소들을 탐색하고알맞은 위치에 삽입하여 정렬하는 알고리즘입니다.구현이 간단하다는 특징이 있습니다. 로직오름차순 정렬 기준1~N-1번째 인덱스를 순차적으로 key로 두고key-1 ~ 0의 인덱스를 감소순회하면서만약 arr[현재의 값] > key 라면, arr[현재의 값+1] = arr[현재의 값]을 넣어줍니다.그렇지 않다면, 순회를 종료합니다.순회가 끝나고 난 후, arr[마지막 위치 + 1] = key 값으로 갱신합니다. 코드자바로 작성한 삽입정렬 코드는 다음과 같습니다.// 삽입 정렬: N^2 순회int key, j;for (int i = 1; i = 0 ; j --) { if (arr[j] > key) arr[j+1..
