본문 바로가기

자료구조와 알고리즘(순한맛)

 (9)
14장 - 공간 제약 다루기 들어가며 이 책 전반에서 다양한 알고리즘의 효율성을 분석하면서 오로지 시간 복잡도에만 초점을 맞췄다. 즉 알고리즘이 얼마나 많은 메모리를 소모하는가로 알고리즘의 효율성을 측정해야 할 때가 있다. 메모리 제한이 있다면 공간 복잡도가 중요한 요인이다. 비교적 적은 양의 메모리만 포함하는 작은 하드웨어 장치를 위한 프로그래밍이나 아주 대량의 데이터가 데이터보다 훨씬 큰 메모리 컨테이너를 빠르게 채우는 상황을 처리할 때 그렇다. 이상적으로는 빠르면서도 메모리를 적게 소비하는 그러한 알고리즘만 사용하고 싶을 것이다. 하지만 빠른 알고리즘은 효율적인 메모리 알고리즘 사이에서 선택해야 하는 상황이 있을 것이고 올바른 선택을 하려면 그러한 상황을 유심히 살펴봐야 한다. 14.1. 공간 복잡도에 빅 오 표기법 적용 흥미..
13장 - 그래프로 뭐든지 연결하기 들어가며 페이스북 같은 소셜 네트워크를 만드다고 하자. 이 애플리케이션에서는 많은 사람이 서로 "친구"가 될 수 있다. 앨리스가 밥의 친구라면 밥 역시 앨리스의 친구이듯 이러한 관계는 상호적이다. 이러한 데이터를 가장 잘 조작하는 방법은 무엇인가? 한 가지 매우 간단한 접근 방식은 2차원 배열로 관계 리스트를 저장하는 것이다. relationships = [ ["Alice", "Bob"], ["Bob", "Cynthia"], ["Alice", "Diana"], ["Bob", "Diana"], ["Elise", "Fred"], ["Diana", "Fred"], ["Fred", "Alice"] ] 불행히도 이 방식으로는 앨리스의 친구가 누구인지 빠르게 알 수가 없다. 배열 내 각 관계를 확인해서 앨리스가 그..
12장 - 이진 트리로 속도 향상 들어가며 2장 알고리즘이 중요한 까닭에서 이진 검색의 개념을 다루면서 정렬된 이진 검색을 사용하면 O(log N) 시간에 어떤 값이든 찾을 수 있음을 알았다. 결국 정렬된 배열에도 한 가지 문제가 있다. 정렬된 배열은 삽입과 삭제가 느리다. 정렬된 배열에 값을 삽입할 때마다 그 값보다 큰 모든 항목들을 한 셀 오른쪽으로 먼저 시프트 해야 한다. 또한, 정렬된 배열에서 값을 삭제할 때마다 그 값보다 큰 모든 값을 한 셀 왼쪽으로 시프트해야 한다. 최악의 시나리오*일 경우, * 배열 앞에 값을 삽입하거나, 배열 첫 번째 값을 삭제할 때 시프트에 N단계가 걸리고, 평균적으로 N/2단계가 걸린다. 어쨌든 O(N)이고, O(N)은 꽤 느리다. 7장 해시 테이블로 매우 빠른 룩업에서 해시 테이블의 검색, 삽입, 삭..
11장 - 노드 기반 자료 구조 들어가며 능력있는 여자한테 장가가서 가정적인 남편이 되고 싶다. 행복한 꿈이자, 오랜 생각이다. 11.0 노드 기반 자료 구조 이어지는 챕터에서 다룰 다양한 자료구조는 모두 노드(node)라는 개념에 기반해 만들어졌다. 노드 기반 자료 구조는 데이터를 조직하고 접근하는 새로운 방법을 제공하는데, 성능상의 큰 이점이 많다. 11장에서는 가장 간단한 노드 기반 자료구조이자 이후 배울 내용의 기반인 연결 리스트를 살펴본다. 또한, 연결 리스트와 배열이 거의 같아 보이지만, 연결 리스트는 효율성 면에서 장단점(tade-off)이 있어 어떤 상황에서 성능이 크게 높아지는지도 알아보겠다. 11.1 연결 리스트 연결 리스트(linked list)는 배열과 마찬가지로, 항목의 리스트를 표현하는 자료 구조다. 사용자가 ..
10장 - 속도를 높이는 재귀 알고리즘 들어가며 사람은 사려서 사귀자. 10.0. 속도를 높이는 재귀 알고리즘 앞서 살펴봤듯이 재귀를 이해하면 파일 시스템 검색과 같은 새로운 알고리즘을 많이 사용할 수 있다. 10장에서는 코드를 훨씬 더 빠르게 실행시킬 수 있는 알고리즘에서도 재귀가 핵심 기술임을 배우겠다. 9장에서 버블 정렬과 선택 정렬, 삽입 정렬 같은 많은 정렬 알고리즘을 살펴봤다. 하지만 실제로 배열을 정렬할 때는 이러한 방법을 쓰지 않는다. 컴퓨터 언어에는 대부분 내장 정렬 함수가 있어 사용자가 스스로 구현하는 데 드는 시간과 노력을 아껴준다. 컴퓨터 언어 중 대다수가 내부적으로 채택한 정렬 알고리즘이 바로 퀵 정렬이다. 많은 컴퓨터 언어에 퀵 정렬이 내장되어 있음에도 불구하고 퀵 정렬을 깊이 알아보려는 이유는 퀵 정렬의 동작 방식을..
09장 - 재귀를 사용한 재귀적 반복 들어가며 뭘 하던 저장을 생활화 합시다. 9.0 재귀를 사용한 재귀적 반복 이후 나올 대부분의 알고리즘을 이해하려면 재귀(recursion)의 핵심 개념을 알아야 한다. 재귀를 사용하면 까다로운 문제를 놀라도록 간단하게 풀 수 있다. 대개는 원래 작성했을 코드보다 훨씬 작다. 대충 다음처럼 정의한 blah() 함수를 호출하면 무슨 일이 벌어질까? function blah() { blah(); } 대충 짐작했겠지만 blah()가 자신을 호출하고, 또 blah()가 자신을 호출하여 반복적으로 자신을 호출하면서 함수 자신을 무한대로 호출할 것이다. 재귀는 함수가 자기 자신을 호출할 때는 말하는 공식 명칭이다. 일반적으로 무한 함수 호출은 쓸모가 없고 위험하기까지 하지만 재귀는 활용 가능성이 큰 강력한 도구다...
08장 - 스택과 큐로 간결한 코드 생성 들어가며 어제 새벽까지 썼던 8장이 파이어폭스가 멈춰서 다 날아갔다. 하,... 처음부터 다시 써야 한다. 하...... 8.0. 스택과 큐로 간단한 코드 생성 지금까지 자료 구조를 논할 때는 주로 자료 구조에 따라 다양한 연산의 성능이 어떻게 달라지는가에 초점을 맞춰왔다. 하지만 프로그래밍 지식 창고에 다양한 자료 구조를 쌓아 두다 보면 보다 간단하고 읽가 쉬운 코드를 생성하는데 도움이 된다. 8장에서는 스택과 큐라는 새로운 자료 구조를 알아보겠다. 사실 두 자료 구조를 완전히 새롭다고 할 수 는 없다. 제약을 갖는 배열일 뿐이다. 하지만 바로 이러한 제약 덕분에 두 자료 구조가 매우 간결해진다. 좀 더 구체적으로 설명하면, 스택과 큐는 임시 데이터를 처리할 수 있는 간결한 도구다. OS 아키텍처부터 ..
01장 - 자료 구조가 중요한 까닭 들어가며 컴퓨터 코드를 조금이라도 작성해 보면 프로그래밍이 데이터를 주로 다루는 것임을 곧 알 수 있다. 컴퓨터 프로그램은 데이터를 입력받아 조작하고 반환하는 게 전부다. 두 수의 합을 계산하는 간단한 프로그램이든, 회사 전체를 관리하는 기업용 소프트웨어든, 소프트웨어는 데이터에 관한 것이다. 데이터는 일반적으로 모든 유형의 정보를 망라하는 용어이며, 가장 기초적인 수와 문자열로 이뤄진다. 간단하지만 고전적인 "Hello World!" 프로그램을 떠올리면 "Hello World" 문자열이 바로 데이터다. 매우 복잡한 데이터라도 대개는 수와 문자열 묶음으로 나뉜다. 자료 구조란 데이터를 조직하는 방법이다. 다음의 코드를 살펴보자. x = "Hello! " y = "How are you " z = "toda..
00장 - 들어가며 들어가며 자료 구조와 알고리즘은 단순히 추상적인 개념이 아니다. 자료 구조와 알고리즘에 숙달하면 더 빠르게 실행되는 보다 효율적인 코드를 작성할 수 있고, 이는 오늘날의 웹과 모바일 앱에서 특히 중요하다. 만일 마지막으로 알고리즘을 마주한 게 대학 수업이나 면접이라면 알고리즘의 진정한 힘을 활용하지 못하고 있는 것이다. 문제는 이러한 주제를 다루는 자료가 대부분 이해하기 어렵게 쓰였다는 점이다. 글은 수학 용어로 가득 차있고 수학자가 아닌 이상 도대체 무슨 말인지 알기 어렵다. 심지어 "쉬운" 알고리즘을 표방하는 책마저도 독자가 수학 석박사 학위를 취득했다고 가정한다. 결국, 무수한 독자들이 자신은 이러한 개념을 이해할 만큼 충분히 "똑똑하지" 않다고 생각하며 회피한다. 하지만 자료 구조와 알고리즘은 전..

티스토리툴바