바다에 퐁당 Ꙭ̮ ꉂ ◡̈⋆*

0. 주의

- 단순 BST 문제와 & Optimal BST 문제는
- 다루는 자료구조 자체는 BST로 동일하지만, 주목하는 특징이 서로 다르다.
 
(1) BST의 경우 Search가 궁극 목적이다. 즉 Binary Tree 자료구조를 통해 우리가 아는 Binary Search(이진 탐색)을 해내는 게 핵심이다. (ex. 숫자 맞추기 게임에서 Up/Down를 알 수 있다고 하면, 일반적으로 가능한 범위를 반으로 잘라서 정중앙의 숫자를 말하는 것이 가장 효율적 - 점차 정답의 범위를 반씩 좁혀나감) 따라서 각 노드에 저장된 숫자(키/데이터)의 양적 비교가 중요하다.
 
(2) Optimal BST의 경우 
형태는 BST로 똑같다. 그러나 이 경우 노드에 저장된 숫자의 양적 비교가 중요하지 않다. 오히려, 각 노드에 저장된 데이터는 문자열과 같이 더 다양한 데이터가 들어갈 수 있고, 우리가 '양적 비교'의 대상으로 고려해야 할 수치는 데이터 자체의 값이 아니라 메타데이터, 즉 데이터의 '검색 빈도(확률)' 및 각 데이터의 검색을 위한 '함수 호출 횟수'이다. 이들을 계산하여 '평균 검색 시간'을 최소화하는 트리 구조로 업그레이드시키는 것이 핵심이다.
 
따라서 완성된 Optimal BST의 모습을 보면, 1번 이진트리와 같이 숫자가 정렬된 상태가 아니다. 오히려 노드 데이터 자체는 마구잡이로 unsorted되었을 가능성이 높다. 노드의 정렬 기준이, 메타데이터 연산 결과를 Minimize하는 것이어야 하기 때문이다.

1. BST (Binary Search Tree) 이진 탐색 트리 (이진 트리 중 하나)

 
BST: ordered set (순서 가능한 집합)에 속한 원소(key)로 이루어진 Binary Tree
* Binary Tree: 각 노드의 자식의 수가 최대 2개인 트리
- 이진 트리 (Binary Tree: 각 노드의 자식의 수가 최대 2개인 트리) 이다.
- 왼쪽 자식 노드의 값은 자신의 값보다 작아야 한다.
- 오른쪽 자식 노드의 값은 자신의 값보다 커야 한다.
- 서브트리도 BST이다.
- 값이 중복되는 노드는 없다.
 
BST는 그 나름대로 풀어야 할 문제들의 특징이 있다!
 
https://gsmesie692.tistory.com/m/115

2. Optimal Binary Search Tree 최적 이진 검색 트리

→ Dynamic Programming으로 최적화
 

Goal: 평균 검색 시간이 제일 낮은, 가장 효율적인 트리를 찾자

1) 전제: 각 검색어의 검색 빈도(확률)이 다를 수 있다
ex) Crystal = 0.1 / Daisy = 0.2 / Beatrice = 0.3 / John = 0.4
 
2) 평균 검색 시간: 각 검색어의 검색 빈도(확률) p와, 검색을 위한 함수 호출 횟수(시간 복잡도) c의 가중합

- '평균'이라는 말에 마지막에 개수로 나눠야 하지 않는가 하고 생각할 수 있지만, 이미 '확률'을 곱하여 더하므로 그 자체로 평균이 됨
- 각 검색어의 검색 빈도는 상수임 (고정된 Input)
- 따라서 검색어들을 어떤 형태의 BST로 구성하느냐에 따라 c가 달라져서 전체 평균 검색 시간이 달라지는 것!
ex)

왼쪽: (0.1*1) + (0.2*2) + (0.3*2) + (0.4*3) = 2.3
오른쪽: (0.1*4) + (0.2*3) + (0.3*2) + (0.4*1) = 2.0
 

