누구나 자료 구조와 알고리즘 #1

안광의·2022년 5월 8일
알고리즘자료구조
2

자료구조와 알고리즘

목록 보기
1/7
post-thumbnail

시작하며

비전공자 개발자로서 CS 지식이 부족하다고 항상 생각해왔고, 아직 실무에서 깊은 CS 지식이 필요하지는 않지만 추후에 최적화나 성능 관련 이슈를 해결하려면 기본이 되어야 한다고 생각한다. 이런 생각을 팀장님께 말씀드렸더니 실무에 적용할 수 있는 자료구조와 알고리즘 관련 공부를 시작으로 범위를 확대해 나가는게 좋겠다고 의견을 주셔서 자료구조와 알고리즘 공부를 시작해보려고 한다.




누구나 자료구조와 알고리즘(개정 2판)

부트캠프에서 자료구조와 알고리즘 관련된 학습과 코딩 문제들을 풀어보긴 했지만 프로젝트와 취업 준비를 하면서 공부했던 내용을 많이 잊어버리게 되었다. 이미 알고 있는 내용이더라도 놓치고 있는 부분이 있을 수도 있고 복습한다는 생각으로 기초부터 정리되어 있는 책을 통해 공부를 시작하려고 한다.

이 책은 비전공자도 쉽게 이해할 수 있도록 정리해놓은 책으로 더북(https://thebook.io/080274/)에서 5장까지 공개되어 있고, 추후 구매하여 끝까지 학습할 예정이다.

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

  • 자료구조
    • 데이터를 조직하는 방법 => 데이터를 어떻게 조직하는가에 따라 코드의 실행 속도에 영향을 미치기 때문에 자료구조를 이해해서 효율적인 코드를 작성할 수 있다.
    • 연산
      • 읽기 : 자료 구조 내 특정 위치를 찾아보는 것
      • 검색 : 자료 구조 내에서 특정 값을 찾는 것
      • 삽입 : 자료 구조에 새로운 값을 추가하는 것
      • 삭제 : 자료 구조에서 값을 제거하는 것
    • 속도 측정 : 연산의 속도는 하드웨어의 성능마다 다르기 때문에 시간이 아닌 계산 단계의 관점에서 측정되어야 한다.
  • 배열
    • 읽기 : 컴퓨터의 메모리는 격자로 된 셀로 이루어져있고 각 셀에 하나의 데이터가 저장되고 특정 주소를 가지고 있어서 한번에 접근이 가능하다. O(1)
    • 검색 : 값을 찾기 위해 셀마다 한번씩 확인해야 하므로 5개의 셀로 이루어진 배열의 최대 단계 수는 5이다. O(N)
    • 삽입 : 배열의 끝에 값을 삽입한다면 시간복잡도는 O(1)이지만 만약 배열의 처음이나 중간에 삽입한다면 데이터들을 한칸씩 이동시켜야 하므로 N+1의 단계를 거치게 된다.
    • 삭제 : 처음이나 중간의 데이터를 삭제한다면 삽입과 마찬가지로 빈 공간을 채우기 위해 한칸 씩 이동하는 과정이 필요하여 N의 단계가 필요하다.
  • 집합(배열 기반 집합)
    • 중복 값을 허용하지 않는 자료구조(ex) javaScirpt의 Set)
    • 읽기, 검색, 삭제 : 배열과 동일
    • 삽입 : 삽입하려는 데이터가 중복되었는지 검색하는 과정이 필요하기 때문에 최악의 경우, 2N+1(N: 검색, N+1: 맨 처음에 삽입)의 단계가 필요하다.


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

  • 알고리즘

    • 어떤 과제를 완수하는 명령어의 집합 => 자료구조 뿐만 아니라 적절한 알고리즘을 통해 계산 단계를 줄일 수 있다.

  • 정렬된 배열

    • 삽입 : 삽입될 데이터와 기존 데이터를 배열의 처음부터 비교한 후 맞는 위치에 삽입한다. 비교 이후에 뒤에 있는 데이터를 한칸씩 이동하는 과정이 필요하기 때문에 삽입의 필요한 단계 수는 새 값의 크기와 관계 없이 비슷하다.
    • 검색 : 배열의 처음부터 값을 확인하다가 찾으려는 값보다 큰 값이 나올 경우 해당하는 데이터가 없기 때문에 검색이 종료된다.

  • 이진 검색

    //부트캠프에서 풀었던 이진 검색 알고리즘을 사용한 코딩 문제
