열이의 개발블로그

https://www.acmicpc.net/problem/2295 2295번: 세 수의 합 우리가 x번째 수, y번째 수, z번째 수를 더해서 k번째 수를 만들었다라고 하자. 위의 예제에서 2+3+5=10의 경우는 x, y, z, k가 차례로 1, 2, 3, 4가 되며, 최적해의 경우는 2, 3, 4, 5가 된다. k번째 수가 최 www.acmicpc.net 문제 분석 중복이 가능한 세 수를 골라 집합에 있는 수를 만들면 된다. N이 1000까지 가능하기 때문에 삼중 for문을 사용하여 세 수를 각각 골라 계산한다면 시간복잡도가 O(N**3)이 될 것이다. 큰 시간복잡도를 가지므로 다른 방법을 생각해보자. 우선 탐색을 위한 하나의 수(k번째 수)를 정한다. 이 수는 세가지 수의 합을 의미하는 수이다. 그..

https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 문제 분석 문제는 A를 B번 곱한 수를 C로 나눈 나머지를 구하는 것이다. 하지만 10의 11 제곱만 하더라도 수가 엄청 커지고 A, B, C의 범위가 상당히 큰 수이므로 직접 제곱수를 구해서 계산할 수 없다. 이 때는 분할 정복을 통한 제곱수를 구하는 방식을 사용한다. 위와 같은 식으로 제곱수를 쪼갤 수 있다. 이를 재귀 함수로 작성하여 B가 1이 될 때까지 계산하여 제곱수를 분할해 계산한다. 제곱수를 분할했다면 나머지를 구해야 한다. 나머지의 경우는 모듈러 ..

https://www.acmicpc.net/problem/9996 9996번: 한국이 그리울 땐 서버에 접속하지 총 N개의 줄에 걸쳐서, 입력으로 주어진 i번째 파일 이름이 패턴과 일치하면 "DA", 일치하지 않으면 "NE"를 출력한다. 참고로, "DA"는 크로아티어어로 "YES"를, "NE"는 "NO"를 의미한다. www.acmicpc.net 문제 분석 패턴과 파일 이름의 일치 여부를 판단하여 "DA", "NE"를 출력하는 문제이다. 패턴은 "a*d"와 같이 문자열과 별표로 이루어져 있고 별표는 하나, 문자열의 길이는 100을 넘지 않는다. 즉, 패턴은 "abc*abc"와 같이 별표의 앞뒤로 총 길이가 100을 넘지 않는 길이를 가진 문자열이 오게 된다. 별표에는 공백, 한 문자, 문자열 등 있거나 없..

https://www.acmicpc.net/problem/1402 1402번: 아무래도이문제는A번난이도인것같다 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 100)이 주어진다. 테스트 케이스마다 두 정수 A, B(-231 ≤ A, B ≤ 231-1)가 주어진다. www.acmicpc.net 문제 분석 처음 문제를 읽었을 때는 경우의 수가 엄청 많다고 생각했다. 일단 소인수분해를 해서 합이 되는 경우를 모두 계산해서 저장해두어야 하나? 입력 범위가 크니 작은 수부터 경우를 구해서 DP를 이용해야 하나? 근데 음수는 어떻게 판단하지? 많은 고민들이 있었던 것 같다. 하지만 정말 어이없게도 문제는 너무 간단했다.. A = a1 * a2 * a3 * ... * an으로 했을 때 A' = a1 + a2 +..

https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 문제 분석 각 집의 색은 이전, 이후의 집과 색이 달라야 한다. 집의 색이 정해진다면 비용을 누적하여 가장 작은 비용을 출력하면 된다. 기준이 없으므로 1번 집부터 색을 칠한다고 가정했을 때, 1번 집의 색이 빨강이라면 2번 집은 초록과 파랑 중 골라야하고 N번 집도 초록과 파랑 중 골라야 한다. 1149번: RGB거리 문제 위의 문제의 경우는 자기 자신의 바로 다음 ..