Problem Solving - Algorithm

1. brute-force

: 모든 경우의 수는 2^(n-1) →exponential
 

2. Dynamic Programming

- Bottom up
- 시간 복잡도: n^3 (for문이 3겹)
- Optimal Substructure: 어떤 BST의 왼쪽, 오른쪽 서브트리가 각각 최적 BST여야, 해당 BST도 최적이다. 
- 메모를 위한 Table(Tabular) 2개 & for문만이 필요하다!!
 
노드(Key)가 1~n개 있다고 하자: K_1 ~ K_n
 

1) Table A:

 K_i부터 K_j까지 최적의 BST로 정렬되어있다고 한다면, optimal 평균 검색 시간을 A[i][j]에 메모
- 원소가 하나인 트리의 경우, 원소를 찾는데 비교를 딱 한 번 하므로 A[i][i] = p_i
 

어떤 Optimal BST가 있고 그것의 root가 Key(Node)k라고 하자.
그러면 그것의 left subtree가 최적이고, right subtree 또한 최적이다.
(최적이 아니라면 그걸 cut 하고 더 최적인 subtree로 paste하면, 현재보다 더 좋은 bst가 된다. 그러나 이는 현재가 optimal bst라는 가정에 모순된다)
 
왼쪽 서브 트리의 최적 값은 A[1][k-1]로 메모되어 있음
오른쪽 서브트리의 최적 값은 A[k+1][n]로 메모되어 있음
- 이때 Key k를 트리의 root로 추가해서 전체 트리를 만든다면, 각 서브 트리에서의 비교 횟수는 기존의 비교 횟수에 추가로 한 번만 더 비교를 하면 됨(각 subtree의 노드마다, 검색을 위한 함수 호출 횟수가 1씩 늘어나기 때문임)
- root에 대한 평균 검색 횟수는: 1(depth) x p_root = p_k
→ 둘을 합친 전체 트리의 최적 값은 (A[1][k-1] + p_1 + ... p_k-1) + p_k + (A[k+1][n] + p_k+1 + ... + p_n)

2) Recurrence Relation

수많은 경우의 수 중 최적의 값은 반드시 존재한다(최솟값)

→ 1부터 n까지가 아니라 i번째부터 j번째까지의 key로 일반화

이 식을 이용해서 2차원 table A를 채워나가서, A[1][n] 의 값을 얻으면 그것이 최적 BST의 평균 검색 시간(최적값)이 됨

3) Table R:

R[i][j]:  K_i부터 K_j까지 최적의 BST로 정렬되어을 때, optimal BST의 root의 인덱스 메모 (A 배열에 최적값을 넣는 순간의 k값)
 
- R의 필요성: A만으로 최적값은 구할 수 있지만 최적 BST의 모양을 알 수 없음
- root 인덱스가 저장되어 있으면, root 이후의 노드 인덱스는 어떻게 아는가? Recursion에 의해 채워진다. 즉, 루트가 된 노드가 k번 노드라고 치면 그 왼쪽 서브트리의 루트노드 (즉 k번 노드의 left child)는 R[1][k-1], 오른쪽 서브트리의 루트노드는 R[k+1][n] 이 된다. 이런 식으로 R 배열의 값들을 이용해 재귀함수를 호출해주면서 노드를 만들어나가면 최적 BST가 만들어진다.
 

https://gsmesie692.tistory.com/m/116 
⭐️⭐️

https://hi-guten-tag.tistory.com/73

https://www.acmicpc.net/problem/11279

힙 자료구조 c++로 직접 구현 (힙 라이브러리 x)

#include <iostream>
#define HEAP_SIZE 100000

using namespace std;

int heap[HEAP_SIZE];
int heap_count = 0;

