어제보다 한걸음 더

https://product.kyobobook.co.kr/detail/S000001834743 누구나 자료 구조와 알고리즘 | 제이 웬그로우 - 교보문고 누구나 자료 구조와 알고리즘 | 사칙 연산으로 복잡한 알고리즘을 쉽게 이해해보자 수학 용어와 전문 용어가 아니어도 이해한다 이 분야의 책은 대부분 컴퓨터 공학 전공자를 대상으로 쓰였거 product.kyobobook.co.kr 삭제 삭제는 이진 탐색 트리에서 가장 어려운 연산이기 때문에 주의 깊게 실행해야한다. 리프 노드(트리의 가장 끝 노드)를 삭제하게 되면 아무런 문제가 없다. 하지만 중간 노드를 삭제하게 되면 해당 서브트리의 노드의 재배치가 필요하다. 삭제 알고리즘의 규칙 삭제 할 노드에 자식이 없으면 그냥 삭제한다 삭제 할 노드에 자식이 하나면 ..

https://product.kyobobook.co.kr/detail/S000001834743 누구나 자료 구조와 알고리즘 | 제이 웬그로우 - 교보문고 누구나 자료 구조와 알고리즘 | 사칙 연산으로 복잡한 알고리즘을 쉽게 이해해보자 수학 용어와 전문 용어가 아니어도 이해한다 이 분야의 책은 대부분 컴퓨터 공학 전공자를 대상으로 쓰였거 product.kyobobook.co.kr 데이터를 자주 정렬해야 한다면 항상 정렬된 순서로 유지하는 것이 좋다. - 정렬 알고리즘은 아무리 빨라도 O(NlogN)의 시간이 걸리기 때문이다. 정렬된 배열은 읽기에는 O(1), (이진)검색에는 O(logN)으로 우수한 성능을 낸다. - 하지만 삽입, 삭제 시에는 O(N)이 걸리기 때문에 비교적 느리다. 해시 테이블은 O(1)..

https://product.kyobobook.co.kr/detail/S000001834743 누구나 자료 구조와 알고리즘 | 제이 웬그로우 - 교보문고 누구나 자료 구조와 알고리즘 | 사칙 연산으로 복잡한 알고리즘을 쉽게 이해해보자 수학 용어와 전문 용어가 아니어도 이해한다 이 분야의 책은 대부분 컴퓨터 공학 전공자를 대상으로 쓰였거 product.kyobobook.co.kr 이어지는 장들에서 다룰 자료구조들은 모두 노드(node) 기반이다. 노드란 컴퓨터 메모리 곳곳에 흩어져있는 데이터 조각이다. 노드 기반 자료 구조는 데이터를 조직하고 접근하는 새로운 방법을 제공하는데 성능상 큰 이점이 많다. 연결 리스트의 효율성 면에서의 장단점(trade-off)를 알아보고, 성능이 크게 높아지는 상황도 알아 볼..

https://product.kyobobook.co.kr/detail/S000001834743 누구나 자료 구조와 알고리즘 | 제이 웬그로우 - 교보문고 누구나 자료 구조와 알고리즘 | 사칙 연산으로 복잡한 알고리즘을 쉽게 이해해보자 수학 용어와 전문 용어가 아니어도 이해한다 이 분야의 책은 대부분 컴퓨터 공학 전공자를 대상으로 쓰였거 product.kyobobook.co.kr 다음으로 읽을 단원은 14장 이지만, 트라이가 궁금해 17장 먼저 읽기로 했다. 정리 스마트폰의 자동완성(autocomplete) 기능은 어떻게 동작하는걸까? 전체 단어 사전에 접근했을 때, 정렬되지 않은 배열에서 찾는다면 O(N)이 걸리고, (N이 전체 단어 개수를 뜻하기 때문에 매우 느린 연산이다.) 해시 테이블도 O(1)으로..

https://product.kyobobook.co.kr/detail/S000001834743 누구나 자료 구조와 알고리즘 | 제이 웬그로우 - 교보문고 누구나 자료 구조와 알고리즘 | 사칙 연산으로 복잡한 알고리즘을 쉽게 이해해보자 수학 용어와 전문 용어가 아니어도 이해한다 이 분야의 책은 대부분 컴퓨터 공학 전공자를 대상으로 쓰였거 product.kyobobook.co.kr 퀵정렬(Quicksort)은 컴퓨터 언어 중 대다수가 내부적으로 채택한 정렬 알고리즘이다. 재귀를 사용함에도 불구하고 어떻게 알고리즘의 속도를 크게 향상시키는지 배우고, 실제 쓰이고 있는 다른 실용적인 알고리즘에도 똑같이 적용해볼 수 있다. 퀵정렬은 매우 빠른 정렬 알고리즘으로 특히 평균 시나리오에서 효율적이다. 최악의 시나리오(..

