https://www.acmicpc.net/problem/1895 1895번: 필터 숫자 9개가 오름차순이나 내림차순으로 정렬되어 있을 때, 중앙값은 다섯 번째 숫자이다. 예를 들어, 1, 3, 4, 1, 2, 6, 8, 4, 10의 중앙값은 4이다. (1 ≤ 1 ≤ 2 ≤ 3 ≤ 4 ≤ 4 ≤ 6 ≤ 8 ≤ 10) 이미지 I는 www.acmicpc.net 문제 분석 RxC 크기인 이미지 배열(=I)를 입력 받고, 3x3 배열의 필터를 씌여서 중앙값을 찾는 문제이다. 필 터를 씌어서 찾은 중앙값들을 정렬한 뒤, T 값 보다 큰 숫자들의 개수를 새는 문제이다. 코드 ㅋ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29..
Koala - 7기/코딩테스트 준비 스터디
https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 문제 분석 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 자연수 n이 주어질 때, n을 최소 개수의 제곱수 합으로 표현하는 문제이다. 조건. 입력은 자연수 n을 포함하는 한 줄로 구성된다. 1 ≤ n ≤ 50,000이다. 코드 다이나믹 프로그래밍 import math n = int(input()) dp = [0,1] for i ..
https://www.acmicpc.net/problem/1463 [문제해석] N을 입력하여 그 수가 위의 조건에 따라 1로 만드는 최소한의 횟수를 찾는 문제이다. [코드] n = int(input()) d = [0] * (n+1) for i in range(2, n+1) : d[i] = d[i-1] + 1 if i % 3 == 0 : d[i] = min(d[i], d[i//3]+1) if i % 2 == 0 : d[i] = min(d[i], d[i//2]+1) print(d[n]) [문제 풀이] n을 입력받는다. n+1 개수만큼의 0으로 된 리스트를 생성하고, 리스트 시작을 0번째가 아닌 첫번째로 시작하기 위해 n+1개로 설정한다. 입력된 값이 1이라면 어차피 계산횟수가 0이고, 그대로 출력하면 되..
백준 1149 RGB거리 Intro Solution 주어진 규칙 중 세 번째 규칙이 앞의 두 규칙을 모두 포함하는 말이다. 연속으로 같은 색깔을 색깔을 선택할 수 없으므로, 색깔별로 나누어 누적 비용을 저장한다. n번째 집에서 빨강을 선택할 때는 n-1번째 집에서 초록을 선택할 경우의 비용의 누적 합과 파랑을 선택할 경우의 비용의 누적 합을 비교하여 최솟값을 찾아 더하면 된다. 예를 들어 입력이 다음과 같다고 해보자. 입력 3 26 40 83 49 60 57 13 89 99 그러면 비용의 누적 합은 다음과 같은 순서로 저장된다. ''' dp[1] = [26, 40, 83] dp[2] = [49+min(40, 83), 60+min(26, 83), 57+min(26, 40)] = [89, 86, 83] dp..
https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 문제 분석 새로운 앱을 활성화하기 위해서 기존에 활성화 된 앱들을 종료해 메모리를 확보하는 문제입니다. 앱을 종료할 때 고려할 사항으로는 앱이 차지하는 메모리와 앱을 종료했을 때 발생하는 비용이 있습니다. 새로운 앱을 활성화 할 수 있을 만큼 충분한 메모리를 확보하면서 비용은 최소화하는 것이 목적입니다. 일종의 배낭 문제로, 다이나믹 프로그래밍을 활용해 문제를 해결할 수 있습니다. 얼핏 보기에 메모리가 ..
https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제분석 분류 DP(동적계획법) 문제설명 입력받은 수를 최소한의 연산으로 1로 만들기 연산은 3종류 x-1 if(x % 3 == 0), x / 3 if(x % 5 == 0), x / 5 동적계획법 Bottom-up 방식으로 진행 입력 10 출력 3 코드 #include #include #include using namespace std; vectordp; int main() { int n; cin >> n; dp.assign(n+1,-1); dp[1] = 0; for (int x = 2; x
https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 문제분석 현재 자신이 있는 위치보다 낮은 위치로 갈 수 있고 0,0 에서 n-1,m-1까지 갈 수 있는 경로의 개수를 구하는 문제이다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokeni..
https://www.acmicpc.net/problem/9657 9657번: 돌 게임 3 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 문제 분석 돌 N개가 있을 때, 상근이와 창영이가 돌아가면서 돌을 1개, 3개 또는 4개를 가져간다. 마지막 돌을 가져가는 사람이 이기게 된다. 둘은 완벽한 게임을 한다. 조건. 상근이가 먼저 돌을 가져간다. 입력으로는 돌의 개수가 주어지고, 상근이가 게임을 이기면 SK, 창영이가 이기면 CY를 출력한다. 코드 #include using namespace std; int main(){ int n; cin>>n; int shobu[n+1]; shobu[1] = 1; shobu[2] = 0; shobu[3] = 1; ..
https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 문제 해석 1이 입력된 곳(=섬)이 8개의 방향으로 이어져 있으면, 하나의 섬으로 인정한다. 지도에 있는 섬의 총 개수를 출력하는 문제이다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 ..
https://www.acmicpc.net/problem/1895 1895번: 필터 숫자 9개가 오름차순이나 내림차순으로 정렬되어 있을 때, 중앙값은 다섯 번째 숫자이다. 예를 들어, 1, 3, 4, 1, 2, 6, 8, 4, 10의 중앙값은 4이다. (1 ≤ 1 ≤ 2 ≤ 3 ≤ 4 ≤ 4 ≤ 6 ≤ 8 ≤ 10) 이미지 I는 www.acmicpc.net 문제분석 분류 완전탐색, 정렬 문제설명 원본 이미지에 3x3 필터를 적용하여 필터링된 이미지에서 값이 T보다 크거나 같은 픽셀의 수를 구하는 문제이다. 첫째 줄에 이미지의 크기 R(행), C(열)가 주어진다. 그 다음 각 R개의 줄에 C개의 픽셀 값이 주어지고, 마지막 줄에 T값이 주어진다. 필터링된 이미지의 각 픽셀 값 중에서 T보다 크거나 같은 것..
15666번: N과 M (12) (acmicpc.net) 15666번: N과 M (12) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 해석 N개의 자연수 중 M개를 고른 수열을 모두 구하는 문제이다. 조건으로는 같은 수를 여러 번 골라도 되고 비내림차순이어야 한다. 그리고 순열은 사전 순으로 출력해야 한다. 코드 문제 풀이 main부분을 보면 s에 N개의 수를 저장해 주었고 s를 오름차순으로 정렬해주었다. 이는 사전 순으로 출력해주기 위함이다. 그리고 arr와 result를 각각 list와 dictionary로 선언해주었는데 ar..
https://www.acmicpc.net/problem/1107 문제 분석 코드 n = int(input()) brokenNum = int(input()) brokenList = list() if (brokenNum == 0): answerList = [abs(n - 100), len(str(n))] print(min(answerList)) elif (brokenNum == 10): brokenList = list(input().split()) print(abs(n - 100)) else: brokenList = list(input().split()) numList = ["0", "1", "2", "3", "4", "5", "6", "7", "8", "9"] numList = list(set(numLi..
