TIL 2023.03.30

알고리즘 세션

 

2일차

 

링크드리스트

노드가 꼬리의 꼬리를 무는 형태

노드를 클래스로 정의할 수 있음

노드를 바탕으로 이러한 자료구조(링크드리스트)를 나타내야하는데

가장 앞에 있는 노드= 헤드 가장 뒤에+테일

헤드에 노드값 넣고 초기화

어팬드 갯 노드

 

예를 들어 노드가 엄청나게 많이 연결돼있어

n번째 노드에 접속하고 싶다

이때 검색의 시간복잡도 O(n) 최악의경우 빅-오

 

링크드리스트 굉장히 호율적인 자료구조지만 아닌 경우도 있어

1000만 회원 웹사이트 1000만회원을 링크드리스트로 저장을해?

검색하는데 천만이면 0.1초 걸리는데 느린거거든요

 

 

스택/ 큐, 정렬

• 컴퓨터 사이언스 전반에서 매우 자주 등장하는 자료구조
• 코딩테스트 빈출 유형

 

스택 개념

한쪽 끝이 막혀 있는 통과 같은 자료구조

스택에 데이터를 저장한다 = 스택에 푸쉬한다

위에 차곡차곡 쌓이게 되겠죠

가장 큰 특성 데이터를 하나를 뺀다고(pop) 가정하자 c부터 빠져나가겠죠.

한 쪽 끝이 막혀있기 때문에 가장 나중에 들어온 데이터가 나온다(pop)

나중에 삽입된(push) 데이터가 먼저 나오는(pop) 자료구조

후입선출(Last-In-First_Out, LIFO)

 

큐 개념

양쪽 끝이 뚫려 있는 통과 같은 자료구조

큐에 데이터 저장 하는 거 = enqueue

큐에 데이터 뺴는 거 = dequeue

먼저 삽입된(enqueue) 데이터가 먼저 나오는(dequeue) 자료구조

선입선출(First-In-First-Out, FIFO)

 

스택/큐의 활용

자료구조/알고리즘, 활자 그대로 암기하지 말 것!

“그래서 이 자료구조/알고리즘이 어디에/어떻게 쓰이는데?”

 

스택의 활용

데이터를 임시 저장하고 싶을 때

• 최근에 임시 저장한 데이터를 가장 먼저 활용해야 할 때
• 쌍을 맞추어 데이터를 임시 저장하고 싶을 때
• 뒤로가기 기능을 만들고 싶을 때

 

큐의 활용

데이터를 임시 저장하고 싶을 때

• 큐를 버퍼로 활용
• 임시저장된 데이터를 차례차례 내보내야/꺼내와야 할 때
• 줄을 세우고 싶을 때

 

스택

스택 선언: 주로 리스트 사용

 

큐

큐 선언

 

변형1: 원형 큐

원형으로 이루어진 큐

 

변형2: 덱

Deque(=Double-Ended Queue)

양쪽에서 데이터 삽입(enqueue), 삭제가 가능한 큐

 

변형3: 우선순위 큐

먼저 저장된 데이터가 먼저 나가는 구조가 아닌

저장된 순서와 무관하게 우선순위가 높은 데이터가 먼저 나가는 큐

 

 

정렬

 

정렬의 개념

데이터를 정해진 기준에 따라 재배치하는 것

다양한 정렬 알고리즘이 존재

• 버블 정렬 O(n^2)
• 선택 정렬 O(n^2)
• 삽입 정렬 O(n^2)
• 퀵 정렬 O(n lon n) 복잡한데 성능 좋아

 

파이썬 내장 정렬 함수

sort() 배열의 값 자체를 바꾼다

sorted() 배열 자체를 조작하진 않음

 

그럼 내장 함수만 알면 되는 건가요?

놉!

코딩테스트에서 사용되는 정렬 유행

• 내장 함수만으로 풀 수 있는 문제
• 정렬 알고리즘의 원리를 묻는 문제

 

다양한 정렬 알고리즘 - 삽입 정렬

앞에서부터 차례대로 비교하여, 자신의 위치를 찾아 삽입하는 방식

시간복잡도 O(n^2)

[5,2,9,1,5,6] -> [1,2,5,5,6,9]

?[0]=5 비교 재배치 [1]=2

배열의 인덱스 조작

 

 

다양한 정렬 알고리즘 - 버블 정렬

요소를 쭉 순회하며

인접한 요소와 비교하며 정렬이 제대로 되었는지 확인하며

정렬이 제대로 될 때까지 인접한 요소와 바꿔치기하는 방법

시간복잡도 O(n^2) 

9라는 요소가 마치 거품이 위로 올라가듯 정렬된대서 버블 정렬

 

 

다양한 정렬 알고리즘 - 선택 정렬

요소들 중 최소값을 찾아

그 값을 요소의 맨 처음 값으로 대체하고

맨 처음 값을 뺀 나머지 요소들이 정렬될 때까지 반복한다

시간복잡도 O(n^2) 

 

 

다양한 정렬 알고리즘 - 퀵 정렬

분할 정복(divide-and-conquer)알고리즘의 일종

• 큰 문제를 작은 분리하여 작은 문제들을 해결함으로써 큰 문제를 해결

이름처럼 빠른 정렬: 시간복잡도 O(nlogn)

내장 정렬 함수의 대부분의 원리가 되는 알고리즘

1. 임의의 하나의 요소를 고른다. 이를 피벗(pivot=기준점)이라고 한다
2. 피벗의 좌,우를 기준으로 정렬한다. 정렬 뒤 피벗은 더이상 움직이지 않는다.
3. 분할된 두 개의 작은 배열에 대해 재귀(Recursion)적으로 이 과정을 반복한다.

재귀에 대한 이해