프로그래머의 개발노트

- 접근 방법 문제를 읽고 dp와 위상정렬로 문제를 풀 것이라 생각했습니다. 위상정렬이란, 방향 그래프에서 적용되는 알고리즘으로 순서가 정해져있는 작업을 차례로 수행해야 할 때 그 순서를 결정해주기 위해 사용되는 알고리즘입니다. 문제 예시를 보면, 2번 3번 건물은 1번 건물이 지어져야 지을 수 있고, 4번 건물은 2, 3번 건물들이 각각 지어져야 지을 수 있습니다. 문제에서 입력을 받을 때 마다 각 정점의 진입 차수를 증가시켜 자신의 priority를 기록하도록 합니다. N의 크기가 작기 때문에, 순차탐색을 이용하여 진입 차수가 낮은 것들을 큐에 넣고 bfs를 돌리는 방식으로 답을 구했습니다. 1234567891011121314151617181920212223242526272829303132333435..

https://www.acmicpc.net/problem/1003 - 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다. - 출력 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. - 풀이 문제에 피보나치 함수에 대한 코드가 주어져 있는데, f(n) = f(n - 1) + f(n - 2) 위의 식을 잘 생각해보면 Base Case인 if(n == 0) return (0);else if (n == 1) return (1); 이 부분을 만날 때 까지 저 식을 타고 타고 들어간다고 생각해 보면 됩니다. n = 3 일 경우를 예시로 들어보면, f(3) = f(..

https://www.acmicpc.net/problem/9095 - 입력 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. - 출력 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. - 풀이 1,2,3 까지 구할수 있는 경우를 생각해보자. - 1 1 - 2 1+12 - 31+1+11+22+1 이제 4를 생각해보면, 3에서 구했던 값들에 1을 더하고, 2에서 구했던 값들에 2를 더하고, 1에서 구했던 값들에 3을 더하면 된다. 1+1+1+11+2+12+1+1=> dp(3)의 갯수와 동일 1+1+22+2=> dp(2)의 갯수와 동일 1+3=> dp(1)의 갯수와 동일 따라서, 점화식은 dp[n] = dp[n-1] + dp[n-2] + dp[n-3] (n >= 4)로 세울 수 있겠..

https://www.acmicpc.net/problem/1463 - 입력 첫째 줄에 1보다 크거나 같고, 10^6보다 작거나 같은 정수 N이 주어진다. - 출력 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. - 풀이 문제 조건을 보면 1. X가 3으로 나누어 떨어지면, 3으로 나눈다.2. X가 2로 나누어 떨어지면, 2로 나눈다.3. 1을 뺀다. 이렇게 3가지 조건이 있는데, dynamic programming(동적 계획법)적으로 문제를 접근해 보면, 현재 내가 조사하는 값은 현재 조하사고자 하는 인덱스를 2로 나누고 그 나머지 값의 합과 3으로 나누고 그 나머지의 합의 최솟값이라는 것을 알 수 있다. 123456789101112131415161718192021222324252627282930#in..

https://www.acmicpc.net/problem/17143 - 입력 첫째 줄에 격자판의 크기 R, C와 상어의 수 M이 주어진다. (2 ≤ R, C ≤ 100, 0 ≤ M ≤ R×C) 둘째 줄부터 M개의 줄에 상어의 정보가 주어진다. 상어의 정보는 다섯 정수 r, c, s, d, z (1 ≤ r ≤ R, 1 ≤ c ≤ C, 0 ≤ s ≤ 1000, 1 ≤ d ≤ 4, 1 ≤ z ≤ 10000) 로 이루어져 있다. (r, c)는 상어의 위치, s는 속력, d는 이동 방향, z는 크기이다. d가 1인 경우는 위, 2인 경우는 아래, 3인 경우는 오른쪽, 4인 경우는 왼쪽을 의미한다. 두 상어가 같은 크기를 갖는 경우는 없고, 하나의 칸에 둘 이상의 상어가 있는 경우는 없다. - 출력 낚시왕이 잡은 ..

https://www.acmicpc.net/problem/1348 - 입력 첫째 줄에 주차장의 세로 크기 R과 가로 크기 C가 주어진다. R과 C의 크기는 50보다 작거나 같다. 둘째 줄부터 R개의 줄에는 주차장의 정보가 주어진다. 주차장의 정보는 왼쪽에 나와있는 예와 같으며, 차의 개수와, 주차 구역의 개수는 모두 0보다 크거나 같고 100을 넘지 않는다. - 출력 첫째 줄에 모든 차가 주차하는데 걸리는 시간의 최솟값을 출력한다. 차가 없는 경우는 0을 출력한다. 만약 모든 차가 주차하는 것이 불가능하다면, -1을 출력한다. - 풀이 우선 출력 마지막 부분에서 차가 없는 경우와, 모든 차가 추자하는 것이 불가능하다는 것을 통해 전처리가 필요하다는 것을 알 수 있었습니다. 그 후에 주차장에 있는 모든 차..

https://www.acmicpc.net/problem/2585 - 입력첫 줄에는 n과 k가 하나의 공백을 사이에 두고 주어진다. 그 다음 n개의 줄에는 각 비행장 (급유지)의 정수좌표가 x y 형식으로 주어진다. - 출력 S에서 T까지 k번 이하로 중간급유 하여 갈 수 있는 항로에서의 최소 연료통 용량에 해당되는 정수를 출력한다. - 풀이 S와 T는 비행기가 무조건 지나가는 곳이라는 것을 생각하고 있어야 한다. S에서 시작 하여 갈 수 있는 곳은 사실상 모든 곳이다. 또한 모든 경유지에서 갈 수 있는 곳 또한 모든 곳이다. BFS를 통해 경유지를 몇 번 거쳤는지를 확인하고 k가 넘어간다면 해당 경유지는 가지 않는다. 이때 생각해볼 수 있는 것은, 한 경유지를 이미 들렸다면 다른 경유지에서 이미 들른 ..

https://www.acmicpc.net/problem/9202 - 문제 설명 Boggle이라는 보드 게임이 있습니다. 글자가 쓰여 있는 주사위로 이루어진 4x4 크기의 그리드에서 최대한 많은 단어를 찾는 게임입니다. 글자수 마다 점수가 주어져있습니다. 단어 사전에 등재되어 있는 단어의 목록과 Boggle 게임 보드가 주어졌을 때, 얻을 수 있는 최대 점수, 가장 긴 단어, 찾은 단어의 수를 구하는 프로그램을 작성하는 것이 목표입니다. - 입력 첫째 줄에 단어 사전에 들어있는 단어의 수 w가 주어진다. (1 < w < 300,000) 다음 w개 줄에는 단어가 주어진다. 단어는 최대 8글자이고, 알파벳 대문자로만 이루어져 있다. 단어 사전에 대한 정보가 모두 주어진 이후에는 빈 줄이 하나 주어진다. 그 ..