시간 복잡도

시간 복잡도(Time Complexity)는 알고리즘의 실행 시간이 입력 크기에 대해 어떻게 증가하는지를 분석하는 것이다. 즉, 알고리즘의 효율성과 실행 시간을 예측하는 데 사용된다. 시간 복잡도는 일반적으로 Big O 표기법으로 표현되며, 입력 크기에 대한 함수로 표현된다.

시간 복잡도를 분석하기 위해 주로 고려하는 것은 알고리즘에서 반복문이나 재귀 호출 등의 반복적인 연산이 몇 번 수행되는지, 입력 크기가 증가함에 따라 반복적인 연산의 횟수가 어떻게 변화하는지를 살펴본다.

일반적으로 시간 복잡도는 다음과 같은 형태로 표현된다

• O(1): 입력 크기에 상관없이 일정한 실행 시간을 가지는 경우이다. 상수 시간 알고리즘으로 간주된다.
• O(log n): 입력 크기에 비례하여 로그의 증가 속도로 실행 시간이 증가하는 경우입니다. 이진 검색 알고리즘과 같은 분할 정복 알고리즘이 이에 해당한다.
• O(n): 입력 크기에 비례하여 선형적으로 실행 시간이 증가하는 경우이다. 단순 탐색 알고리즘이 이에 해당한다.
• O(n log n): 입력 크기에 비례하여 로그의 증가 속도로 실행 시간이 증가하며, 각각의 요소에 대해 로그 시간이 소요되는 경우 병합 정렬, 퀵 정렬 등의 정렬 알고리즘이 이에 해당한다.
• O(n^2): 입력 크기에 비례하여 제곱의 증가 속도로 실행 시간이 증가하는 경우 이차 정렬 알고리즘, 중첩 반복문 등이 이에 해당한다.
• O(2^n): 입력 크기에 비례하여 2의 지수적인 증가 속도로 실행 시간이 증가하는 경우 하위 집합 생성, 피보나치 수열과 같은 재귀적인 알고리즘이 이에 해당한다.

시간 복잡도 분석은 알고리즘의 성능을 예측하고 비교하는 데 중요하다. 더 효율적인 알고리즘은 입력 크기가 커질수록 실행 시간의 증가율이 더 낮아지므로 선호된다.

또한, 시간 복잡도를 분석하는 이유는 다음과 같다

1. 알고리즘의 효율성 비교: 시간 복잡도를 통해 서로 다른 알고리즘들의 성능을 비교할 수 있다. 입력 크기가 증가할 때 더 효율적인 알고리즘을 선택하여 실행 시간을 줄일 수 있다.
2. 알고리즘의 최적화: 시간 복잡도 분석을 통해 알고리즘의 성능을 개선할 수 있는 부분을 파악할 수 있다. 반복문이나 재귀 호출 등의 연산을 최적화하여 실행 시간을 단축시킬 수 있다.
3. 문제 해결에 필요한 자원 예측: 알고리즘의 시간 복잡도를 파악하면 실행 시간을 예측할 수 있다. 따라서 문제를 해결하기 위해 필요한 컴퓨팅 자원(시간, 메모리 등)을 미리 예상하고 할당할 수 있다.
4. 대용량 데이터 처리: 시간 복잡도 분석은 알고리즘의 성능을 파악하므로, 대용량의 데이터를 처리해야 할 때 어떤 알고리즘을 사용해야 효율적인지를 판단할 수 있다. 대용량 데이터 처리는 현대의 다양한 분야에서 중요한 요소이다.

따라서, 알고리즘의 시간 복잡도를 분석하여 효율적인 알고리즘을 선택하고 개선하는 것은 프로그래밍에서 핵심적인 요소 중 하나이다. 시간 복잡도 분석을 통해 실행 시간을 예측하고 알고리즘을 효율적으로 설계할 수 있다.

공간 복잡도

