[누구나 자료구조와 알고리즘] 1~2장_자료구조와 알고리즘이 중요한 이유

읽게된 계기

• 비전공자이다보니 CS에 대한 기본지식이 부족했다.
• 최근 프로그래머스 문제를 많이 풀다보니 자료구조와 알고리즘이 절실하게 필요했다.
• 처음이므로, 쉽게 풀어쓴 책이어야 했다.

1장 자료구조가 중요한 까닭

• 자료구조
  1. 자료구조란 데이터를 조직하는 방법이다. => 데이터 조직을 어떻게 하는가에 따라 "코드의 실행 속도"에 미치는 영향이 매우 크기 때문에 자료구조를 이해해서 효율적인 코드를 작성할 수 있어야 한다.
  2. 연산
     • 읽기 : 자료 구조내 특정 위치를 찾아보는 것
     • 검색 : 자료 구조내에서 특정 값을 찾는 것
     • 삽입 : 자료 구조에 새로운 값을 추가하는 것
     • 삭제 : 자료 구조에서 값을 제거 하는 것
  3.  속도 측정
     
     • 시간이 아닌 얼마나 많은 "단계"가 필요한지를 측정
       • Why? 하드웨어마다 성능이 천차만별이기 때문
     • 연산의 속도 측정은 연산의 "시간 복잡도" 측정 => 속도/시간복잡도/효율성/성능 모두 같은 의미로 사용
• 배열의 연산
  • 읽기 : 한 단계로 끝나는 연산은 가장 빠른 연산 유형 => 컴퓨터의 메모리는 격자로 된 셀로 이루어져 있고 각 셀에 하나의 데이터가 저장되고 특정 주소를 가지기 때문. O(1)
  • 검색 : 값을 찾기 위해 인덱스를 모두 들여다 봐야한다. 만약 5의 길이를 가진 배열은 최악의 경우 5단계를 거쳐야만 찾을 수 있다. O(N)
  • 삽입 : 배열의 끝에 값을 삽입할 시 시간복잡도는 O(1)이다. 하지만 배열의 처음 혹은 중간에 삽입할 시 삽입되는 기점으로 데이터들을 한칸씩 이동시켜야 하므로 최악의 경우 N+1의 단계를 거치게 된다.
  • 삭제 : 처음이나 중간의 데이터를 삭제할 시 삽입과 동일하게 한칸 씩 이동하는 과정이 필요하다. 최악의 경우 N의 단계를 거치게 된다.
    
    
• 집합(단 하나의 규칙으로 달라지는 효율성)
  • 집합 = 중복 값을 허용하지 않는 자료구조 = JAVA의 Set
  • 읽기,검색,삭제 = 배열과 동일
  • 삽입 : 삽입하려는 데이터가 중복되었는지 검색하는 과정이 필요하다 최악의 경우 2N+1(검색 : N + 맨 처음 삽입 N+1)
    • 위 배열보다 시간복잡도가 떨어지지만 중복데이터가 없어야 할 때는 필수로 쓰일 수 있다. 다만, 이러한 요구사항이 없다면 집합 삽입보다 배열 삽입이 효율적이므로 배열이 나을 수 있다.
• "자료 구조의 성능 측정은 연산에 필요한 단계 수를 구하는 게 핵심이다.

---

2장 알고리즘이 중요한 까닭

• 알고리즘
  • 어떤 과제를 완수하는 명령어 집합
• 전형적인 배열 VS 정렬된 배열
  • 삽입 : 전형적인 배열 > 정렬된 배열
    • 정렬된 배열의 경우 값을 넣을 시 정렬에 맞게 넣어야 하기에 과정이 더 필요하다 => N+1
    • 전형적인 배열의 경우 맨 끝에 넣을 시 O(1) 가장 짧다
  • 검색 : 전형적인 배열 < 정렬된 배열
    • 전형적인 배열(선형검색) 시간복잡도 O(N)

public static int LinearSearch(int[] arr, int find) {
	//for문으로 순회
	for (int i = 0; i < arr.length; i++) {
    //찾는값이 있을 시 반환
    	if (find == arr[i]) {
        	return i;
           }
      }
      // 최악의 경우 arr.length만큼 반복
        return -1;
 }

• 정렬된 배열(이진검색) 시간복잡도 O(logN)

int binarySearch1(int key, int low, int high) {
	int mid;

	if(low <= high) {
		mid = (low + high) / 2;

		if(key == arr[mid]) { // 탐색 성공 
			return mid;
		} else if(key < arr[mid]) {
			// 왼쪽 부분 arr[0]부터 arr[mid-1]에서의 탐색 
			return binarySearch1(key ,low, mid-1);  
		} else {
			// 오른쪽 부분 - arr[mid+1]부터 arr[high]에서의 탐색 
			return binarySearch1(key, mid+1, high); 
		}
	}

	return -1; // 탐색 실패 
}

• 정렬된 배열은 삽입의 경우 일반 배열보다 느리지만 이진 검색 알고리즘을 사용한 검색은 훨씬 빠르다 => 애플리케이션의 사용자 관점에서 삽입을 많이 하겠는가? 검색을 많이 하겠는가? => 검색이다. 그렇기 때문에 애플리케이션은 정렬된 배열을 사용한다.
  • 즉 누가 사용하는가?에 따라 같은 자료구조라도 알고리즘이 완전히 달라질 수 있는 것이다.

---

2장까지 읽었을때 먼저 새로운 사실은 내가 자료구조와 알고리즘의 의미를 모르고 있었다는 것이다.

자료구조는 자바에서 자료형과 마찬가지로 자료가 구성되어 있는 것(list인지 set인지)이고 그것을 풀어나가는 과정이 알고리즘인 것이다.

흥미로운 사실은 알고리즘은 사용자 관점에 따라 구성한다는 것인데, 그동안 문제를 풀어오기에 급급했지 사용자 관점(누가 사용하는가?)에서 고려하지 않았다. 앞으로 코드를 작성할 시 누가 사용할지에 따라 적절한 자료구조를 가져와 적절한 알고리즘을 전개해나가는 연습이 필요할 것 같다.