알고리즘 풀이 참고사항

1. 풀이 아이디어

• 거리에 관한 문제 → bfs, dfs
• 2진수 → 비트마스킹
• 최단거리
  • 한 노드에서 모든 노드까지의 최단 거리 -> Dijkstra
  • 모든 노드를 잇는 최단 거리 -> MST (Minimum Segment Tree)

2. 주의사항

0) 공통

• pop할 때 : len == 0 확인
• 0인 케이스 고려했는지 주의

1) Python

2) Java

• int / int = int -> 최소 하나는 double로 casting

3. 메소드

1) Python

• heapq
  • import heapq
  • heapq.nlargest(n, pq) : pq에서 최대값 n개를 list로 반환
  • heapq.nsmallest(n, pq)
  • heapq.heappush(pq, n) : n을 pq에 push
• del vs. remove
  • del : index로 제거 ex. del list[0]
  • remove : 값으로 제거. 가장 첫 번째 것만 ex. list.remove(3)
• zip
  • 두 개의 리스트의 요소를 순서대로 튜플로 묶어줌

  ex.

    item = ['candy', 'coffee']
    price = [500, 1000]
      
    z = zip(item, price)
    print(list(z))
      
    >> [('candy', 500), ('coffee', 1000)]
  

• 이분탐색 : bisect 라이브러리
  • bisect_left(a, x) : 배열 a의 정렬된 상태를 유지하면서 x를 삽입할 수 있는 가장 왼쪽 인덱스를 반환
  • bisect_right(a, x) : 배열 a의 정렬된 상태를 유지하면서 x를 삽입할 수 있는 가장 오른쪽 인덱스를 반환

• 순열/조합 : itertools 라이브러리
  • 순열 : permutations([반복 가능 객체], r)
  • 조합 : combination([반복 가능 객체], r)
  • 중복 순열 : product([반복 가능한 객체], repeat=r)
  • 중복 조합 : combinations_with_replacement([반복 가능한 객체], r)

2) Java

• 이진수
  • Integer.toBinaryString(n); : int n을 2진수로 변환한 값을 String으로 반환
  • Integer.bitCount(n); : int n을 2진수로 변환한 값의 1의 개수를 반환
• 반올림, 올림, 버림
  • 반올림 : Math.round(n);
  • 올림 : Math.ceil(n);
  • 버림 : Math.floor(n);