const binarySearch = function (arr, target) {
let up = 0
let down = arr.length-1
while(up <= down) {
  let half = Math.floor((up+down)/2)
  if(arr[half]=== target) return half;
  if(arr[half] > target) {
    down = half -1
  }
  else {
    up = half + 1
  }
}
return -1
};
    • 100개의 값을 갖는 배열에서 검색에 필요한 최대 단계 수
      • 선형 검색 : 100단계 O(N)
      • 이진 검색 : 7단계 O(logN)
    • 정렬된 배열은 삽입의 경우 일반 배열보다 느리지만 이진 검색 알고리즘을 사용한 검색은 훨씬 빠르다. => 애플리케이션의 기능(삽입과 검색 중 어떤 연산이 자주 일어나는가)을 고려해서 적절한 자료구조와 알고리즘을 적용할 수 있어야 한다.


3장 빅 오 표기법

  • 빅 오 : 데이터가 늘어날 때 알고리즘의 성능이 어떻게 바뀌는지를 의미하며 단순히 알고리즘에 필요한 단계 수를 알려주는 것이 아니라, 데이터가 늘어날때 단계 수가 어떻게 증가하는지를 설명한다.
    • 항상 3단계가 필요한 알고리즘은 데이터의 수에 관계 없이 일정하기 때문에 O(1)로 표기한다.
      • O(100) -> O(1)
      • O(3N) -> O(N)
      • O(3N2) -> O(N2)
    • 선형 검색이 항상 N의 단계가 걸리는 것은 아니지만 빅오는 일반적으로 최악의 시나리오를 가정한다.
  • O(logN)
    • 컴퓨터 과학에서 O(logN)은 사실 O(log2N)을 줄여 부르는 말로 원소가 하나가 될 때까지 데이터 원소를 계속해서 반으로 줄이는 만큼의 단계 수가 걸린다는 뜻이다.


4장 빅 오로 코드 속도 올리기

  • 버블 정렬(bubble sort)
    1. 배열의 처음부터 연속된 두 항목을 비교하여 올바른 위치로 바꾼 후 그 다음 항목도 배열의 마지막 항목 차례가 될때까지 같은 방식으로 정렬한다. (길이가 n인 배열 : 0,1비교 -> 1,2 비교 ... n-2,n-1 비교)
    2. 1번 과정을 패스 스루라고 하며, 더 이상 항목간 자리 교환이 일어나지 않을 때까지 패스 스루를 반복한다.

    //버블 정렬 예시
const bubbleSort = function (arr) {
  let temp = 0
  for (let i=0; i<arr.length-1; i++) {
    let breakcheck = 0
    for (let j=0; j<arr.length-1-i; j++) {
      if(arr[j] > arr[j+1]) {
        temp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = temp
        breakcheck ++
      }
    }
    if(breakcheck === 0) break; 
  }
  return arr
};
  ```

  • 버블 정렬의 효율성

    • 버블 정렬은 비교(어느 쪽이 더 큰지 두 수를 비교)와 교환(정렬하기 위해 두 수를 교환), 두가지 단계를 포함한다.
    • 최악의 경우를 고려하여, 내림차순으로 정렬된 10개의 요소를 가진 배열을 정렬할 때 45번의 비교와 45번의 교환 총 90단계가 필요하다.
    • (9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1) * 2
    • O(N2)

  • N2 개선

    //시간복접도 O(N^2)의 중복 여부 검사 함수
function hasDuplicateValue(array) {
  for(let i = 0; i < array.length; i++) {
      for(let j = 0; j < array.length; j++) { 
          if(i !== j && array[i] === array[j]) {
              return true; 
          }
      } 
  }
  return false; 
}
    //배열의 인덱스를 활용하여 O(N)으로 시간 복잡도 개선
function hasDuplicateValue(array) {
  let existingNumbers = [];
  for(let i = 0; i < array.length; i++) {
      if(existingNumbers[array[i]] === 1) { 
          return true;
      } else {
          existingNumbers[array[i]] = 1;
      } 
  }
  return false; 
}



마치며

누구나 자료구조와 알고리즘의 목차를 읽어보니 대부분은 이미 알고 있는 내용이여서 복습하는 식으로 공부한 이후에 추가적으로 학습할 수 있는 책이나 알고리즘을 활용한 코딩 테스트를 공부할 예정이다. 이번에 정리한 1~3강 역시 이미 배운 내용이었지만 부트캠프를 진행하면서 짧은 시간에 학습했기 때문에 빠진 내용은 없었는지 꼼꼼하게 읽어보면서 정리하였다.

profile
안광의
개발자로 성장하기
다음 포스트

누구나 자료 구조와 알고리즘 #2

0개의 댓글