https://product.kyobobook.co.kr/detail/S000001834743 누구나 자료 구조와 알고리즘 | 제이 웬그로우 - 교보문고 누구나 자료 구조와 알고리즘 | 사칙 연산으로 복잡한 알고리즘을 쉽게 이해해보자 수학 용어와 전문 용어가 아니어도 이해한다 이 분야의 책은 대부분 컴퓨터 공학 전공자를 대상으로 쓰였거 product.kyobobook.co.kr 이번 장에서는 재귀 작성법에 대해 알아 볼 것이다. 재귀는 알고리즘의 시간 복잡도에 몹시 부정적인 영향을 미치지만, 우선은 재귀적 사고방식을 기르는 데 집중한다. 1. 재귀 카테고리: 반복 실행 - 상향식 재귀에는 다양한 "카테고리"가 존재한다. 어떤 카테고리에 효과적인 기법을 터득하면 같은 카테고리에 속하는 문제와 마주했을 때 ..

https://product.kyobobook.co.kr/detail/S000001834743 누구나 자료 구조와 알고리즘 | 제이 웬그로우 - 교보문고 누구나 자료 구조와 알고리즘 | 사칙 연산으로 복잡한 알고리즘을 쉽게 이해해보자 수학 용어와 전문 용어가 아니어도 이해한다 이 분야의 책은 대부분 컴퓨터 공학 전공자를 대상으로 쓰였거 product.kyobobook.co.kr 재귀(recursion)는 이후에 나올 보다 고급 알고리즘을 이해하기 위한 컴퓨터 과학의 핵심 개념이다. 재귀는 함수가 자기 자신을 호출할 때를 뜻하는 용어다. 잘못 사용하게 되면 무한재귀가 되어 전혀 쓸모없게 되지만, 올바르게만 활용하면 재귀는 강력한 도구가 될 수 있다. 루프 대신 재귀 루프 대신 재귀를 사용할 수 있다. 기저..

누구나 자료 구조와 알고리즘 | 제이 웬그로우 - 교보문고 누구나 자료 구조와 알고리즘 | 사칙 연산으로 복잡한 알고리즘을 쉽게 이해해보자 수학 용어와 전문 용어가 아니어도 이해한다 이 분야의 책은 대부분 컴퓨터 공학 전공자를 대상으로 쓰였거 product.kyobobook.co.kr 스택과 큐는 제약을 갖는 배열이다. 운영체제 아키텍처, 출력 잡, 데이터 순회 등 임시 컨테이너로 사용해 뛰어난 알고리즘을 만들 수 있다. 이러한 스택과 큐는 임시 데이터를 처리하되 데이터를 처리하는 순서에 특히 중점을 둔다. 스택 Stack 스택에는 다음과 같은 세가지 제약이 있다. 데이터는 스택의 끝에만 삽입할 수 있다. 데이터는 스택의 끝에서만 삽입할 수 있다. 스택의 마지막 원소만 읽을 수 있다. 이미지 출처: ht..

누구나 자료 구조와 알고리즘 | 제이 웬그로우 - 교보문고 누구나 자료 구조와 알고리즘 | product.kyobobook.co.kr 배열에서 특정 요소를 검색할 때, 정렬된 배열이면 O(logN), 정렬되지 않은 배열이면 O(N) 단계가 걸린다. 이 때, 해시 테이블을 사용하면 O(1) 만에 데이터를 룩업할 수 있다. 해시 테이블 해시 테이블은 쌍(key, value)으로 이뤄진 값들의 리스트이다. 해시 , 맵, 해시 맵, 딕셔너리, 연관 배열 등의 이름을 갖는다. 해시 함수를 이용하여 key를 해싱한다. 이 해싱 된 key의 값이 value가 저장될 위치를 결정한다. 때문에 key로 검색 시, O(1)의 성능을 가진다. value로 검색 시에는 일반 배열과 동일하게 O(N)의 성능을 가진다. 언어에 ..

누구나 자료 구조와 알고리즘 | 제이 웬그로우 - 교보문고 누구나 자료 구조와 알고리즘 | product.kyobobook.co.kr 원래 8장 해시테이블 부터 읽어야됐는데 포스트잇이 잘못 붙어있어서 실수로 건너뛰고 읽었습니다..ㅎㅎ.. 하지만 그래도 읽으면서 크게 이질감 드는 부분이 없어서 확실히 읽기 좋은 책이다 싶었습니다! 정리 1번 상황 - 배열에서 최대 값 구하기 재귀 호출 시, 불필요한 재귀 호출이 일어나는 경우가 있습니다. def max(array) // 배열의 크기가 1이라면 첫번째 요소 반환 return array[0] if array.length == 1 if array[0] > max(array[1, array.length - 1]) return array[0] else return ..