열이의 개발블로그

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/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로 나누면서..

https://www.acmicpc.net/problem/2866 2866번: 문자열 잘라내기 첫 번째 줄에는 테이블의 행의 개수와 열의 개수인 R과 C가 주어진다. (2 ≤ R, C ≤ 1000) 이후 R줄에 걸쳐서 C개의 알파벳 소문자가 주어진다. 가장 처음에 주어지는 테이블에는 열을 읽어서 문자 www.acmicpc.net 문제 분석 R개의 행과 C개의 열로 이루어진 테이블에서 열을 기준으로 단어를 만들어 총 R의 길이를 갖는 C개의 단어를 만든 후 단어들의 중복 여부를 확인한다. 처음에는 동일한 문자열이 존재하지 않는 입력이 주어지고 다음 연산부터는 가장 위의 행을 지운, 즉 단어의 첫 번째 문자를 없앤 단어들의 중복 여부를 판단한다. 단어들 중 중복이 없다면 count를 1 증가, 중복이 있다면..

https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 문제 분석 예은이의 위치에 따라 수색범위 안에서 방문할 수 있는 지역을 모두 탐색한 뒤, 그 지역에서 얻을 수 있는 아이템들의 합을 구하는 문제이다. 플로이드-워셜 대표적인 문제라고 볼 수 있을 것 같다. [플로이드-워셜 알고리즘] 하지만 알고리즘 분류를 보기 전에는 그래프 탐색만으로 충분히 풀 수 있어 보여서 그래프 탐색을 이용한 풀이를 작성하고자 한다. 우선, 모든 노드를 탐색하면서 그 노드에서 출..