B Test

http://baactree.tistory.com/53

[필수]

※ 레퍼런스 코드도 참고

 

[추가]

  • Trie – 문자열 문제
  • LCA(Lowest Common Ancestor) – 디렉터리 구조나 가계도 문제 등
  • BST (Binary Search Tree)
  • Segment Tree

 

[유형]

  • https://swexpertacademy.com/main/main.do , 블록 부품 맞추기
  • 구현력, 복잡도 최적화
  • 자료구조에 대한 응용력 혹은 문제를 접근하는 방법에 초점을 맞춰 우선 공부하고 만약 대략적인 구조는 설계했으나 구현을 완벽히 못했다면 구현력을 충분히 연습하는게 좋다.

 

[문제]

  • BOJ – 3425, 5373, 15778, 15949, 2680, 15827, 11743
  • oj.uz – 보물 찾기, cmp
  • 기출

 

[Tip]

  • 1시간 문제 이해 설계
  • 2시간 구현 디버깅, 정확한 아웃풋 출력
  • 1시간 최적화 [전처리, 메모이제이션, 이분탐색, 해싱] 로, [트라이,LCA,세그먼트 트리]도 가끔 최적화 시 사용
  • STL 먼저 쓰고, output보장되면 STL 구현하는 식으로 코딩하면 쉬움

 

[기법들]

  • 차원 압축 – 모든 데이터는 (해당하는 데이터를 표현하는데 필요한 총 비트 수) / ( sizeof(int) or sizeof(long long) )로 압축 가능
  • 좌표 압축 –  데이터의 범위가 너무 크다면 등장하는 데이터들을 [0,N) 범위로 다시 넘버링 할 수 있음
  • 랜덤 엑세스 링크드 리스트 – 링크드 리스트의 단점이 랜덤 엑세스가 불가능하다는 것인데 해당하는 노드를 특정할 수 있고( id 라던지 value가 distinct 하다던지 ) 그 값이 충분히 작다면 링크드 리스트에 존재하는 모든 노드에 대해 해당하는 key를 전역변수로 노드 포인터를 저장하여 O(1)로 해당하는 노드에 접근 할 수 있음
  • 이분탐색 + 휴리스틱 : 데이터가 유니폼하게 분포되어 있는 상황에서는 정확한 이분탐색이 가장 효율적.  하지만 데이터를 분석해봤을 때 유니폼하지 않고 특정값에 몰려있다면 확률적으로 해당부분을 포함하게 적절히 쪼개는 것이 좀 더 효율적임을 알 수 있음
  • Struct 값끼리 크기 비교, 조건 여러개 일 때 비교

 

[디버깅]

 

It's only fair to share...Share on Facebook
Facebook
Share on Tumblr
Tumblr
Share on Google+
Google+
Tweet about this on Twitter
Twitter
Email this to someone
email
Musicals, Travel, Photo, Coding, English, Cat