je_record

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

알고리즘 그리디 알고리즘 정렬 풀이 나무 중 자라는 길이가 큰 것을 가장 나중에 자르도록 한다. 첫날 나무의 길이에 매일 자라는 길이만큼 더해지므로, 정수 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", "..

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

알고리즘 자료 구조 정렬 이분 탐색 해시를 사용한 집합과 맵 풀이 1. 가지고 있는 숫자 카드를 card 배열에 오름차순으로 정렬한다. 2. card 배열의 원소들을 돌며 숫자가 동일한 카드 번호를 하나로 만들고 card 배열의 원소들의 개수를 cardCnt배열에 저장한다. 우선, cardCnt 배열을 완성시키고 cardCnt 배열의 원소 인덱스를 나타내는 point 변수를 0으로 초기화한다. cardCnt에 1을 넣고 연속되는 동일한 card 번호가 나오는 동안 해당 cardCnt[point]++ 한다. 반복문을 빠져나오면 해당 card 번호의 개수를 다 세아린 것이므로 point++한다. erase와 unique 함수를 통해 동일한 숫자는 한개만 남긴다. 3. lt=0, rt=n-1로 카드의 존재 여..

알고리즘 자료 구조 정렬 이분 탐색 풀이 1. 가지고 있는 숫자 카드를 card 배열에 오름차순으로 정렬한다. 2. 가지고 있는지 구분하기 위해서 lt=0, rt=n-1로 카드의 존재 여부를 표시하는 변수 exist=0으로 초기화한다. 3. mid=(lt+rt)/2하여 card[mid] 값이 확인하고자 하는 숫자와 일치하면 exist 변수를 1로 하고 반복문을 탈출한다. card[mid] 값이 확인하고자 하는 숫자보다 작으면 lt=mid+1로 하여 탐색한다. card[mid] 값이 확인하고자 하는 숫자보다 크면 rt=mid-1로 하여 탐색한다. 이 과정은 lt num; card.push_back(num); } sort(card.begin(), card.end()); cin >> m; for(int i=0..

알고리즘 정렬 과정 1. sort() 함수를 이용하여 정렬 시 N은 최대 10,000,000개로 전부 저장 시 메모리가 남아나지 않는다. 2. 입력되는 수는 10,000보다 작거나 같은 자연수 이므로 배열에 count를 올려 기록 3. C와 C++의 표준 stream의 동기화를 끊어 CIN과 COUT의 속도를 높인다. 성공 코드 #include #include #include using namespace std; int main() { // freopen("input.txt", "rt", stdin); ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n, in; int input[10001]={0}; cin >> n; for(in..