GRAY | 추천 알고리즘의 과학 저자

해쉬테이블은 파이썬에서 사용하는 dictionary, 자바스크립트에서 사용하는 객체와 같다. string 형태의 key와 값을 받아 저장하고, key를 알고 있으면 O(1)의 시간복잡도로 value를 가져올 수 있는 엄청난 자료구조이다! 개념을 명확히 알면 나중에 응용할 때에 더욱 빛을 발하는 자료구조이니 반드시 알아두자. Hash function ( 해시 함수 ) 해시함수는 입력받는 key에 따라 특정 index를 반환하는 함수이다. 같은 key에 대해 항상 같은 index를 반환하여야 하고, 최대한 일관성을 유지하는 것이 좋다. 위의 해시함수는 문자열 'cat'이 입력되면 항상 1을 반환하고, 'dog'이 입력되면 2를 반환한다. 이렇게 반환된 index에 입력된 key, value 가 해시테이블에 ..

오늘은 분할정복과 퀵정렬에 대해 이야기를 해볼까 한다. 지난번 알고리즘에서 재귀함수를 설명했는데, 재귀함수야 말로 분할정복의 가장 대표적인 예이다. 문제를 base case와 recursive case로 나누어서 생각하고, 가장 최소 단위가 해결이 될 때 전체가 해결되도록 하기 때문이다. [ Hello Coding, 그림으로 개념을 이해하는 알고리즘 ]의 챕터 4에 나오는 내용으로 설명을 시작해본다 Divide and conquer ( 분할 정복 ) 한자로 번역이 되니까 어려워보인다. 조금 말을 쉽게하자면, "쪼개고 쪼개서 하나씩 해결하자" 이다. 아래의 그림은 책의 예제이다. 여러분이 농부이고, 위의 그림과 같은 농장을 가지고 있다고 가정한다. 이 농장을 똑같이 생긴 정사각형 토지로 나누고 싶습니다. ..

링크드 리스트는 기본적인 노드 개념을 처음으로 학습하게 되는 자료구조이다. 링크드 리스트는 하나의 노드가 자신의 값과 다음 노드를 가리키는 포인터, 이 두 가지만 가지고 있다. 따라서, 한 번 지나간 노드는 이전 노드로 돌아갈 수 없다는 게 포인트이다. Linked List ( 링크드 리스트 / 연결 리스트 ) 위에서 언급했고, 위 그림에서 볼 수 있듯이 가장 기본이 되는 개념은 노드이다. 하나의 노드는 value와 next 두가지로 이루어져 있다. class Node { constructor(value) { this.value = value; this.next = null; } } 링크드 리스트는 이 노드의 연결로 이루어진 자료구조이다. 이 노드의 next에 새로운 노드를 넣어줌으로써 노드간에 연결이 ..

Loops may achieve a performance gain for your program. Recursion may achieve a performance gain for your programmer. Choose which is more important in your situation! : 루프는 프로그램의 성능을 향상시킵니다. 재귀는 프로그래머의 실력을 향상시킵니다. 상황에 따라 더 적합한 걸 선택하세요! Recursion ( 재귀 ) 재귀는 반복문과 그 역할을 서로 바꿀 수 있다. 재귀를 쓰면 복잡한 코드가 조금 더 간결해보이는 효과를 나타낸다. 피보나치를 구현해보자. 반복문: const fib1 = (n) => { if ( n < 3 ) { return n === 0 ? 0 : 1; } ..

자료구조의 가장 기본이 되는 stack ( 스택 ) 과 queue ( 큐 ) 는 자료구조의 처음을 장식한다. 그런데 정작 사용할 때에는 어떻게 해야할 지 막막한 게 초보자의 마음이리라. 자료구조는 구현과는 제법 거리가 있다. 스택과 큐는 그냥 배열로 선언해서 사용해도 무방하다. 이처럼 자료구조는 어떤 방식으로 데이터를 관리할 지 그 구조에 대해 설명하는 것이지, 어떤 방식으로 구현해야만 한다는 건 아니다. 따라서 앞으로 정리하게 될 모든 자료구조도 개념에 대해 이해하는 게 우선이라는 점을 기억하자. 또, 자료구조는 알고리즘과 뗄 수 없는 관계이기때문에 아주아주 중요한 개념이라는 것 정도는 알고 있자. Stack ( 스택 ) 스택은 동전쌓기처럼 가장 나중에 쌓은 동전을 가장 먼저 꺼낼 수 있는 구조이다. ..

이진탐색은 [Hello Coding] 그림으로 개념을 이해하는 알고리즘의 가장 첫번째로 소개되는 알고리즘이다. 간단하게는 Up&Down 게임을 생각하면 쉽다. Up & Down 게임을 해보려면 여기를 통해 해보자. 이진탐색 이진탐색을 하기에 앞서, 단순탐색에 대해 생각해보자. 내가 0부터 100 사이의 숫자 중 하나를 선택했을 때 단순하게 내가 생각한 숫자를 맞히기 위해서는 0부터 시작해서 100까지 1씩 증가하면 된다. const myNumber = 88; for ( let i = 0; i < 100; i++ ) { if ( i === 88 ) { console.log("Find the number you thought! It's ${i} !"); } } 위의 코드처럼 0부터 1씩 증가하며 내가 생각한..

컴퓨터과학의 기초를 알아두면 코딩을 하는 데 매우 도움이 된다. 특히 논리적인 사고와 순서, 그리고 효율에 관한 내용을 다루는 것이 컴퓨터과학의 기초인 자료구조와 알고리즘이다. 이 둘은 뗄레야 뗄 수 없는 관계에 있지만, 무엇을 먼저하든 크게 상관은 없다. ( 전공에서는 일반적으로 데이터구조를 먼저 학습한다. ) 말만 들어도 복잡하고 머리아픈 내용이 가득할 것 같지만, 어떻게 시작하느냐에 따라 학습의지가 불타오를 수도, 꺾일 수도 있는 분야이다. 그렇기에 그 시작은 아주 가볍고 쉽게 풀이해 이해할 수 있는 정도의 수준이어야 하고, 오늘 소개할 책은 그 시작을 함께하기에 현존하는 서적 중 단연 최고가 아닐까 한다. Hello Coding - 그림으로 개념을 이해하는 알고리즘 저자: 아디트야 바르가바 폴님께..