728x90
그리디는 탐욕적인 이라는 의미로
지금 현재 가장 최적의 것을 계속 골르는 것이다.
주로 정렬과 함께 한다.
회의실 배정 코드 :
if __name__=="__main__" :
n = int(input())
meeting = [list(map(int,input().split())) for _ in range(n)]
meeting.sort(key = lambda x : (x[1],x[0]))
endTime,cnt = 0,0
for s,e in meeting :
if s >= endTime :
cnt +=1
endTime = e
print(cnt)
=> 끝나는 시간을 오름차순으로 정렬한 후
시작시간이 이전 회의의 끝나는 시간보다 늦거나 같으면 해당 회의를 넣는다.
씨름 선수 코드 :
if __name__=="__main__" :
n = int(input())
person = [list(map(int,input().split())) for _ in range(n)]
# 키가 큰 순으로 정렬
person.sort(key = lambda x : x[0],reverse= True)
weight,cnt = 0,0
for h,w in person :
if weight < w :
cnt +=1
weight = w
print(cnt)
-> 키가 큰 순으로 정렬한다.
-> person을 돌면서 키는 무조건 앞에 사람보다 작으니까 무게를 비교하며 지원자의 수를 구한다.
만약 앞에 지원자의 무게보다 내가 작다면 나는 키 , 몸무게 둘 중 무엇도 이기지 못한것이기 때문이다.
창고 정리 코드 :
<내 코드 >
if __name__=="__main__" :
n = int(input())
ch = list(map(int,input().split()))
m = int(input())
for _ in range(m) :
ch[ch.index(max(ch))] -=1
ch[ch.index(min(ch))] += 1
print(max(ch) - min(ch))
< 선생님 풀이>
if __name__=="__main__" :
n = int(input())
ch = list(map(int,input().split()))
m = int(input())
ch.sort()
for _ in range(m) :
ch[0] +=1
ch[n-1] -=1
ch.sort()
print(ch[n-1] - ch[0])
아...정렬이 있었구나,,,
침몰하는 타이타닉 코드 :
if __name__=="__main__" :
n,m = map(int,input().split())
person = list(map(int,input().split()))
person.sort()
cnt = 0
while person :
if len(person) == 1 :
cnt +=1
break
if person[0]+person[-1] <= m :
cnt +=1
person.pop(0)
person.pop()
else :
cnt +=1
person.pop()
print(cnt)
리스트는 pop(0)을 하면 나머지 값들이 한칸씩 앞으로 가는 연산을 한다. -> 비효율적
덱이 빠르다. 덱은 그저 포인터 변수만 옮기면 되기 때문에
person을 deque으로 바꿔주고 pop(0)를 popleft()로 바꾸면 된다.
증가 수열 만들기 코드 :
if __name__=="__main__" :
n = int(input())
num = list(map(int,input().split()))
endNum, start,end = 0, 0,n-1
ans = ""
tmp_num = []
while start <= end :
if num[start] > endNum : tmp_num.append([num[start],'L'])
if num[end] > endNum : tmp_num.append([num[end],'R'])
tmp_num.sort()
if len(tmp_num) == 0: break
else :
ans += tmp_num[0][1]
endNum = tmp_num[0][0]
if tmp_num[0][1] == 'L' :
start +=1
else : end -=1
tmp_num.clear()
print(len(ans))
print(ans)
이전 수열의 마지막 값보다 큰 값만을 tmp_num에 방향 (L 또는 R)을 넣는다.
그리고 정렬한다.
둘 중 작은 것이 앞으로 가도록 정렬되었다.
만약 길이가 0이라면 마지막 값보다 작은 값이 없는 거이므로 break
0이 아니라면 0번째 값을 저장하고 왼쪽에서 왔냐 오른쪽에서 왔냐에 따라 start, end 를 조정한다.
역수열 코드 :
if __name__=="__main__" :
n = int(input())
num = list(map(int,input().split()))
ans = [0]*n
for i in range(n) :
for j in range(n) :
# 나보다 큰 친구가 들어오는 수는 이미 만족 , 그리고 내가 드러갈 수 있는 자리 찾기
if num[i] == 0 and ans[j] ==0 :
ans[j] = i+1
break
# 나보다 큰 친구가 들어오는 수
elif ans[j] ==0 :
num[i] -=1
print(*ans)
반응형
'스터디 > 알고리즘스터디-알까기🎯' 카테고리의 다른 글
완전탐색_바둑이 승차_cut edge 방법,DFS 시간초과를 방지하는 법 (0) | 2022.09.19 |
---|---|
이분탐색_ 이분탐색,랜선자르기,뮤직비디오,마구간 정하기 (0) | 2022.09.02 |
냅색 알고리즘 _ 가방문제, 동전교환, 최대 점수 구하기 (0) | 2022.09.02 |
[7]알고리즘스터디 - 섹션7_3주차 스터디 (0) | 2022.02.28 |
[6]알고리즘스터디 - 섹션6_3주차 스터디 (0) | 2022.02.28 |