22강
접근법 :
-
인트형 배열에서 연속되는 특정 구간의 최댓값 구하는 문제
-
배열의 정해진 구간을 슬라이딩 해가면서 답을 구한다.
-
윈도우 슬라이딩 기법의 구조와 비슷하다.
cf) vector 라이브러리를 이용하면 배열을 동적으로 할당 할 수 있다.
std::vector<int> a(n) // n크기의 int형 배열 a를 만든다.
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
}
23강
접근법 :
-
배열에 연속된 두 수를 비교해서 값이 커지면 cnt를 증가하는 문제이다.
-
변수명을 pre와 now로 두면 편하다.
24강
접근법 :
-
졸리점퍼 문제 : n가지의 수를 입력 했을 때, pre와 now의 값의 차가 1~n-1 까지가 있는지 확인 하는 문제이다.
-
해당 문제는 check 배열을 하나 만든다.
-
n개를 입력 받았을 때, 1~n-1 까지의 차가 있다는 것은 각각의 차가 모두 다른 값이라는 것이다. 즉 for문을 도는 도중 값의 차의 중복이 있거나, 차가 n이상이라면 답은 틀리게 된다.
cf) algorithm 라이브러리에 있는 abs() 메소드 사용. 절댓값 메소드
&& 연산자는 앞에 것이 거짓이면 뒤에 것을 확인 하지 않는다.
26강
접근법 :
- O()으로 풀 수 있던 이유는 n이 10000까지 밖에 안되서 그렇다. 만약에 수가 더 크다면 O() 병합 정렬을 이용해 자기 앞쪽에 있는 수중에서 나보다 큰 수가 몇개인지 알 수 있다.
27강
접근법 :
-
소인수분해를 해서 해당 수가 어떤 수의 곱에 의해서 소인수분해 되어지는지에 대한 문제이다.
-
이제 체크 배열을 하나 두고 이 체크배열의 크기는 n을 소인수분해 한다 했을 때 1부터 n까지가 필요하니까, n+1로 일단 선언한다.
-
이제 이렇게 생긴 체크배열에 속하는 숫자 1 ~ n 까지에 대해서 반복문을 돌면서 n 숫자에 % 연산을 해준다. 그리고 그값이 0인 경우에는 % 연산을 해주는 연산숫자에 대한 인덱스 값을 +1 해준다.
-
그리고 이 %연산을 했던 숫자로 n을 나눠준다. n을 나눠준 결과를 또 같은 수로 %연산을 해준다. 만약 여기서 %연산의 결과가 0이 아니라면, n은 그대로 두고 %연산을 했던 숫자를 +1 해준다.
-
결과적으로 n이 1이 될때 이 반복문은 종료하고, %연산을 했던 수가 나왔던 횟수를 샜던 check 배열의 값이 결과가 된다.
