꾸준함

문제 링크입니다: https://www.acmicpc.net/problem/3045 3045번: 이중 연결 리스트 문제 창영이는 1학년 때 숙제로 했던 이중 연결 리스트 소스를 상근이에게 생일 선물로 보내주었다. 상근이는 드디어 자신이 원하던 기능이 있는 소스를 받게 되어서 매우 기뻤다. 상근이는 하�� www.acmicpc.net 블로그 방문하셨던 분이 질문주셨던 문제여서 풀어보기 시작했던 문제였습니다. 처음에는 제목만 보고 이중 연결 리스트만 구현하면 되는줄 알았는데 생각보다 많은 부분을 고려해야 풀 수 있었던 문제였습니다. 우선, 이중 연결 리스트가 어떤 식으로 삽입 삭제되는지 A 1 4 연산을 예시로 그림과 함께 설명드리겠습니다. 1. 1번 노드를 떼어내야하기 때문에 1번 노드의 다음 노드인 2번..

문제 링크입니다: https://www.acmicpc.net/problem/2957 2957번: 이진 탐색 트리 문제 이진 탐색 트리는 모든 노드가 많아야 2개의 자식 노드를 가지고 있는 트리이고, 각 노드에는 수가 하나씩 쓰여있다. 만약 어떤 노드에 쓰여 있는 수가 X라면, 그 노드의 왼쪽 서브트리에는 X보다 작은 수, 오른쪽 서브트리에는 X보다 큰 수만 저장되어 있어야 한다. 1보다 크거나 같고, N보다 작거나 같은 수 N개가 한 번씩 등장하는 수열이 입력으로 주어진다. 이 수열을 이용해서 이진 탐색 트리를 만들려고 한다. 이제 배열의 첫 번째 수를 루트 노드로 www.acmicpc.net N은 최대 300,000이고 이진 탐색 트리를 구성할 때 최악의 경우 skewed binary tree가 되기 ..

문제 링크입니다: https://www.acmicpc.net/problem/2143 N, M이 최대 1000이기 때문에 미리 시간복잡도 O(N^2)으로 모든 부분합을 전처리해주고 lower_bound, upper_bound를 이용하면 쉽게 풀 수 있는 문제였습니다. *답의 범위는 int 범위를 초과하므로 result는 long long이여야합니다. #include #include #include using namespace std; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); long long T; cin >> T; int N; cin >> N; vector A(N); for (int i = 0; i > A[i]; i..

문제 링크입니다: https://www.acmicpc.net/problem/2632 N과 M이 최대 1000이기 때문에 미리 시간복잡도 O(N^2)으로 전처리해도 무방한 문제였습니다. 알고리즘은 아래와 같습니다.1. 모든 가능한 합을 미리 v와 v2에 전처리 해줍니다.2. v[i]에 대해 lower_bound와 upper_bound를 이용하여 v2에 (pizza - v[i])가 몇개 있는지 확인하고 결과에 더해줍니다. #include #include #include using namespace std; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); int pizza; cin >> pizza; int M, N; cin >> M >> N; vecto..

문제 링크입니다: https://www.acmicpc.net/problem/3020 lower_bound와 upper_bound를 적절히 이용하면 쉽게 풀 수 있는 문제였습니다.코드를 보면 금방 이해할 수 있을 것입니다. #include #include #include using namespace std; const int INF = 987654321; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); int N, H; cin >> N >> H; vector bottom(N/2), top(N/2); for (int i = 0; i > bottom[i] >> top[i]; sort(bottom.begin(), bottom..

문제 링크입니다: https://www.acmicpc.net/problem/7453 완전탐색법을 적용하여 시간 복잡도 O(N^4)으로 풀려고 하면 절대 시간 안에 풀 수 없는 문제입니다. 알고리즘은 아래와 같습니다.1. 4개의 배열을 2개로 나눕니다. {첫 번째 배열, 두 번째 배열}, {세 번째 배열, 네 번째 배열}2. 첫 번째 배열과 두 번째 배열의 가능한 모든 합은 미리 전처리 할 필요 없고 세 번째 배열과 네 번째 배열의 모든 가능한 합만 미리 전처리해두고 오름차순으로 정렬합니다.3. 첫 번째 배열과 두 번째 배열의 모든 가능한 합을 구하고 해당 합의 부호를 바꾼 값을 갖고 있는 인덱스를 2번에서 구한 배열에서 찾아봅니다.4. 3번에서 구한 인덱스의 합과 2번에서 구한 합의 합이 0이라면 결과에..