노랑꼬리의 개발 블로그

문제링크 : https://www.acmicpc.net/problem/26073 26073번: 외로운 곰곰이는 친구가 있어요 첫 번째 줄에 친구의 수 $N\ (1 \le N \le 10\,000)$이 주어집니다. 이후 $N$개의 친구 정보가 각각 두 줄에 걸쳐 주어집니다. $i$번째 친구 정보의 첫 번째 줄에는 친구의 처음 위치 $X_i$, $Y_i\ (-100\,000 \le X www.acmicpc.net 작성코드 해설 1) 좌표에 도달하기 위한 시간 제한 같은것은 없기 때문에 얼마나 오랫동안 헤매던 상관없이 도달만 하면 된다. 즉, 좌표이동 값의 최소단위를 알면 도달 가능 여부를 알 수 있다. (Ex. 이동 가능 거리가 9999와 9998이 있다면 오른쪽으로 9999 이동 후 왼쪽으로 9998을 이..

문제링크 : https://www.acmicpc.net/problem/26072 26072번: 곰곰이와 시소 첫번째 줄에 정수 $N$과 $L$이 공백을 사이에 두고 주어진다. $(1 \le N, L \le 100\,000)$ 두번째 줄에 정수 $x_1, x_2, \cdots, x_N$이 공백을 사이에 두고 주어진다. $(0 \le x_i \le L)$ 세번째 줄에 정수 $w_1, w_2, \c www.acmicpc.net 작성코드 풀이 1) 문제 노트에 있는 공식을 활용해서 풀어야한다. WL은 왼쪽에 있는 치킨들의 값 WR은 오른쪽에 있는 치킨들의 값으로 생각하면 된다. Σ 는 숫자의 합이므로 Σ(1~N)이라면 1~N 까지의 합이다 2) 시그마 공식을 그대로 써서 계산하면 바로 나오겠지만 이해하기 쉽도록..

문제링크 : https://www.acmicpc.net/problem/26071 26071번: 오락실에 간 총총이 모든 곰곰이를 하나의 칸에 모으기 위해, 총총이가 최소 몇 번 버튼을 눌러야 하는지 구하시오. www.acmicpc.net 작성코드 풀이 1) G(곰곰이)가 한 곳에 모이기 위해서는 한 변에 도달해야 겹쳐지기 시작한다. 이렇게 모을 경우 모든 G를 모으기 위해 4가지 경우의 수가 존재한다. - G가 하나 : 움직일 필요 없음 - G가 가로 한줄 : 가로 변에서 합침 - G가 세로 한줄 : 세로 변에서 합침 - G가 가로 세로 흩어짐 : 모서리로 이동 2) 이를 코드로 바꿔 해결하려면 우선 G의 위치를 찾아야한다. 입력 받을 때 바로 처리를 해주는 방식으로 작성했다. 3) G가 존재하는 위치의..

문제링크 : https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 작성코드 풀이 1) 꼭대기부터 내려가면서 최댓값을 찾아야하는 문제이다. 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 2) 내려가면서 해당 위치에 도달할 수 있는 최대값을 dp에 저장해주어 재활용 해준다. ※ 알아보기 쉽도록 dp 배치를 1번 입력과 동일한 형식으로 만들어주었다. 3) 가로줄에서 2차배열의 0과 세로줄과 같은 숫자의 경우는 선택지가 하나로 고정되어있다. dp[h][0] = dp[h-1][0] dp[h][h] = dp[h-1][h-1]..

문제링크 : https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 작성코드 풀이 1) dp 배열에 이전 연속된 수들의 합을 저장해주어 다음 연산에 사용한다. 2) 만약 이전 연속된 수들의 합이 음수가 된다면 합할 시 오히려 손해가 되므로 음수인 경우 현재 수를 dp에 저장해준다. 3) dp에 미리 0으로 채워둔 수가 연속값의 최대를 구할 때 영향을 주므로 새로운 배열에 저장값들을 옮겨준다

문제링크 : https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 작성코드 풀이 1) 규칙 찾기 도형의 접하지 않는 건너편 2개의 큰 삼각형 변 길이 합이 이번 삼각형의 변 길이가 됨을 찾을 수 있다. P = [1, 1, 1, 2, 2, 3, 4, 5, 7 ,9, 12] 수열로서 찾아도 확인이 가능하다. 수식으로 보자면 P[N] = P[N-2] + P[N-3]의 값이 나오는 것을 찾을 수 있다. 2) 구현하기 찾은 규칙에 따라 리스트에 저장해 주는데 테스..

문제링크 : https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 작성코드 풀이 1) 기본 구현 방식 단순하게 i에서 j까지 리스트의 값들을 sum에 계속 저장해주는 방식이다. 하지만 이렇게 작성하면 시간 복잡도가 O(N*M)으로서 숫자가 커지게 되면 시간초과가 나오게 된다. 기본 방식으로 일정 구간 합을 구할 경우 10의 길이를 가진 arr 배열을 예시로 비교해보겠다. arr = [0, 1, 2, 3, 4, 5, 6, 7, ..

문제링크:https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 작성코드 풀이 2차원 dp 문제이다. 우선 문제를 분석해보면 이전 집과의 색이 동일하면 안되는 규칙을 가지고 가장 작은 비용으로 집을 칠해야한다. 즉, 이전 집의 색과 다른 두 색 중 작은 값이 채택된다. 이게 계속 반복되는데 dp 방식으로 저장해줄 값은 해당 색을 선택했을때 이전까지 최소 도달 값 + 현재값이 된다. 이를 코드로 구현하면 이와 같이 나온다. for문..

문제링크: https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 작성코드 풀이 규칙을 알아보기 위해 우선 4까지 직접 작성해보자. # dp[N] dp[1] = 1 dp[2] = 00, 11 dp[3] = 001, 111, 100 dp[4] = 0011, 1111, 1001, 0000, 1100 일부러 규칙이 보이는 순서로 dp[4]를 작성하였다. 기존의 수열에서 다른 수를 뒤에 붙혀주면 서로 다름을 유지하면서 새로운 수가 완벽하게 생성된다. 1을 추가하는..

문제링크:https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 작성코드 풀이 우선 문제의 의사 코드를 재귀함수로 풀어보았다. 주어진 의사코드를 바로 python으로 작성하면 위와 같이 나온다. 하지만 이와 같은 방식은 같은 w(a,b,c) 값이 나오더라도 저장을 하지 않고 매번 새로 계산 하므로서 계산 부하가 심하다 DP(동적 프로그래밍, dynamic programming) 최적화 기법으로서 하나의 문제를 작은 여러개의 문제로 분할한 뒤 작은 문제의 ..