부분합. [25682]
[1. 문제 설명]https://www.acmicpc.net/problem/25682[2. 풀이 접근] 완전 탐색모든 구간에 대해서, 색칠해야 할 개수를 확인 후 최소값을 업데이트 해나가는 방법위 방식은 3중 for 문을 유도하며, N, M, K 가 최대 2000 까지이므로, 1초 안에 계산하기 어려움,그러나, 모든 구간에 대해서는 확인 해봐야 함.# 어떤 구간이 최소가 될지는 알 수 없기 때문,즉, 특정 구간에 대해서 (crop? 한 영역) 에서 몇번 색칠 할 지를 logn 이하로 확인 할 수 있어야 한다.결과의 특성문제 조건 상, K*K 로 잘라내고, 색칠한 형태는 아래와 같은 두가지 구조만 갖는다.(y, x) = (1, 1) 위치가 검정색인 경우 => Case A(y, x) = (1, 1) 위치가 ..
stack, queue reverse
[1. 개요]queue 를 reverse 해야 할 때, 주의 할 점(?)[2. 잘못된 구현]for (int i=1; iqueue 에 저장된 순서를 바꿔야 할 때,q: [1, 2, 3, 4, 5]expected: [5, 4, 3, 2, 1]result : [5, 1, 2, 3, 4]당시에 뭔가 착각했었음,[3. 맞는 구현?]while (q.size() > 0) { st.push(q.front()); q.pop();}while (st.size() > 0) { q.push(st.top()); s.pop();} 큐의 경우, 스택을 이용하도록 하고,스택은, 큐를 이용하여 뒤집을 수 있도록 한다.
중복 된 숫자 개수 세기
[1. 개요]어떤 배열에서 중복 된 숫자의 개수를 세야 할 때,재귀로 구현했을 때 간과할 수 있는 오류(?) 등을 정리[2. 재귀적인 방법]fn _solve(input: &Vec, i: usize) -> i32 { if i >= input.len() { return 0; } let mut ret = 0; for j in i+1..input.len() { if input[i] == input[j] { ret += 1; } } return ret + _solve(&input, i+1);} 아래는 위 rust 함수에 입력과 출력을 정리한 것이다.입력출력[7, 7, 7]3[6, 5, 4]0[6, 2, 6] 1 [7, 7, ..