공간 복잡도(Space Complexity)는 알고리즘을 실행하는 동안 사용되는 메모리 공간의 양을 나타낸다. 알고리즘이 문제를 해결하기 위해 필요한 추가적인 메모리의 양을 분석하는 것이다.

공간 복잡도는 주로 다음과 같은 방식으로 표현됩니다:

1. Big O 표기법: 알고리즘의 공간 요구 사항을 대략적으로 표현하기 위해 사용된다. 예를 들어, O(1), O(n), O(n^2) 등으로 표기됩니다. 이는 알고리즘의 공간 사용량이 입력 크기에 대해 어떻게 증가하는지를 표현
2. 공간 복잡도 함수: 실제로 필요한 메모리 공간의 크기를 함수로 표현한다. 예를 들어, f(n) = n, f(n) = n^2 등으로 표기됩니다. 이는 입력 크기 n에 대한 공간 사용량을 직접적으로 표현

공간 복잡도는 주로 다음과 같은 요소들을 고려하여 분석된다

1. 변수 및 데이터 구조의 크기: 알고리즘이 실행되는 동안 사용되는 변수, 배열, 리스트, 트리, 그래프 등의 데이터 구조의 크기를 고려한다. 이는 데이터를 저장하는 데 필요한 메모리 양을 결정한다.
2. 임시 저장 공간: 알고리즘이 실행되는 동안 생성되는 임시 변수, 스택, 큐, 힙 등의 저장 공간을 고려한다. 이러한 임시 저장 공간은 알고리즘의 수행 중에 필요한 중간 결과나 작업에 사용된다.
3. 재귀 호출 스택: 재귀적인 알고리즘의 경우, 재귀 호출 스택에 필요한 메모리 공간을 고려한다. 재귀 호출이 깊이 우선으로 이루어지는 경우 스택 메모리가 필요하며, 이는 공간 복잡도에 반영된다.

공간 복잡도 분석을 통해 알고리즘의 메모리 요구 사항을 평가할 수 있고, 제한된 메모리 환경에서의 실행 가능성을 평가할 수 있다. 또한 공간 복잡도 최적화는 메모리 사용량을 최소화하여 효율성을 높이고, 대용량 데이터나 임베디드 시스템과 같이 메모리 제약이 있는 환경에서 알 수 있다.

공간 복잡도는 알고리즘이 실행되는 동안 사용되는 메모리 공간의 양을 분석하는 것입니다. 이는 알고리즘이 처리하는 데이터의 크기와 관련이 있다.

공간 복잡도 분석은 다음과 같은 이유로 중요하다:

1. 메모리 제한: 일부 시스템이나 플랫폼에서는 제한된 메모리 용량이 주어질 수 있다. 이런 경우 공간 복잡도를 분석하여 알고리즘의 메모리 사용량이 제한 내에 있는지 확인할 수 있다.
2. 성능 향상: 메모리 액세스는 실행 속도에 영향을 줄 수 있다. 메모리를 효율적으로 사용하는 알고리즘은 CPU 캐시의 지역성(locality)를 개선하여 성능을 향상시킬 수 있다.
3. 스케일링 및 확장성: 공간 복잡도를 분석하여 알고리즘이 대용량의 데이터나 확장 가능한 시스템에서도 작동할 수 있는지 확인할 수 있다. 이는 알고리즘의 확장성과 잠재적인 성장성을 평가하는 데 도움을 준다.

공간 복잡도는 알고리즘 설계와 최적화에 중요한 역할을 합니다. 메모리 사용량을 최소화하고 효율적으로 관리함으로써 시스템의 성능과 확장성을 향상시킬 수 있다. 따라서 공간 복잡도 분석은 알고리즘의 성능을 평가하고 최적화하는 데 필수적이다.

공간 복잡도는 알고리즘이 실행될 때 필요한 메모리 공간을 정량화하여 분석하는 것이다. 이는 알고리즘의 효율성을 평가하고 개선하는 데 도움을 준다.

공간 복잡도를 분석할 때는 주로 다음과 같은 개념들을 사용한다

