1일 차: 보고서 수리

Problem

Code

문제 1에 대한 연습

이 문제의 경우 한 줄에 하나씩 숫자 목록이 주어지고 합계가 2020인 두 항목을 찾도록 요청받습니다. 두 숫자가 있으면 곱하여 답을 얻습니다.

순진한 접근

고전적인 합계 2 문제를 해결하기 위한 순진한 접근 방식은 중첩 검색을 사용하여 원하는 양(2020)에 추가되는 모든 숫자 조합을 테스트하는 것입니다.

let mut v: Vec<i32> = Vec::new();

// load data
let input = File::open("./input.txt").unwrap();
let reader = BufReader::new(input);

for line in reader.lines() {
    let integer = line.unwrap().parse::<i32>().unwrap();
    v.push(integer);
}

// for every number in the vector, check if any other value in the vector sums
// with that number to equal 2020. If a pair of numbers is found, print them
// and the answer.

for num1 in &v {
    for num2 in &v {
        if num1 + num2 == 2020 {
            println!{"Values: {} and {}", num1, num2};
            println!{"Answer: {}", num1 * num2};
            break
        }
    }
}

이 접근 방식은 시간이 매우 비효율적입니다. 입력의 모든 추가 고유 숫자에 대해 이 솔루션은 벡터의 모든 항목에 대해 추가 계산 단계를 추가합니다. 이 솔루션의 시간 복잡도는 O(n2)입니다.

최적의 접근

보다 효율적인 방법 중 하나는 이진 검색 알고리즘을 사용하는 것입니다.

먼저 사용할 이진 검색 알고리즘이 필요합니다.

fn binary_search(vector: &Vec<i32>, len: usize, target: &i32) -> Option<bool> {
    // set the low and high indices
    let mut low: i8 = 0;
    let mut high: i8 = len as i8 -1;

    while low <= high {
        // find the mid point by floor dividing the sum of the high and low
        let mid = ((high - low) / 2) + low;
        let mid_index = mid as usize;
        let val = vector[mid_index];

        // return the index of the number if it is found, or set the high and
        // low to reduce the search space
        if val == *target { return Some(true); }

        if val < *target { low = mid + 1; }
        if val > *target { high = mid - 1; }
    }
    Some(false)
}

이제 이진 검색 구현이 있으므로 이를 사용하여 2020까지 합산되는 목록의 각 항목에 대한 가수를 검색할 수 있습니다.

let mut v: Vec<i32> = Vec::new();

// load data
let input = File::open("./input.txt").unwrap();
let reader = BufReader::new(input);

for line in reader.lines() {
    let integer = line.unwrap().parse::<i32>().unwrap();
    v.push(integer);
}

for num1 in &v {
    //  calculate the value we would need to sum with num1 to get to 2020.
    let target = 2020 - num1;

    // check if that item is in the vector
    let answer = binary_search(&v, v.len(), &target);

    if answer.unwrap() == true {
        println!{"Values: {} and {}", num1, target};
        println!{"Answer: {}", num1 * target};
    }
}

이 기능은 문제에 대한 입력의 크기에 관계없이 합리적인 시간 내에 첫 번째 문제에 대한 답변을 제공합니다. 시간 복잡도는 N*log(N)입니다.

그러나 더 간단하고 똑같이 효율적인 옵션은 세트를 사용하는 것입니다.

    println!("\n Puzzle 1: \n");

    let mut set: HashSet<i32> = HashSet::new();

    let input = File::open("./input.txt").unwrap();
    let reader = BufReader::new(input);

    // I decided to use a set because it eliminates duplicate values and
    // reduces the iteration and accessing times to roughly 0.

    for line in reader.lines() {
        let integer = line.unwrap().parse::<i32>().unwrap();

        set.insert(integer);
    }

    // iterate over all of the items in the set checking if the second value
    // for the solution is in the set. If so, print and exit.
    for number in &set {
        let target: i32 = 2020 - number;

        if set.contains(&target){
            println!{"Values: {} and {}", number, target};
            println!{"Answer: {}", number * target};
            break;
        }
    }

순진한 접근 방식처럼 보이지만 세트를 사용하면 즉각적인 항목 액세스와 O(n)의 시간 복잡도가 가능합니다.

문제 2

첫째 날의 두 번째 문제는 첫 번째 문제와 매우 유사합니다. 유일한 차이점은 합이 2020인 세 개의 덧셈을 반환하는 솔루션을 찾아야 한다는 것입니다. 마지막 문제와 마찬가지로 답은 세 숫자의 곱입니다.

순진한 접근

문제 2에 대한 이 순진한 솔루션은 문제 1에 대한 순진한 솔루션과 거의 동일합니다. 유일한 차이점은 이제 솔루션의 검색 부분에 추가 루프를 추가한다는 것입니다.

let mut v: Vec<i32> = Vec::new();

// load data
let input = File::open("./input.txt").unwrap();
let reader = BufReader::new(input);

for line in reader.lines() {
    let integer = line.unwrap().parse::<i32>().unwrap();
    v.push(integer);
}

// for every number in the vector, check if any other value in the vector
// sums with that number to equal 2020. If a pair of numbers is found, print
// them and the answer

for num1 in &v {
    for num2 in &v {
        for num3 in &v {
            if num1 + num2 + num3 == 2020 {
                println!{"Values: {}, {}, and {}", num1, num2, num3};
                println!{"Answer: {}", num1 * num2 * num3};
                process::exit(0x0100);
            }
        }
    }
}

이것은 문제 1의 순진한 솔루션보다 훨씬 더 느린 알고리즘입니다. 추가 루프로 인해 이 솔루션의 시간 복잡도는 이제 O(n3)입니다. 아야.

최적의 접근

이 문제에 대한 최적의 솔루션은 문제 1과 유사합니다. 그러나이 솔루션의 경우 목록의 모든 항목을 반복하는 루프를 추가한 다음 문제 하나의 솔루션을 실행하여 다른 두 숫자를 찾습니다. 이는 알고리즘의 시간 복잡도를 크게 증가시키지만 비교적 비슷한 수준의 코딩 복잡도를 가진 다른 솔루션이 없습니다.

let mut set: HashSet<i32> = HashSet::new();

let input = File::open("./input.txt").unwrap();
let reader = BufReader::new(input);

for line in reader.lines() {
    let integer = line.unwrap().parse::<i32>().unwrap();

    set.insert(integer);
}

// While this implementation uses nested for loops, it is only O(n^2)
// in the worst case and is still the best solution to this problem.
// In terms of space complexity, it could be more efficient if I didn't
// copy all of the data into a set first, but I valued speed more than
// space in this instance.

for number1 in &set {
    for number2 in &set {
        let target: i32 = 2020 - number1 - number2;

        if set.contains(&target){
            println!{"Values: {}, {}, and {}", number1, number2, target};
            println!{"Answer: {}", number1 * number2 * target};
            process::exit(0x0100);
        }
    }
}