목록전체 글 (95)
서랍장
그리디 알고리즘 을 사용하는 문제였다. 일단 시간제한이 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..
1021번: 회전하는 큐 단순한 구현문제이다. 시간제한은 2초임에 불구하고 입력값의 크기가 50이므로 n^2 의 복잡도를 가질 시 2500 밖에 걸리지 않아 매우 널널한 문제이다. index 를 가지고 0일때 왼쪽으로 돌리면 다시 오른쪽 끝으로, 반대로 n일 때 오른쪽으로 돌리면 0으로.. 의 로직을 기준으로 코드를 짜면 끝나는 코드이다. 밑의 코드는 단순 무지성으로 코드만 짠거긴 한데 중간중간 왼쪽으로 돌릴지, 오른쪽으로 돌릴지에 대해 그리디 방식으로 구하게 되면 코드가 더 깔끔하게 나오게 된다. #define _CRT_SECURE_NO_WARNINGS #include #include using namespace std; int num[100]; int check[100]; int arr[100]; i..
2346번: 풍선 터뜨리기 풍선을 터뜨리고 각 index 별로 터지는 순서를 적어야하는 줄 알고 삽질한 문제이다. 일단 시간제한이 2초에 입력값의 범위가 1000까지라 n^2 의 복잡도로는 널널하게 패스하기 때문에 넉넉잡아 풀어도 상관 없을거라고 생각한다. 로직은 단순하게 index 를 돌려가면서 0이 되었을 때, n-1 이 되었을 때 나누어서 풀면 된다. 코드는 다음과 같다. #define _CRT_SECURE_NO_WARNINGS #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n, input; deque dq; cin >> n; fo..
1629번: 곱셈 시간복잡도를 먼저 봐야하는 문제이다. 0.5초의 시간제한에 2147483647 이하의 입력값에 직접 모든 계산을 돌린다면 엄청난 차이로 시간이 터지게 된다. 때문에 log(n) 이하의 알고리즘을 생각해야 한다. log 를 보자마자 절반으로 나눠볼까? 라는 생각을 한 뒤 분할하여 값을 구하면 되지 않을까 생각이 든다. 즉 다음과 같은 로직으로 코드를 짤 수 있다. 제곱수를 절반으로 쪼개 분할정복 틀 만든 뒤 return (?!) 생각보다 간단하게 끝난다. 다만 계산 중간 곱한 뒤 나누는 과정에서 int 의 범위를 벗어날 수 있기 때문에 long long 으로 처리해주어야 한다. #include using namespace std; typedef long long LL LL _get(LL ..
1918번: 후위 표기식 경우의 수 나눠서 처리하면 된다. 입력받은 string 을 돌면서 숫자인 경우 answer 에 push 연산자인 경우 +, - 인 경우 이미 들어있는게 *, / 인 경우: 우선 순위가 높은 *, / 를 stack 에서 뺀 후 answer 에 push → 그리고 기존 거 stack 에 push 이미 들어있는게 +, - 인 경우: 먼저 들어있는 +, - 를 stack 에서 뺀 후 answer 에 push → 그리고 기존 거 stack 에 push *, / 인 경우 이미 들어있는게 *, / 인 경우: 먼저 들어있는 *, / 를 stack 에서 뺀 후 answer 에 push → 그리고 기존 거 stack 에 push 이미 들어있는게 +, - 인 경우: 기존의 *, / 가 우선순위 높으..
https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net union_find 이거 하나만 알면 풀 수 있는 문제이지 않을까 한다. 시간복잡도에 대해 알아보면 1초의 시간 제한이 있고, 입력된 선분 정보의 개수가 100만개이므로 최소 nlog(n) 의 시간복잡도로 풀어야 통과가 되는 문제이다. 이에 따라 바로 로직을 알아보면 다음과 같다. 입력받은 n 만큼 root 배열을 초기화 시켜준다. 하나씩 입력 받을 때마다 root 배열을 통해 set_uni..