1. 자료구조(Data Structure)

• 자료 구조는 서비스나 어플리케이션에서 필요한 데이터를 메모리에 구조적으로 잘 정리해서 담아두고, 관리하고 최종적으로 가장 효율적인 방식으로 필요한 데이터에 빠르게 접근하고 필요한 수정 삽입 삭제를 할 수 있도록 도와준다.

• 서비스에서 클라이언트에게 데이터를 제공하거나 어플리케이션에서 사용자에게 필요한 데이터를 보여주거나 수정 할 때 효율적으로 일을 처리하기 위해서는 기능에 적합한 자료구조를 사용하는 것이 중요하다.

  • 1) 배열(Array): 백엔드 개발자는 배열을 사용하여 데이터를 순차적으로 저장하고 접근할 수 있다. 예를 들어, 사용자의 정보를 배열에 저장하고 해당 사용자에 대한 검색, 추가, 삭제 작업을 수행할 수 있다.

    • 검색: 선형 탐색(Linear Search) 알고리즘을 사용하여 배열을 순차적으로 탐색하며 원하는 요소를 찾는다. 이 알고리즘의 시간 복잡도는 O(n)이다.
    • 읽기: 배열에서 특정 인덱스에 접근하여 해당 요소를 반환한다. 이 작업은 상수 시간인 O(1)에 수행된다.
    • 삽입: 배열의 특정 위치에 새로운 요소를 삽입하기 위해서는 삽입 위치 이후의 요소들을 이동시켜야 한다. 이 작업은 최악의 경우 배열의 크기에 비례하는 O(n)의 시간 복잡도를 갖는다.
    • 삭제: 배열에서 특정 위치의 요소를 삭제하기 위해서는 삭제 위치 이후의 요소들을 이동시켜야 한다. 이 작업은 최악의 경우 배열의 크기에 비례하는 O(n)의 시간 복잡도를 갖는다.

  • 2) 큐(Queue)와 스택(Stack): 큐와 스택은 데이터의 삽입과 삭제에 특화된 자료구조이다. 백엔드 개발자는 큐와 스택을 사용하여 요청이나 작업을 관리할 수 있다. 예를 들어, 웹 서버에서 요청을 처리하는 작업을 큐에 추가하고, 순차적으로 처리하여 공정한 분배를 할 수 있다. 또는 로그 메시지를 스택에 저장하여 나중에 역순으로 출력할 수 있다.

    • 검색: 큐와 스택은 선형 구조이므로, 요소를 찾기 위해서는 순차적으로 탐색해야 한다. 따라서 검색 작업의 시간 복잡도는 큐와 스택의 크기에 비례하는 O(n)이다.
    • 읽기: 큐와 스택에서 가장 앞이나 뒤의 요소를 반환하기 위해서는 상수 시간인 O(1)이 소요된다.
    • 삽입: 큐의 경우, 새로운 요소를 큐의 뒤에 추가하는 경우 상수 시간인 O(1)이 소요된다. 스택의 경우, 새로운 요소를 스택의 맨 위에 삽입하는 것도 상수 시간인 O(1)이 소요된다.
    • 삭제: 큐와 스택에서 삭제 작업은 가장 앞이나 뒤에 있는 요소를 제거하는 것으로, 상수 시간인 O(1)이 소요된다.

  • 3) 해시 테이블(Hash Table): 해시 테이블은 키-값 쌍을 저장하는 자료구조로, 백엔드 개발자가 빠른 검색과 삽입을 위해 사용할 수 있다. 예를 들어, 사용자의 ID와 해당 사용자 정보를 해시 테이블에 저장하여 효율적인 검색과 업데이트를 수행할 수 있다.

    • 검색: 해시 테이블에서의 검색은 평균적으로 상수 시간인 O(1)이 소요된다. 하지만 해시 충돌(Collision)이 발생하는 경우 선형 탐색이 필요하므로 최악의 경우에는 O(n)의 시간 복잡도를 가질 수 있다.
    • 읽기: 해시 테이블에서는 키를 해시 함수를 통해 변환하여 해당 키에 대응하는 버킷으로 접근한다. 이 작업은 상수 시간인 O(1)에 수행된다.
    • 삽입: 해시 테이블에 새로운 키-값 쌍을 삽입하기 위해서는 해당 키를 해시 함수를 통해 변환하여 적절한 버킷에 저장한다. 이 작업은 평균적으로 상수 시간인 O(1)이 소요된다.
    • 삭제: 해시 테이블에서 특정 키를 가진 요소를 삭제하기 위해서는 해당 키를 해시 함수를 통해 변환하여 해당 버킷을 탐색하고 삭제한다. 이 작업은 평균적으로 상수 시간인 O(1)이 소요된다.

  • 4) 트리(Tree): 트리는 계층적인 구조를 가진 자료구조로, 백엔드 개발자가 데이터를 구조화하고 효율적으로 탐색하기 위해 사용할 수 있다. 예를 들어, 조직도를 표현하기 위해 트리 자료구조를 사용할 수 있다. 각 노드는 직원의 정보를 저장하고 자식 노드로는 부서 또는 하위 직원을 가질 수 있다.

    • 검색: 이진 탐색 트리(Binary Search Tree)에서의 검색은 트리의 높이에 비례하는 시간이 소요된다. 균형 잡힌 이진 탐색 트리인 AVL 트리나 레드-블랙 트리(Red-Black Tree)를 사용하면 평균적으로 O(log n)의 시간 복잡도를 갖는다.
    • 읽기: 트리에서 특정 노드를 읽는 작업은 해당 노드로의 경로를 탐색하며 수행되므로, 트리의 높이에 비례하는 시간이 소요된다. 따라서 이진 탐색 트리의 경우 O(log n)의 시간 복잡도를 갖는다.
    • 삽입: 트리에 새로운 노드를 삽입하기 위해서는 탐색 후 삽입 위치를 결정하고, 새로운 노드를 생성하여 연결해야 한다. 이 작업은 트리의 높이에 비례하는 시간이 소요된다.
    • 삭제: 트리에서 특정 노드를 삭제하기 위해서는 삭제할 노드의 자식 노드와 부모 노드를 재조정해야 한다. 이 작업은 트리의 높이에 비례하는 시간이 소요된다.

