2022.11.9 TIL / 알고리즘 array, linked list

특정 자료구조는 삽입/삭제가 빠르고

특정 자료구조는 조회가 빠르다.

어떤 경우인가에 따라 다양한 자료구조와 알고리즘을 사용해야한다.

 

 

 

array와 linked list의 차이점

 

 

array

• 크기가 정해진 데이터의 공간. 한번 정해지면 바꿀 수 없다.
• 원소에 즉시 접근 가능하다. room[0]
• 상수 시간 내에 접근 할 수 있다는 것을 의미 O(1)
• 배열은 원소를 중간에 삽입/삭제 하려면 모든 원소를 다 옮겨야한다. O(N)의 시간 복잡도
• 원소를 새로 추가하려면 새로운 공간을 할당해야 하므로 매우 비효율적인 자료구조

 

 

linked list

• 리스트는 크기가 정해지지 않은 데이터의 공간. 연결고리로 이어주기만 하면, 자유자재로 늘어난다.
• 리스트는 특정 원소에 접근하려면 연결고리를 따라 탐색해야한다. O(N)의 시간복잡도를 가진다.
• 리스트는 원소를 중간에 삽입/삭제 하기 위해서 앞 뒤의 포인터만 변경하면 된다. 원소의 삽입/삭제는 O(1)의 시간 복잡도를 가진다.

 

 

 

오늘은 강의 보면서 이것저것 알고리즘 문제 푸는걸 따라했다. 원래 알고리즘에 취약한 사람이라 너무나도 힘들고 진빠진다.

그래도 처음 볼 땐 ????????????? 상태에서 여러 번 보니 .....의 상태로 변했다. (그나마 다행..)

아직 내가 직접 짜 보는데에는 어려움이 있지만 코드를 보고 해결 방법을 이해하려고 노력하고 있다.

 

강창민 튜터님이 준 팁을 많이 연습해봐야겠다. 알고리즘 푸는 방법을 우선 한국말로 설명 할 수 있을 것!