잠보

연결리스트란?

연결리스트란 여러개의 노드를 연결함으로써 데이터를 보관하는 자료구조로 노드는 데이터를 가진 data 부분과 다음 노드를 연결하는 

link 부분으로 나뉘어져 있다.

연결리스트의 장점

1. 배열과는 다르게 필요한 만큼 메모리를 동적으로 할당 받아서 사용한다. 즉, 데이터 삽입 시에만 메모리 추가 사용하므로 효율적.
2. 삽입 삭제가 간단하다 : 새로운 노드 삽입 삭제 시 포인터 값(link)만 변경해주면 되기 때문이다.

연결리스트의 단점

1. 노드 접근이 배열보다 오래 걸린다 : 첫 노드부터 순차적으로 접근해야하기 때문이다. 메모리 구조상 차이.
2. 물리적으로 인접한 메모리에 위치해있지 않다 : 배열과 달리 포인터로 다음 노드의 위치를 알 수 있으므로 메모리 주소 공간이 떨어져있다.
3. 참조 포인터를 위한 메모리 공간이 낭비된다.

연결리스트의 시간복잡도

※ 중간 삭제 삽입 시 해당 위치의 전과 후의 데이터에 접근해야하고 작업을 해야하므로 O(n + 1)이 걸린다. 위의 삽입 삭제 상수시간은 접근을 고려하지 않고 삽입 삭제만 봤을 때의 시간이다.

연결리스트의 종류

1. 단일 연결리스트 : 가장 기본적인 연결리스트로 마지막 노드는 가리키는 노드가 없다. 보통 스택 구현에 많이 사용. 마지막 노드가 null을 가르킨다.
2. 이중 연결리스트 : 노드를 연결하는 link가 앞 뒤로 존재해서 앞 뒤 노드들 간의 관계를 바로 알 수 있다. 보통 큐 구현에 많이 사용. 단일 연결리스트는 헤드노드 유실시 전체 자료를 다 잃어버리지만 이중 연결리스트는 헤드만 아닌 테일 노드도 가지고 있으면 복구가 가능하다 또한 단일 연결리스트는 헤드에서만 탐색이 가능하나 이중 연결리스트는 테일에서도 탐색이 가능하므로 탐색의 방향이 바뀌어야 하는 경우 사용한다. 현실에서 사용하는 연결 리스트는 대부분 이중 연결리스트라고 보면 된다.
3. 원형 연결리스트 : 마지막 노드가 다시 처음 노드를 가리키는 연결리스트. 헤드와 테일의 구분이 없다. 스트림 버퍼의 구현에 많이 사용.

※ 물론 위의 연결리스트 구현될 수 있다는 스택, 큐 등 자료구조는 배열로도 큐를 단일 연결리스트로도 구현 가능하다 해당 자료구조만큼보다는 조금 비효율적이다라는 것이다.

배열과 연결리스트 사용 의문과 결론

동적배열과 연결리스트의 이 2개의 글을 읽어보셨으면 아시겠지만 결국 시간복잡도만 봤을 때 배열과 연결리스트는 데이터 접근과 탐색(탐색은 빅오 표기법은 같으나 메모리를 생각했을 때 조금의 차이)을 제외하면 별 다른 점이 없다. 

결국 자료구조의 설계를 기준으로 결정해야하는데 연결리스트는 마지막 노드에 한 해 데이터 추가 삭제 시 상수 시간이 걸리는 점을 생각 동적 배열은 마지막에 데이터를 추가 삭제 시 분할 상환할 경우에 상수 시간이 걸리다는 점과 데이터의 접근과 탐색을 생각하면 될 것 같다.

또한 보통 개발자가 배우기를 연결리스트는 삽입, 삭제에 유리, 배열은 접근 탐색에 유리하다는 것을 알고있다는 점도 반영.

결론은 데이터 접근, 탐색이 중요하면 배열을 사용. 데이터의 추가 삭제가 중요하면 연결리스트를 사용.

하지만 실무에서는 대부분 동적배열을 애용한다?!

