IT/모바일
제공 : 한빛 네트워크
저자 : Michael McMillan
역자 : 홍영기
원문 : Data structures in JavaScript
자바스크립트는 이제 더이상 브라우저에서만 실행되는 클라이언트 사이드 스크립트 프로그래밍 언어가 아닙니다. 지난 몇년 동안 서버 사이드 자바스크립트 엔진과 프레임워크들이 도입되었고, 이제는 더이상 설명이 필요없는 Node.js와 Mozilla JavaScript shell이 좋은 예입니다. 자바스크립트가 서버 사이드에서 동작이 가능해짐에 따라, 개발자들은 브라우저에서는 처리할 수 없었던 문제들을 서버에서 자바스크립트를 이용하여 효율적으로 해결하기 위해 고수준의 자바스크립트 기술들이 필요하게 되었습니다.
수 년전, 스위스의 컴퓨터 과학자 Niklaus Wirth는 그의 저서 "Algorithms + Data Structures = Programs" 를 통해 프로그램은 특정 문제 상황에 기반한 알고리즘과 자료구조로 구성된다고 하였습니다. 그는 그의 저서를 통해 데이터를 구조화된 자료구조로 적절히 표현하고 알고리즘이 이러한 데이터들을 변형, 가공하는 것이 성공적인 프로그램을 작성하는 공식이라고 하였습니다. 애초에 잘못 작성된 자료구조 위에서 구현된 프로그램의 실패는 자명한 것입니다.
자바스크립트에서 자료구조 만들기
자바스크립트에서 기본적으로 사용할 수 있는 자료구조로는 배열(Array)과 객체(Object)가 있습니다. 배열이 평평(flat)한 구조의 데이터를 표현할 때에는 효과적으로 사용될 수 있지만, 대부분의 데이터 구조는 계층(hierarchical)을 이루고 있거나 서로 연관성(associative)을 가지고 있거나 트리(tree) 형태로 구성되는 경우가 많습니다. 객체가 간단한 매핑(mapping)처럼 서로 연관성을 표현하는 자료구조에는 적절하지만, 키-밸류 값(key-value pair)을 효과적으로 저장(store)하고 검색(retrieve)하기 위해 사용되는 사용자 정의 사전 자료구조(custom-made dictionary data structure) 처럼 가변적이지는 않습니다.
문제 해결을 위해 적절한 자료구조를 선택하는것은 그 문제의 해결법을 찾는데 가장 중요한 요소입니다. 강조하자면, 잘못된 자료구조의 선택은 문제 해결을 아예 불가능하게 할 수 있습니다. 예를 들어, 데이터 집합(data set)을 빠르게 찾는 것이 목적인 프로그램이 데이터를 객체의 형태로 메모리에 저장한다면 아마 잘못된 선택이 될 것입니다. 따라서 자료구조의 적절한 사용법을 배우는 것만이 이러한 잘못된 선택을 방지할 수 있습니다.
실용적인 스택
스택(Stack)은 자료구조 사용만으로 효율적인 문제 해결이 가능한 자료구조 중 한가지 입니다. 스택은 가장 최근에 저장한 탑 요소(top element)의 접근만이 가능한 리스트(list)입니다. 푸시 연산(Push operation)을 통해 스택에 새로운 요소를 저장할 수 있고, 팝 연산(Pop operation)으로 스택의 탑 요소를 제거할 수 있습니다. 이 두 연산 외에 스택 자료구조에서 유일하게 허용하는 연산으로는 탑 요소를 제거하지 않고 반환(return)하는 Peek/View 연산이 있습니다.
스택은 어디에 사용될까요? 컴퓨터 과학(computer science)에서는 프로그래밍 언어의 함수 호출 구현에 스택을 사용하고, 컴퓨터 하드웨어 구조에서는 메모리 할당(allocate)과 접근(access)에 스택을 이용합니다. 이 외에도 스택을 활용하는 분야가 아주 많지만 일상적인 작업들 중에서 스택이 어떻게 사용이 알아봅시다.
십진수에서 이진수로의 변환은 스택 활용의 좋은 예제입니다. 이 변환에 사용되는 알고리즘은 아주 간단합니다. 변환하고 싶은 십진수를 1) 2로 나눈 나머지를 스택에 푸시하고, 2) 몫이 0보다 크면 다시 1)의 과정을 반복합니다. 이후 스택이 빈 상태(Empty)가 될때까지 팝을 하면 변환된 이진수를 얻을 수 있습니다.
또한, 수식에서 괄호가 올바르게 사용되었는지 검사하는 것도 스택 사용의 좋은 예 입니다. 수식을 스캔하면서 왼쪽 괄호를 만나면, 괄호의 종류를 괄호의 위치와 함께 스택에 푸시하고, 오른쪽 괄호를 만나게 되었을때 스택에서 팝을 합니다. 이 때 팝이 반환한 괄호의 종류가 현재 스캔중인 괄호와 종류가 같으면 괄호의 쌍이 잘 사용된 것입니다. 수식의 스캔이 끝났을 때 스택이 빈 상태가 아니라면 이 수식에서는 괄호가 균형있게 사용되지 않은 것 입니다.
효과적인 이진 탐색 트리
이진 탐색 트리(Binary Search Tree)는 그 자체가 매우 효율적인 알고리즘인 자료구조입니다. 트리(tree)는 각 데이터 요소가 노드(node)에 저장되는 자료구조이고, 첫 번째 노드인 루트 노드(root node)와 자식 노드(child node)들로 구성 됩니다. 이진 탐색 트리에서는 부모 노드(parent node)는 오직 두 자식 노드만 가질 수 있는데 하나는 부모 노드의 왼쪽 자식 노드, 다른 하나는 부모 노드의 오른쪽 자식 노드 입니다. 이 트리는 부모 노드보다 작은 값을 가지는 자식 노드는 왼쪽 자식으로, 부모 노드 보다 큰 값을 가지는 자식 노드는 반드시 오른쪽 자식이 되야하는 규칙이 있습니다. 이진 탐색 트리가 잘 구성이 되면 이 트리가 가지고 있는 데이터 중 가장 작은 값은 트리에서 맨 아래 왼쪽 노드의 값이 되고, 가장 큰 값은 맨 아래 오른쪽 노드가 저장하고 있는 값입니다. 이러한 특성은 정렬되지 않는 데이터들의 검색과 비교해 엄청난 검색 성능 향상을 보여줍니다.
자료구조를 자신의 스킬에 추가하세요
서버 사이드에서 자바스크립트의 실행이 가능해지면서 기존 개발자들에게 새로운 기회를 제공하고 있습니다. 정규 컴퓨터 과학 과정을 이수하지 않았던 자바스크립트 개발자들은 자료구조를 배움으로써 매일 매일 직면할 수 있는 문제들을 효과적으로 해결할 수 있습니다. 자료구조와 익숙해지고 효과적인 활용법을 배우는 것은 좀 더 전문적인 컴퓨터 프로그래머로 가는 핵심 스킬이 될 것입니다.
저자 : Michael McMillan
역자 : 홍영기
원문 : Data structures in JavaScript
자바스크립트는 이제 더이상 브라우저에서만 실행되는 클라이언트 사이드 스크립트 프로그래밍 언어가 아닙니다. 지난 몇년 동안 서버 사이드 자바스크립트 엔진과 프레임워크들이 도입되었고, 이제는 더이상 설명이 필요없는 Node.js와 Mozilla JavaScript shell이 좋은 예입니다. 자바스크립트가 서버 사이드에서 동작이 가능해짐에 따라, 개발자들은 브라우저에서는 처리할 수 없었던 문제들을 서버에서 자바스크립트를 이용하여 효율적으로 해결하기 위해 고수준의 자바스크립트 기술들이 필요하게 되었습니다.
수 년전, 스위스의 컴퓨터 과학자 Niklaus Wirth는 그의 저서 "Algorithms + Data Structures = Programs" 를 통해 프로그램은 특정 문제 상황에 기반한 알고리즘과 자료구조로 구성된다고 하였습니다. 그는 그의 저서를 통해 데이터를 구조화된 자료구조로 적절히 표현하고 알고리즘이 이러한 데이터들을 변형, 가공하는 것이 성공적인 프로그램을 작성하는 공식이라고 하였습니다. 애초에 잘못 작성된 자료구조 위에서 구현된 프로그램의 실패는 자명한 것입니다.
자바스크립트에서 자료구조 만들기
자바스크립트에서 기본적으로 사용할 수 있는 자료구조로는 배열(Array)과 객체(Object)가 있습니다. 배열이 평평(flat)한 구조의 데이터를 표현할 때에는 효과적으로 사용될 수 있지만, 대부분의 데이터 구조는 계층(hierarchical)을 이루고 있거나 서로 연관성(associative)을 가지고 있거나 트리(tree) 형태로 구성되는 경우가 많습니다. 객체가 간단한 매핑(mapping)처럼 서로 연관성을 표현하는 자료구조에는 적절하지만, 키-밸류 값(key-value pair)을 효과적으로 저장(store)하고 검색(retrieve)하기 위해 사용되는 사용자 정의 사전 자료구조(custom-made dictionary data structure) 처럼 가변적이지는 않습니다.
문제 해결을 위해 적절한 자료구조를 선택하는것은 그 문제의 해결법을 찾는데 가장 중요한 요소입니다. 강조하자면, 잘못된 자료구조의 선택은 문제 해결을 아예 불가능하게 할 수 있습니다. 예를 들어, 데이터 집합(data set)을 빠르게 찾는 것이 목적인 프로그램이 데이터를 객체의 형태로 메모리에 저장한다면 아마 잘못된 선택이 될 것입니다. 따라서 자료구조의 적절한 사용법을 배우는 것만이 이러한 잘못된 선택을 방지할 수 있습니다.
실용적인 스택
스택(Stack)은 자료구조 사용만으로 효율적인 문제 해결이 가능한 자료구조 중 한가지 입니다. 스택은 가장 최근에 저장한 탑 요소(top element)의 접근만이 가능한 리스트(list)입니다. 푸시 연산(Push operation)을 통해 스택에 새로운 요소를 저장할 수 있고, 팝 연산(Pop operation)으로 스택의 탑 요소를 제거할 수 있습니다. 이 두 연산 외에 스택 자료구조에서 유일하게 허용하는 연산으로는 탑 요소를 제거하지 않고 반환(return)하는 Peek/View 연산이 있습니다.
스택은 어디에 사용될까요? 컴퓨터 과학(computer science)에서는 프로그래밍 언어의 함수 호출 구현에 스택을 사용하고, 컴퓨터 하드웨어 구조에서는 메모리 할당(allocate)과 접근(access)에 스택을 이용합니다. 이 외에도 스택을 활용하는 분야가 아주 많지만 일상적인 작업들 중에서 스택이 어떻게 사용이 알아봅시다.
십진수에서 이진수로의 변환은 스택 활용의 좋은 예제입니다. 이 변환에 사용되는 알고리즘은 아주 간단합니다. 변환하고 싶은 십진수를 1) 2로 나눈 나머지를 스택에 푸시하고, 2) 몫이 0보다 크면 다시 1)의 과정을 반복합니다. 이후 스택이 빈 상태(Empty)가 될때까지 팝을 하면 변환된 이진수를 얻을 수 있습니다.
또한, 수식에서 괄호가 올바르게 사용되었는지 검사하는 것도 스택 사용의 좋은 예 입니다. 수식을 스캔하면서 왼쪽 괄호를 만나면, 괄호의 종류를 괄호의 위치와 함께 스택에 푸시하고, 오른쪽 괄호를 만나게 되었을때 스택에서 팝을 합니다. 이 때 팝이 반환한 괄호의 종류가 현재 스캔중인 괄호와 종류가 같으면 괄호의 쌍이 잘 사용된 것입니다. 수식의 스캔이 끝났을 때 스택이 빈 상태가 아니라면 이 수식에서는 괄호가 균형있게 사용되지 않은 것 입니다.
효과적인 이진 탐색 트리
이진 탐색 트리(Binary Search Tree)는 그 자체가 매우 효율적인 알고리즘인 자료구조입니다. 트리(tree)는 각 데이터 요소가 노드(node)에 저장되는 자료구조이고, 첫 번째 노드인 루트 노드(root node)와 자식 노드(child node)들로 구성 됩니다. 이진 탐색 트리에서는 부모 노드(parent node)는 오직 두 자식 노드만 가질 수 있는데 하나는 부모 노드의 왼쪽 자식 노드, 다른 하나는 부모 노드의 오른쪽 자식 노드 입니다. 이 트리는 부모 노드보다 작은 값을 가지는 자식 노드는 왼쪽 자식으로, 부모 노드 보다 큰 값을 가지는 자식 노드는 반드시 오른쪽 자식이 되야하는 규칙이 있습니다. 이진 탐색 트리가 잘 구성이 되면 이 트리가 가지고 있는 데이터 중 가장 작은 값은 트리에서 맨 아래 왼쪽 노드의 값이 되고, 가장 큰 값은 맨 아래 오른쪽 노드가 저장하고 있는 값입니다. 이러한 특성은 정렬되지 않는 데이터들의 검색과 비교해 엄청난 검색 성능 향상을 보여줍니다.
자료구조를 자신의 스킬에 추가하세요
서버 사이드에서 자바스크립트의 실행이 가능해지면서 기존 개발자들에게 새로운 기회를 제공하고 있습니다. 정규 컴퓨터 과학 과정을 이수하지 않았던 자바스크립트 개발자들은 자료구조를 배움으로써 매일 매일 직면할 수 있는 문제들을 효과적으로 해결할 수 있습니다. 자료구조와 익숙해지고 효과적인 활용법을 배우는 것은 좀 더 전문적인 컴퓨터 프로그래머로 가는 핵심 스킬이 될 것입니다.
TAG :
이전 글 : 신입 개발자를 위한 디버깅
최신 콘텐츠