[Book] Hello Coding 알고리즘 (알고리즘 소개, 선택 정렬)

[ 1장 알고리즘 소개 ]

• 많이 사용하는 빅오 실행 시간의 예
  • O(log n), 로그 시간 : 예) 이진 탐색
  • O(n), 선형 시간 : 예) 단순 탐색
  • O(n * log n) : 예) 퀵 정렬과 같이 빠른 정렬 알고리즘
  • O(n²) : 예) 선택 정렬과 같이 느린 정렬 알고리즘
  • O(n!) : 예) 외판원 문제와 같이 정말 느린 알고리즘
• 빈 종이에 16개의 네모칸을 만드는 문제를 예로 들어 각 빅오 실행 시간을 알아보자.

네모 칸의 수	O(log n)	O(n)	O(n log n)	O(n²)	O(n!)
16개	0.4초	1.6초	6.4초	25.6초	66301년
256개	0.8초	25.6초	3.4분	1.8시간	2. x 10⁴⁹⁸년
1024개	1.0초	1.7분	17분	1.2일	1.72 x 10²⁶³¹년

 

• 이진 탐색은 단순 탐색보다 아주 빠르다.
• O(log n)은 O(n) 보다 빠르다. 리스트의 원소의 개수가 증가하면 상대적으로 더 빨라진다.
• 알고리즘의 속도는 시간으로 측정하지 않는다.
• 알고리즘의 시간은 어떻게 증가하는가로 측정한다.
• 알고리즘의 시간은 빅오 표기법으로 나타낸다.

 

---

[ 2장 선택 정렬 ]

• 배열
  • 배열의 장점 : 배열은 배열만의 어떤 원소든 바로 찾을 수 있기 때문에 임의의 원소 값을 읽는데 최고.
  • 배열의 단점 : 모든 원소의 값을 한 번에 읽을 경우
• 연결 리스트
  • 연결 리스트의 장점 : 모든 원소의 값을 한 번에 읽을 경우.
  • 연결 리스트의 단점 : 특정한 원소만 알고 싶을 경우

 

• 중간에 원소 삽입하기 (리스트👍)
  • 리스트는 이전 원소가 무엇을 가리키는지 바꾸기만 하면 되므로 리스트에 삽입하는 것이 훨씬 쉬움.
  • 배열은 다음에 오는 모든 원소의 위치를 바꾸어야 하고,
    만약 공간이 부족하면 모든 원소를 새로운 장소로 복사해야 한다.
• 원소 삭제하기 (리스트👍)
  • 리스트는 이전 원소가 가리키는 위치만 바꾸면 되기 때문에 훨씬 쉬움.
  • 배열은 원소 하나만 삭제하고 싶을 때도 모든 것을 다 옮겨야 함.
    삽입할 때와 달리 삭제는 실패할 경우가 없다, 삽입할 때는 가끔 메모리에 남아있는 공간이 없어서 실패할 수 있지만, 원소를 지우는 것은 언제나 할 수 있음.

 

	배열	리스트
읽기	O(1)	O(n)
삽입	O(n)	O(1)
삭제	O(n)	O(1)

• 지우고자 하는 원소에 바로 접근할 수 있을 때만 삽입과 삭제가 O(1) 시간이 된다.
• 연결 리스트에서 첫 번째 원소와 마지막 원소는 보통 바로 접근이 가능하기 때문에 지우는 데 O(1) 시간 소요.
• 배열을 더 많이 사용하는 이유 : 배열에서는 임의의 원소에 접근하는 것이 가능하기 때문에.
  
  
• 자료 접근 방식
  • 임의 접근 (random access) : 
    • 배열은 임의 접근이 가능하다.
  • 순차 접근 (sequential access) : 원소를 첫 번째부터 하나씩 읽는 것.
    • 연결 리스트는 순차 접근밖에 할 수 없다. 

 

< 2장 요약 >

• 컴퓨터 메모리는 거대한 서랍장과 같다.
• 여러 개의 항목을 저장하고 싶을 때는 배열이나 리스트를 사용해라.
• 배열을 쓰면 모든 항목은 이웃하는 위치에 저장된다.
• 리스트를 쓰면 모든 항목이 흩어지지만, 각 항목은 다음 항목의 주소를 저장하고 있다.
• 배열은 읽기가 빠르다.
• 연결 리스트는 삽입과 삭제가 빠르다.
• 배열의 모든 원소는 같은 자료형(예 : 모두 정수형이거나 모두 실수형)이어야 한다.

---

[ 출처, 참고 : Hello Coding 알고리즘 ]