void swap(int*a, int*b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void push(int data){
    heap_count ++;
    heap[heap_count] = data;
    int child = heap_count;
    int parent = heap_count/2;
    while (child>1 && heap[child]>heap[parent]){
        swap(&heap[child], &heap[parent]);
        child = parent;
        parent = child/2;
    }
}

void pop(){
    if (heap_count <= 0) {cout << 0 << "\n";}
    else {
        cout << heap[1] << "\n"; //나중에 Return
        swap(&heap[1], &heap[heap_count]);
        heap_count--;

        int parent = 1;
        int child = 2;
        if ((heap_count > 2) && (heap[child+1]>heap[child])) {
            child ++;}

        while ((child <= heap_count) && heap[parent] < heap[child]) {
            swap(&heap[parent], &heap[child]);

            parent = child;
            child = parent * 2;
            if (child <= heap_count){
                if ((child < heap_count) && (heap[child+1] > heap[child])){
                    child ++;
                }
            }
            else {break;}
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int N;
    cin>>N;
    int input;
    for (int i=0; i<N; i++){
        cin >> input;
        if (input==0){
            pop();
        }
        else {
            push(input);
        }
    }
}

메모

- pointer를 사용한 swap 함수: 주소는 그대로, 해당 주소에 아이템 자체를 바꿈

- pop함수에 유의

특히, 인덱스 다룰 때는 반드시 해당 인덱스 value가 False가 아닌지 조건문으로 먼저 체크해야 함!!!⭐️✌️

- 조건연산자 개념

(condition) ? value_if_true : value_if_false

//condition이 참이면 value_if_true가 반환됩니다.
//condition이 거짓이면 value_if_false가 반환됩니다.

int a = 5;
int b = 8;
int max_value = (a > b) ? a : b;
//max_value에는 b의 값인 8이 할당

- 시간초과 관련 팁

1) ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); 

2) endl; 말고 "\n"

https://www.acmicpc.net/board/view/22716

- 끄적 메모

1. 힙 자료구조 선언: 1차원 int array

2. 힙 원소 삽입(push)

메커니즘

- heap size를 하나 늘림

- 마지막 노드에 삽입

- 반복: (그것의 부모 노드보다 크면 swap)

3. 힙 원소 삭제(pop) (=최대값 꺼내기)

메커니즘

- root 노드의 내용물 임시 저장

- root 노드와 마지막 노드를 swap(주소는 그대로, 내용물만 바꿈, 애초에 swap 함수 입력을 포인터 주소값으로 받음)

- heap size를 하나 줄임

<heapify(=reconstruct)>

: 자식노드가 heap 자료구조에 이미 포함되어 있다면, 부모노드가 더 큰 자식노드보다 커진 상태가 완성될 때까지 swap한다

—> 둘 중에 더 큰 것을 비교! 

- 첫번째 swap을 위해, parent와 child를 지정해주어야 함

: parent = 1, child = parent*2. 

이때 child 중 어느 것이 더 큰지 모르므로 비교한 후 child에 입력.

If child의 idx가 heap_count 이하라면(=해당 child가 heap 자료구조에 포함된 원소이고) swap

이후부터 while문으로 힙 성질 만족할 때까지 반복

- return 저장된 최대값 내용물

4. Swap 함수.

References

https://velog.io/@junhok82/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%9E%99heap

https://velog.io/@kon6443/Data-Structure-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-C-%ED%9E%99

다른 사람 코드

https://kyunstudio.tistory.com/241

- priority queue 라이브러리 사용

https://cherishvert.tistory.com/98

1. 힙 자료구조

0. 개념

- max heap, min heap ((a)트리 형태의 자료구조로 설명하지만, 실제로는  (b)1차원 배열 형태로 표현)

- 인덱스는 위치에 따라 고정되어 있는 느낌,,

왼쪽 자식의 인덱스 = (부모의 인덱스) * 2
오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1
부모의 인덱스 = (자식의 인덱스) / 2
https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

- max heap에서, 부모가 자식보다 크거가 같은 것은 보장되지만, 자식 간 대소비교는 인덱스로 구분하기 어려움. 

2. 주요 쓰임 두 가지:

(1) 힙 정렬 (2) 우선순위 큐

