문제 종류

• 배열이 주어지고, 이걸 순서대로 f개로 나눠야됨. 이 때 f개 구간의 합을 각각 구함. 그 합들의 최댓값이 최소가 되게 하는 문제.
• 백준 2343: 위랑 비슷한 문제임.
  • 1번 블루레이에 1, 2, 3, 4, 5, 2번 블루레이에 6, 7, 3번 블루레이에 8, 9 를 넣으면 각 블루레이의 크기는 15, 13, 17이 된다. 블루레이의 크기는 모두 같아야 하기 때문에, 블루레이의 크기는 17이 된다. 17보다 더 작은 크기를 가지는 블루레이를 만들 수 없다.

특징

• 탐색의 범위를 반씩 줄여가는 방식

  • ex) 크기순으로 정렬되어 있는 길이 N 배열 주어짐(탐색범위: [0,N-1])-> 배열에 x가 있는지 알아내라!

• 풀이 1)

  • 하나씩 확인 하며 찾으면 복잡도 O(N)

• 풀이 2)

  • 탐색범위를 절반씩 줄여가며 찾으면 복잡도 $$O(log_2^N)$$ :N을 2로 최대 몇번 나눌 수 있냐 라는 뜻임

1. 가운데 y를 찾음
2. y= x? y>x? y<x 판단

(이미지 출처: https://wtg-study.tistory.com/28)

• 항상 이분탐색적인 사고하기: left, right, middle을 업데이트하기

• 백준 1946: skyline 찾기가 기본문제인듯

• 배열이 정렬 되어 있어야 x가 있는지 없는지 빨리 찾을 수 있다.

• sort 함수의 복잡도는 nlogn이다. -> 시간복잡도에 걸리면, sort 사용하지 않고, 새로운 리스트에 요소를 뽑아서 추가하는 방식으로 생각하기.

  • 파이썬 sort 함수는 복잡도가 왜 nlogn인가?
    • Timesort 알고리즘을 사용하기 때문-> timesort란 Insert sort+ Merge sort
      • Insert sort: 작은 조각들로 나눠서 각각 정렬: 거의 log(n): 원래 최악의 상황에서 insert sort는 n^2인데,조각이 작으면, O(n)에 가까움
      • merge sort: 정렬된 조각들끼리 합치기
        • logn단계로 이루어짐(logn개로 나눴었으니까)
        • 각 단계별로 병합할 때 n개를 다 보고 합침 -> n
        • 따라서 nlogn임

• 모든 경우의 수를 다 시도해본다.
• from itertools import combinations, permutations,product# 중복순열
• 부분집합은 combinations 사용

• 2003: 배열 주어지고, 배열의 구간의 합이 M이 되는 경우의 수
  • [1 1 1 1] 주어지고, 합이 3이 되는 경우의 수 구하기
• 7795: A의 크기가 B보다 큰 쌍이 몇개나 있는지
  • 

• sub pointer와 main pointer를 한칸씩 옮겨주는거 (복잡도 N)
  • 합이 x보다 크면 sub이동
  • 작으면main 이동
  • 2 포이트 사이 거리가 0이되면 종료
• 그냥 다 더해보면 복잡도 N^2

• 각 상황마다 최적의 선택을 하는 알고리즘

• 11724: 그래프에서 클러스터 갯수 구하기
• 11725: 트리의 간선 정보 주어지고 이걸로 부모 배열 만들기
• 1389: 케빈 베이컨 수 구하기
• 1068: 부모 배열이 주어진다. 만약 k노드를 지웠을 때, 리프 노드의 개수를 구하라.
  • k 노드의 자식, 그 자식의 자식 ...을 지우는데 dfs를 쓸 수 있음
• 2606: K 번 컴퓨터의 바이러스가 감염되었을 때, 감염되는 총 컴퓨터갯수
• 5567: 친구의 친구까지 결혼식 초대 할 때 총 몇명 초대하는지

• 왜함? 현재 노드가 X노드와 연결 되어있나? 밑의 과정을 반복하다가 "도달 가능한 노드 목록"이 비면 종료

• 1. 현재 노드 "방문 완료" 체크
• 2. 현재 노드랑 연결된 노드들을 "도달 가능한 노드목록"에 추가 -> 이 과정에서 최단거리 리스트 업데이트
  • 초기값 -1로 채워놓고, -1이 아니라 이미 채워져있는건 pass
  • -1인 애들을 업데이트 하는건데, 현재 노드의 최단거리 +1로 업데이트
  • 위의 그림에서 4번 업데이트 할 때, 3번의 최단거리 +1이라서 2임.
• 3. "도달 가능한 노드 목록" 중에서 방문 완료 체크 안 된 노드 방문
  • 방문완료 체크 되어있는 애는 "도달 가능한 노드 목록"에서 제거

• 코딩 할 때는 queue(도달 가능한 노드 목록에 추가하는 순간 visit 처리 하면됨)

"한 노드에서출발해서 visit 배열 채우는거 복잡도" : O(N + V)

• 노드 갯수 + 간선 갯수

• 1753: 웨이트가 있는 방향 그래프에서 주어진 시작점에서 모든 정점까지의 최단 경로 구하기
• 1238: 파티가 x마을에서 열릴 때, 노드마다 x로 갔다가 다시 오는데까지 걸리는 최단 시간

밑의 과정을 반복한다.(최단 거리 개발중이 비면 종료)

1. 최단거리 개발중에서 가장 최단 거리 작은거를 최단 거리 확정으로 옮긴다.

• 가장 최단 거리 작은 걸 뽑아야 되니까 우선순위 큐 자료 구조 사용

2. 최단거리 개발중에서 방금 옮긴애랑 인접한 애들의 최단거리를 업데이트한다.(최단 거리 확정에 있는애는 당연히 업데이트 당연히 안함.)

• 밑의 그림에서 최단거리 개발중에 있는 3의 최단거리는 원래 4였는데, 2를 최단거리 확정에 넣을 때, 2+1로 업데이트됨
  • "2의 최단거리 확정" 2 + "2와 3의 거리" 1 =3
  • 만약 기존 값보다 크면 업데이트 안 하면됨

• 1463: 정수 n을 3으로 나누기, 2로 나누기, 1빼기 반복해서 1로 만들기
• 2579: 조건을 만족하며 계단 오르기 게임을 해서 얻을 수 있는 최대값구하기

• 점화식을 만들어서 문제를 푸는 것
  • 정수 n을 1,2,3의 합으로 나타내는 경우의 수

• 2252: 키 순서대로 줄세우기
• 1766: 선수 문제부터 먼저 풀기 + 쉬운 문제 부터 먼저풀기 -> 어려워 보여서 아직 안함(4/23)

• 방향 그래프에서 노드를 1자로 나열할 때, 간선이 모두 왼쪽에서 오른쪽으로 향하도록 나열하는 방법.
• 대학교 커리큘럼 짤 때, 선수과목 고려해서 짜기
• 요리 레시피

• 인접리스트, 수강해야 하는 과목수를 만들기

• 정답배열, 수강 가능 목록 큐로 만들고, 그 다음에 밑의 과정 반복()

• 1. 수강해야 하는 과목수가 0인 애를 먼저 수강한다. 수강하면서 수강 배열에 추가하면됨
• 2. 방금 수강한 과목을 선수 과목으로 가지고 있는 애들의 수강해야하는 과목수를 1씩 뺀다.