생각 생각

https://acmicpc.net/problem/11444 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 도저히 내 머리로는 1000000007번째 피보나치 수열을 내가 아는 재귀나 반복의 방법으로 풀 수 있는 방법이 생각나지 않았다. 그래서 찾아보니 도가뉴 항등식이라는 피보나치 수열과 관련된 항등식이 있었다. ​ am+n=am-1an+aman-1 ​ 이 항등식을 이용해야 한다고 하는데, 여전히 어떻게 풀 지 감이 잘 오지 않아 더 찾아보니 다른 방법이 있었다. 문제 조건에도 써 있는 거듭제곱을 이용한 분할 정복이다. 요컨대 이런 말이다. ​ 2의 1000승을 구하기 위해 2를 100..

https://acmicpc.net/problem/1932 dp 문제. 모양을 착각해서 잠시 헤매고 다시 풀었다. 특별히 어려운 부분은 없었다.

https://acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 스택 문제. 차차 익숙해져 가는 중이다. 예전 풀었던 괄호 문제와 동일하지만 조금 더 머리를 써야 했던 문제. https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열..

https://acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net dp지만 메모리를 줄여보려는 발악까지 해야 했던 문제. 4MB의 제한이니, 십만 개의 열을 3행으로 배열한 리스트를 두기는 무리다. 최대, 최소 각각 3개의 메모이제이션과 3개의 입력값 자리씩 총 12개의 숫자 자리만 할당해서 풀었다.

https://acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 문제 푸는데 걸린 시간 20분, 파이썬때문에 시간 초과 걸려서 헤멘 시간 4시간이었다. C++을 공부해야겠다는 생각을 다시 한번 한다. 선언부는 늘 그랬던 것과 동일하게 받는다. bfs 함수 안에, 다시 세 개의 함수를 정의한다. 각각 가로, 세로, 대각선 파이프의 다음 경로가 벽인지 확인한다. 이제 bfs 돌면 끝이다. ​ 시간을 줄이기 위해 신경 썼던 것은 크게 두 개였다. ..

https://acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 가중치가 양수일 때 사용할 수 있는 다익스트라 알고리즘을 공부했다. 개념이 어려웠다기보단 적용이 조금 헷갈리는 부분이 많았다. 이 방법의 핵심은, heap 안에 현재 가중치와 현재 지점을 넣으며 최소 비용을 업데이트하는 것이다. s[cur_d] 안에는 cur_d에서 출발하여 도착할 수 있는 지점들이 있다. 따라서 cur_d에서 갈 수 있는 지점들을 체크해주며 그 지점까지..

https://acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 아기 상어처럼 네 달 전 풀려고 시도했던 문제였다. 분할 정복이라고 생각하니 잘 와닿지 않았었다. 그러나 백트래킹 개념을 이해하고 보니 잘 이해 되는 문제였다. 이 문제의 핵심적인 아이디어는, 검증하는 함수와 퀸을 놓는 함수 두 개를 두는 것이다. 검증하는 함수에서는 퀸을 둘 수 있는지를 알아본다. 어차피 row는 겹치지 않게 둘 것이니 column과 대각선만 확인해 주면 문제가 없다. 퀸을 두는 함수가 백트래킹의 개념..

https://acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 간단한 dp 문제. 딱 두 줄 뿐이었기에, 생각해 줄 것은 하나다. a줄과 b줄이 있을 때, a줄의 현재 위치와 b줄의 하나 전을 취하는 것. 혹은 a 줄의 하나 전을 취하는 것 중 더 큰 것을 취하면 된다.