3. Building heap

3-1. 원소 삽입 push : 마지막 노드에 삽입 

→ 힙 성질 만족할 때까지 부모 노드와 swap (아래→위의 Bottom Up 방식)

→ 반복 반복...

3-2. 원소 삭제 pop : max heap에서 원소를 삭제한다는 것은 root node(=최댓값)을 삭제한다는 것 

→ 최댓값을 미리 저장 후,

→ 삭제된 자리(root)에 마지막 노드 A를 가지고 옴 (=마지막 노드와 루트 노드를 swap)

→ 힙 성질 만족할 때까지(=A보다 더 큰 자식노드가 없을 때까지) A를 A의 더 큰 자식노드와 swap 반복...

    : 위→아래의 Top Down 방식

→ 미리 저장해둔 최댓값을 return시키고, heap의 크기를 1 감소시킴

2. 힙 정렬

1-1. 개념

max heap(내림차순)이나 min heap(오름차순) 자료구조를 활용하여 sorting하는 방법

1-2. 강점

- 시간 복잡도가 좋은 편

- 힙 정렬이 가장 유용한 경우는, 전체 자료를 정렬하는 것이 아니라, 가장 큰 값 몇 개만 필요할 때.

1-3. 방법

- 힙은 1차원 배열로 구현됨. 정렬해야 할 n개의 input들을 최대 힙 삽입을 통해 차례대로 삽입함.

(=즉 우리의 input으로 구성된 힙 자료구조를 직접 생성)

- 최대 힙으로 구성된 1차원 배열에서, 차례대로 삭제함 (=root에 있는 최댓값이 나옴)

- 그때마다 최대 힙 트리는 update됨 (힙의 성질 만족)

1-2. 복잡도

- 전체 t-c는 O(nlgn)

- Worst t-c는 omega(nlgn)

- 원소가 중복이 없을 때는 Best t-c가 omega(nlgn)

힙, 힙정렬 개념 야무지게 잘 정리된 페이지 링크 모음 🤩

https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

https://gmlwjd9405.github.io/2018/05/10/algorithm-heap-sort.html

https://www.daleseo.com/python-heapq/

https://docs.python.org/ko/3/library/heapq.html

https://velog.io/@junhok82/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%9E%99heap

문제 개요

- 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 함

- 말이 최대한 몇 칸을 지날 수 있는지 (첫 번째 칸도 포함)

https://www.acmicpc.net/problem/1987

나의 코드

R, C = list(map(int, input().split()))
inputs = []
for _ in range(R):
    inputs.append(list(input()))

from collections import deque

def solution(R,C,inputs):
    max = 1
    # cand = deque([((0,0),inputs[0][0])])
    cand = set()
    cand.add(((0,0),inputs[0][0]))

    dx = [-1,0,0,1]
    dy = [0,-1,1,0]
    
    while cand:
        (x,y), a = cand.pop()
        for k in range(4):
            cx = x + dx[k]
            cy = y + dy[k]
            if cx<0 or cx>R-1 or cy<0 or cy>C-1:
                continue
            else:
                if inputs[cx][cy] not in a:
                    cand.add(((cx,cy), a+inputs[cx][cy]))
                    if len(a+inputs[cx][cy]) > max:
                        max = len(a+inputs[cx][cy])                 
                    
    return max

print(solution(R,C,inputs))

우여곡절

- 구현은 크게 어렵지 않았으나, 그놈의 효율성 문제... ㅎ

- BFS에 deque가 사용된다면 안 된다니! :D set 자료형을 사용해야 했다

why? 중복 이슈

deque의 시간복잡도는 O(1)이 맞음. 그러나 deque를 사용한 코드를 보면 중복값에 대해서도 모두 O(1)의 연산을 하니, 아무리 O(1)이지만 중복값이 수없이 많다면... 효율성 문제 발생. set 자료구조자체가 중복을 허용하지 않기때문에 훨씬 효율적으로 처리하며, 아마 deque에도 중복체크 넣으면 효율적으로 개선될 것.

