목록책장/알고리즘 (57)
서랍장
생각보다 간단한 문제였다. N번째 큰 수를 찾아야하므로 크기가 N 초과가 되면 안되는 우선순위 큐를 선언한 다음에 하나씩 입력받다가 N 초과가 되는 경우 제일 작은 값을 뺴주어 N개를 유지시키는 식으로 쭉 입력받고 맨 마지막에 우선순위 큐에 있는 N개의 수 중에서 제일 작은 값이 N번째 큰 수가 된다. #define _CRT_SECURE_NO_WARNINGS #include #include using namespace std; priority_queue pq; int main() { int n, input; scanf("%d", &n); for (int i = 0; i n) { pq..
단순 탐색 문제인것 같다. 문자와 정수 pair 를 저장하는 vector 를 만든다. 그 후 문자열의 값을 하나씩 확인하면서 문자를 vector 에 넣되, 넣을 때 비교할 폭탄 문자열과 확인하여 같은 값이라면 몇번재 index 와 같은지를 정수로 같이 넣어준다. 이로써 폭탄이 만일 터지더라도 그 다음에 저장되어있는 정수를 확인해 계속해서 이어지는 문자가 들어올 시 폭탄이 터지도록 로직을 구현할 수 있다. 복잡도는 100만 * 36 + 36n? 정도? 라서 2초에 비해 넉넉한 복잡도를 가질 것이라 생각된다. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include #include..
#define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include using namespace std; typedef pair pii; int n, cnt = 0, a, b; priority_queue pq; vector v; int main() { int n; long double a, b; scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%Lf %Lf", &a, &b); v.push_back({ a, b }); } long double x1, y1, x2, y2, x3, y3; x1 = v[0].first; y1 = v[0].second; long d..
간단한 백트래킹을 사용한 구현 문제이다. 로직은 생각보다 간단하다. dfs 순회를 하면서 넣으려는 숫자가 행에 있는지 열에 있는지 박스에 있는지 3가지만 확인하면 된다. 이 때 각각을 전부 순회를 때리게 되면 각각 9번의 연산이 생기게 된다. 그렇게 되면 81번의 공간에 9개의 숫자를 확인하되 각각 27번의 check 연산을 하게 되어 복잡도에 큰 문제가 생기지 않는다고 판단된다. 허나 좀더 빠르게 연산하기 위해 해쉬를 두어 숫자를 체크하게 되면 메모리를 조금 더 두어 check 연산을 O(1) 만큼의 복잡도로 처리할 수 있게 된다. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #..
전형적인 세그먼트 트리 문제이다. 일단 시간 제한이 2초이기 때문에 일일이 10만개의 정수 쌍 입력에 대해 10만개의 배열에서 최솟값과 최댓값을 뒤지게 되면 복잡도가 터지게 된다. 이를 위해 미리 답들을 트리 형태로 저장해놓는 세그먼트 트리를 사용하여 복잡도를 줄일 수 있다. 값을 저장할 때마다 최솟값과 최댓값을 log(n) 의 복잡도로 저장해놓는 식이다. 그 후 정수 쌍 입력을 받을 때마다 만들어 두었던 세그먼트 트리에 query를 날리는 식으로 문제를 풀게 되면 답이 금방 나오게 된다. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include #include #include..
그리디 알고리즘 을 사용하는 문제였다. 일단 시간제한이 2초인데, 입력값이 (위치, 인구수) 쌍으로 10만개이다. 이를 일반적인 브루트포스로 풀게되면 전체 평균을 구하는 과정 중에 값의 범위 때문에 터질 수도 있다. 다만 시간으로는 안 터지지 않을까 싶다. 즉, 이 문제의 경우 그리디하게 위치를 정해주어야 하는데 그 로직은 다음과 같다. 입력받은 쌍을 위치 순으로 정렬한다. 해당 위치까지의 누적합을 배열에 저장해둔다. 그 후 이분탐색으로 왼쪽 누적합, 오른쪽 누적합의 차이가 최소인 지점을 찾는다. 생각보다 간단한 로직이다. 허나 평균을 구하는게 아닌 누적합 자체로 이분탐색을 한다는 것 자체가 생각하기 어렵기 때문에 경험이 필요한 문제라 생각한다. #define _CRT_SECURE_NO_WARNINGS ..
( "팰린드롬 "이란 뒤집어도 똑같은 수를 의미한다. ) 일단 시간 제한이 0.5초(5천만줄) 정도이고, 입력의 크기가 2000 개의 수열의 크기, 백만개의 질문의 개수이다. 이를 보아 질문마다 2000 번의 연산을 하게 된다면 문제가 바로 터진다는 걸 알 수 있다. 때문에 백만개의 질문마다 log(n) 의 연산을 하던가 아예 처음에 다 계산한 이후 O(1) 의 복잡도로 답을 내버리던가 해야 한다. 팰린드롬은 대표적인 dp 문제라고 할 수 있다. 예를 들어 1, 2, 1, 3, 1, 2, 1 위와 같이 7개의 수가 있을 때 (3, 7) 이 팰린드롬인지 확인해보자. (3,7) 은 1, 3, 1, 2, 1 로 양끝의 수가 같은 팰린드롬 같은(?) 수이다. 이 때 양끝의 수가 같으니 (3, 7) = (4, 6..
dp 를 사용하여 빠른 시간에 조합 값을 구하는 문제였다. n과 m에 따라 값을 구하기만 하면 되는데 이 때 수의 범위가 long long 을 벗어나기 떄문에 string 으로 합을 처리해주는 로직이 필요하다. 이를 위해 밑의 코드에서는 get_sum 이라는 함수에서 string을 통해 수의 합을 표현해주어 문제를 풀 수 있었다. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long LL; string dp[103][103]; string get_sum(st..
간단한 bfs 이지만 경우의 수가 매우 많은 귀찮은(?) 문제였다. 일단 시간제한은 2초 이지만 보드의 가로 세로가 최대 10 이므로 어떻게든 지지고 볶아도 시간 초과는 나지 않는 문제였다. 때문에 구현에만 정성을 쏟으면 된다. 로직은 다음과 같다. 위, 아래, 오른쪽, 왼쪽 4가지로 구분한다. 각 4가지별로 빨강이 앞에 있는 경우, 뒤에 있는 경우로 나눈다. 나눈 경우에 따라 while 문으로 벽이 나올 때까지 빨간 공과 파란 공을 움직인다. (이 때 서로 앞지르지는 못한다) 위의 1→2→3 을 반복하면 간단하게 문제가 풀린다. 이 때 시간 복잡도는 이전에 위로 움직인 경우 다음에 위로 움직이지 않게끔 하여 최대 3^10 정도가 나오게 된다. 대략 6만 정도가 나오게 되고, 각 케이스마다 1000줄씩 ..
최소 스패닝 트리 문제이다. 일단 시간제한부터 보면 2초의 제한을 가지고 있다. 그 후 입력값의 범위를 보면 100000 개 이하의 노드와 1000000(백만개) 이하의 edge 가 있는 것을 볼 수 있다. 이 문제를 크루스칼을 통해 구하게 되면 nlog(n) 의 복잡도를 가지게 되어 널널하게 통과할 수 있다. (크루스칼 → 사실상 정렬알고리즘과 union-find 알고리즘의 복잡도와 비슷하다.) 여튼 크루스칼 알고리즘으로 최소 weight 를 가지는 edge 부터 차근차근 cycle 이 있는지 확인해가며 처리해주면 쉽게 풀리는 문제이다. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #includ..