8.4

바이너리 카운팅

바이너리 카운팅, Binary Counting
  - 원소 수에 해당하는 N개의 비트열을 이용한다.
  - n번째 비트값이 1이면 n번째 원소가 포함되었음을 의미한다.
  - bit 하나를 flag로 사용.

arr[i]의 위치를 보려면 1<<i shifting


int arr[] = {3,6,7,1,5,4};
int n = arr.length;

for (int i=0;i<(1<<n);i++){
  for(int j=0;j<n;j++){
    if((i&(1<<j)) != 0) // 근데 이게 빠르지 않음;
      System.out.println(arr[j]+" ");
  }
  System.out.println();
}
 
- 큰 수 다룰 때 bigInteger말고  boolean형 배열 쓰는게..?
- 재귀, 반복문.

- 곱하기 / 나누기에서의 장점.
- 메모리 측면에서 장점.
- 비트 마스킹을 한다. 의 경우 입력이 30이하인 경우가 많을것임. (4byte 32bit)

-----

스택, stack
 - push()
 - pop()
 - peek()
 - isEmpty()
 - size() 
 정도..

괄호 검사.
  - 조건
    - 왼쪽 괄호와 오른쪽 괄호의 개수가 같아야
    - 같은 괄호에서 왼쪽은 오른쪽보다 먼저 나와야
    - 괄호 사이에는 포함 관계만 존재한다
  - 알고리즘
    - 문자열에 괄호를 조사하면서 왼쪽 괄호는 스택에 삽입
    - 오른쪽 괄호는 스택에서 top 요소 삭제 후 짝이 맞는 지 검사.
    - 만약 스택이 비어있다면 오른쪽 괄호가 먼저 나온 것이므로 에러
    - 짝이 맞지 않다면 그것도 에러.

Function call
  - 프로그램에서의 함수 호출과 복귀에 따른 수행 순서를 관리
  - 스택 이용
  - 함수 호출이 발생하면 호출한 함수 수행에 필요한 지역변수, 매개변수 및 수행 후 복귀할 주소 등의 정보를 스택 프레임, stack flame에 저장하여 시스템 스택에 삽입
  - 함수의 실행이 끝나면 시스템 스택의 top 원소(스택 프레임)을 삭제하면서 프레임에 저장되어 있던 복귀주소를 확인하고 복귀.
  - 전체 프로그램 수행이 종료되면 시스템 스택은 공백 스택이 된다.
  
후위 표기식.
  - 피연산자를 만나면 스택에 push
  - 연산자를 만나면 필요한 만큼 스택에서 pop해서 연산 후 다시 스택에 push
  - 수식이 끝나면 마지막으로 스택을 pop하여 결과 출력.

-----

큐, Queue
  - 선입선출! 편의점 재고!
  - offer()
  - poll()
  - peek()
  - isEmpty()
  - size()
  
  - LinkedList
  - ArrayDeque -> 데이터 많을 때 30% 빠름

-----

덱, Deque

ArrayDeque..!

초기 상담

IT 산업 종류
  - IT 서비스
  - IT 플랫폼
  - 금융업
  - 제조/유통
  
CS도 준비.

어학 8월 내.
  - 삼성. 오픽 IM2

B형 대비

불필요한 반복문 범위. 최적화.
불필요한 메소드 권장하지 않음.
 - 스택오버플로우
 - 메소드 호출 시간.
 - 매번 지역변수 생성 / 삭제

-----

선형 / 비선형
1:1 인가 1:N 인가.
  - 하나의 데이터에 몇 개가 연결되었나?
  - 한 줄 짜리 트리도 트리이므로 N개는 1개 이상이라고도
  
-----

효율적인(최적화) 자유구조.
List Hash...
내가 자료구조를 구현할 수 있는지.
 - MyStack.
 - 쓸 것만 구현.
정렬도 할 줄 알아야. Merge Sort..! 
 - Quick은 최악의 경우 n^2..

-----

시간 복잡도.
  - 제한시간 1초 기준 연산 대략 1억 번.
  - nlogn -> N의 크기 100만이하일 경우 ok.
  - n^2 -> 5000 이하로 확 줄음.
  - 2^n -> 25 이하..
  - n! -> 11 이하..
  
-----

pq -> PriortyQueue.