https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 문제 분석 팰린드롬(palindrome)이란? 팰린드롬[나무위키] 회문 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 회문(回文) 또는 팰린드롬(palindrome)은 거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말, 숫자, 문자열(sequence of characters) 등이다. 보통 낱말 사이에 있는 띄 ko.wikipedia.org 문제는 N개의 자연수 중 S번째 수부터 E번째까지의 수가 팰린드롬인지 ..

https://www.acmicpc.net/problem/1958 1958번: LCS 3 첫 줄에는 첫 번째 문자열이, 둘째 줄에는 두 번째 문자열이, 셋째 줄에는 세 번째 문자열이 주어진다. 각 문자열은 알파벳 소문자로 이루어져 있고, 길이는 100보다 작거나 같다. www.acmicpc.net 문제 분석 LCS란 최장 공통 부분수열이다. 만약 문자열이 두 개(예제 입력 1의 위 두 문자열)라고 가정하였을 때, 다이나믹 프로그래밍(DP)를 사용하여 쉽게 LCS를 계산할 수 있다. 위의 그림과 같이 두 문자열을 앞에 공백이 있는 이차원 리스트로 만든다. 그 후 이중 반복문을 돌면서 같은 문자열이 있는지 탐색한다. 1. 같은 문자를 만난 경우 이 때, 같은 문자를 만난다면 대각선 왼쪽 위에 있는 수에 1을..

https://www.acmicpc.net/problem/2961 2961번: 도영이가 만든 맛있는 음식 첫째 줄에 재료의 개수 N(1 ≤ N ≤ 10)이 주어진다. 다음 N개 줄에는 그 재료의 신맛과 쓴맛이 공백으로 구분되어 주어진다. 모든 재료를 사용해서 요리를 만들었을 때, 그 요리의 신맛과 쓴맛은 www.acmicpc.net 문제 분석 N개의 재료 중 몇 가지의 재료를 골라 음식을 만든다. 음식을 만들 때 재료의 신맛과 쓴맛이 정해지는데, 신맛은 사용한 재료의 신맛의 곱이고 쓴맛은 합이다. N개의 재료 중 몇 가지 재료를 고르는 방법은 N의 길이를 가진 집합의 부분 집합을 구하는 것이다. 단순 반복을 통해 파이썬 라이브러리인 combinations를 구하면 쉽게 구할 수 있겠지만 백트래킹 알고리즘..

https://www.acmicpc.net/problem/1205 1205번: 등수 구하기 첫째 줄에 N, 태수의 새로운 점수, 그리고 P가 주어진다. P는 10보다 크거나 같고, 50보다 작거나 같은 정수, N은 0보다 크거나 같고, P보다 작거나 같은 정수이다. 그리고 모든 점수는 2,000,000,000보 www.acmicpc.net 문제 분석 비오름차순으로 저장되어 있는 점수들 사이에 태수의 새로운 점수를 끼워넣는 문제. P가 주어지면 P는 랭킹 리스트의 길이이며, 새로운 점수가 점수 리스트에 들어간 뒤 새로운 점수의 앞에 점수가 P개 이상일 경우 -1을 출력한다. 새로운 점수가 리스트에 들어갈 때 같은 점수가 있다면 같은 점수의 맨 뒤에 들어가게 된다. 또한, N이 0보다 클 경우만 점수 리스트..

https://www.acmicpc.net/problem/2448 2448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) www.acmicpc.net 문제 분석 별 찍기 문제는 재귀를 활용하면 쉽게 풀 수 있다. 재귀를 하기 위해서는 기준점과 재귀의 기준이 필요하다. 여기서는 시작점과 길이를 기준으로 재귀를 진행한다. 출력을 보면 높이가 3인 작은 삼각형이 3번 반복해서 큰 삼각형을 만들고 또 그 삼각형 3개가 모여 하나의 삼각형을 이룬다. 결론적으로 높이가 3일 때 삼각형을 만들어주면 쉽게 재귀를 진행할 수 있다. 처음 탐색을 할 경우, 총 길이 n을 탐색하고 n이 3이 될 때까지 2로 나누면서..