Reference

• 코업프

Why Coding Test

• Computational Thiking을 할 수 있는지를 보는 것이다.
• 이는 Time, Space Complexity를 이해하고 있는지를 확인할 수 있고, 이러한 것이 가능한 개발자만이 Scalable한 개발을 할 수 있다고 판단하고 있다.

Array

• random access가 가능한 연속적인 메모리 구조의 자료구조이다.
• 보통 아래 문제들로 구성된다.

Sorting

• O(nlogn)을 추구한다.
• Stable, Unstable Sorting 형태로 C++ 같은 경우 라이브러리가 지원된다.
• Stable : Sorting 전의 Order가 유지되는 것을 의미한다.
• Unstable : 위와 반대인 Sorting 상태이다.

Key	Value	=> Stable Sorting	Key	Value
a	4		d	1
b	3		e	1
c	2		f	1
d	1		c	2
e	1		b	3
f	1		a	4

• 위 처럼 Stable은 d,e,f의 값이 같음에도 Sorting 전의 순서를 따른다.
  • Unstable은 Random으로 배치되는 것을 말한다.

#include <iostream>
#include <vector>
#include <algorithm>

struct Employee
{
    int age;
    char name;
};

bool operator<(const Employee &lhs, const Employee &rhs)
{
    return lhs.age < rhs.age;
};

int main()
{
    std::vector<Employee> v{
        {200, 'A'},
        {200, 'B'},
        {200, 'C'},
        {200, 'D'},
        {200, 'F'},
    };

    for (int i = 9; i < 30; i++)
        v.emplace_back(Employee{i, 'Z'});

    std::stable_sort(v.begin(), v.end());

    for (const Employee &e : v)
        std::cout << e.age << ", " << e.name << std::endl;
}

...
25, Z
26, Z
27, Z
28, Z
29, Z
200, A
200, B
200, C
200, D
200, F

• Stable

...

for (int i = 9; i < 30; i++)
        v.emplace_back(Employee{i, 'Z'});

    std::sort(v.begin(), v.end());

    for (const Employee &e : v)
        std::cout << e.age << ", " << e.name << std::endl;

25, Z
26, Z
27, Z
28, Z
29, Z
200, F
200, D
200, C
200, B
200, A

• Unstable

Search

• O(n)을 기본적으로 추구한다.
• Sorting 되어있는 자료구조의 경우 Binary Search로 O(logn)을 추구한다.

2-d, N-d

• 보통 그래프, 트리 형태로 주어지므로 배열과는 연관만 있다고 보면된다.