꾸준함

문제 링크입니다: https://www.acmicpc.net/problem/2003 투 포인터 알고리즘을 적용하면 쉽게 풀 수 있는 문제였습니다.시간 제한이 0.5초이기 때문에 O(N^2)으로 풀면 안되고 low와 high를 적절히 선정하여 O(N^2)보다 빠르게 풀어야합니다. 알고리즘은 아래와 같습니다.1. low가 high 이하이고 high가 N 미만일 때 아래와 같은 상황을 계속 확인해줍니다.i)구간 합이 M보다 작다면 high를 하나 더 오른쪽으로 가고 해당 숫자도 구간 합에 더해줍니다.ii)구간 합이 M과 같다면 경우의 수를 늘려주고 high를 하나 더 오른쪽으로 가고 해당 숫자도 구간 합에 더해줍니다.iii)구간 합이 M보다 크다면 low를 하나 더 오른쪽으로 가주고 low 위치에 있던 숫자를..

문제 링크입니다: https://www.acmicpc.net/problem/9576 이분매칭으로 푼 사람들이 더 많지만 저는 그리디하게 접근해서 풀었습니다.b를 기준으로 오름차순 정렬을 한 상태에서 책을 나눠주면 풀리는 문제였습니다.그리디 문제들은 사실 그리디하게 풀 수 있는 근거가 있어야하지만 왜 이렇게 풀어야하는지는 증명하지 못하겠습니다.혹시 이렇게 풀어도 되는 이유를 아신다면 댓글 남겨주신다면 정말 감사하겠습니다. #include #include #include #include using namespace std; const int MAX = 1000 + 1; bool visited[MAX]; bool cmp(pair a, pair b) { if (!(a.second == b.second)) ret..

문제 링크입니다: https://www.acmicpc.net/problem/2831 N이 최대 100,000이기 때문에 O(NlogN)으로 풀어야하는 문제였습니다.저는 우선순위 큐를 이용해 풀었습니다. 알고리즘은 아래와 같습니다.1. 음수로 주어진 남성과 양수로 주어진 남성, 음수로 주어진 여성과 양수로 주어진 여성을 각각 다른 최소 우선순위 큐에 넣었습니다.2. 1번을 완료하고 음수로 주어진 남성과 양수로 주어진 여성을 그리고 양수로 주어진 남성과 음수로 주어진 여성을 짝을 맺게 했습니다.3. 2번의 전자 같은 경우 현재 남성과 짝을 맺을 수 있을 때까지 여성만 pop을 했고 짝이 맺어지면 그제서야 남성도 pop을 했습니다.(그리디하게 접근)4. 2번의 후자 같은 경우 현재 여성과 짝을 맺을 수 있을 ..

문제 링크입니다: https://www.acmicpc.net/problem/2828 쉬운 그리디 문제였습니다.바구니의 범위 내에 사과가 있는지 확인하고 없으면 왼쪽으로 움직일지 오른쪽으로 움직일지 판별하면 되는 문제였습니다. #include using namespace std; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); int N, M; cin >> N >> M; int J; cin >> J; int idx = 1; int result = 0; for (int i = 0; i > num; while (1) { bool flag = false; //범위 내에 사과가 있는지 확인 for(int j=i..

문제 링크입니다: https://www.acmicpc.net/problem/11333 규칙을 찾아서 재귀함수로 해결하고 싶었지만 역량이 부족했습니다.결국 stackoverflow(https://stackoverflow.com/questions/22191801/given-an-integer-n-in-how-many-ways-can-we-tile-a-4-x-n-rectangle-with-3-x-1-ti)에서 점화식을 참고하여 풀 수 있었습니다. *이런 문제는 규칙을 찾아서 점화식 세우는 것 밖에 답이 없는지 궁금합니다. #include using namespace std; const int MAX = 10000; const long long MOD = 1000000007; long long cache[MAX..

문제 링크입니다: https://www.acmicpc.net/problem/11058 CtrlA + CtrlC + CtrlV를 한 뒤에는 복사한 문자열을 다시 붙여넣을 때 (CtrlA + CtrlC)를 누를 필요없이 CtrlV만 눌러도 된다는 부분만 이해했다면 쉽게 풀 수 있는 문제였습니다. #include #include #include using namespace std; const int MAX = 100 + 1; int N; long long cache[MAX]; long long func(int idx) { long long &result = cache[idx]; if (result != -1) return result; result = 1 + func(idx - 1); //A 추가 //Ctrl..

문제 링크입니다: https://www.acmicpc.net/problem/2568 백준 2565번 전깃줄(https://jaimemin.tistory.com/1094)의 연장선 문제였습니다. 알고리즘은 아래와 같습니다.1. 연결한 줄을 입력받고 A 전봇대 인덱스를 모두 visited 배열에 표시합니다.2. LIS 함수를 통해 가장 긴 부분 증가 수열의 길이를 구합니다.-> answer 배열에 {인덱스, 연결된 B 전봇대 인덱스} 표시해줍니다.3. N - (2번에서 구한 길이)를 출력해줍니다.4. 각 인덱스에 위치한 A 전봇대 인덱스를 구하고 해당 인덱스는 연결이 되어있는 상태이므로 visited 배열에서 빼줍니다.5. 4번까지 완료하면 visited 배열에 표시되어있는 인덱스는 초기에는 연결했지만 LI..

문제 링크입니다: https://www.acmicpc.net/problem/14002 가장 긴 증가하는 부분 수열 5(https://jaimemin.tistory.com/1095)와 동일한 문제였습니다. #include #include #include using namespace std; const int MAX = 1000 + 1; int N; int arr[MAX]; int cache[MAX]; pair answer[MAX]; stack s; int LIS(void) { int idx = 0; cache[idx] = arr[0]; answer[0] = { 0, arr[0] }; for (int i = 1; i < N; i++) { if (cache[idx] < arr[i]) { cache[++idx]..

문제 링크입니다: https://www.acmicpc.net/problem/14003 Crocus님(https://www.crocus.co.kr/681) 덕분에 풀 수 있었던 문제였습니다.O(NlogN)에 LIS의 최대 길이를 구하는 알고리즘을 통해서는 정확한 LIS 배열을 구할 수 없다는 것을 처음 알았습니다. 기존의 LIS 코드는 동일하고 pair answer 배열과 스택을 이용해 정확한 LIS 배열을 구하는 것은 코드의 주석을 보면 이해가 될 것입니다! #include #include #include using namespace std; const int MAX = 1000000 + 1; int N; int arr[MAX]; int cache[MAX]; pair answer[MAX]; stack s..

문제 링크입니다: https://www.acmicpc.net/problem/2565 백준 2352번 반도체 설계(https://jaimemin.tistory.com/488)와 유사한 문제였습니다. #include #include using namespace std; const int MAX = 500 + 1; int N; pair connect[MAX]; int cache[MAX]; int LIS(void) { int idx = 0; int length = 0; cache[idx] = connect[0].second; for(int i=1; i> N; for (int i = 0; i > connect[i].first >> connect[i].second; sort(connect..