je_record

문제 일정의 개수와 각 일정의 시작날짜, 종료날짜가 주어질 때 수현이가 자르는 코팅지의 면적 https://www.acmicpc.net/problem/20207 20207번: 달력 수현이는 일년의 날짜가 1일부터 365일로 표시되어있는 달력을 가지고있다. 수현이는 너무나도 계획적인 사람이라 올 해 일정을 모두 계획해서 달력에 표시해놨다. 여름이 거의 끝나가자 장 www.acmicpc.net 조건 일정이 있는 곳에 코팅지를 달력에 붙인다. 연속된 두 일자에 각각 일정이 1개 이상 있다면 이를 일정이 연속되었다고 표현한다. 연속된 모든 일정은 하나의 직사각형에 포함되어야 한다. 연속된 일정을 모두 감싸는 가장 작은 직사각형의 크기만큼 코딩지를 오린다. 달력은 다음과 같은 규칙을 가진다. 일정은 시작날짜와 종..

크루스칼 알고리즘을 이용하는 문제이다. 처음에 문제를 보고 크루스칼 알고리즘이 떠오르지 않아 헤매다가 구글링을 통해 찾아보며 풀이 방법을 알게 되었다. 크루스칼 알고리즘이란? 간단하게 설명하면 그래프 내의 모든 정점들을 가장 적은 비용으로 연결하기 위해 사용된다. 그래프 내의 모든 정점을 포함하고 사이클이 없는 연결 선을 그렸을 때, 가중치의 합이 최소가 되는 상황을 구하고 싶을 때 크루스칼 알고리즘을 사용하게 된다. 즉 최소 신장 트리를 구하기 위한 알고리즘이다. 참고 https://chanhuiseok.github.io/posts/algo-33/ 알고리즘 - 크루스칼 알고리즘(Kruskal Algorithm), 최소 신장 트리(MST) ## chanhuiseok.github.io 다른 풀이 코드 #i..

성공 코드(내 코드) 문자열로 저장되어 있는 숫자를 v 벡터에 정수로 변환하여 넣는다. 선택해야 하는 숫자의 개수만큼 반복문을 돌린다. 총 n개를 뽑아야 한다고 가정하면, 1번째 숫자를 고를 때 뒤에 최소한 n-1개의 숫자가 남아있어야 한다. 뒤에 숫자가 n-1개가 남기 전까지 v 벡터를 탐색하며 가장 큰 숫자를 찾는다. 찾은 가장 큰 숫자를 answer에 string으로 변환하여 추가한다. 똑같은 방법으로 2번째 숫자를 고른다. 이 과정을 n개의 숫자를 모두 뽑을 때 까지 반복한다. 이때는 뒤에 최소한 n-2개의 숫자가 남아있어야 한다. #include #include #include using namespace std; string solution(string number, int k) { strin..

알고리즘 그리디 알고리즘 정렬 풀이 나무 중 자라는 길이가 큰 것을 가장 나중에 자르도록 한다. 첫날 나무의 길이에 매일 자라는 길이만큼 더해지므로, 정수 ans 변수에 첫날 나무의 길이를 다 더해둔 후 매일 자라는 길이 * 자르기 전까지 자라난 일 수를 반복문을 통해 더해준다. 매일 자라는 길이는 오름차순 정렬 후 배열의 끝에서부터 사용하였다. 시간 초과 코드 grow 배열을 정렬하지 않고 굳이 max 값을 일일이 구하여 O(n^2) 시간복잡도가 되어 시간초과 발생 #include #include #include using namespace std; int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); // freopen("input.txt", "..

알고리즘 그리디 알고리즘 풀이 0번째 스위치를 누르는 경우와 0번째 스위치를 누르지 않는 경우를 나누어 생각한다. 1~n-1번째 스위치를 누를지 말지 여부를 결정하기 위해 for문을 돌린다. i번째 스위치를 누를지 말지를 결정하기 위해 i-1번째 전구의 상태와 목표로 하는 i-1번째 전구의 상태를 비교한다. 같으면 누르고 cnt++ 다르면 누르지 않는다. 현재 전구의 상태와 목표로 하는 전구의 상태가 같으면 cnt를 리턴하고 그렇지 않으면 2147000000을 리턴한다. 0번째 스위치를 누르는 경우와 0번째 스위치를 누르지 않는 경우 중 최소값을 골라 출력한다. 만약에 두 경우 모두 답이 나오지 않아 리턴값이 2147000000인 경우 -1을 출력한다. 전체 코드 #include #include usin..

알고리즘 그리디 알고리즘 정렬 풀이 시작하는 시간이 빨라도 늦게 긑나면 최대 회의의 수를 맞출 수 없으므로 각각의 스케줄에서 회의의 종료시간이 중요하게 작용한다. 각 회의 시작시간과 종료시간을 입력받으면 이를 종료시간을 기준으로 오름차순으로 정렬한다. 이때 종료시간이 같으면 시작시간을 기준으로 오름차순으로 정렬한다. 첫번째 end 변수는 종료시간이 가장 빠른 스케줄의 종료시점으로 초기화한다. 두번째 스케줄의 시작 지점이 첫번째 스케줄의 종료시점보다 크거나 같은지 확인한다. 크거나 같아면 cnt++ 한다. 모든 스케줄을 확인할 떄 까지 2번을 반복한다. 성공 코드 #include #include #include using namespace std; int n; struct Con{ int s, e; Con..