복습.
탐욕적 알고리즘이란? 매 반복시 최선의 것을 선택하는 알고리즘
A. 마감시간이 있는 최적 스케줄링 문제
마감시간 있는 최적 스케줄 문제는 일에 대한 마감시간과 그에따른 이익이 함께 주워 진다. 그리고 구하는 것은 이익이 최대가 되는 스케줄이다.
우선 문제에 들어가기 앞서 참고하면 좋은 영상과 그 영상으로부터의 코드를 소개한다.
https://www.youtube.com/watch?v=x9iDSJHV8F8
크루스칼에서는 feasible 과정이 있지만
같은 MST를 구하는 프림알고리즘에서는 feasible과정이 없다.
그 이유는 프림 알고리즘은 정점을 선택하는 것이기 때문이다.
프림 알고리즘에서 for문 사용으로 매번 다른 정점을 선택하는
코드 구조이다.
그렇다면 마감시간있는 프로젝트에서는 왜 feasible과정이 있나 그리고 이문제에서 feasible(적절함)이란 무엇인가?
이문제에서는 답이 될수 있는데 있어서 제한이 있고 그것이 마감시간이다. 마감시간이 지켜진다면 그것이 곧 적절함이다.
(마치 크루스칼알고리즘에서 매번 싸이클은 형성되어야 하지 않아야 "적절한" 것처럼)
다시! 크루스칼=간선을 선택하므로 사이클형성여부를 하는 feasible
test과정이 있음.
프림=매번 다른 정점을 선택하므로 사이클 형성여부를
검사하지 않아도 됨. feasible test 과정이 없음.
마감시간이 있는 스케줄링=각각의 프로젝트들이 마감시간을
시켜야 하므로 feasible test과정이 있는 것임.
크루스칼과 마찬가지로 우선 선택하고feasible test과정을
통과하면 정답에 추가 되는 것임
마감시간 있는 최적 스케줄 짜기 문제란? 주워진 마감시간에 어떻게 하면 최대의 이익을 얻을 수 있는가?
마감시간있는 최적 스케줄짜기 문제에서의 적절함이란? 어떤 작업의 시작이 그 deadline보다 이전에 시작되어야 적절한 것임.
어떻게 boolean 배열을 이용하면 deadline을 기준으로한 오름차순으로 프로젝트를 insert하는 과정과 feasible검사로 분리된 A의 코드를 단 한큐에
처리하는 B와 같이 만들수 있는 것인가?
#A코드
def insert(arr, i, deadline):
k=arr[:]
for j in range(len(k),0,-1):
if(deadline[i][0]>=k[j-1][0]):
j+=1
break
k.insert(j-1, deadline[i])
return k
def feasible(k, deadline):
for i in range(1, len(k)+1):
if(i>k[i-1][0]):
return False
return True
#deadline=>(deadline, iden)
def schedule(deadline):
n=len(deadline)-1
arr=list([deadline[1]])
for i in range(2, n+1):
k=insert(arr, i, deadline)
if(feasible(k, deadline)):
arr=k[:]
return arr
#B코드
def schedule(data, boolArr):
answer=list()
length=len(data)
for i in range(length):
k=data[i][1]
for j in range(k-1, -1, -1):
if(not boolArr[j]):
boolArr[j]=True
answer.append(data[i][0])
break
answer.sort()
print(*answer)
이것은 단순히 boolean배열만을 사용해서 이룬 성과가 아니다. 내부반복문을 for j in range(k-1, -1, -1):와 같이 설정해 줌으로써 시작부터 아예 알맞은 위치에 insert하게끔 하고 이것은 feasible(적절함)한 위치에 insert되는 것을 동시에 보장한다. 즉, boolean배열을 사용하고 범위를 조정해 주면 애초에 한번에 feasible하게 알맞은 위치에 insert할수 있다.
문제A. 마감 시간이 있는 최적 스케줄 짜기 정답
from sys import stdin
def insert(arr, i, deadline):
k=arr[:]
for j in range(len(k),0,-1):
if(deadline[i][0]>=k[j-1][0]):
j+=1
break
k.insert(j-1, deadline[i])
return k
def feasible(k, deadline):
for i in range(1, len(k)+1):
if(i>k[i-1][0]):
return False
return True
#deadline=>(deadline, iden)
def schedule(deadline):
n=len(deadline)-1
arr=list([deadline[1]])
for i in range(2, n+1):
k=insert(arr, i, deadline)
if(feasible(k, deadline)):
arr=k[:]
return arr
def main():
n=int(stdin.readline())
for _ in range(n):
length=int(stdin.readline())
data=list()
arr=list(map(int, stdin.readline().split()))
data=[(id, deadline, profit) for id, deadline, profit in zip(range(1, length+1), arr[0::2], arr[1::2])]
#아래와 같은 다양한 방식으로 프로젝트에 indexing을 먹일수 있다
# for iden, (deadline, profit) in enumerate(zip(arr[0::2],arr[1::2]), start=1):
# data.append((iden, deadline, profit))
# data=[(id,deadline, profit) for id, (deadline, profit) in enumerate(zip(arr[0::2], arr[1::2]), start=1)]
#이득을 기준으로 우선정렬하고 이득이 같다면 작업 id를 이용하여 정렬
data.sort(key=lambda e:(-e[2],e[0]))
deadline=list([(0,0)])
profit=list([0])
for id, a, b in data:
deadline.append((a,id))
profit.append(b)
# print("deadline:",deadline) #Successful
sc=schedule(deadline)
sc.sort(key=lambda e:e[1])
for i in range(len(sc)):
print(sc[i][1],end=' ')
print()
main()
시간복잡도 측면에서도 둘이 O(NlogN)으로 같다. 하지만 교수가 말하는 아래 내용을 지켜야 실질적인 실행시간도 짧아진다. 과연 이 복제가 반드시 필요한 것인가. 리스트 중간에 삽입하는 이 행위가 반드시 필요한 것인가를 항상 염두해 두어야 한다.
그리고 코드 자체의 성능 향상을 위해서 복사나 삽입이 쓰였다면 반드시 그 코드를 개선할 방법을 생각해 보아야 한다.
아래의 더 좋은 코드가 있음에도 불구하고 나는 위의 비효율적인 코드까지 같이 알아 두도록 한다. 나쁜 사례를 기억해 두고 왜 나쁜지를 알수 있는 효과와 greedy알고리즘의 전형적인 choosing, feasible의 과정을 거치는 예가 되는 코드이기 때문이다.
#교수의견 반영하여 다시 개선한 코드.
#기본적으로 insert함수내에서 깊은복사(k=arr[:])나 insert연산을 이용하는 것은 매우 비효율적임.
#이런 비효율성은 bool배열을 통하여 해결할 수 있었음
from sys import stdin
def schedule(data, boolArr):
n=len(data)
arr=list()
for i in range(n):
k=data[i][1]
for j in range(k-1, -1,-1):
if(not boolArr[j]):
arr.append(data[i][0])
boolArr[j]=True
break
arr.sort()
print(*arr)
def main():
n=int(stdin.readline())
for _ in range(n):
length=int(stdin.readline())
data=list()
arr=list(map(int, stdin.readline().split()))
leng=-1
for id, deadline, profit in zip(range(1, length+1), arr[0::2], arr[1::2]):
data.append((id, deadline,profit))
if(deadline>leng):
leng=deadline
data.sort(key=lambda e:(-e[2],e[0]))
boolArr=[False]*leng
schedule(data, boolArr)
main()
마지막으로 Java Code!
복습.
배열을 정렬하는데 굳이 stream을 가져다 쓸 필요가 없다. 자료구조 클래스또한 정렬만 한다고 하면 굳이 stream라이브러리를 사용하지 않아도 된다. 그냥 Collections.sort(자료구조객체)해주면 된다. 다만 정렬에 더해 추가적 작업(예를들면 int를 string으로 바꾸어 그것을 한 칸 간격을 두어 문자열로 collect하고 싶다던지)이 필요할때 stream라이브러리가 필요한 것이다. 배열은 그 자체로 완벽하다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.stream.Collectors;
class Project{
private int id;
private int deadline;
private int profit;
public Project(int id, int deadline, int profit){
this.id=id;
this.deadline=deadline;
this.profit=profit;
}
public int getId(){
return this.id;
}
public int getProfit(){
return this.profit;
}
public int getDeadline(){
return this.deadline;
}
}
public class Main{
public static List<Integer> schedule(Project[]projects, boolean[]boolArr){
List<Integer>answer=new LinkedList<>();
for(int i=0;i< projects.length;i++){
int curDeadline=projects[i].getDeadline();
for(int j=curDeadline-1;j>-1;j--){
if(! boolArr[j]){
boolArr[j]=true;
answer.add(projects[i].getId());
break;
}
}
}
return answer;
}
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int T=Integer.parseInt(br.readLine());
for(int t=0;t<T;t++){
int length=Integer.parseInt(br.readLine());
int[]arr= Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
int i=0;
Project[]projects=new Project[length];
int len=-1;
for(int j=0;j<length;j++){
int deadline=arr[i++];
int profit=arr[i++];
projects[j]=new Project(j+1, deadline, profit);
if(deadline>len)
len=deadline;
}
//배열을 정렬하는데 굳이 stream을 가져다 쓸 필요가 없다. 자료구조 클래스또한
//정렬만 한다고 하면 굳이 stream라이브러리를 사용하지 않아도 된다.
//그냥 Collections.sort(자료구조객체)해주면 된다. 다만 정렬에 더해 추가적
//작업(예를들면 int를 string으로 바꾸어 그것을 한 칸 간격을 두어
//문자열로 collect하고 싶다던지)이 필요할때 stream라이브러리가 필요한 것이다.
//배열은 그 자체로 완벽하다.
boolean[]boolArr=new boolean[len];
Arrays.sort(projects, Comparator.comparing(Project::getProfit).reversed().thenComparing(Project::getId));
System.out.println(schedule(projects, boolArr).stream().sorted().map(s->s.toString()).collect(Collectors.joining(" ")));
}
}
}'알고리즘 > School Algo Through Java' 카테고리의 다른 글
| S-algo10 동적프로그래밍(1) howSum (0) | 2023.12.26 |
|---|---|
| S-algo10 동적프로그래밍(1) cansum (0) | 2023.11.11 |
| School algo02 전수조사(답만 깔끔하게 제시한 버전) (0) | 2023.10.31 |
| School algo02 전수조사 (0) | 2023.10.31 |
| 그래프 탐색 BFS, DFS (0) | 2023.09.17 |
