알고리즘

Algorithm/BOJ

백준(BOJ) 11047번 동전 0 [그리디(Greedy)/알고리즘/파이썬(python)]

2021.08.11

그리디 알고리즘이란? "매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자"라는 모토를 가지는 알고리즘 설계 기법이다. 거스름돈을 돌려주는 문제를 생각해보자. 우리는 대부분 거스름돈을 돌려줄때 큰 단위의 동전부터 거슬러준다. ex ) 500원을 돌려줘야 한다면, 100원을 5개 주는 것보다 500원을 1개 주는 편이 더 편하다. 하지만 만약에 동전의 단위가 100, 250, 300 이라면, (300 * 1) + (100 * 2) 로 3개로 거슬러주는 것보다는 250 * 2 의 방법으로 2개로 거슬러주는 것이 더 최적의 방법이다. 따라서 그리디 알고리즘은 항상 최적의 해를 제공해주는 것은 아니다. 하지만 만약 이 상황에서 큰 단위의 수부터 거슬러줘야하는 조건이 존재할 때 그리디 알..

Algorithm/BOJ

백준(BOJ) 11000번 강의실배정 [그리디(Greedy)/알고리즘/파이썬(python)/큐]

2021.08.06

11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si < Ti ≤ 109) www.acmicpc.net 문제 수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다. 김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다. 참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.) 수강신청 대충한 게 찔리면, 선생님을 도와드리자! 입력 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si < ..

백준(BOJ) 11047번 동전 0 [그리디(Greedy)/알고리즘/파이썬(python)]

백준(BOJ) 11000번 강의실배정 [그리디(Greedy)/알고리즘/파이썬(python)/큐]

티스토리툴바