Krafton_jungle 5기 4일차 TIL - 기본 자료구조

 오늘 발표를 마무리 하고 이제 본격적으로  알고리즘 학습주차에 접어들었다.

 

본격적으로 알고리즘 학습주차에 들어가기 전 백승현 코치님께서 기본적으로 알고 가야 할 개념들에 대해 한번씩 집어주셨다.

 

알고리즘을 시작하기 전 정확히 알고있어야 하는 개념들

1. 링크드 리스트, 배열

• 링크드 리스트와 배열은 비슷한 개념으로 이해하면 된다. 링크드 리스트는 각 메모리가 연속되어 나열되는 배열의 개념과는 다르게 현재 값과 다음 순서의 자료가 있는 주소를 가르키는 데이터를 하나의 노드로 묶어 배열을 구성한다.
• 링크드 리스트와 단순 배열의 가장 큰 차이는 저장된 값의 배열이 메모리 상에 연속되는지 아닌지 차이다.

	장점	단점
배열	배열의 경우 정적 자료구조에 해당하며, 최초 할당  시 미리 크기를 정해놓게 되어 연속된 메모리 주소를 할당받게 된다. 따라서 배열은 인덱스로 접근이 가능하며, 인덱스가 제공될 경우 접근과 탐색에 용이하다 ex ) 주소를 알고있으면 배달하기 쉽다	하지만 미리 크기를 정해놓았기 때문에 수정하는 것이 불가능하다. 이미 크기를 정해놓아 배열의 크기 이상의 데이터를 저장할 수 없다.
연결 리스트	연결 리스트의 경우 연속된 메모리를 할당받지 않고 노드로 구성되는데, 노드에는 값을 입력받는 메모리와 다음 노드를 가르키는 주소값을 저장하는 구조로 이루어져 있다. 이는 크기의 제한이 없고, 데이터의 추가와 삭제가 자유롭다는 장점을 가진다.	하지만 배열처럼 인덱스를 통해 내가 원하는 노드로 바로 이동할 수 없다는 단점이 있으며 , 이는 하나의 연결리스트를 탐색하려면 무조건 O(n)의 시간 복잡도가 나온다고 해석할 수 있다.

 

2. 스택, 큐, 해시 테이블

• 스택이란 이름과 같이 데이터가 하나씩 쌓아올라가는 형식을 생각하면 이해가 편하다.

• 이는 즉 데이터가 들어온 역순으로 데이터를 빼낸다는 의미이다.
• 이를 LIFO(Last In First Out) 라고 하며 파이썬 코드로 비유하자면 배열에 삽입하는 push 연산과 배열의 마지막을 추출하는 pop 연산을 생각하면 편하다.

 

• 큐란 스택과는 어쩌면 반대의 개념으로 이해해도 될 정도로 동작 원리가 반대이다.

• 편의점 사장님이 좋아할것 같은 구조로 이루어져 있다.
• 이를 FIFO (First In First Out) 라고 하며 파이썬 코드로 비유하자면 dequeue의 push와 popleft 연산을 생각하면 될 것 같다. 

 

• 마지막으로 해쉬 테이블인데 Key와 Value로 데이터를 저장하는 자료구조이고, 파이썬의 dict 자료구조형을 생각하면 편하다.
• 해시 테이블은 빠른 검색속도 O(1) 를 제공하는데 이는 내부적으로 배열을 사용하여 데이터를 저장하기 때문이다.
• 이와같은 검색이 가능한 이유로는 key를 hash함수 연산을 통해 인덱스 값을 계산하고 해당 인덱스에 value를 저장하기 때문에 key값만 제공이 되면 O(1)이라는 겅이로운 탐색 속도를 제공할 수 있다.
• 이 때문에 동일한 key값을 가지고 있는 value가 따로 존재할 수 없는것
• 이럼에도 불구하고 hash값이 충동하는 경우가 발생할 수 있는데 이는 분리 연결법(Separate Chaining)과 개방 주소법 (Open Addressing)으로 해결한다. ( 추가적으로 학습 필요 ) 

 

3. 시간 복잡도, 공간 복잡도

 

• 시간 복잡도란 하나의 알고리즘이 실행될때 발생하는 연산의 횟수를 나타낸다.
• 공간 복잡도란 프로그램 실행과 완료에 얼마나 많은 메모리가 필요한지를 나타낸다.
• 주로 빅오 표기법을 주로 사용하며, 보통 알고리즘의 성능을 판단할 때는 시간 복잡도를 위주로 판단한다. ( 백준만 봐도 시간초과가 많이뜨는것을 알 수 있음 )
• 각 알고리즘의 시간복잡도가 더 빠른지 숙지하고 어떤 상황에서 사용해야 할 지 숙달이 필요함

 

4. 재귀함수 ( 너무싫어 )

 

• 애증의 재귀함수는 작성하고 나면 기본 반복문보다 훨씬 더 직관적으로 코드의 로직을 파악할 수 있다.
• 수학적 귀납법을 이해하면 재귀함수를 이해하기 쉽다.
• 재귀함수는 기본 반복문보다는 느리다는 단점이 있지만 조건이 좀 더 명확하다.

 

5. 정렬 알고리즘

 

• 대표적인 알고리즘에 속하는 삽입정렬, 병합정렬, 힙 정렬, 퀵 정렬은 개발을 하는 사람이라면 무조건 알아야 한다.

 

삽입정렬

2중 for문

출처 : https://commons.wikimedia.org/wiki/File:Insertion-sort-example.gif

우선 코드를 보면 2중으로 for문을 돌리며 현재 노드와 다음 노드를 비교하고, 만약 현재 노드가 더 작으면 서로 위치를 스왑하는 방식으로 정렬을 하는 것을 확인할 수 있다.

이렇게 되면 2중 포문을 돌리기 때문에 O(n^2) 시간복잡도를 제공하는 것을 알 수 있다.

장점	단점
알고리즘이 단순하며, 최선의 경우 O(n)의 시간 복잡도를 제공해 다른 알고리즘에서도 일부 차용될정도로 안정적이다. 정렬하고자 하는 배열 안에서 교환되어 추가 메모리를 사용하지 않는다.	배열의 길이가 길어질수록 비효율적이며, 평균과 최악의 시간 복잡도가 O(n^2)로 비효율적이다.

 

 

병합 정렬

병합정렬 코드

 

내가 재귀를 이해하는데 가장 많은 도움을 준 병합 정렬이다. 어떻게 이런 생각을 했을까

예시를 보면 알 수 있다 싶이 최선과 최악의 경우 모두 O(nlog₂n)임을 알 수 있다

장점	단점
대규모 데이터 처리에 효율적이다. 요소가 많은 경우에도 성능의 변화가 없다.	재귀 호출을 함으로 아무래도 메모리를 많이 사용할 수 밖에 없다. 작은 데이터를 처리할 경우 다른 정렬보다 비효율적이다.

 

 

나머지 자료구조는 내일 학습해야징