TIL 081623

Q: 배열, 링크드리스트를 비교하여 설명해주실 수 있을까요?

A: 

 

배열과 연결 리스트 비교

장점

• 배열 : 인덱스를 통한 빠른 접근 가능
• 연결 리스트 : 삽입/삭제 용이

단점

• 배열 :
  • 삽입/삭제가 오래 걸림
  • 배열 중간에 있는 데이터가 삭제되면, 공간 낭비가 발생함
• 연결 리스트 : 임의 접근이 불가능하여, 처음부터 탐색을 진행해야 함

용도

• 배열 : 빠른 접근이 요구되고, 데이터의 삽입과 삭제가 적을 때
• 연결 리스트 : 삽입과 삭제 연산이 잦고, 검색 빈도가 적을 때

 

배열(Array)	연결 리스트(Linked List)
정적 자료구조	동적 자료구조
미리 크기를 정해 놓음	크기를 정할 필요가 없음
연속된 메모리 주소를 할당 받음	연속된 메모리 주소를 할당 받지 않음
접근, 탐색 용이	추가, 삭제 용이
index 존재	Node 존재

 

https://kimmeh1.tistory.com/473

[자료구조] Array와 Linked List의 차이는 무엇일까?

https://velog.io/@xxhaileypark/%EC%9E%90%EB%A3%8C-%EA%B5%AC%EC%A1%B0-%EB%B0%B0%EC%97%B4-%EC%97%B0%EA%B2%B0-%EB%A6%AC%EC%8A%A4%ED%8A%B8-Array-LinkedList

[자료 구조] 배열 & 연결 리스트 (Array & LinkedList)

https://blacklobster.tistory.com/8

간략 설명! 배열(Array)과 연결 리스트(Linked List)에 대해서 알아보자! - 차이점과 시간복잡도, 활용

 

 

 

Q: 우선순위 큐의 시간복잡도는 어떻게 되며 그 이유는 무엇인지 설명해주실 수 있을까요?

A: 

배열로 저장한 데이터에서 우선순위가 가장 높은 데이터를 찾는 것은 시간복잡도는 O(N)입니다.

데이터가 정렬되어 있다면 이진 탐색(Binary Search)을 통해 O(logN)도 가능합니다.

 

https://laboputer.github.io/ps/2017/10/06/priorityqueue/

[자료구조 2] 우선순위 큐(Priority Queue) 이해하기

 

Priority Queue에서 특정 원소를 찾기 위해서는 전체 노드를 우선순위에 따라 반복적으로 확인해야 한다. 이 때문에, O(N)의 시간 복잡도를 가진다.

 

https://kotlinworld.com/442

[Kotlin] PriorityQueue란 무엇인가? Priority Queue의 삽입, 삭제, 탐색을 위한 시간 복잡도 알아보기

• 우선순위 큐의 삽입과 삭제는 𝑂(𝑙𝑜𝑔𝑁)의 시간 복잡도를 가집니다
• 따라서 우선순위 큐를 이용한 정렬은 𝑂(𝑁𝑙𝑜𝑔𝑁)의 시간 복잡도를 가진다

https://velog.io/@april_5/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%9A%B0%EC%84%A0%EC%88%9C%EC%9C%84-%ED%81%90Priority-Queue

🌈 자료구조:: 우선순위 큐(Priority Queue)

 

• range()

https://www.codingfactory.net/11747

Python / range() / 연속된 수 또는 일정 간격의 연속된 수를 만드는 함수

https://dojang.io/mod/page/view.php?id=1271 

COS Pro 2급 파이썬: 15.4 숫자를 감소시키기

 

 

• 각 자릿수 분리해서 더하기

https://go-hard.tistory.com/96

[python] 파이썬 각 자리수 분리, 더하기