KPU CE

문제 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]..

심심해서 평소에 만들고 싶었던 바둑판을 만들어 보려고 한다. 대국을 할 수 있는 바둑판이다. 1일차에서는 간단한 인터페이스와 흑,백이 둔 곳을 맵을 출력해서 보여지게 하는 작업과 2일차에 있을 돌을 따먹는 과정을 bfs로 어느정도 구현을 했다. 2일차에서는 돌을 따먹는 것을 구현한 후 인터페이스를 개선할 것이다. 계가 시스템과 패싸움 같은 부분을 구현 할 생각에 막막하지만 할 수 있을 거라 믿고 있다... 1일차 코드 #include #include #include using namespace std; /* map 설명 검은돌은 9, 흰색돌은 7, 맨바닥은 0 */ string map[20][20]; int b_catch = 0,w_catch = 0,cnt = 0; bool b = false,w = fa..