• 따라서, 아래 4가지 작업에 맞춰 각각의 자료 구조에 대한 이해도가 필요하다.

  • 1. 검색 / 2.읽기 / 3.삽입 / 4.삭제

• (공부방법) 자료 구조 안의 데이터 순서가 보장되는 지, 중복된 데이터가 들어갈 수 있는지, 검색이나 수정 할 때 얼마나 효율적인지를 중점으로 공부하는 것이 좋다.

2. 알고리즘(Algorithm)

• 알고리즘이란 제한된 공간과 시간 안에서 데이터를 어떻게 처리 할 것인지를 정해놓은 로직이다. 즉 주어진 인풋으로 정의된 계산을 수행한 다음에 아웃풋 결과값을 내는 것을 말한다.
• Big O는 동일한 알고리즘의 로직으로 인풋의 사이즈가 점점 커질 수록 시간이 얼마나 더 걸리느냐를 정의한 시간 복잡도를 나타내는 방법이다.
• 따라서 알고리즘은 주어진 데이터를 검색하거나 정렬 또는 총점을 구하는 등의 다양한 계산을 할 수 있는 것을 말한다.
• (공부 방법) 인풋 사이즈가 커질 수록 Big O가 어떻게 변화하는지, 공간과 시간 복잡도는 어떠한지 , 어떤 자료구조를 이용해서 이 알고리즘을 사용하는 것이 좋은 지를 중점으로 공부하는 것이 좋다.

3. 코딩 테스트

• 회사는 코딩 테스트를 통해 지원자를 평가 할 수 있다.

  • 기술적 능력 평가: 코딩테스트를 통해 개발자의 기술적인 능력과 프로그래밍 능력을 평가할 수 있다. 이는 알고리즘과 데이터 구조, 문제 해결 능력 등을 확인하여 개발자의 기술 수준을 판단하는 데 도움이 된다.

  • 문제 해결 능력 평가: 코딩테스트는 주어진 문제를 해결하기 위한 논리적 사고와 문제 해결 능력을 평가하는 데 사용된다. 개발자는 제한된 시간 안에 주어진 문제를 분석하고 효율적인 알고리즘을 설계하여 구현해야 한다.

  • 코드 품질 및 가독성 확인: 코딩테스트는 개발자가 작성한 코드의 품질과 가독성을 평가하는 데 도움이 된다. 개발자가 코드를 깔끔하고 효율적으로 작성할 수 있는지, 적절한 변수명과 주석을 사용하는지 등을 확인할 수 있다.

4. 결론

• 자신이 알고 있는 것을 프로그래밍 언어로 변환하는 과정인 구현 능력은 중요하지 않다. 구현이라는 것은 책이나 문서를 보고 누구든 할 수 있다. 중요한 것은 올바르게 분석하고 이해해서 선택하는 것이다. 앞으로 자료구조와 알고리즘을 공부함에 있어서, 어떤 것이 적합한지에 대해 생각하고 판단하는 시간을 많이 가질 예정이다 !