40강~ 42강

40강

접근법 :

• 두 배열의 교집합을 찾는 문제이다.

• 이 문제는 투포인터 방법을 가지고 문제를 풀 수 있다.

• 두 배열의 포인터 변수를 선언하고, 교집합이 될 원소를 저장할 C 배열을 선언해준다.

• 그리고 이제 A와 B배열을 정렬을 해준다.

sort(A.begin(),A.end());
sort(B.begin(),B,end());

• 정렬된 두 배열에 맨 앞 부분의 수를 비교한다. 만약에 A포인터에 해당되는 값이 B포인터가 가리키는 값보다 크면 B포인터의 값을 하나 늘린다.

• 그리고 두 포인터가 가리키는 값이 같다면 C배열에 해당 값을 추가하고 A와B포인터를 ++ 해준다.

• 그리고 마지막으로 B포인터가 A포인터보다 큰 경우에는 A포인터의 값을++ 해준다.

• 이 상황은 두 쪽 중 하나의 배열의 마지막 인덱스 값과 포인터가 같아 질 때까지 진행한다.

• while( A.size() < n && B.size() < m)

cf) 해당 문제를 풀다가 sort 를 통해서 안하고 삽입 정렬을 구현하여 내가 직접 하였는데, 삽입 정렬 소스를 잘못 짰다. 내가 실수한 부분은
1) i의 값은 index인데 n과 같을때 까지 삽입을 하게 하여 index를 초과하였다.
2) 현재 삽입하는 값을 tmp에 저장을 하여 tmp에 저장된 수가 위치하는 곳을 찾는 것인데 A[j+1] 과 A[j]의 값을 비교 하였다.
3) 어차피 i 앞쪽의 인덱스들은 다 정렬된 상태이기 때문에 tmp와 하나하나 비교해가면서 tmp의 위치를 찾는 것이 삽입정렬임을 기억하자.

41강

접근법 :

• 어떤 수를 입력 받았을 때, 입력 받은 수를 연속된 자연수의 합으로 구하는 문제였다.

• 연속된 자연수를 출력하기 위하여 for문을 돌 때, i의 값은 몇개의 자연수가 있는지를 결정하는 요소로 생각을 하자.

• i의 값을 가지고 연속된 자연수를 출력하기에는 너무 복잡한 식을 쓰게 된다.

• 따라서 i는 1(or 0)로 시작하는 변수로 하고, 특정한 값에 i를 더해주는 방식으로 코딩을 하자
  ex) 특정값 : 3,

 for(i=1;i<5;i++){
 	x=3+i;
 }

x=4,5,6,7이 된다.

• 어떤 수 x를 연속된 자연수의 합으로 표현 하는 방법
  1) 몇개의 연속된 자연수의 합으로 구할 것인지 생각한다. ex)2개
  2) x의 값에서 1과 2를 뺀다. ex)x-1-2
  3) 여기서 1과 2를 뺀 이유는 현재 x를 2개의 연속된 자연수의 합으로 나타 낼 것이기 때문이다.
  4) 이제 1과 2를 뺀 x값을 숫자의 가지수로 나눈 나머지가 0 인지를 확인한다.
  ex) x%2 ==0
  5) 만약에 0 이라면 이 수는 연속된 자연수로 나눌 수 있는 수이다. 따라서 x/2를 한 값을 각각 1과 2에 더해준다.

#include<stdio.h>
int main(){
	freopen("input.txt", "rt", stdin);
	freopen("output.txt", "wt", stdout);
	int a, b=1, cnt=0, tmp, i;
	scanf("%d", &a);
	tmp=a;
	a--;
	while(a>0){
		b++;
		a=a-b;
		if(a%b==0){
			for(i=1; i<b; i++){
				printf("%d + ", (a/b)+i);
			}
			printf("%d = %d\n", (a/b)+i, tmp);
			cnt++;
		}
	}
	printf("%d\n", cnt);
	return 0;
}

42강

접근법 :

• 이분검색 방법

• 정렬되어 있는 배열에서 어떠한 수를 찾는 문제에서는 이분검색을 이용한다.

• 이분검색
  1) lt=0 , rt=끝 인덱스 의 값으로 초기화 한다.
  2) lt와 rt를 더해서 나누기 2를 한 값을 mid로 한다.
  3) mid의 값이 0일때까지 while문을 진행한다.
  4) 현재 찾으려는 숫자보다 mid 값이 큰 경우에는 rt=mid-1
  5) 현재 찾으려는 값과 mid 값이 같다면, 몇번째로 큰 숫자인지를 알기 위해서는 mid+1이 된다.
  6) 현재 찾으려는 값보다 mid 값이 작은 경우에는 lt=mid+1이 된다.

cf) vector의 begin(), end() 는 주소값을 가지고 있다 값을 가져오기 위해서는 *a.begin() , *a.end() 이런식으로 사용하면 된다.
활용 : *(a.end()-1) 끝에서 앞 인덱스의 값