=>같은 위치에 같은 문자열을 가진 상황을 중복해서 확인할 필요없으니, 같은 값은 같은 객체로 취급하는 집합 자료형을 사용

이라는데...... 이 문제에서 어떤 경우에 중복이 발생하는지 아직 이해하지 못했다.

그냥 visted에서 deque와 set 모두 구현해보고 시간이 더 빠른 걸 택한다는...분도 계셨다.

더 알아봐야겠다.

참고: https://www.acmicpc.net/board/view/81429

- 한번도 방문한 적 없은 알파벳만을 선택한다는 조건(a) 자체가 → visit한 원소는 아예 제외한다는 조건(b)을 포함한다

: 즉, a가 구현되면 b를 별도로 구현할 필요가 없다

: 즉, 방문한 알파벳에 대한 리스트(a)만 체크하면, 이미 방문한 원소에 대한 리스트(visited)를 따로 생성할 필요가 없다

- 참, 저기서 add할 때 a.append(inputs[cx][cy])로 하면 안 된다. for문 전체에 global하게 해당되는 a가 변형되기 때문이다. 슬라이싱 통해 temp로 복제하는 방법도 있지만, 그보다는 그냥 마지막에 cand에 add할 때 '+' 를 사용해주는 게 best!

새로 배운 것

1. 문자열(string)은 자기들끼리 덧셈 연산이 된다.

print('a'+'b') #ab

2. set 자료형

- append가 불가능한 대신 add로!

- pop을 할 경우 임의의 원소가 반환되므로, remove를 사용해야 한다 (나는 여기서... 대강 pop으로 때려맞혀서 이건 수정해야 한답)

https://blockdmask.tistory.com/451

3. time 모듈로 코드 실행시간(시간복잡도) 측정

import time

#코드 하단에 추가
t0 = time.time()
print(time.time() - t0)

4. deque..

Deque(데크)는 double-ended queue 의 줄임말로, 앞과 뒤에서 즉, 양방향에서 데이터를 처리할 수 있는 queue형 자료구조

https://excelsior-cjh.tistory.com/entry/collections-%EB%AA%A8%EB%93%88-deque

https://www.acmicpc.net/problem/2206

나의 코드

inputs=[]
[N,M] = list(map(int,input().split()))

for _ in range(N):
    inputs.append(list(map(int,input())))

from collections import deque

def solution(N, M, inputs):
    if N==1 and M==1:
        return 1

    cand = deque()
    visited = [[[0,0] for _ in range(M)] for _ in range(N)] #3차원의 visited array
    cand.append(((0,0),0))
    visited[0][0][0] = 1

    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]

    while cand:
        ((x,y),i) = cand.popleft()
        for k in range(4):
            cx = x + dx[k]
            cy = y + dy[k]
            if cx<0 or cx>N-1 or cy<0 or cy>M-1:
                continue
            else:
                if inputs[cx][cy] == 0 and visited[cx][cy][i]==0:
                    if cx == N-1 and cy == M-1:
                        return visited[x][y][i] + 1
                    cand.append(((cx,cy),i))
                    visited[cx][cy][i] = visited[x][y][i] + 1

                elif inputs[cx][cy] == 1 and i==0:
                    cand.append(((cx,cy),1))
                    visited[cx][cy][1] = visited[x][y][0] + 1

    return -1

print(solution(N,M,inputs))

1. BFS + Depth !!를 효율적으로 구현

 visited[cx][cy][i] = visited[x][y][i] + 1

2. visited를 두 유형으로 나누어야 한다(visited array를 3차원으로 표현) → 벽을 부수기 전 & 벽을 부순 후.

- 이유:

결국 방문배열이란 것은, bfs에서 '모든 경우'를 살펴보며 진행할 때, 같은 행위를 두번하면 비효율적이니 그걸 막기 위해 사용합니다.

