[알고리즘] LinkedList _Simple Linked List 구현

main

LinkedList 멤버변수 선언 및 생성자

값 추가, 해당 인덱스 값 삭제

해당 인덱스 값 가져옴, 전체 데이터 출력, 사이즈 가져옴

[알고리즘] LinkedList_Sorted Linked List 구현

main

결과

값 추가, 이미 정렬된 링크드리스트에 추가되는 값보다 큰 값 앞으로 들어감

[알고리즘] LinkedList

Node와 Link를 구조화 시킨 것이다.
Node: 데이터 집합
Link: 노드의 순서를 유지할 수 있게 해주는 연결 고리

장점
배열에 비해 데이터의 추가/삽입 및 삭제가 용이하다.
배열에 비해 공간의 낭비가 없다.

단점
특정 위치의 요소에 바로 접근하지 못한다.

Simple Linked List (단순 연결 리스트)

데이터를 저장하는 노드와 바로 다음의 노드를 가르키는 링크 하나로 구성되어 있다.
Head 노드를 참조하는 주소를 잃는 경우 데이터 전체를 쓰지 못한다.
중간에 있는 링크가 끊어지는 경우에도 뒤쪽 자료들을 쓰지 못하게 된다.

Doubly Linked List (이중 연결 리스트)

다음 노드 뿐만 아니라 이전 노드를 가리키는 링크도 추가한다.

Circular Linked List (원형 연결 리스트)

Simple Linked List에서 마지막 원소가 null  대신 처음 원소를 가리키게 한다.

[관련 페이지]
단순 연결 리스트 구현
이중 연결 리스트 구현
정렬된 연결 리스트 구현

[알고리즘] Bubble Sort (거품정렬)

1번째와 2번째 원소를 비교하여 정렬하고 2번째와 3번째를 비교하여 정렬하는 식으로 n번째를 정렬하고 다시 1번째와 2번째부터 비교하여 n-1번째를 비교하는 방식으로
돌때마다 마지막 하나가 정렬됨으로 원소들이 거품이 올라오는 것처럼 보인다고 하여 거품정렬이다.

for i = n to i = 1
 a[0] 와 a[1]의 비교를 시작으로 a[j]와 a[j+1]값을 비교하여 a[j]가 더 크면 바꾸어 준다.

시간복잡도: O(n²)

장점
- 구현이 간단하다.

단점
- 다른 정렬에 비해서 연산시간이 오래 걸린다.

코드

숫자의 정렬

문자의 정렬

관련 영상

[알고리즘] Insertion Sort (삽입 정렬)

앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 삽입하는 방식
시간 복잡도가 입력 자료의 구성에 따라 달라진다.

for i = 1 to n
 정렬된 a[0]부터 a[i-1] 숫자 들과 차례대로 비교하여 a[i]보다 첫번째로 큰 수의 자리에  a[i] 값을 두고 그 자리부터 이후에 있는 값들의 인덱스를 뒤로 미뤄준다.

시간복잡도: O(n²)

장점
- 구현이 간단하다.
- 입력 자료가 정렬되어 있으면 있을 수록 빨라진다. 따라서 같은 시간복잡도를 가지는 다른 정렬(선택, 버블) 보다 효율이 높다.
- 같은 값인 경우 상대적 위치가 바뀌지 않는다. -> 안정한 정렬
- 주어진 자료공간 이외의 공간을 사용하지 않고 정렬한다.

단점
- 배열이 길어지면 효율이 떨어진다.
- 자료구조에 따라 역으로 정렬되어 있는 값들에 적용되면 최악의 성능을 보인다.

코드

숫자의 정렬

문자의 정렬

관련 영상

[알고리즘] Selection Sort (선택정렬)

현재 위치에 들어갈 값을 찾아 정렬하는 방식
인간이 사용하는 정렬방식을 가장 많이 닮음

for i = 0 to n:
    a[i]부터 a[n - 1]까지 차례로 비교하여 가장 작은 값이 a[j]에 있다고 하자.
    a[i]와 a[j]의 값을 서로 맞바꾼다.

시간복잡도: O(n²)

장점
- 데이터 양이 적을 때 좋은 성능을 나타냄.
- 방법이 직관적임
- 비교는 여러번 수행되지만 실제 교환 횟수는 적다.
  (그럼으로 교환이 많이 이루어져야 하는 정렬에서 가장 효율적으로 적용된다.)
 
단점
- 데이터 양이 많아지면 속도가 현저히 떨어진다.
- 이미 정렬된 상태에서 소수의 자료가 추가됨으로 재정렬하게 되는 상황에서 최악의 처리 속도를 보여준다.

코드

[숫자의 정렬]

[문자의 정렬]

관련 영상

Protocel Buffer

수행단계
1. Proto파일 작성
2. Proto Compiler를 통해 각 언어에 맞는 Data Handler Class 생성
3. 생성된 class의 set 함수를 통해 데이터 설정
4. writeTo()함수를 통해 Binary Data로 Serialize
5. serial data 전송
...
6. serial data 수신
7. parseFrom() 함수를 통해 Binary Data를 parsing
8. get 함수를 통해 원하는 데이터 값 조회

장점
사용이 간단하다
20~100배 빠르다
모호하지 않다
프로그램에서 사용가능한 클래스를 생성해준다.(C++/Java/Python 공식 지원)
최대 64MB크기의 message까지 지원한다.(성능보장을 위해)
JSON포맷 전환을 지원한다.
BSD License 정책으로 100% 무료이다

단점
repeat 사용 시 serialize/parse시 성능이 저하될 수 있다
데이터를 눈으로 확인할 수 없다 (Binary Data VS. Text Data)
표준 프로토콜이 아니다
단말기/세톱박스 등 RTOS에서의 지원이 어렵다
공식 지원 언어는 C++/Java/Python이다 (이외 언어는 3rd party에서 지원)
Map/Set를 지원하지 않는다.

Proto파일의 작성
Proto 파일은 구조체와 같이 해당되는 데이터 변수 및 타입을 명시합니다.  각 변수는 아래와 같은 한정자 조건을 갖습니다.
-requied: 1개만 존재 가능
-optional: 0개 혹은 1개 존재 가능
-repeated: 여러 개 존재 가능(0개 포함)


http://skccblog.tistory.com/1001