목록책장/알고리즘 (57)
서랍장
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..
11000번: 강의실 배정 그리디 "활동 선택 문제" 방식의 문제이다. 먼저 시간복잡도부터 살펴보면 1초의 제한시간에 input 의 길이가 20만이다. 따라서 제곱의 복잡도를 가지게 되면 터진다는 걸 알 수 있다. 이 점에 착안해 각 프로세스를 돌면서 log(n) 의 탐색 복잡도 로직으로 같이 이어서 들을 강의를 체킹하여 문제를 풀기로 하였다. 로직은 다음과 같다. 각 프로세스를 "시간 순 → 짧게 끝나는 순" 으로 정렬한다. 정렬한 프로세스를 하나씩 돌면서 나머지 프로세스 중 바로 시작할 수 있는 프로세스를 이분탐색을 통해 찾는다. (반복) 찾은 프로세스들을 모두 checking 해주고 다시 2번으로 돌아간다. 이에 대한 코드는 다음과 같다. #define _CRT_SECURE_NO_WARNINGS #..
#include #include #include using namespace std; string solution(string number, int k) { string answer = ""; int window_size = number.size() - k; int max_idx = -1; char max_val; for(int i=0 ; i< window_size ; i++) { max_val = '0'; for(int j = max_idx + 1 ; j
1028번: 다이아몬드 광산 dp 문제였다. dp 배열에 문자열을 넣고 drop up 방식으로 단순하게 탐색하는 식으로 문제를 풀 수 있었다. 로직은 다음과 같다. dp[1] 부터 차례대로 값을 비교하되 하나의 dp 마다 n개의 수를 넣기 전의 dp 값과 비교하여 해당 수를 추가한 뒤 값이 더 큰 값을 dp 값으로 갱신하는 로직. 말이 좀 어려울 수 있겠지만 dp[i - (수의값)] 에서 해당 수를 첨가하여 커지나 안커지나만 확인하면 되는 문제였다. dp 라 푸는데 좀 오래 걸렸지만.. 다음에는 더 잘 기억하자 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include #incl..
15684번: 사다리 조작 이거는 약간 구현에 신경써야 하는 문제이다. 여러번 풀어보는 것도 나쁘지 않다고 생각한다. 일단 하나씩 다 돌아보는 단순한 브루트포스 알고리즘으로 풀리는 문제이다. 다만 각 가로줄들을 데이터로 잘 표현하여 탐색을 돌리는 구현이 깔끔하게끔 짜야하는 문제가 있다. 각 가로줄을 일일이 저장하는 것이 아닌 특정 점에서 밑으로 내려올 수 있다 없다 로 가로줄을 판단할 수 있다. 예를 들어 check[3][4]=1 이라면 (3,4) 에서 사다리 밑으로 내려올 수 있다는 의미가 될 수 있다. 이를 이용해 check[x][y], check[x][y-1], check[x][y+1] 이 3개의 값을 비교하여 1인 경우 dfs 탐색을 돌리는 식으로 로직을 구성하면 문제를 풀 수 있다. #defin..
2805번: 나무 자르기 간단한 이분탐색 문제이다. 최대값을 right로 0을 left 로 설정한 후 calc 함수만 짠뒤 간단히 이분탐색을 돌리면 풀리는 간단한 문제이다. 다만 값의 범위가 int 값의 범위를 넘어가기 때문에 이를 long long 으로 변환해주어 적절하게 풀면 간단히 풀린다. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include #include #include using namespace std; typedef pair pii; typedef tuple tii; typedef long long LL; LL n, m; LL arr[1000001]; LL c..