2020-2021/누구나 알고리즘[책 스터디]4 4. Big O Big O : 단계 수 계산 알고리즘의 효율성을 쉽게 분류하고 이해하기 위해서 사용된 표기법 Big O는 시간단위가 아닌 알고리즘에 필요한 단계 수만을 고려한다. "데이터가 증가할수록 단계 수는 어떻게 변하는가 ?" 라는 질문의 답 자료구조에 표기된 Big O는 최악의 시나리오를 바탕으로 표기됨 , 왜? 최악의 시나리오에서 알고리즘이 얼마나 비효율적인지 파악해야 최악을 대비함과 최선의 알고리즘을 선택할 수 있기 때문에 최악의 경우를 표기한다. ex) 보통 배열에서 검색을 할 때, 찾고 싶은 요소가 배열의 맨 앞에 있을 때, Big O는 constant이다. 하지만 배열의 검색은, 찾고 싶은 요소가 배열의 맨끝에 있다는 시나리오로 표기한다. Big O의 종류 1. O(1) 상수시간 [constant tim.. 2021. 2. 21. 3. 정렬된 배열과 이진검색 선형검색(Linear Search) 모든 요소들이 내림차순 또는 오름차순으로 정렬되어 있는 상태의 배열과 기존 배열이 있다. 이때 50을 각각의 배열에서 찾을 때 더 효율적인 배열은 ? 기존배열에서 50이라는 요소를 찾기 위해서는 모든 요소를 순회해야하는 반면 50이라는 요소를 배열안에서 찾을 때, 타깃숫자가 순회하는 숫자보다 작다면 순회를 멈춘다. 즉 정렬된 배열은 기존 배열보다 순회하는데 있어서 효율적이다. [단 찾는 요소가 배열의 마지막 일 때에 시간 복잡도는 같다.] 정렬된 배열에 요소를 추가할 경우, 추가하려는 요소와 기존 배열의 요소들을 비교한 후, 추가된다. 이때 배열을 추가하기 위한 최악의 상황은 모든 요소를 순회한 후 추가해야 하기 때문에 효율적이라고 보기 어렵다. 이진검색 (Binary.. 2021. 2. 13. 2. 배열과 집합 배열 배열은 순서라는 개념을 갖고 있는 기본적인 자료구조 배열은 요일약통처럼 데이터를 보관할 수 있는 통! 요일은 index, 요일안에 들어있는 약들이 element라고 생각하기! 자료구조에는 크게 읽기 ,검색, 추가, 삭제의 기능이 있다. 읽기 읽기는 월요일부터 일요일까지 써져있는 약통을 열어보는 것이다. 할아버지께서 화요일에 있는 약을 꺼내달라는 부탁을 들었을 때, 약통에 화요일이라고 써져있는 케이스 안에 있는 약을 드리면된다. 약통을 보는 순간 화요일를 바로 찾을 수 있듯이, 컴퓨터도 배열의 index(요일)값을 통해 element(약)를 조회할 수 있다. 검색 검색은 약통에 모든 알약의 색이 다르다고 가정했을 때, 특정색의 약을 찾는 것과 같다. 할머니께서 노란색 영양제를 꺼내달라고 하셨을 때, .. 2021. 2. 10. 1. 누구나 자료구조와 알고리즘 ! 봄결님과 여래님의 추천으로 오늘부터 가볍게 읽으려고 구매한 책이다 : ) 이 책의 목적은 독자에게 자료구조와 알고리즘의 원리를 이해시키고, 이해한 원리를 로직에 적용시켜 보다 빠르고, 간결한 코드를 생각할 수 있게 돕기 위함이라고 한다. 오늘은 이 책의 인트로를 자세하게 읽어보았다. 가장 눈에 들어온 글귀는 "자료구조와 알고리즘은 우리 상식선에서 이해할 수 있다. 개념은 쉽고 분명한 말로 풀어서 설명하고, 많은 그림을 사용해 즐겁게 이해할 수 있도록 돕는다." 이다. 어려운 개념을 쉬운말로 풀어서 이해가 쉽게하고, 거기에 시각자료를 넣어 재미를 주며 집중력을 높인다. 이 책이 어떻게 독자에게 어려운 개념을 이해시킬지에 대한 전략이다. 말은 쉽지만 누군가를 이해시키는 것은 정말 어려운 일이다. 정말 기대된.. 2021. 2. 9. 이전 1 다음
