KPU CE

문제 해결 일반적으로 사용하는 bfs 케이스(상하좌우)에 체스 말 케이스를 추가해서 12가지의 케이스를 고려해서 bfs 코드르 작성하렸다. 여기서 주위해야될 점은 체스말로 이동한 곳은 따로 visit를 해야된다. visit을 할때 그곳이 k가 0~30번까지 올 수 있기 때문이다. 코드 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 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 #include #..

문제 https://www.acmicpc.net/problem/14438 14438번: 수열과 쿼리 17 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 i j : Ai, Ai+1, ..., Aj에서 크기가 가장 작은 값을 www.acmicpc.net Solve 세그먼트 트리를 활용해서 풀었다. init함수를 만들어서 트리를 초기화하고 update함수를 만들어서 수를 변경하였다. 그리고 query 함수는 구간의 가장 작은 값을 출력하는 함수이다. update를 할 때 만약 구간이 아니라면 현재 노드의 값을 반환 , 만약 start == end라면 바뀌는 값을 ..

문제 https://www.acmicpc.net/problem/14427 14427번: 수열과 쿼리 15 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 : 수열에서 크기가 가장 작은 값의 인덱스를 www.acmicpc.net Solve min_index라는 함수를 만들어서 작은 수의 인덱스를 반환하고 만약 수가 같으면 작은 인덱스를 반환하는 함수를 작성한다. 그리고 세그먼트 트리를 구현하는데 리프노드에 수를 넣지 말고 인덱스를 넣어서 노드들 마다 인덱스가 들어가도록 한다. query 1번일 경우는 update 함수를 돌려서 노드들을 바꿔준다. query 2번..

문제 https://www.acmicpc.net/problem/11505 11505번: 구간 곱 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 문제 풀이 이 문제는 세그먼트 트리를 이용해서 푸는 문제이다. 기본적으로 세그먼트 트리의 지식이 있어야 풀 수 있다. 세그먼트 트리에서 구간 합을 구하는 방법과 비슷하게 풀었다. 1. 초기화를 해줄 때 자식 노드들의 곱으로 노드를 초기화했다. 2. 업데이트를 해줄 때는 구간에 있는 노드들을 전부 바꿨다. (리프 노드도 바꾸어줌)-..

문제 https://www.acmicpc.net/problem/13699 13699번: 점화식 다음의 점화식에 의해 정의된 수열 t(n)을 생각하자: t(0)=1 t(n)=t(0)*t(n-1)+t(1)*t(n-2)+...+t(n-1)*t(0) 이 정의에 따르면, t(1)=t(0)*t(0)=1 t(2)=t(0)*t(1)+t(1)*t(0)=2 t(3)=t(0)*t(2)+t(1)*t(1)+t(2)*t(0)=5 ... 주어진 입력 0 ≤ n www.acmicpc.net 문제 해결 문제에서 주어진 점화식을 다이나믹으로 그대로 구현하였다. 코드 #include using namespace std; int main(void){ int N; long long dp[36],temp = 0; dp[0] = 1; dp[1]..

문제 https://www.acmicpc.net/group/board/view/9362/19864 로그인 www.acmicpc.net 문제해결 다이나믹 프로그래밍으로 풀었다. fibo(n) = fibo(n-1) +fibo(n-2) 이라는 식을 규칙을 보고 유추하여서 배열로 구현하였다. 코드 #include #pragma warning(disable : 4996) int main(void) { int n; long long int ary[92]; ary[0] = 0; ary[1] = 1; scanf("%d",&n); for (int i = 2; i

문제 https://www.acmicpc.net/problem/2747 2747번: 피보나치 수 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 문제 해결 재귀를 이용하여 0이면 0을 리턴하고 1이면 1를 리턴하고 그외는 n-1,n-2의 함수를 호출하여 구현했다. 코드 #include using namespace std; int fibo(int n){ if(n == 1){return 1;} else if(n == 0){return 0;} return (fibo(n-1)+fibo(n-2)); } int ..

문제 https://www.acmicpc.net/problem/2167 2167번: 2차원 배열의 합 첫째 줄에 배열의 크기 N, M(1 ≤ N, M ≤ 300)이 주어진다. 다음 N개의 줄에는 M개의 정수로 배열이 주어진다. 배열에 포함되어 있는 수는 절댓값이 10,000보다 작거나 같은 정수이다. 그 다음 줄에는 www.acmicpc.net 문제 해결 입력받은 그대로 반복문을 만들어서 풀었다. 코드를 보면 이해가 될 것이다. 코드 #include using namespace std; int N,M,map[302][302]; int solve(int x,int y,int dx,int dy){ int result = 0; for(int i = y;i N >> M; for(int i = 1;i map[i]..

문제 https://www.acmicpc.net/problem/2953 2953번: 나는 요리사다 "나는 요리사다"는 다섯 참가자들이 서로의 요리 실력을 뽐내는 티비 프로이다. 각 참가자는 자신있는 음식을 하나씩 만들어오고, 서로 다른 사람의 음식을 점수로 평가해준다. 점수는 1점부터 5 www.acmicpc.net 문제 해결 한 행을 입력받을 때마다 Max값을 갱신해가면서 만약 Max값이 바뀌면 인덱스 값도 바꿔가면서 그때 그때마다 갱신하는 식으로 풀었다. #include using namespace std; int main(void){ int Max = -1,idx; for(int i = 0;i a; temp +=a;} if(temp>Max){Max = temp;temp = 0;idx = i;}} c..

문제 https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net X문자열과 Y문자열이 있다고 하자. X 문자열은 X(1)~X(i)까지 있다고 하고 Y문자열은 Y(1)~Y(j)까지 있다고 하자. X(i)와 Y(j)가 같은 경우와 다른 경우가 있을 수 있다. -만약 X(i)와 Y(j)가 같은 경우라면 X(1)~X(i-1), Y(1)~Y(j-1)의 LCS길이를 구하면 된다. 그리고 마지막 문자가 추가됨으로써 +1을 ..