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

한줄평 9월 27일 (토) Today I Learned 알고리즘 스터디, 알고리즘 문제풀기 Tomorrow I'll Learn 휴식 + 넷닌자 감상

어제, 오늘 계속해서 놀라움의 연속이 눈 앞에서 펼쳐지고 있다. 이런 때 일수록 겸손해져야 하고, 냉정하게 스스로를 되돌아 보아야 하는 시기라고 생각한다. 나는 무언가 설명하고자 할 때, 최대한 상대방의 입장에서 이해할 수 있는 어휘와 방식을 차용하는 편이다. 그러나 다른 사람의 사고 방식을 완전히 이해하는 건 있을 수 없다. 그러다보니 당연히 내가 생각한 방식이 특정 부분에 치우쳐 다른 사고방식을 가진 사람들의 이해를 해칠 때도 있다. 그 때는 그 사람들을 위해 또 설명하면 괜찮지 않을까? 적어도 말로 하는 강의는 이 방식이 아주 유효했다. 지난 10년동안 수많은 학생을 만났다. 입시 학원에서, 그룹 스터디로, 어떤 때에는 학교로 출강을 다니면서 학생들을 가르칠 때에나 그 학생들의 학부모님과 면담하거나..

KNN 알고리즘은 추천 시스템의 기본이 되는 알고리즘이다. 우리는 한 번 쯤 이미 비슷한 경험을 해본 적이 있다. 넷플릭스나 와챠에서 나와 비슷한 성향을 가진 사람이 본 영상을 추천받기도 하고, 유튜브나 페이스북에서 친구들이 봤거나 좋아요, 댓글달기와 같이 참여한 게시물 또는 영상이 추천된다. 여기에 조미료처럼 머신러닝 한 스푼을 넣어주면 내가 봐 온 영화를 토대로 어떤 영화를 내가 좋아할 지 추천하는 것도 가능하고, 새로나온 영화에 대해서 내가 별점을 얼마나 줄 지 예측할 수도 있다. 하지만 머신러닝은 단순한 조미료가 아니므로 ( 참고로 한국 구글에서 머신러닝 부트캠프를 무료로 진행한다 ) 지금은 아 그렇구나~ 정도로만 하고 넘어가도록 하자. K-nearest neighbors algorithm ( K..

동적 프로그래밍은 말이 동적이지 쉽게 이해하자면 프로그램이 돌아갈 때 자체적으로 기억을 하게 하는 것이다. 모든 값을 검사할 때, 이전의 값 중 최적의 해를 저장해두었다가, 다음 값을 검사할 때 비교하는 방식이다. 아주 아주 간단한 동적 프로그래밍은 최댓값 혹은 최솟값을 찾는 문제이다. 숫자로만 이뤄진 배열을 입력받는 경우, 가장 작은 수를 이미 가지고 있는 최댓값을 구하는 함수 또는 가장 큰 수를 이미 가지고 있는 최솟값을 구하는 함수를 이용해 문제를 풀 수 있을 거다. const findMax = (arr) => { let max = -Infinity; for ( let value of arr ) { // value 는 arr[index] 와 같다 ( for...of 검색 ) if ( max < va..

탐욕 알고리즘은 현재 주어진 상황에서 최적의 값을 골라 결과를 채우는 알고리즘을 말한다. 가장 많은 예시인 배낭 채우기는 간단하게 설명하고, 다른 예시를 보도록 하자. 탐욕 알고리즘은 그 이름에서 유추할 수 있듯이 욕심쟁이라면 당연히 따를 법한 알고리즘이다. 배낭 채우기 ( 갑자기 ) 우리는 도둑이다. 도둑이라면 응당 가장 비싼 물건을 훔쳐야 할 것이다. 맥북을 훔치기 위해 도둑이지만, 일반 고객인 척 위장하여 애플매장을 방문하였다. 우리에게는 남들에게는 보이지 않는 마법의 '배낭' ( 혹은 가방 ) 이 있다. 이 배낭은 보이지않는 대신에 너무 작게 만들어져서 중량 초과를 할 경우 밑바닥이 터져버린다! ( 요즘 종이 가방도 이것보단 튼튼하겠다! ) 내 배낭이 버틸 수 있는 총 중량과 애플매장에서 훔칠 수..

많은 자료구조 중에서 자주 사용되는 구조 중 하나는 트리구조이다. 어떤 웹사이트에서, 사이트맵 이라는 걸 본 적이 있다면 이해하기 쉽다. 또, 우리가 사용하는 PC를 폴더단위로 관리한다면, 더 이해하기가 쉽다. 따오기라는 폴더 안에는 꿩, 가마우지, 새폴더, 새 새폴더 라는 이름의 4개의 폴더가 있다. 하나의 부모 아래에 여러개의 자식이 있는 구조. 이게 트리구조 다. 우리가 자료를 찾거나 정리하기 위해 사용하는 자료구조 중에서 트리를 기반으로 한 다양한 구조가 있다. Binary Tree ( 이진 트리 ) 이진 트리는 하나의 부모가 가질 수 있는 자식의 수가 최대 2개인 트리를 말한다. Full Binary Tree ( 포화 이진 트리 ) 포화 이진 트리는 모든 부모노드가 두 개의 자식노드를 가지고 있..

DFS ( Depth-first search ) 의 꽃인 N queens 를 구현하였다. 물론 자의로 주어진 스켈레톤에 구현하였고, 타의로 내 레포지토리에 하나가 쌓이게 되었다. 우선 N queens를 구현하기에 앞서, BFS 와 DFS를 모른다면 이 링크를 통해 개념 정도는 숙지를 해두자. [Algorithm] BFS, DFS - 너비우선탐색, 깊이우선탐색 BFS와 DFS는 탐색에서 대조적으로 설명하는 대표적인 두가지 방법이다. BFS와 DFS의 중간 그 어딘가에는 Heuristic ( 휴리스틱 ) 함수를 사용한 A* search ( 에이스타 서치 ) 등이 존재한다. 오늘은 BFS와 DFS dev-gp.tistory.com Backtracking ( 백트래킹, 퇴각검색 ) 백트래킹은 한정 조건을 가지는..

BFS는 가중치가 없는 균일 그래프에서 최단경로를 계산하는 반면, 다익스트라 알고리즘은 가중치가 있는 그래프에서 최단 거리를 계산하는 데 사용된다. 아래 그림은 균일 그래프이다. 1번 vertex에서 출발하여 4번 vertex에 도착하기까지의 최단경로는 A, B 둘 중의 하나이다. 그렇다면 가중치가 있는 경우는 어떨까? 아까의 A경로 혹은 B경로 모두 7이라는 가중치를 가진다. 그런데, 우리는 직관적으로 더 짧은 길이 있음을 알 수 있다. 아래 그림의 화살표를 따라 이동하면, 가중치 6만에 도착할 수 있다. 대체 가중치가 뭐길래? 쉽게 이해하자. 1번은 서울이고, 4번은 부산이다. 2번은 울산이고, 3번은 대전이다. 그래프의 간선에 표기된 가중치는, 현실 시간으로 30분이라고 가정하자. 서울에서 부산까지..

BFS와 DFS는 탐색에서 대조적으로 설명하는 대표적인 두가지 방법이다. BFS와 DFS의 중간 그 어딘가에는 Heuristic ( 휴리스틱 ) 함수를 사용한 A* search ( 에이스타 서치 ) 등이 존재한다. 오늘은 BFS와 DFS에 대한 간략한 설명과, 트리구조에서 어떤 방식으로 접근하여 사용하는 지 이야기해보자. BFS ( Breadth-First Search, 너비 우선 탐색 ) BFS는 시작점에서 출발하여 종점에 도착할 때 까지 시작점으로부터 같은 거리에 있는 좌표 혹은 노드를 가장 먼저 탐색한다. 위 그림에서 왼쪽의 grid는 start로부터 end까지 도달하기 위해 BFS가 동작하는 모습을 단편적으로 보여준다. 마찬가지로 오른쪽의 트리에서 루트로부터 end에 도달할 때까지 거리가 가까운 ..

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