B.U.D 기술

사진 작성자Cookie the Pom가 Unsplash
최적화 알고리즘은 새로운 소프트웨어 엔지니어가 습득해야 할 중요한 기능인데 특히 기술 면접에서 그렇다.이것은 내가 여전히 열심히 공부하고 향상시키는 기술이다.최근 나는 가일 라크맨 맥도웰의 코딩 해독 인터뷰라는 책을 읽고 있다.나는 작가가 언급한 몇 가지 유용한 기교를 만났다.제가 알아본 기술 중 하나는 B.U.D입니다. 이 기술은 다음과 같습니다.

B 오트런크스

필수 작업

D 반복 작업

BUD의 기본 요점은 효율이 낮은 해결 방안이 시간을 낭비하는 세 가지 가장 흔히 볼 수 있는 임무를 대표한다는 것이다.한 가지 방법은 모든 것을 검사하기 위해 너의 만력 알고리즘을 두루 훑어보는 것이다.그리고 개선될 때까지 복구에 전념하세요.따라서 모든 문제를 상세하게 분석하고 BUD 기술을 사용하는 알고리즘에서 이를 식별하여 해결 방안을 최적화하는 데 도움을 주는 방법을 설명하겠습니다.

병목

병목은 알고리즘에서 운행 속도를 크게 낮추는 부분이다.예를 들어 다음과 같은 문제를 해결해야 합니다.
문제: 두 개의 수조가 같은 다른 원소를 가지고 있다.어떻게 공공 원소의 수량을 계산합니까?
무리한 방법: 그룹 A의 모든 원소를 추출하고 그룹 B를 옮겨다니며 현재 원소가 포함되어 있는지 확인합니다.
이것은 대체로 O(A*B)가 운행할 때와 같다.이 예에서 병목은 B입니다. 우리는 A의 모든 요소를 검사해서 B의 모든 요소를 포함하는지 확인합니다. 동작은 O (B) 입니다.이런 중복은 우리의 운행 시간에 부정적인 영향을 끼칠 수 있다.이 병목을 인식한 후에 우리는 이런 유형의 조작을 실행하는 가장 좋은 방식을 고려해야 한다.낱개로 찾아보는 게 어때요?
병목에 대한 최적화: 그룹 B의 모든 요소를 해시 테이블에 추가합니다.그리고 모든 요소가 해시표에 존재하는지 확인하십시오.
이렇게 하면 운영 시간을 O(A+B)로 줄여 병목 현상에서 벗어날 수 있습니다.

불필요한 일

불필요한 업무에 대해 우리는 기본적으로 다른 필요하지 않은 조작을 찾아서 알고리즘을 재구성하고 작은 변경을 해서 더욱 좋은 최적화를 할 것이다.해독 프로그래밍 면접서에서 다음과 같은 문제 예시를 선택하자.
문제: 출력 방정식 a≥+b≥=c≥+d≥의 모든 정수 풀이, 그 중에서 a, b, c와 d는 1과 1000 사이의 정수이다. — 코드 해독 면접
강력 방법: 다음 Javascript 예와 같이 여러 개의 네스트된 for 루프를 사용하기만 하면 됩니다.

for (let a = 1; 1 < 1000; a++) {
    for (let b = 1; 1 < 1000; b++) {
        for (let c = 1; 1 < 1000; c++) {
            for (let d = 1; d < 1000; d++) {
                if (Math.pow(a, 3) + Math.pow(b, 3) == 
                    Math.pow(c, 3) + Math.pow(d, 3)) {
                    console.log(a, b, c, d)
                }
            }
        }
    }
}
// Note: I don't suggest running this code in you're console

이 코드는 우리의 문제를 해결했지만, 불필요한 작업량을 사용했다.최적화를 위해 우리는 해결 방안을 찾은 후 즉시 순환을 깨뜨릴 수 있다.이런 상황에서 우리는 d의 내부 순환을 깨뜨릴 것이다.
불필요한 작업에 최적화:

for (let a = 1; 1 < 1000; a++) {
    for (let b = 1; 1 < 1000; b++) {
        for (let c = 1; 1 < 1000; c++) {
            for (let d = 1; d < 1000; d++) {
                if (Math.pow(a, 3) + Math.pow(b, 3) == 
                    Math.pow(c, 3) + Math.pow(d, 3)) {
                    console.log(a, b, c, d)
                    break // solution found, break from loop 
                }
            }
        }
    }
}

이것은 우리의 코드를 개선하는 데 거의 도움이 되지 않는 아주 작은 최적화일 수도 있지만, 만약 당신이 계속 이렇게 작은 조정을 한다면, 이것은 당신의 알고리즘의 전체 운행 시간에 영향을 줄 수 있다.

복제품

여기서, 우리는 이전과 같은 예시를 사용하여 중복된 일을 찾을 것이다.
문제: 출력 방정식 a≥+b≥=c≥+d≥의 모든 정수 풀이, 그 중에서 a, b, c와 d는 1과 1000 사이의 정수이다. — 코드 해독 면접
중복 작업에 대한 최적화: 이것도 해시표를 사용하여 최적화할 수 있는 문제이다.모든 c, d 쌍을 하나의 그룹에 추가합니다.그리고 그것을 값으로 해시 맵에 저장합니다.

const map = {}
for (let c = 1; c < 1000; c++) {
    for (let d = 1; d < 1000; d++) {
        let result = Math.pow(c, 3) + Math.pow(d, 3)
        map[result] = [c, d]
    }
}

for (let a = 1; a < 1000; a++) {
    for (let b = 1; b < 1000; b++) {
        let result = Math.pow(a, 3) + Math.pow(b, 3)
        let list = map[result]
        for (const pair of list) {
            console.log(a, b, pair)
        }
    }
}

우리는 여러 개의 플러그인 for 순환을 실행함으로써 우리의 일을 반복한다는 것을 깨달았다.이 문제를 해결하기 위해서, 우리는 일을 두 개의 독립된 끼워 넣는 순환으로 나눌 것이다.첫 번째 플러그인 순환 계산 c≥+d≥의 결과를 하쉬 플러그인의 c, d 대수 그룹에 비추십시오.두 번째 플러그인 순환은 같은 계산을 하지만, a, b 쌍에 대해서는 인쇄 결과일 뿐입니다.이렇게 하면 이전 O(n²)에서 O(n²)로 운영 시간이 감소합니다.⁴).

리소스

Cracking the Coding Interview book

Cracking The Coding Interview

최초는 2021년 6월 26일https://coderjay06.github.io에 발표됐다.