따라서 방문배열은 '모든 경우'를 나타낼 수 있어야 합니다. 일반적인 bfs 문제에서 모든 경우는 결국 '이 위치에 이미 왔었다' 입니다.

따라서 그냥 2차원 방문배열로 나타내면 되는거구요.

이 문제에서 모든 경우는 말로 설명하자면 '해당 위치에 벽을 부순 상태로 이미 왔었거나, 해당 위치에 아직 벽을 부수지 않은 상태로 이미 왔었다.' 정도가 되겠습니다.

따라서 이걸 표현하기 위해 3차원 배열로 나타낸거구요.

이런식으로 모든 경우를 나타낼 수 있는 방문배열을 만들지 않을 경우 다음과 같은 문제가 발생합니다.

출처: https://www.acmicpc.net/board/view/67446

 - 추가 설명:

모든 작업을 한 번의 BFS 탐색을 통해 처리해야했기 때문에, 최적의 벽을 '탐색'하는 것보다는 '기록'하는 방식이 필요했다.

그리고 3차원 배열을 통해서 이 문제를 해결할 수 있었다.

visited에는 이미 우리에게 친숙한 2차원 배열의 각 인덱스 [x][y]뿐 아니라 w라는 값을 하나 더 만들어서 (x, y)까지 오는 과정에서 벽을 뚫은 경우와 그렇지 않고 온 경우를 모두 기록해준다. (각각 1번 인덱스와 0번 인덱스에 기록)

다시 말해, visited[x][y][0]에 (x, y)까지 벽을 뚫지 않고 왔을 때 걸린 거리(시간)을 기록해준다.

반대로, visited[x][y][1]에는 (x, y)까지 오는 데 벽을 한 번이라도 뚫고 온 경우 걸린 거리(시간)을 기록해준다.

출처: https://seongonion.tistory.com/107

추가: https://nahwasa.com/entry/BFS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%84%88%EB%B9%84-%EC%9A%B0%EC%84%A0-%ED%83%90%EC%83%89-%EB%B0%B0%EC%97%B4-BFS-%EA%B7%B8%EB%9E%98%ED%94%84-BFS

3. 이하 코드는 항상 요긴하게 씁사..

        for k in range(4):
            cx = x + dx[k]
            cy = y + dy[k]
            if cx<0 or cx>N-1 or cy<0 or cy>M-1:
                continue

- 배운 점: BFS문제 다 똑같지 않다. 변형 테크닉이 어렵고, 익숙해지면 아이디에이션 생각보다 간단하다.

나의 방황 기록

초기 코드1: Depth를 2 type으로 구분하지 않고 1 type으로 몰아갔다..

→ 당연히 틀림 (초반에는 경로가 비효율적이더라도 벽을 아직 부수지 않아서 최종 목적지까지 다다를 수 있는 경로가 배제됨)

inputs=[]
[N,M] = list(map(int,input().split()))

for _ in range(N):
    inputs.append(list(map(int,input())))

from collections import deque

def solution(N, M, inputs):

    cand = deque()
    cand.append(((0,0),0))
    inputs[0][0] = 1

    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]

    while cand:
        ((x,y),i) = cand.popleft()
        for k in range(4):
            cx = x + dx[k]
            cy = y + dy[k]
            if cx<0 or cx>N-1 or cy<0 or cy>M-1:
                continue
            else:
                if inputs[cx][cy] == 0:
                    inputs[cx][cy] = inputs[x][y]+1
                    if cx == N-1 and cy == M-1:
                        return inputs[cx][cy]
                    cand.append(((cx,cy),i))
                elif inputs[cx][cy] == 1:
                    if i == 0:
                        inputs[cx][cy] = inputs[x][y]+1
                        cand.append(((cx,cy),1))
    
    return -1

print(solution(N,M,inputs))

초기 코드2: visited 내역을 queue의 각 원소마다 포함해줬다

→ 예상한 대로 시간초과... 애초에 이렇게 풀 수 있는 문제 거의 없음

