Data Structures and Algorithms

Understading Computation requirement in Coding Test

You might have experienced runtime failure because of computation speed limitation in Coding test problem, as just like me. This can certainly be attributed to the lack of your knowledge of the relationship between "given computation cacpability" and "time limitation".

Types of DSA to learn

You must learn the concenpts below before you actully start solving problems [1]:

1. basics (brute-force, sorting, data structures)
2. Dynamic programming
3. Greedy Algorithm
4. Math (Prime Number, GCD, Log)
5. Backtracking
6. BFS, DFS
7. Simulation
8. Binary Search
9. Two Pointers
10. Single Source Shortest Path Problem
11. Union Find
12. Minimum Spanning Tree

Refereces

1. 성목, (2022), Tistory, "코딩테스트를 준비하는 효율적인 방법".

Appendix A. Greatest Common Division

Recurive version

public static int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

Using While loop

public static int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}