Doby's Lab

https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net Level: Silver II Solved By: Stack 이미 기존에 버린 값을 찾는 것은 'NO'를 출력해야 하기 때문에 pop을 통해 버린 값이라면, visited를 통해 체크를 해줍니다. 핵심 아이디어는 이전 값과 지금 값을 비교하면서 2가지로 나누어지는 케이스에 대해 조건을 잘 걸어주면 됩니다. 이전 값(..

https://www.acmicpc.net/problem/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net Level: Silver III Solved By: Deque 📄 Deque 양방향에서 push와 pop이 가능하도록 해야 합니다. 즉, 덱(Deque)을 사용하기 위해 파이썬에서는 아래와 같이 불러와줍니다. from collections import deque 파이썬의 deque은 아래와 같이 사용 가능하며, 인덱싱이 가능하다는 것을 인지하고 있으면 좋습니다. 인덱싱이 가능할 거면 list를..

https://www.acmicpc.net/problem/1051 1051번: 숫자 정사각형 N×M크기의 직사각형이 있다. 각 칸에는 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 www.acmicpc.net Level: Silver III Solved By: Brute-Force 구할 수 있는 제일 큰 정사각형의 사이즈를 알아냅니다. -> \(size = min(n,m)\) 이 사이즈부터 시작하여 사이즈에 해당하며, 원소 값이 모두 동일한 정사각형이 있는지 Brute-Force 하게 탐색합니다. 정사각형이 있을 때까지 2번 과정을 사이즈를 한 칸씩 줄여가면서 탐색합니다. 만약에 있다고 판단이 되면, ..

https://www.acmicpc.net/problem/1026 1026번: 보물 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거 www.acmicpc.net Level: Silver IV Solved By: Implementation 문제에서 등차수열이라 나오지는 않았었지만, A, B 둘 다 1부터 1씩 증가하는 등차수열이라 가정하고 풀이에 접근했습니다. A, B가 둘 다 증가하는 수열일 경우 A는 증가하는 수열, B는 감소하는 수열일 경우 1번 경우에는 \( 1^2+2^2+...+n^2 \)로 풀이되어 이는 \( \sum_{k=1}^{n}k^..

https://www.acmicpc.net/problem/1551 1551번: 수열의 변화 첫째 줄에 수열의 크기 N과 K가 주어진다. N은 20보다 작거나 같은 자연수이고, K는 0보다 크거나 같고, N-1보다 작거나 같은 정수이다. 둘째 줄에는 수열이 ‘,’로 구분되어 주어진다. 수열을 이루 www.acmicpc.net Level: Bronze I Solved By: Implementation 하나의 배열은 입력받을 배열 li, 다른 하나의 배열은 B[i] = A[i+1] - A[i]를 담을 배열 li_2를 선언하여 과정을 k번 반복하며 li를 li_2로 덮어감으로써 최신화시키는 코드를 작성하였습니다. 문제점은 쉽게 파악할 수 있으나, Ternary Operator를 사용함으로써 출력부에서 마지막 인..

https://www.acmicpc.net/problem/1788 1788번: 피보나치 수의 확장 첫째 줄에 F(n)이 양수이면 1, 0이면 0, 음수이면 -1을 출력한다. 둘째 줄에는 F(n)의 절댓값을 출력한다. 이 수가 충분히 커질 수 있으므로, 절댓값을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net Level: Silver III Solved By: DP 음수에 관한 피보나치는 기존의 피보나치를 수정하여 간단하게 만들 수 있습니다. 또한, 이를 구하기 위한 DP를 사용하여 풀 수 있었습니다. 저는 양수 피보나치, 음수 피보나치를 따로 배열을 선언하여 문제를 풀었습니다. #include #include #define MAX 1000001 #define MOD 10..

https://www.acmicpc.net/problem/11909 11909번: 배열 탈출 상수는 2차원 배열 A[1..n][1..n] (n≥2, n은 자연수)을 가지고 있습니다. 이 배열의 각 원소는 1 이상 222 이하의 정수입니다. 배열을 가지고 놀던 상수를 본 승현이는, 질투심이 불타올라 상수를 A[1][1] www.acmicpc.net Level: Gold V Solved By: DP 처음에는 Dijkstra로 풀려고 했었습니다. pair 같은 복잡한 자료형을 만들어서 구현했는데 메모리 초과로 다른 키워드를 생각해내야 했습니다. DP 태그가 달려있어서 DP로도 구현할 수 있겠다 싶었습니다. 제가 생각한 아이디어와 관계식은 아래와 같습니다 \(cache\)는 해당 원소로 갔을 때, 최단 경로 값..

https://www.acmicpc.net/problem/1124 1124번: 언더프라임 자연수 X를 소인수분해하면, 곱해서 X가 되는 소수의 목록을 얻을 수 있다. 예를 들어, 12 = 2 × 2 × 3이다. 1은 소수가 아니다. 어떤 수 X를 소인수분해 해서 구한 소수의 목록의 길이가 소수이면, www.acmicpc.net Level: Silver I Solved By: Miller Rabin, Pollard's Rho 소인수분해를 하는 알고리즘이라면 예전에 공부했었던 Pollard's Rho 알고리즘이 기억나서 코드를 가져와서 소인수 분해를 가능하게 했습니다. factors vector의 사이즈를 Miller Rabin에 물려서 소수로 판별이 난다면 res 값을 더해주는 식으로 답을 구했습니다. #..