→ 조건 추가된 depth 계산은, 무조건 이 방식 말고 다른 방식을 떠올려야 함

(ex. visited array를 별도로 생성하여 0->1->2.. 이런 식의 표현을 베이스로 깔거나(이후 변형) / 조건 잘 따져서 global queue(set)을 생성하거나 등등. )

inputs=[]
[N,M] = list(map(int,input().split()))

for _ in range(N):
    inputs.append(list(map(int,input())))

from collections import deque

def solution(N, M, inputs):
    if N==1 and M==1:
        return 1
    
    cand = deque()
    cand.append(((0,0),0,[(0,0)]))

    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]

    while cand:
        ((x,y),i,visit) = cand.popleft()
        for k in range(4):
            cx = x + dx[k]
            cy = y + dy[k]
            if (cx<0 or cx>N-1 or cy<0 or cy>M-1) or ((cx, cy) in visit):
                continue
            else:
                if inputs[cx][cy] == 0:
                    if cx == N-1 and cy == M-1:
                        return len(visit) + 1
                    cand.append(((cx,cy),i, visit+[(cx,cy)]))
                elif inputs[cx][cy] == 1:
                    if i == 0:
                        cand.append(((cx,cy),1,visit+[(cx,cy)]))
    
    return -1

print(solution(N,M,inputs))

https://school.programmers.co.kr/learn/courses/30/lessons/43238

문제 요약

목표: 총 심사 시간 최소화.

Input

n: 입국 심사 기다리는 사람 수 (엄~~~~청 큼.)

Times: ‘각 심사관이 한 명을 심사하는 데 걸리는 시간’이 담긴 배열 (각 시간이 엄청 큼) (사람 수는 10만.)

e.g) 6, [7,10]

Return

심사 총 시간.

e.g) 28

한 심사대 - 한 명

가장 앞에 있는 사람: 비어 있는 심사대에서 심사 받기.

더 빨리 끝나는 심사대 있으면: 기다렸다가 그곳에서 심사 받기.

*20분이 되었을 때, 두 번째 심사대가 비지만 6번째 사람이 그곳에서 심사를 받지 않고 1분을 더 기다린 후에 첫 번째 심사대에서 심사를 받으면 28분에 모든 사람의 심사가 끝납니다.

예제

(7) 끝난 사람 1

(10) 끝난 사람 2

(14) 끝난 사람 3

(20) 끝난 사람 4

(21) 끝난 사람 5

(28) 끝난 사람 6

(30) 끝난 사람 6

정답은 각 시간의 배수 중 하나.

• 7 (<=7*1, 10*0) : 1
• 14 (<=7*2, 10*1) : 3
• 21 (<=7*3, 10*2): 5
• 28 (<=7*4, 10*2): 6

• 10 (<=10*1, 7*1) : 2
• 20 (<=10*2, 7*2) : 4
• 30 (<=10*3, 7*4) : 7 (6)
• 40 (<=10*4, 7*5) : 9 (6)

times의 각 원소의 배수들을 모두 나열.

각 배수를 우측의 부등호처럼 표현하고 곱한 수의 합이 n이상인 경우 중

가장 작은 배수값을 찾아냄.

이때 합이 n이상이면 max(합, n)으로 간주.

28 // 7 = 4

28 // 10 = 2

내 코드

def solution(n, times):
    
    times.sort()
    start = times[0]
    end = times[0]*n
    cand = end #candidate: 정답 후보
    
    while start <= end: #이분탐색은 start, end를 지정해주어야 함
        mid = (start+end) // 2 #start, end를 바탕으로 mid 생성

        if sum([mid//i for i in times]) < n:
            start = mid + 1
        elif sum([mid//i for i in times]) > n:
            cand = mid
            end = mid - 1
        else:
            if start==end: #해당 조건 없으면 무한루프
                return start
            cand = mid
            end = mid
    
    #반복문 종료되었을 때, 반복문의 최종 candidate값으로 정답을 반환
    
    return cand