0914 TIL
알고리즘 문제 풀이
- 프로그래머스 "구명보트" 해결
- 특이점
1. 투 포인터 이용
- 시작점과 끝점 인덱스 포인터를 잡고 조작해가면서 원하는 것을 얻는 형태
2. 전체 정렬
3. s=0, e=배열의 마지막 길이-1
4. while (s<=e) 일때까지 진행
5. 정렬된 상태이기 때문에 처음과 끝의 합을 구하고
IF) 합이 limit을 이하하면 s+=1, e-=1로 변경하여 둘다 통과하게 함.
ELSE ) e-=1로 하여 마지막 것만 통과하게 함.
마지막으로 answer+=1로 증가하고 변경된 다음 인덱스를 참조하게 함 - 코드
import java.util.*;
class Solution {
public int solution(int[] people, int limit) {
ArrayList<Integer> arrayList=new ArrayList<>();
for (int i:people) {
arrayList.add(i);
}
// 정렬
Collections.sort(arrayList);
int start=0;
int last=arrayList.size()-1;
int answer = 0;
while (start<=last) {
int maxVal=arrayList.get(last);
int minVal=arrayList.get(start);
int hap=minVal+maxVal;
if (hap<=limit) {
// 둘다 통과
start+=1;
last -=1;
}
else {
// 마지막 것만 통과
last-=1;
}
answer+=1;
}
return answer;
}
}- 장점
- 배열을 삭제하지 않아도 되기때문에 시간 절약
- 리스트를 한 번만 탐색하기 때문에, 리스탁 이미 정렬되어 있는 경우 O(n), 정려되어 있지 않더라도 O(nlongn)이라는 정도의 시간 복잡도를 얻을 수 있음. - 참조 블로그
https://velog.io/@adorno10/%ED%88%AC-%ED%8F%AC%EC%9D%B8%ED%84%B0-Two-Pointer
CS 스터디
- CPU 스케쥴링 : 어떤 프로세스가 CPU를 점유할지를 결정하는 것
- 선점형 vs 비 선점형
- 선점 : 이미 진행중인 CPU를 다른 프로세스가 빼았아서 진행
- 비선점 : 하나의 프로세스가 완료될때까지 기달리는 방식 - CPU 스케쥴링 알고리즘
- 모든 프로세스의 AWT(Average Wating Time)을 계산하여 처리
-
FCFS (First-Come, Frist -Served) : 먼저 오면 먼저 처리 / 대표적인 비 선점형 스케쥴링 방식
-
SJF (Shorted Job First) : Busrt Time (실행시간)이 가장 짧은 것부터 처리 하는 방식
- 비 선점 진행 : 모든 프로세스의 Busrt Time을 미리 계산 (추가 오버헤드)하여 짧은 것부터 차례로 진행
- 선점형 진행 : arrival Time을 추가적으로 계산하여 P1이 진행중 P2의 Arrival Time이 오고 P2의 busrt time이 더 짧으면 P2를 진행으로 변경
- 장점 : AWT만 놓고 보면 선점에 비해 더 빠를 수 있음
- 단점 : Context switching overhead 가 발생
-
Priority Scheduling : 우선 순위가 높은 순서대로 처리 (일반적으로 숫자가 낮을수록 우선순위가 높음)
- 기아 상태 (Starvation)이 발생할 수 있음 : 이는 우선순위가 낮은 프로세스가 레디 큐에서 계속 기다리는 상태 (새로 들어온 프로세스가 더 우선순위가 높아서 계속 대기)
- 방지 기법 : Aging 기법을 통해 오래 기다린 프로세스의 우선순위를 높여주는 방식
-
Round Robin : 임의의 Time quantum( or time slice)을 두고 일정 시간이 지나면 다음 프로세스에게 CPU 점유를 넘기는 방식
- Time quantum이 길어지면 FCFS와 같아짐
- Time quantum이 짧다면 context switching이 매우 빈번하게 일어나므로 오버헤드도 증가
참고 블로그
BackEnd Developer