본문 바로가기

전체 글657

외판원 순회(TSP: Traveling Salesperson Problem) 외판원 순회(TSP: Traveling Salesperson Problem)란 도시들이 있고 특정 도시에서 도시로 이동할 때 드는 비용이 주어졌을 때 불특정한 도시에서 출발해서 모든 도시를 돌고 다시 출발 도시로 돌아왔을 때 드는 최소 비용을 구하는 문제입니다. 외판원 순회는 NP문제로 이번에 소개할 알고리즘은 N이 16개 이하일 때 DP와 비트마스크를 이용하여 구하는 방법입니다. DP는 특정 도시들을 방문한 상태일 때 최소 비용을 저장해 놓고 이를 사용합니다. 비트마스크는 특정 도시를 방문한 상태를 저장할 때 사용합니다. 예를 들어서 1~3번 도시가 있다고 했을 때, 110(2)는 2,3번 도시를 방문한 상태입니다. 110(2)를 십진수로 바꿔보면 6(1x22 + 1x21 + 0x20)이 됩니다. 즉,.. 2019. 8. 31.
[Vue.js] node-sass, fsevents Error Problem 33 warnings and 15 errors generated. make: *** [Release/obj.target/fse/fsevents.o] Error 1 gyp ERR! build error gyp ERR! stack Error: `make` failed with exit code: 2 gyp ERR! stack at ChildProcess.onExit (/*****/node_modules/npm/node_modules/node-gyp/lib/build.js:196:23) gyp ERR! stack at ChildProcess.emit (events.js:209:13) gyp ERR! stack at Process.ChildProcess._handle.onexit (internal.. 2019. 8. 30.
[leetcode] 1172. Dinner Plate Stacks 문제 : https://leetcode.com/problems/dinner-plate-stacks/ let) capacity = 2 index 0 1 2 3 stack 4 1 3 5 fullStack : 가득찬 스택 인덱스 (2) blankFullStack : fullStack 사이사이의 index (0, 1, 3(3인덱스 스택이 가득찼다가 삭제된 경우)) stackMap : key - index, value - stack ({0, {1}}, {2, {4,3}}, {3, {5}) push 처음 push하는 경우는 0번 인덱스 stack에 push. 가득찬 스택들 중간에 빈 곳이 있는 경우(blankFullStack이 있는 경우) 빈 곳 중 가장 왼쪽에 넣어준다. 왼쪽부터 차례대로 스택들이 모두 차있는 경.. 2019. 8. 30.
[leetcode] 1171. Remove Zero Sum Consecutive Nodes from Linked List 문제 : https://leetcode.com/problems/remove-zero-sum-consecutive-nodes-from-linked-list/ 링크드리스트 문제. 링크드리스트를 앞에서부터 탐색하면서 현재까지의 sum을 key, ListNode*을 value로 하는 map을 만들어서 저장해간다. 1, 3, 2, -3, -2, 5, 5, -5, 1 을 예로 들어보자. index 1 2 3 4 5 6 7 8 9 array 1 3 2 -3 -2 5 5 -5 1 subsum 1 4 6 3 1 6 11 6 7 합을 구하면 위 표와 같다. 링크드리스트라 인덱스로 표현되지는 않지만 말하기 쉽게 임의로 차례대로 인덱스를 붙여놓았다. 1. subsum으로 검색시 map에 없는 경우 인덱스 1~4가 이에 속한다.. 2019. 8. 28.
너비 우선 탐색(BFS: Breadth First Search) 그래프를 탐색하는 보편적인 방법은 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS)이 있습니다. 이번 시간에는 그 중 너비 우선 탐색에 대해 알아보겠습니다. 너비 우선 탐색은 그래프를 넓게 탐색하는 방법입니다. 예를 들어 보겠습니다. 너비 우선 탐색의 알고리즘은 1. 노드와 연결된 탐색하지 않은 모든 이웃 노드를 탐색한다. 2. 방금 탐색한 노드들에 1번 과정을 실행한다. 입니다. 즉, 1번 2번을 모든 노드가 탐색될 때까지 번갈아가며 실행합니다. 이해를 돕기위해 위의 예시 그래프를 너비 우선 탐색(BFS)으로 탐색해 보겠습니다. 시작 노드는 1번으로 하겠습니다. 일단 시작 노드인 1번 노드를 탐색합니다. 그리고 1번 노드의 이웃 노드 중 탐색하지 않았던 노드들을 우선 모두 탐색합니다. 즉, 2번 3번.. 2019. 8. 28.
[테트리스] 8. 키보드 버튼 구현 2018. 8. 1. # html # css // 기본 화살표 배경-흰, 화살표-검 .arrow { color: black; background-color: white; } // 클릭 시 화살표 배경-검, 화살표-흰 .click { color: white; background-color: black; } # js // 키보드 keyCode 상수 const LEFT = 37; const UP = 38; const RIGHT = 39; const DOWN = 40; const SPACEBAR = 32; // 키보드 element 가저온 변수 var arrow_up = $(".fa-arrow-up"); var arrow_down = $(".fa-arrow-down"); var arrow_left = $(".f.. 2019. 8. 27.

티스토리툴바