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

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

솔로위크 시작 솔로위크 These days what I learned 이번 솔로위크 기간에는 블로깅을 위주로 진행할 예정이다. 매일 장문의 긴, 그리고 유익한 포스팅 매일 하나씩하기 뿐만 아니라, 기존에 흥미를 가지고 있던 D3를 학습해봐야겠다. 데이터 시각화 도전 Next week what I'll learn Async & 타이머 API 학습

오늘은 hiring assessment for basic computer science 를 진행했다. 지난 ha와 마찬가지로 쉽게 풀 수 있는 문제와 난이도 있는 문제가 공존했다. 약간 고등학교때 수학문제집 푸는 기분을 느꼈다. 9월 16일 (수) Today I Learned 오늘은 ha를 진행하였다 yarn.lock 때문에 제출이 되지 않는 문제가 있었다 이전에 같은 문제를 겪은 적이 있어서 혹시나 하고 접근했는데 다행히 삭제만 하는 것으로 패스되었다 Tomorrow I'll Learn 솔로윜동안 뭘해야할까? 고민을 좀 해야할 거 같다.

많은 자료구조 중에서 자주 사용되는 구조 중 하나는 트리구조이다. 어떤 웹사이트에서, 사이트맵 이라는 걸 본 적이 있다면 이해하기 쉽다. 또, 우리가 사용하는 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분이라고 가정하자. 서울에서 부산까지..

블로그 내용을 조금 더 알차게 쓸 필요가 있다. TIL도 오늘 뭐 했다 정도가 아니라, 다른 카테고리에 작성하는 정도가 좋을까. 잘 모르겠다. 조금 더 고민해볼 내용. 9월 14일 (월) Today I Learned 오늘은 n queens에 대해 공부하였다 n queens 는 대표적인 DFS 문제이다 유효성 검사를 통해 DFS의 비효율을 조금 개선할 수 있다 ( 백트래킹 ) 체스판이다보니 y축 대칭을 이루므로 최대 n/2 + 1 번 실행하는 것으로 모든 경우를 파악할 수 있다 2, 3 의 경우는 결과가 0이다 Tomorrow I'll Learn n queens 마무리

컨디션이 좋지 않다. 감기기운이 있다. 쉰다 9월 13일 (일) Today I Learned Tomorrow I'll Learn

그래프는 자료의 관계도에 주로 사용되는 자료구조이다. 가장 대표적인 예는 역시 싸이월드 페이스북 친구이다. 나와 친구의 관계를 가중치1이라고 한다면, 친구의 친구는 가중치2 정도로 두고, 친구의 친구의 친구는 가중치3정도로 두는 것이다. 그러면 나를 기준으로 가중치가 1인 사람은 가장 가까운 사람들이고, 가중치가 2인 사람들은 그 다음으로 가까운 사람들이고, 3정도의 가중치는 내 친구와 그 사람의 친구가 서로 친구인 경우니까 그냥 남이다. Graph 그래프는 이전의 링크드리스트에서 보던 노드라는 개념을 가져와서 사용한다. 다른 점이 있다면, 실제로 그래프에서는 노드 대신 Vertex ( 점 ) 와 Edge ( 간선 ) 을 사용한다. ( 참고로 vertex의 복수형은 vertices 이다 ) 그래프에는 방..

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