배열이란?

배열이란 연관된 데이터를 하나의 변수에 그룹핑해서 관리하기 위한 방법이다. 

즉, 배열은 하나의 변수에 여러 정보를 담을 수 있어 많은 정보를 효율적으로 처리할 수 있는 자료구조이다.

배열의 장점

1. 검색 성능이 좋다 : 인덱스를 이용한 무작위 접근이 가능하므로 빠르다.
2. 순차 접근의 경우에도 데이터를 하나의 연속된 메모리 공간에 할당하므로 연결 리스트보다 빠르다.

배열의 단점

1. 자료의 삽입과 삭제에 비효율적이다 : 항목의 모든 요소를 이동시켜야해서 비효율적.
2. 메모리 공간 낭비 : 배열은 메모리를 할당 받아 사용하기 때문에 데이터의 존재 유무와 상관없이 일정한 크기의 공간을 점유하고 있기 때문에 데이터를 삭제하더라도 배열 자체를 제거하지 않은 이상 낭비를 유발한다.

배열의 시간복잡도

※ 배열의 마지막 원소에 삽입, 삭제 삽입은 당연히 간단하게 끝내지만 (상수 시간) 아닌 경우. 즉, 시간 복잡도의 평균과 최악을 가정하여O(n)이라고 생각하면 될 것 같습니다.

Array과 ArrayList의 차이점

Array

- 통상적으로 말하는 자료구조 상의 배열.

- 고정 배열.

- 배열의 크기를 지정하며 그 크기 이상 데이터 삽입 시 불가.

- 배열의 사용하지 않는 인덱스가 있더라도 고정 크기이므로 메모리 낭비.

ArrayList

- 동적 배열.

- 자동적으로 크기가 지정되며 그 크기 이상 데이터 삽입 시 원래 크기의 1.5 ~ 2배 사이즈로 크기가 확장되며 삽입 가능.

- 배열의 사용하지 않는 인덱스가 있을 시 크기가 줄어들며 만약 인덱스 1의 데이터를 삭제 시 고정 배열은 1에 접근하였을 때 데이터가 
없지만 동적 배열은 1에 접근하였을 때 2에 있던 데이터가 1로 가있어 데이터가 있다.

- Hash Map, Dictionary, Linked List로 구현되어 있다.

코드 예시

// 자바스크립트의 배열은 다른 데이터 타입을 배열안에 같이 넣을 수 있다.
// 다트의 배열은 타입 지정이 없을 시 다른 데이터 타입을 배열안에 같이 넣을 수 있다.

javascript

고정 배열
1. let arr = new Array(3);

동적 배열
1. let arr = [];
2. let arr new Array();

1. 알고리즘별 정의, 장점, 단점 정리

2. 알고리즘별 시간복잡도 및 공간 복잡도

ETC

• 추가적인 메모리 할당이 불가능한 경우 병합 vs 큌 : 데이터가 최악인 것만 본다면 퀵 보다 병합 정렬이 훨씬 빠르지만 추가 메모리 할당이 없다면 병합 정렬은 사용 불가이기에 퀵을 써야한다
• 안정 정렬 : 중복된 값을 입력 순서와 동일하게 정렬하는 특성 ex) 삽입 정렬, 버블 정렬, 합병 정렬, 계수 정렬
• 불안정 정렬 : 중복된 값이 입력 순서와 동일하지 않게 정렬되는 특성 ex) 선택 정렬, 퀵 정렬, 힙 정렬
• 기본으로 탑재 되어있는 언어의 라이브러리 중 정렬은 시간 복잡도가 보통 NlogN으로 잘 판단하여 사용할 것.

Data(자료)

참고 또는 분석을 위해 수집된 사실과 통계.

현실 세계로부터 수집되는 값 또는 이들의 집합이며 가공되기 전의 상태.

데이터를 가공하고 해석한 후의 상태를 정보(Information)이라고 한다.

자료구조(Data Structure)

컴퓨터 메모리상에서 데이터를 표현하건 저장하는 방법이다.

