[자료구조] 자료구조와 알고리즘

📌 기술면접 질문 (답해보기)

Q. 자료구조의 정의와 중요한 이유를 설명하세요.

    A. 말 그래도 자료를 저장하는 구조 = 대량의 데이터를 효율적으로 관리할 수 있게끔 하는 구조
         문제의 해결을 위해 여러 가지 형태의 자료구조가 활용된다.
          - 형태에 따라 장단점이 존재한다.
         - 프로그램에서 특정 알고리즘을 구현하기 위해 적정한 자료구조를 사용해야 좋은 성능을 낼 수 있다.

Q. 자료구조란? / 알고리즘이란?

    A. 자료구조 : 데이터를 어떠한 형태로 저장하고 관리할 것인지에 대한 방법.
            → 그래서 자료구조는 어떻게 효율적으로 자료를 저장할 것인가에 대한 고민이 필요하다
        알고리즘 : 저장된 데이터를 찾거나 변형하거나 수정할 때 필요한 방법.
            → 그래서 알고리즘은 문제를 해결하기 위한 절차에 대한 고민이 필요하다.

Q. 알고 있는 자료구조의 종류에  대해 이야기해보세요.

    A. List(리스트), Linked List(링크드 리스트), Array(배열), Stack(스택), Queue(큐), Dequeue(디큐), Tree(트리),

        Heap(힙), Graph(그래프)

Q. 빅오 표기법에 대해서 설명해주세요.

    A. 알고리즘의 효율성을 표기해주는 표기법. 보통 알고리즘의 시간 복잡도에 주로 사용된다.

 

 

자료구조란 무엇인가?

말 그래도 자료를 저장하는 구조로, 대량의 데이터를 효율적으로 관리할 수 있게끔 하는 데이터의 구조.

• 문제의 해결을 위해 여러 가지 형태의 자료구조가 활용된다.
• 형태에 따라 장단점이 존재하며, 구현하고자 하는 프로그램의 성능을 고려하여 알맞은 자료구조를 선택해야 한다.
• 자료를 효율적으로 담기 위해 자료구조를 배우며, 프로그램에서 특정 알고리즘을 구현하기 위해 적정한 자료구조를 사용해야 좋은 성능을 낼 수 있다.

 

자료구조의 분류

• 단순 구조 : 프로그래밍에서 사용되는 기본 데이터 타입
• 선형 구조 : 저장되는 자료의 전후관계가 1:1 (리스트, 스택, 큐)
• 비선형 구조 : 데이터 항목 사이의 관계가 1:n 또는 n:m (트리, 그래프 등)
• 파일 구조 : 서로 관련된 필드들로 구성된 레코드의 집합인 파일에 대한 자료구조

 

 

 

알고리즘이란 무엇인가?

자료구조가 자료의 표현 및 저장방법을 뜻한다면, 알고리즘은 이렇게 표현 및 저장된 데이터를 활용하여 문제를 해결하는 방법을 의미한다.

 

 

시간 복잡도와 공간 복잡도

• 시간 복잡도(Time complexity) :  알고리즘을 실행시켜 완료하는 데 필요한 컴퓨터 시간의 양

시간 복잡도 구하는 법 : '데이터의 수 n에 대한 연산 횟수의 함수 T(n)을 구성한다’. 
                                → 데이터 수의 증가에 따른 연산 횟수의 변화 정도를 판단할 수 있다.

• 공간 복잡도(space complexity) : 알고리즘을 실행시켜 완료하는 데 필요한 메모리의 양

 

 

빅-오 표기법(Big-Oh Notation)

알고리즘의 시간 복잡도를 나타내는 수학적인 표기법이며, O(f(n))으로 나타낸다.

 

• O(1) : 상수형 빅-오, 데이터 수에 상관없이 연산횟수가 고정 (ex: push, pop)
• O(log n) : 로그형 빅-오, '데이터 수의 증가율'에 비해서 '연산 횟수의 증가율'이 훨씬 낮음 (ex: 이진트리)
• O(n) : 선형 빅-오, 데이터의 수와 연산횟수가 비례하는 알고리즘이다  (ex: for문)
• O(n*log n) : 데이터의 수가 두 배로 늘 때, 연산 횟수는 두 배를 조금 넘게 증가  (ex: 퀵 정렬, 병합 정렬, 힙 정렬)
• O(n²) : 데이터 수의 제곱에 해당하는 연산 횟수를 요구
• O(n³) : 데이터 수의 세제곱에 해당하는 연산 횟수를 요구
• O(2ⁿ) : 지수형, 사용하기에 무리가 있으며 데이터 증가에 따라 연산 횟수가 기하급수로 늘어남 (ex: 피보나치 수)

지금까지 설명한 빅-오 표기들의 성능(수행 시간, 연산 횟수)의 대소를 정리하면 다음과 같다

O(1) < O(log n) < O(n) < O(n*log n) < O(n²) < O(n³) < O(2ⁿ)

 

 

 

자료구조와 알고리즘

자료구조 : 데이터를 어떠한 형태로 저장하고 관리할 것인지에 대한 방법.
→ 그래서 자료구조는 어떻게 효율적으로 자료를 저장할 것인가에 대한 고민이 필요하다.

 

알고리즘 : 저장된 데이터를 찾거나 변형하거나 수정할 때 필요한 방법.
→ 그래서 알고리즘은 문제를 해결하기 위한 절차에 대한 고민이 필요하다.

 

프로그램 = 자료구조 + 알고리즘

프로그램의 일반적 정의는 데이터를 처리하여 특정 작업을 수행하는 일련의 명령어들의 모음이다. 즉, 데이터를 처리할 때에 자료구조가 사용되고, 주어진 문제를 해결하기 위해 특정 작업을 수행하는 절차는 알고리즘인 것이다. 따라서, 프로그램은 자료구조와 알고리즘으로 이루어진다고 표현되고는 한다.

ex : 최댓값을 찾는 프로그램 = 배열(자료구조) + 순차 탐색(알고리즘)