www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net kau-algorithm.tistory.com/49 [모의 테스트 풀이] RGB거리 www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다.. kau-algorithm.tistory.com R..
전체 글
항공대 알고리즘 동아리 Koala 🥰
www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net if a 20, then w(a, b, c) returns: w(20, 20, 20) if a < b and b < c, then w(a, b, c) returns: w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c) otherwise it returns: w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1) 위와 같은 재..
https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net TOP-DOWN 방식을 이용하는 DP 문제이며, DP 배열에 자기 자신의 상태를 저장한다. 삼각형의 맨 위 꼭지점부터 아래로 내려올때 각 지점에서 최대값을 저장하며 마지막까지 내려간다. 마지막에 도달하면 그 중에서 최대값을 골라내면 된다. 그림에 나타낸것과 똑같이 1,2~N-1,N 의 세가지 경우에 대해 점화식을 세워서 해결하였다. N번째의 첫번째 원소의 경우, dp[n][0] = dp[n - 1][0] + 자기자신의 값 N번째의 2~N-1번째 원소의 경우, dp[n]..
www.youtube.com/watch?v=8hGnFEw3D-c&t=3s&ab_channel=%EC%A0%84%EC%A4%80%ED%9C%98 C는 매우 빠르고 익숙한 언어지만 지원하는 기능이 부족해 알고리즘을 풀기에는 부적절합니다. 알고리즘을 풀때는 C++을 많이 사용하는데요, 이 언어가 어색하신 분들을 위한 간단한 설명 영상입니다. +추가 kau-algorithm.tistory.com/72 [C++] sort 함수 내림차순, 내맘대로 정렬 (+DNA, 2017 아주대학교 프로그래밍 경시대회 (Large) 풀이) 알고리즘 헤더파일에는 배열의 정렬을 쉽게 처리해주기 위한 sort가 내장되어 있습니다. 오름차순 정렬, 내림차순 정렬과 Pair가 있을 때 내맘대로 정렬하는 법을 살펴보겠습니다. 1. 오름차순..
youtu.be/3p6sW_v61Hs
youtu.be/rHJyQaYI9nQ youtu.be/cuxzMqkLPRg
https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 문제 n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다. 예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다. 입력 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지..
www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오. 덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다. 입력 첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다. 출력 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. 접근 DP(Dynamic programming) dp[n][k] = 정수 n을 n보다 작거나 같은 k개의 정수로 만들 수 있는 경우의 수 더보기..
www.acmicpc.net/problem/10826 10826번: 피보나치 수 4 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 피보나치 수의 범위가 long long 범위를 초과하므로, string을 이용하여 풀어야합니다. 점화식 dp[i] = dp[i-1] + dp[i-2] string 덧셈 길이가 짧은 문자열 앞쪽에 '0'을 추가하여 두 문자열의 길이를 같게 만들어 준 뒤 덧셈연산을 수행하였고 10이상이면 carry를 하나 늘리고 다음자릿수 계산에서 carry가 있으면 1더해주도록 했습니다. ..
www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 동적 계획법을 통해 풀 수 있는 문제입니다. 하나의 스티커를 떼면, 맞닿아있는 3개의 스티커는 뗄 수 없게 됩니다. 이 조건을 지키면서 각 칸마다 얻을 수 있는 최대값을 구해봅시다. 1번 열은 그대로입니다. 2번 열의 10점 스티커가 얻을 수 있는 최대 점수는 10+30점, 2번 열의 50점 스티커가 얻을 수 있는 최대 점수는 50+50점입니다. 따라서 스티커를 선택했을 때 얻을 수 있는 최대 점수로..
www.acmicpc.net/problem/5582 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 이 문제는 동적 계획법을 2차원 배열에 적용하여 풀 수 있습니다. 두 문자열을 각각 A와 B라고 할 때, 2차원 배열의 가로는 문자열 A, 세로는 문자열 B로 지정하고, 인덱스 마다 해당 지점까지 존재할 수 있는 가장 긴 부분 문자열의 길이를 저장하면 됩니다. 해당 지점 (X, Y). A문자열의 X까지, B문자열의 Y까지 등장할 수 있는 공통 부분 문자열의 길이는 A의 X - 1까지, B의 Y - 1..