[코테 문제 유형 정리]

1. 공유기 설치

- 문제 : N개의 집이 있고(각 좌표가 주어짐), C개의 공유기가 있을 때 C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램?

- 알골: 이분탐색 

- 추가 해설:

# min_distance = 1, max_distance = N번 집 좌표 - 첫번째 집 좌표

# mid_distance로 min과 max의 중간값을 가지고, 1번 집부터 mid_distance거리만큼 공유기를 설치했을 때 설치가능한 공유기 개수 확인 -> C개보다 크면 거리가 넘 짧은 것이므로 max 값 줄이고, C개보다 적으면 answer와 값 비교 후 min값 크게 함

 

 

2. 튜플

- 문제: n개이면서 중복 원소가 없는 튜플 (a1,a2,..an)이 주어졌을 때 집합은 {a1}, {a1,a2}, {a1,a2,a3|으로 만들 수 있다. 집합이 주어졌을 때 튜플을 반환하라 

- 알골 : 구현 (set)

- 추가해설:

   #집합을 길이 순으로 정렬하고 나면 i-1번째와 i번째 집합에서 없는 문자가 a[i]임 => set으로 찾음 

   # 차집합 : int( list(set(list[i]) - set(list[i-1]) ) ) 

 

 

3, 캐시

- 문제 : 캐시의 크기가 주어지고 각 도시들이 주어졌을 때, 해당 도시가 캐시에 있었다면 (cache hit)1초가 걸리고, 캐시에 없었다면 가장 예전에 들어온 도시를 지우고 해당 도시를 캐시에 넣는 과정에서 5초가 걸린다. 도시배열이 주어졌을 때 총 실행 시간은?

- 알골: 구현 

- 추가해설: 이번에 탐색할 도시가 cache에 있으면 cache에서 지운 후 마지막에 붙이기, 이번에 탐색할 도시가 cache에 없으면 맨 앞에다 city를 넣는다. 이 때 무조건!!!!!이전 cache내 데이터를 지우는 게 아니라!!! 붙이고 나서 그 크기가 cache size보다 클때만 pop한다!!!!!