프로그래머의 개발노트

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글자이고, 알파벳 대문자로만 이루어져 있다. 단어 사전에 대한 정보가 모두 주어진 이후에는 빈 줄이 하나 주어진다. 그 ..

https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net (맨 밑에 수정본이 있습니다. 끝까지 읽어주시면 감사드리겠습니다 👍👍 (수정 : 2021-02-09)) 후.. 이 문제를 풀고 내가 많이 부족하다고 느꼈다. 자료구조 트리로 다시 풀고, dfs도 정의도 확실히 공부할 것이다. 또한 if else문으로써 자료형이나 초기화된 값을 사용하는 것이 올바른 방법인지에 대한 고민을 하고, 만약 올바르다고 판단될 경우 나만의 방법을 확립할 예정이다. 1 ..