효과적으로 설계된 자료구조는 프로그램 실행시간을 단축하며 메모리 용량을 최소한으로 사용한다.

1. 단순 구조 (기본 자료형 + 사용자 정의 자료형)

 1-1. 2진수

 1-2. 정수, 실수

 1-3. 문자, 문자열

2. 선형 구조

 2-1. 리스트(배열)

 2-2. 연결 리스트

  - 단순 연결 리스트

  - 이중 연결 리스트

  - 원형 연결 리스트

 2-3. 데크

 2-4. 스택

 2-5. 큐

3. 비선형 구조

 3-1. 트리

  - 일반 트리

  - 이진 트리

 3-2. 그래프 

  - 방향 그래프

  - 무방향 그래프

4. 파일 구조

 4-1. 순차 파일

 4-2. 색인 파일

 4-3. 직접 파일

알고리즘 (Algorithm)

저장된 데이터를 이용하여 문제를 해결하기 위한 절차나 방법

시간 복잡도 & 공간 복잡도(메모리)

효과적인 알고리즘을 얻기 위해 알고리즘의 성능을 분석하고 평가할 수 있어야 한다.

시간 복잡도(Time Complexity) : 알고리즘의 수행 시간을 분석한 결과, 알고리즘이 시작되어 완료되는 데까지 걸리는 시간 but 실제 실행 시간은 하드웨어 성능 혹은 프로그래밍 언어에 따라 값이 달라지므로 고려하지 않는다. 즉, 알고리즘에서의 시간 복잡도란 명령어의 실행 횟수를 뜻한다.

공간 복잡도(Space Complexity) : 메모리 사용량을 분석한 결과

Big-O 표기법

알고리즘의 시간복잡도와 공간복잡도를 표현하는 대표적인 방법에는 Big-O 표기법이 있다.

이 표기법은 알고리즘 실행에 있어 최악의 경우를 나타낸다.

즉, 시간 또는 공간의 상한선을 두는 것이다.

예를 들어 3n^2 + 20n + 100 이라는 시간복잡도 함수가 있으면 입력값 n이 증가할수록 차수가 가장 큰 항이 결과값에 가장 큰 영향을 

미치며, 다른 항들은 상대적으로 무신된다. 최고 차항의 상수 계수 3 또한 무시된다.

따라서, Big-O 표기법에서는 영향력이 없는 항과 상수 계수를 제거하고 가장 영향력이 큰 항으로만 시간복잡도를 표현한다.

O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(n^3) < O(2^n) < O(n!) : 오른쪽으로 갈수록 비효율적인 순서

자료구조 연산별 평균 시간복잡도

그래서 알고리즘 어떻게 공부하는건데?

기본적인 개념을 알았으니 공부하는 방법에 대해 말해보겠습니다. 위 글을 읽어도 어떻게 공부해야하는지 감이 안 잡히실텐데요 

제 기준 공부 순서는

1. 자신이 사용하는 언어로 자료구조들 구현해보기 (코딩테스트에서 제공이 안 될수있으므로 암기 해주시면 좋음)
2. 유튜브나 검색을 통해 알고리즘 종류별로 공부 후 개념 파악 후 코드를 따라서 처본 후 확실하게 이해하기
3. 문제 풀이를 통한 숙달과 재암기 및 응용

2번까지 공부하셨으면 문제에 대해 궁금하실 것 같은데 가장 기본적으로 백준을 통해 접근하시는게 좋을 것 같아 유형별로 

소개해드리겠습니다.

주의 사항으론 문제 해결 시간을 자기만의 기준을 세워서 (약 30분 ~ 1시간) 그 시간안에 풀지 못할 시 단계적으로 힌트를 보고 

풀어보며 그래도 안 될시 답을 보며 재학습을 하는게 좋습니다.

백준 알고리즘을 다 푸셔서 기본 토대가 마련되셨으면 프로그래머스, 리트코드, 코드포스 등을 통해 더 높은 난이도의 알고리즘을 통해

연습하시면 될 것 같습니다