[자료구조] 2일차 자료구조란? - 구슬넣기 문제

💡 양쪽이 뚫린 파이프에 구슬을 넣을거다

: 이 문제에서는 연결 리스트가 더 좋다.

좋은 해법인지 판단하는 기준은 여러가지가 있다.

• 코드가 간결한가?
• 얼마나 빠른가?
• 리소스를 얼마나 차지하는가?
• 구현 시간이 짧은가?
• 등등

문제 해결방법

1. 문제를 파악한다. : 어떤 자료를 담을지, 자료에 어떤 의미가 있는지 파악
2. 자료구조에 필요한 기능을 파악한다. : 자료를 어떻게 사용하는지 파악
3. 문제를 효율적으로 해결하는 자료구조를 설계 및 사용한다. : 목적에 맞는 자료구조로 문제를 해결

시간 복잡도

• 알고리즘이 문제를 해결하는 데 걸리는 시간을 정량화하여 나타낼 수 있는 방법
• 일반적으로, 문제에서 주어지는 최악의 경우에 대한 소요 시간을 나타내는 데 사용.

 

---

배열

대략 몇 개의 명령이 수행되는가?

구슬을 왼쪽으로 삽입하면, 배열 내에서 한 칸씩 이동해야 하므로 느리다.

최악의 경우(구슬 n개를 모두 왼쪽으로만 삽입할 경우), 연산 횟수는??

 

---

연결리스트

• 연결리스트는 구슬을 어디로 넣든 한 번의 연산으로 수행된다.

대략 몇 개의 명령이 수행되는가?

구슬 n개를 모두 왼쪽으로만 삽입했을 때