1. 추가적인 공간: 알고리즘이 실행될 때 생성되는 추가적인 데이터 구조나 변수의 공간을 고려한다. 이러한 공간은 입력 데이터의 크기에 비례하거나 고정된 크기일 수 있다.
2. 입력 데이터 공간: 입력 데이터를 저장하기 위해 필요한 공간을 고려한다. 입력 데이터의 크기에 따라 공간 요구 사항이 변할 수 있다.
3. 공간 사용 패턴: 알고리즘의 실행 중에 사용되는 공간의 패턴을 분석한다. 예를 들어, 반복문의 실행마다 메모리를 할당하고 해제하는 경우와 재귀 호출 시에 스택 메모리를 사용하는 경우 등을 고려

공간 복잡도를 분석하여 알고리즘을 개선하는 것은 다음과 같은 이유로 중요하다.

1. 메모리 효율성: 제한된 메모리 환경에서 작업할 때, 공간 복잡도를 최적화하여 메모리 사용량을 줄일 수 있다. 이는 더 많은 데이터를 처리할 수 있거나 다른 작업을 수행할 수 있는 여유 공간을 확보하는 데 도움을 준다.
2. 성능 향상: 메모리 액세스 속도는 CPU 캐시와 관련이 있기 때문에, 메모리 사용을 최적화하여 캐시 지역성을 개선할 수 있다. 이는 알고리즘의 실행 시간을 단축시키고 전체적인 성능을 향상시킬 수 있다.
3. 스케일링 및 확장성: 공간 복잡도 분석을 통해 알고리즘의 메모리 요구 사항이 입력 크기에 어떻게 반응하는지 파악할 수 있다. 이는 알고리즘이 큰 데이터 세트에서도 효율적으로 작동하는지 예측하고 스케일링 및 확장성을 고려하는 데 도움을 준다.

알고리즘의 시간 복잡도와 공간 복잡도는 함께 고려되어야 한다.

시간 복잡도

• 알고리즘이 문제를 해결하는 데 필요한 시간을 나타낸다.
• 보통 알고리즘이 처리해야 하는 데이터의 크기에 따라 얼마나 시간이 증가하는지를 나타내는 데 사용된다.
• 시간 복잡도를 표현할 때 보통 빅 오 표기법(Big O notation)을 사용한다. 예를 들어, O(n)은 알고리즘이 처리해야 하는 데이터의 크기에 비례하여 시간이 증가함을 나타낸다.

공간 복잡도

• 알고리즘이 문제를 해결하는 데 필요한 메모리 공간을 나타낸다.
• 알고리즘이 실행되는 동안 사용하는 총 메모리를 포함하며, 이는 입력 크기와 관련된 변수 저장, 스택, 큐 등의 공간이 포함된다.

시간 복잡도와 공간 복잡도는 중요하다. 왜냐하면 제한된 리소스(시간과 메모리) 내에서 문제를 해결해야 하기 때문 특히 대량의 데이터를 처리해야 하는 경우, 시간과 공간 복잡도가 낮은 알고리즘을 선택하는 것은 매우 중요하다. 높은 시간 복잡도를 가진 알고리즘은 실행 시간이 오래 걸릴 수 있으며, 높은 공간 복잡도를 가진 알고리즘은 많은 메모리를 사용할 수 있다.

절차지향 / 객체지향 / 함수형 프로그래밍이란 무엇이고 차이점은 무엇인가?

절차지향 프로그래밍

프로그램을 연속적인 절차나 단계로 분해하여 작성하는 프로그래밍 패러다임 이러한 방식은 일련의 명령문으로 구성된 프로시저 또는 함수를 사용하여 문제를 해결하려는 것을 강조 프로시저나 함수는 순차적으로 실행되며, 데이터는 전역적으로 공유될 수 있다.

절차지향 프로그래밍에서 프로그램은 작은 단위로 나누어진 함수나 프로시저의 집합으로 구성된다. 각 함수는 입력을 받아 일련의 작업을 수행하고 결과를 반환한다. 이러한 함수들은 서로 상호작용하면서 문제를 해결한다. 이러한 방식은 프로그램을 논리적으로 분해하여 이해하기 쉽고 유지보수가 용이하도록 한다.

