코딩스토리

https://www.acmicpc.net/problem/2749 2749번: 피보나치 수 3 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 본격적인 행렬 제곱 DP를 사용한 문제이다. 피보나치 수를 구하는 문제는 다이나믹 프로그래밍의 전형적인 문제 유형이다. 대부분 DP를 시작하는 사람들은 피보나치 수를 처음 접하면서 시작한다. 이 문제 역시 피보나치 수를 구하는 문제이다. 다른 점은 n 제한 하나이다. 이 문제의 n제한은 "1,000,000,000,000,000,000"이다. 이번에도 이 숫자가 내 통장잔고였으면.. 하지만 이번 건 스케일이 좀 남다르다. 내 통장잔고의 문제가 아니라 몇 년치 국가 예산보다 크지 ..

https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 행렬 제곱 DP를 공부하기 위해 먼저 이 문제를 풀어보았다. 주어진 조건 중 "1 ≤ B ≤ 100,000,000,000"을 보고 저게 내 통장 잔고였음 좋겠다... 뻘 생각 한번 해주고 시간 복잡도는 O(logN)으로 구해야겠다 싶었다. 내가 문제를 보고 생각했던 logN 풀이는 반드시 (A^2)*(A^2) = A^4를 만족해야 했다. 나는 행렬을 고등학교때 배우고 온 세대가 아니기 때문에(나름 신생아^^) ..

www.acmicpc.net/problem/1484 1484번: 다이어트 첫째 줄부터 한 줄에 하나씩 가능한 성원이의 현재 몸무게를 오름차순으로 출력한다. 가능한 몸무게가 없을 때는 -1을 출력한다. 현재 몸무게는 자연수로 떨어지지 않을 수도 있는데, 이런 경우 www.acmicpc.net 이분 탐색으로 쉽게 해결할 수 있었던 문제이다. 문제 태그에는 수학, 투 포인터가 적혀 있는데 나는 문제를 보고 이분 탐색으로 충분히 풀릴 것 같아서 제출해봤는데.. 틀렸습니다.. 잉? 하고 문제를 다시 보니 가능한 몸무게가 없을 때 -1을 출력하는 것을 까먹어버렸다ㅎㅎ 저 조건을 다시 붙여서 바로 제출하니 맞았습니다를 받을 수 있었다. 풀이 과정 일단 G의 값이 100000 보다 작은 자연수라는 조건이 가장 큰 힌트..

www.acmicpc.net/problem/2602 2602번: 돌다리 건너기 첫째 줄에는 마법의 두루마리에 적힌 문자열(R, I, N, G, S 로만 구성된)이 주어진다. 이 문자열의 길이는 최소 1, 최대 20 이다. 그 다음 줄에는 각각 와 를 나타내는 www.acmicpc.net KOALA의 이번 주 모의테스트 문제였다. 누가 봐도 DP 문제였다. 처음에 문제를 제대로 안 읽고 풀다가 시간을 많이 날렸다. 돌다리의 길이가 최대 100인데 10으로 보고 풀다가.. 내 시간ㅠㅠ 핵심은 반드시 한 번씩 마법의 두루마리에 적힌 문자열을 모두 밟아야 한다는 것이다. dp 문제의 핵심은 당연히 dp를 어떻게 정의하냐이다. 나는 dp[ i ][ j ][ k ]를 아래와 같이 정의했다. 마법의 두루마리에 적힌 ..

www.acmicpc.net/problem/16120 16120번: PPAP 첫 번째 줄에 문자열이 주어진다. 문자열은 대문자 알파벳 P와 A로만 이루어져 있으며, 문자열의 길이는 1 이상 1,000,000 이하이다. www.acmicpc.net 그리디 알고리즘이라길래 풀었다가 크게 당한 문제다.. 그리디 문제를 여러 번 풀수록 내 멍청함에 한 번 감탄하고 내가 풀이법을 떠올리는 것에 또 한 번 감탄한다. 참 신기한 알고리즘이야.. 이거 풀려고 연습장에 PPAP를 몇 번을 썼는지 모르겠다ㅋㅋ 처음에 접근을 완전히 이상하게 해서 너무 많은 시간을 버리고 결국 코드를 처음부터 다시 짰다. 먼저 정답을 받은 방법부터 설명하자면 아래와 같다. 1. 문자열의 마지막부터 시작하여 하나의 문자씩 확인한다 (딱 봐도 ..

HTTP란 Hyper Text Transfer Protocol의 약자로 클라이언트와 서버 사이의 데이터 교환에 사용되는 프로토콜이다. 클라이언트(사용자, 브라우저)가 서버에 요청하는 것을 요청(request), 요청에 대한 답으로 서버가 클라이언트에게 보내는 것을 응답(response)이라고 한다. HTTP는 어플리케이션 레이어에 속한 프로토콜이다. 웹 페이지가 우리에게 보이는 과정을 간단하게 살펴보면 웹 브라우저가 Web 페이지의 HTML 문서를 가져오기 위해 서버로 요청(request)을 보낸다. Web 페이지의 파일들을 분석하여 실행해야 할 스크립트, 하위 리소스들(이미지, 비디오 등), 레이아웃 정보 등 에 해당하는 추가적인 요청들에 대한 응답(response)을 서버로부터 받는다. 브라우저는 완..

www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 코드포스 만년 초록 따리를 벗어나기 위해 그리디 문제를 많이 풀어봐야겠다고 마음먹었다. 이 문제의 풀이는 다음과 같다. 1. 모든 단어에서 각 문자가 얼마만큼의 계수를 갖는지를 구하기 ex) AB이면 10A + B, 즉 A = 10, B = 1을 저장 2. 계수가 큰 알파벳 순으로 정렬 (어차피 전체 단어의 합이기 때문에 계수가 크면 큰 수를 할당해야 한다.) 3. 정렬된 알파벳에 9부터 순서대로 할당하여..

www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 연구소 문제는 매우 유명한? 문제이기 때문에 한번 풀어보았다. 문제를 읽어보면 알겠지만 연구소 1과 비슷하게 백트래킹과 bfs를 사용하여 해결하면 될 것 같았다. 가장 걱정되었던 것은 시간제한이 0.25초인 거였지만 아무리 봐도 다른 풀이가 떠오르지 않아서 생각한 대로 구현해보았다. 풀이과정은 다음과 같았다. 1) 바이러스를 놓을 수 있는 모든 위치를 찾아놓음(최대 10개) 2) 모든 경우를 계산함 3) 이때 각 위치에..