자료 구조 리스트(선형리스트,연결리스트)

(선형리스트)

순차 자료 구조 (배열을 이용)

구현할 자료들을 논리적인 순서대로 메모리에 연속하여 저장하는 구현 방식

 

모든 데이터가 메모리에 연속적으로 저장된다.

데이터 저장을 위해 정확하게 데이터 크기만큼 메모리를 사용한다.

 

• 읽기

선형 리스트는 임의 접근이 가능하기 때문에 O(1)의 시간이 걸린다.

 

• 검색

하나하나 원소를 비교해가야 하므로 O(n)의 시간이 걸린다. 정렬되어 있다면 이진 검색을 사용할 수 있으며 이 경우 O(logn)이다.

 

• 삽입

원소를 어디에 삽입하냐에 따라 시간이 달라진다. 맨 끝에 데이터를 추가할 경우 O(1)이지만, 처음이나 중간이라면 모든 데이터를 이동해야 하기에 O(n)이 걸린다.

 

• 삭제

삽입과 마찬가지로 원소를 어디에서 삭제하냐에 따라 시간이 달라진다. 맨 끝의 데이터를 삭제할 경우 O(1)이지만, 처음이나 중간이라면 모든 데이터를 이동해야 하기에 O(n)이 걸린다.

(연결리스트)

연결 자료 구조(포인터를 이용)

노들는 여러 개의 메모리 청크에 데이터를 저장하여,이를 연결하여 구현하는 방식

데이터는 노드에 저장되고, 노드는 메모리에 곳곳에 흩어져 있을 수 있다.

• 읽기

연결 리스트는 임의 접근이 불가능해 요소 하나하나를 탐색해야 하므로 O(n)의 시간이 걸린다. 하지만 처음과 끝이라면 구현에 따라 O(1)이 될 수 있다.

 

• 검색

하나하나 원소를 비교해가야 하므로 O(n)의 시간이 걸린다. 선형 리스트와 다르게 이진 검색을 사용할 수 없다.

 

• 삽입

원소를 어디에 삽입하냐에 따라 시간이 달라진다. 앞이나 뒤에 데이터를 추가할 경우 O(1)이지만, 중간이라면 해당 위치까지 검색해야 하기 때문에 O(n)이 걸린다.

 

• 삭제

삽입과 마찬가지로 원소를 어디에서 삭제하냐에 따라 시간이 달라진다. 앞이나 뒤의 데이터를 삭제할 경우 O(1)이지만, 중간이라면 O(n)이 걸린다. 

위치를 알면 O(1)이다.

 

연결 리스트가 삽입과 삭제에서 효율적이고,탐색은 순차 리스트가 더 효율적이다.

 

객체지향적 알고리즘

순차 자료구조와 연결 자료구조를 둘의 특징을 명확히 알고 구현할 작업의 요구 조건 및 사용 빈도에 따라 둘 중 하나를 선택하거나 또는 두 개를 조합하여 응용 프로그램을 개발해야 한다.

 

알고리즘을 분석하는 것은 알고리즘의 자원의 사용량을 분석하는것

 

하드웨어와 소프트웨어 환경을 배제한 객관적인 지표가 필요.

 

시간 복잡도 :알고리즘을 수행하는 데 필요한 연산이 몇 번실행되는지

 

공간 복잡도 :알고리즘을 수행하는 데 필요한 자원 공간의 양

 

시간 복잡도 VS 공간 복잡도

효율적인 알고리즘은 실행 시간이 적게 걸리며, 자원을 적게 소모하는것 , 시간과 공간은 반비례적인 경향이 있어 보통 알고리즘의 척도는 시간 복잡도를 위주로 판단한다.

ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin.tie(nullptr);

↑ 위에꺼는 cin cout 속도를 빠르게 해주는 함수셋

 

vector<char>left,rightReversed; 이런식으로 쓰면

vector<char>left , vector<char>rightReversed 생성할수 있다.

 

for (char ch : input) 다시알아보자