절차지향 프로그래밍은 명령형 프로그래밍 패러다임의 일부로서, 프로그램의 제어 흐름이 명령문의 연속으로 표현된다. 프로그램의 상태를 변경하는 명령문들이 연속적으로 실행되면서 프로그램의 동작이 결정된다.

절차지향 프로그래밍은 다음과 같은 특징을 가지고 있다

1. 프로그램은 함수나 프로시저의 연속적인 호출에 의해 제어된다.
2. 전역 변수를 통해 데이터가 공유될 수 있다.
3. 데이터와 함수가 분리되어 있으며, 함수는 데이터에 대한 명령문의 집합으로 이루어진다.
4. 프로그램은 주로 상태 변경을 강조하며, 데이터 흐름보다는 제어 흐름에 중점을 둔다.

절차지향 프로그래밍은 초기의 주류 프로그래밍 패러다임 중 하나였으며, C 언어 등에서 널리 사용된다. 절차지향 프로그래밍은 단순하고 직관적인 접근 방식을 제공하며, 작은 규모의 프로그램을 개발하기에 적합하다. 그러나 큰 규모의 프로그램이나 복잡한 문제를 해결하는 데에는 한계가 있을 수 있다.

객체지향 프로그래밍

객체지향 프로그래밍(Object-Oriented Programming, OOP)은 프로그램을 독립적인 객체들의 모임으로 바라보고, 객체들 간의 상호작용을 통해 프로그램을 구성하는 프로그래밍 패러다임이다. 이러한 방식은 현실 세계의 개념과 그들 간의 관계를 모델링하여 문제를 해결하려는 것을 강조한다.

객체지향 프로그래밍에서 객체는 상태와 행위를 가지는 개체로 표현된다. 상태는 객체의 속성이나 데이터를 나타내고, 행위는 객체가 수행할 수 있는 동작이나 메서드를 나타낸다. 이러한 객체들은 클래스라는 템플릿을 사용하여 생성된다. 클래스는 객체의 공통된 속성과 행위를 정의한 것으로, 객체들의 설계도나 청사진 역할을 한다.

객체지향 프로그래밍은 다음과 같은 특징을 가지고 있다.

1. 캡슐화(Encapsulation): 데이터와 해당 데이터를 조작하는 메서드를 하나의 단위로 캡슐화하여 외부로부터의 접근을 제어하고 데이터의 무결성을 보호한다.
2. 상속(Inheritance): 클래스들 간에 상속 관계를 통해 코드의 재사용성을 높이고, 계층적인 관계를 표현합니다. 부모 클래스의 속성과 메서드를 자식 클래스가 상속받아 사용할 수 있다.
3. 다형성(Polymorphism): 같은 타입이지만 다양한 형태로 동작할 수 있는 능력을 의미합니다. 다형성을 통해 코드의 유연성과 확장성을 높일 수 있다.
4. 추상화(Abstraction): 공통적인 속성과 행위를 추출하여 클래스로 정의하고, 복잡한 시스템을 단순화하여 모델링합니다. 구체적인 구현 내용을 감추고 필요한 기능에만 집중할 수 있다.

객체지향 프로그래밍은 현실 세계의 개념과 그들 간의 관계를 모델링하기 때문에 문제를 더 직관적이고 유연하게 해결할 수 있다. 코드의 재사용성과 유지보수성이 높아지며, 대규모 프로젝트의 개발과 관리에 용이하다. 또한 객체 간의 상호작용을 통해 모듈화되고 협업이 용이한 개발 환경을 제공한다.

함수형 프로그래밍

함수형 프로그래밍(Functional Programming, FP)은 프로그램을 수학적인 함수의 계산으로 간주하고, 상태 변경과 가변 데이터보다는 함수 호출과 데이터 변환을 강조하는 프로그래밍 패러다임이다.

