알고리즘 트레이닝 2장

1장은 경진 프로그래밍이 무엇인지, 책의 개략적인 내용이 어떠한지에대하여 설명 하고있으므로 생략

지금 내가 배우고 있는 언어는 c/c++임 이전 내용에 관한 정보는 쿨프로그래밍 블로그에가 c언어와 c++을 공부하면됨

13. 구조체

2장 - 프로그래밍 기법

• 언어적 특성
  • 입출력 방법, 수를 처리하는 방법, 코드를 짧게 만드는 방법
  • #include<bits/stdc++.h>
    • 경진 프로그래밍 대회에서 사용되는 C++코드 템플릿의 전형적인 형태 
    • iostream, vector, algorithm등의 라이브러리를 모드 포함하고 있음
  • 입력과 출력
    • cin(입력), cout(출력)
      • 대부분의 대회에서 표준 스트림을 사용 '
      • scanf, printf와 같은 c언어 함수도 사용가능 
    • 병목현상 방지
      • ios::sync_with_stdio(0); cin.tie(0);
        • 코드 시작 부분에 작성시 입출력이 빨라짐
        • 단 scanf, printf와 같은 c언어 입출력함수 사용 불가능
    • 파일 사용
      • 표준 스트림을 사용하는 코드 작성 후, 다음 두줄을 코드의 시작부분에 추가
      • freopen("inout.txt", "r", stdin);
      • freopen("output.txt", "w", stdout);
  • 수를 처리하는 방법
    • 정수
      • int
        • 32bit
        • -2^31...2^31 - 1(대략 20억)
      • lon long
        • 64 bit
        • -2^63...2^63-1(대략 9*10^18)
    • 나머지 연산(mod, %)
      • x mod m
        • x를 m으로 나눈 나머지
        • (a+b) mod m = (a mod m+ b mod m)mod m
        • 위와 같이 +를 - , * 으로 바꾸어도 가능하다 하지만 / 는 불가능
        • 연산을 하다가 나머지 즉 mod를 취한 값이 음수가 될 수도 있음  ' - ' 를 할 경우 그렬경우 결과 값에 m을 더해주면 됨  
          • x = x% m;
          • if ( x < 0) x += m;
    • 부동 소수점 실수
      • 대회에서는 대게 double이면 충분하지만 long double의 정밀도가 좀 더 높음
      • 부동 소수점 형태로 실수 표현시 오차가 생길수 있음
        • ex) double x = 0.3*3 +0.1;//당연히 1.0이라고 생각하지만 
        • printf("%.20f\n", x); // 0.999999999999999999989889 이런식으로 나옴 %f 사이에 .숫자 입력시 원하는 소수점만큼 숫자 출력가능
        • 위와 같은 이유 떄문에 ==연산자 사용은 매우 위험
        • if( abs(a-b) < 1e-9 ){ //일치 } //다음과 같이 매우작은수와 비교해 더 작을시 일치하다고 판단
  • 코드 짧게 만들기
    • 자료형
      • typedef
        • typedef long long ll; // 작성할 경우
        • long long a = 123457889345; //해당코드를
        • ll a = 123457889345; // 로 작성해도 됨
        • typedef vector<int> vi;  //다음과 같은 코드도 가능
        • typedef pair<int,int> pi;
    • 매크로
      • #define
        • #define F first // 컴파일 전 F를 first로 치환 해줌
        • #define REP( i, a, b) for(int i=a; i<=b;i++) // 와 같은것도 가능
• 재귀적 알고리즘
  • 부분집합 생성하기
    • 원소가 n개인 집합의 모든 부분집합 생성 알고리즘
      • 책 참조
      • search(1) 함수가 시작
        • 1을 subset(vector)에 넣고  search(2)함수를  호출 한다 (subset에는 1)
        • search(2) 함수 시작
          • 2를 subset 에 넣고 search(3) 호출(subset에는 1,2)
          • search(3)함수 시작
            • 3을 subset에 넣고 search(4)호출(subset에는 1,2,3)
            • search(4)시작
              • 4==3+1 이므로 부분집합 처리 (1,2,3)
            • 3을 subset에서 뺴고 search(4)호출( subset에는 1,2)
            • search(4)시작
              • 4==3+1 이므로 부분집합 처리 (1,2)
          • 2를 subset 에서 빼고 search(3) 호출(subset에는 1)
          • search(3)함수 시작
            • 3을 subset에 넣고 search(4)호출(subset에는 1,3)
            • search(4)시작
              • 4==3+1 이므로 부분집합 처리 (1,3)
            • 3을 subset에서 뺴고 search(4)호출( subset에는 1)
            • search(4)시작
              • 4==3+1 이므로 부분집합 처리 (1)
        • 위와같이 하면 나머지 부분함수도 구해짐 즉 각 search(n)마다 n이 포함된 부분함수를 찾은후 n이 빠진 부분 함수를 찾는것이다.
  • 순열 생성하기
    • 원소가 n개인 집합의 모든 순열을 생성하는 알고리즘
    • search() 함수가 시작
      • for문 (int i =1->3) 
      • i = 1
        • chosen[1]에 체크가 되어 있지 않으므로 패스
        • 1을 방문했다고 chosen[1]에 1
        • purmutation(vector)에 1포함
        • search() 함수가 시작
          • for문 (int i =1->n) 
          • i = 1
            • chosen[1]에 체크가 되어 있으므로 continue
          • i =2
            • chosen[2]에 체크가 되어 있지 않으므로 패스
            • 2을 방문했다고 chosen[2]에 1
            • purmutation(vector)에 2 포함
            • search() 함수가 시작
              • for문 (int i =1->n) 
              • i = 1
                • chosen[1]에 체크가 되어 있으므로 continue
              • i =2
                • chosen[2]에 체크가 되어 있으므로 continue
              • i = 3
                • chosen[3]에 체크가 되어 있지 않으므로 패스
                • 3을 방문했다고 chosen[3]에 1
                • purmutation(vector)에 3 포함
                • search() 함수가 시작 
                  • permutiation의 크기가 3이므로 순열처리
                  • (1,2,3)
                • 3을 뺄 것이므로 chosen[3]에 0 
                • permutation에서 3 제거
            • 2를 뺄 것이므로 chosen[2]에 0
            • permutation 에서 2 제거
          • i = 3
            • chosen[3]에 체크가 되어 있지 않으므로 패스
            • 3을 방문했다고 chosen[3] 에 1
            • permutation에 3포함
            • search()함수 시작
              • for문 (int i =1->n) 
              • i = 1
                • chosen[1]에 체크가 되어 있으므로 continue
              • i =2
                • hosen[2]에 체크가 되어 있지 않으므로 패스
                • 2을 방문했다고 chosen[2]에 1
                • purmutation(vector)에 2 포함
                • search() 함수가 시작 
                  • permutiation의 크기가 3이므로 순열처리
                  • (1,3,2)
                • 2을 뺄 것이므로 chosen[2]에 0 
                • permutation에서 2 제거
              • i = 3
                • chosen[3]에 체크가 되어 있으므로 continue
    • 와 같은 방식으로 진행됨
  • 퇴각 검색(backtracking)
    • 비어있는 길을 탐색하고 단계마다 해를 확장해 나가는 방식의 알고리즘
• 비트 연산
  
  • int 는 32bit자료형
  • 정수의 이진수 표현에는 부호가 있을 수도 없을 수도 있다.
    • 부호가 없으면 범위가 2배로 늘어남
  • 부호가 있는 정수 표현
    • 제일 왼쪽 비트가 부호를 나타냄
      • 0은 음이 아닌 정수(0 포함)
      • 1은 음의 정수
    • 나머지 n-1비트가 정수의 크기 표현
    • 2의 보수
      • 모든 비트를 뒤집은 후 1을 더하는 방식
  • 비트 연산
    • And 연산 ( & )
      • 공통으로 1이 들어간 위치에 1이 들어감(비트)
      • 1과 &할시 0이면 짝수이고 1이면 홀수
    • Or 연산 ( | )
      • 둘중 하나라라도 1이 들어간 위치에 1이 들어감
    • Xor 연산 ( ^ )
      • 둥중 하나에만 1이 들어간 위치에 1이 들어감
    • Not 연산( ~ )
      • 모든 비트를 뒤집어 놓은 정수
      • 보수를 생각한다면 ~x = -x -1이다
        • -x = ~x+1
    • 비트 시프트 연산
      • x << k
        • 정수의 오른쪽에 비트 0을 k개 덧붙이는 연산
        • x에 2를 k번 곱하는 것과 같음
      • x>>k
        • 정수의 오른쪽 비트 k개를 제거하는 연산
        • x를 2로 k번 나누고 정수로 내림한 것과 같음
    • 비트 마스크
      • 1<<k
        • k번째 위치에만 비트 1이있고 나머지 위치에는 비트 0이 있는 정수
  • 집합 표현하기
    • n비트 정수를 이용해 n개의 수 보관여부를 저장 할 수 있다.
      • bool arr[n] 과 같이 비트가 1일 경우 보관하고 있다고 생각하면 된다.
      • 숫자 1,3,4,8을 저장 하고 싶으면 2^1+ 2^3 + 2^4 + 2^8 = 282 를 저장하면 된다.