함수형 프로그래밍은 부작용(side effect)을 최소화하거나 없애려는 원칙을 따르며, 데이터와 상태를 불변(immutable)으로 다루는 것을 중요

함수형 프로그래밍에서 함수는 일급 객체로 취급되어 변수에 할당하고 다른 함수의 인자로 전달하거나 함수의 반환값으로 사용할 수 있다. 함수는 순수 함수(pure function)로 작성되어야 하며, 동일한 입력에 대해 항상 동일한 결과를 반환하고 외부의 상태를 변경하지 않는 특징을 가진다. 이러한 순수 함수는 병렬 처리, 테스트, 디버깅 등에서 이점을 가지며, 코드의 예측 가능성과 안정성을 높여준다.

함수형 프로그래밍은 다음과 같은 특징을 가지고 있습니다

1. 불변성(Immutability): 데이터는 불변이며, 한번 생성된 값은 변경되지 않습니다. 이를 통해 예측 가능하고 안전한 동작을 보장한다.
2. 순수 함수(Pure Functions): 입력에 대해 예측 가능하고 부작용이 없는 함수입니다. 외부 상태를 변경하지 않고 오로지 입력에 의해 결과가 결정되며, 동일한 입력에 대해 항상 동일한 결과를 반환하다.
3. 상태 변경 대신 데이터 변환: 데이터를 변경하는 대신 새로운 데이터를 생성하고 변환하는 것에 초점을 맞춥니다. 함수형 프로그래밍은 데이터의 흐름을 중요시하며, 함수들이 연속적으로 적용되어 데이터를 가공한다.
4. 재귀와 고차 함수: 재귀적인 방식으로 문제를 해결하고, 고차 함수를 사용하여 함수를 추상화하고 조합한다. 함수를 인자로 받거나 반환하는 함수를 사용하여 코드를 간결하고 유연하게 작성할 수 있다.

함수형 프로그래밍은 병렬 처리, 분산 시스템, 이벤트 기반 프로그래밍 등과 같은 동시성과 관련된 문제에 강점을 가지며, 간결하고 모듈화된 코드를 작성할 수 있다. 또한 테스트와 디버깅이 쉽고, 함수 조합을 통해 코드 재사용성이 높아진다. 함수형 프로그래밍은 데이터와 함수의 분리를 강조한다. 데이터는 불변하고 함수는 순수하며, 이를 통해 프로그램의 동작을 예측 가능하고 안정적으로 만든다.

함수형 프로그래밍은 다음과 같은 개념과 기법을 활용한다

1. 고차 함수(Higher-Order Functions): 함수를 인자로 받거나 반환하는 함수를 말한다. 고차 함수를 사용하면 함수를 추상화하고 조합할 수 있으며, 코드의 재사용성과 유연성을 높일 수 있다.
2. 순수 함수(Pure Functions): 순수 함수는 외부의 상태를 변경하지 않으며, 동일한 입력에 대해 항상 동일한 결과를 반환한다. 이는 함수의 결과가 입력에만 의존하므로 예측 가능하고 테스트하기 쉽다. 순수 함수는 부작용(side effect)을 없애고 코드의 안정성을 높여준다.
3. 불변성(Immutability): 데이터의 불변성은 데이터를 변경하지 않고 새로운 데이터를 생성하는 것을 의미한다. 이를 통해 데이터의 상태를 추적하기 쉽고, 다중 스레드 환경에서 안전하게 데이터를 공유할 수 있다.
4. 재귀(Recursion): 재귀는 함수가 자기 자신을 호출하는 것을 의미한다. 재귀를 통해 반복적인 작업을 처리할 수 있으며, 많은 함수형 프로그래밍 언어에서 반복문의 대안으로 사용된다.
5. 함수 합성(Function Composition): 함수 합성은 두 개 이상의 함수를 조합하여 새로운 함수를 생성하는 것을 의미한다. 함수 합성은 코드를 간결하고 모듈화된 단위로 분리할 수 있으며, 재사용성을 높여준다.

함수형 프로그래밍은 코드의 가독성과 유지보수성을 높여준다. 또한 병렬 처리와 분산 시스템에 적합하며, 상태 관리와 부작용을 최소화하여 코드를 안전하게 만든다. 함수형 프로그래밍은 최종적으로 코드의 품질과 개발자의 생산성을 향상시키는 데 기여한다.

절차지향 프로그래밍

• 프로그램의 실행 순서에 초점을 맞춘 프로그래밍 패러다임
• 코드는 일련의 명령문으로 구성되며, 프로그램은 이러한 명령문을 위에서 아래로 순차적으로 실행
• 가장 대표적인 절차지향 언어는 C
• 이러한 방식의 장점으로는 코드의 추적이 비교적 쉽다는 점이 있으나, 유지 보수가 어렵고 코드 재사용성이 떨어진다는 단점도 있다.

객체지향 프로그래밍

• 프로그램을 일련의 독립적인 '객체'들로 보고 이들의 상호작용으로 이해하는 프로그래밍 패러다임
• 객체는 데이터와 그 데이터를 처리하는 메서드를 가지고 있으며, 이를 통해 더 높은 수준의 추상화를 가능하게한다.
• 대표적인 객체지향 언어로는 Java, C++, Python 등이 있다.
• 객체지향 프로그래밍의 장점으로는 코드 재사용성이 높고 유지보수가 용이하다는 점이 있다.
• 단점으로는 설계 시간이 오래 걸릴 수 있으며, 객체 간의 관계가 복잡해질 수 있다는 점이 있다.

함수형 프로그래밍

• 계산을 수학적 함수의 평가로 간주하고 상태와 변경 가능한 데이터를 피하는 프로그래밍 패러다임
• 순수 함수를 사용하여 사이드 이펙트를 최소화
• 대표적인 함수형 언어로는 Haskell, Lisp, Scala 등이 있다.
• 함수형 프로그래밍의 장점으로는 동시성 처리와 추상화 수준이 높다는 점이 있다.
• 단점으로는 학습 곡선이 가파르며, 디버깅이 어렵다는 점이 있습니다.

각 패러다임은 서로 다른 문제를 해결하는 데 적합하며, 종종 혼합되어 사용되기도 한다. 일부 현대 언어는 이러한 패러다임을 모두 지원하여 프로그래머가 상황에 따라 적절한 접근 방식을 선택할 수 있도록 한다.

1. Stack (스택): 스택은 LIFO(Last In, First Out) 원칙을 따르는 자료구조이다.
   즉, 가장 최근에 추가된 항목이 가장 먼저 제거된다.
   스택은 함수 호출, 실행 취소(undo) 등에 주로 사용된다.
   나중에 집어넣은 데이터가 먼저 나오는 구조 / LIFO (Last In First Out), peek(가장 마지막 집어넣은 데이터 확인)
   • peek 가 있는 이유를 생각해봤을 때, 브라우저에서 이전 페이지, 작업을 확인하는 경우에 필요하다고 생각된다.
   <스택 구조도> 
   

• 한쪽이 막혀있는 상태에서 pop을 할 경우 가장 마지막에 저장된 데이터가 빠져나간다.

<스택 pseudocode>

• 데이터가 순서대로 입력을 받는다.(저장된다.) / push
• 스택이 가득 찬 경우, 가장 마지막에 입력된 데이터가 빠져나간다. / pop
• 가장 마지막에 저장된 데이터를 확인할 수 있다. / peek

2. Queue (큐): 큐는 FIFO(First In, First Out) 원칙을 따르는 자료구조이다.
즉, 가장 먼저 추가된 항목이 가장 먼저 제거된다.
큐는 데이터를 순차적으로 처리해야 하는 상황, 예를 들어 인쇄 작업 대기열이나 메시지 대기열 등에 사용된다.

Stack 과 마찬가지로 데이터를 집어넣을 수 있는 선형(Linear) 자료형

먼저 집어넣는 데이터가 먼저 나오는 방식 / FIFO (First In First Out)

사용되는 Property 또는 메소드는 Enqueue, dequeue (shift)

• 자바스크립트에서 Array method 중 shift() 메소드가 배열의 첫 번째 요소를 삭제하고 삭제된 요소를 반환해주기 때문에(mutable 한 메소드), dequeue 를 구현할 때 사용한다.

<큐 구조도>

3. Array (배열): 배열은 동일한 타입의 여러 항목을 저장하는 데 사용되는 가장 간단한 자료구조 중 하나이다.
배열의 모든 요소는 연속적인 메모리 위치에 저장되며, 인덱스를 사용하여 각 요소에 직접 접근할 수 있다.
그러나 배열의 크기는 생성 시 정의되고 변경할 수 없으며, 이로 인해 메모리를 비효율적으로 사용할 수도 있다.

Array(배열)이 인덱스와 value 로 정해진 공간에 데이터가 저장

인덱스를 가지고 있기 때문에, 검색 / 접근 / 정렬 등에 장점

자료의 추가 / 삭제 측면에서, 중간에 자료가 추가 / 삭제 되면 그 다음에 위치한 이미 지정된 인덱스를 모두 바꿔주어야 하기 때문에, 많은 시간이 소요된다.

4. Linked List (연결 리스트): 연결 리스트는 각 요소가 메모리의 어느 위치에 있는지를 가리키는 링크 또는 참조를 포함하는 노드로 구성된 선형 자료구조이다.
연결 리스트는 삽입과 삭제가 자주 발생하는 경우에 유용하며, 메모리를 효율적으로 사용할 수 있다.
그러나 연결 리스트에서 특정 요소에 접근하려면 리스트의 처음부터 차례대로 거쳐가야 하므로, 이는 배열에 비해 더 많은 시간이 소요된다.

Linked list 는 존재하는 데이터 만큼의 공간을 차지한다.

Linked list 가 데이터 공간을 절약하는 데 더 효과적이라 할 수 있다.

순차적으로 검색을 하기 때문에, 많은 시간이 소요됨.

자료의 추가 / 삭제 측면에서, Linked List 는 추가 / 삭제된 노드 이전과 이후의 포인터(주소)만을

바꿔주면 되기 때문에 빠른 처리가 가능하다.

Array와 Linked list 차이

<Linked List Pseudo 코드>

1. 노드를 데이터와 next 포인터로 구분한다.
2. head (첫 번째 데이터 참조)가 기본적으로 존재해야 한다.

• Stack과 Queue는 추가 및 제거 순서에 따라 다르게 동작합니다. Stack은 가장 마지막에 추가된 요소를 먼저 제거하고, Queue는 가장 먼저 추가된 요소를 먼저 제거한다.
• Array와 Linked List는 데이터 저장 방식과 접근 방식에서 차이가 있다. Array는 연속적인 메모리 공간에 데이터를 저장하고 인덱스를 통해 직접 접근할 수 있지만, 크기가 고정되어 있다.
• Linked List는 비연속적인 메모리 공간에 데이터를 저장하며, 각 노드는 다음 노드를 가리키는 링크를 가지고 있다. 이 구조는 데이터의 삽입과 삭제를 용이하게 만들지만, 특정 요소에 접근하려면 리스트를 처음부터 순차적으로 거쳐가야 한다.

각 자료구조의 사용 케이스에 따라 그 성능과 효율성이 달라질 수 있다.
예를 들어, 데이터의 삽입과 삭제가 빈번한 경우에는 Linked List가 적합할 수 있다.
반면, 인덱스를 통해 특정 요소에 빠르게 접근해야 하는 경우에는 Array가 더 적합하다.
마찬가지로, 가장 최근의 항목을 먼저 처리해야 하는 경우에는 Stack을, 항목을 추가된 순서대로 처리해야 하는 경우에는 Queue를 사용하는 것이 좋다.