본문 바로가기

전체 글

 (163)
알고리즘6 Djikstra Algorithm Djikstra Algorithm 유명한 Shortest Path의 정답. 프림 알고리즘과 유사하다. 시작은 한군데지만 모든 목적지로 가는 shortest path를 다 구한다. shortest path의 모든 부분은 shortest path이다. 대부분 path를 구하는 것이 아니라 path의 길이만을 구한다. => 길까지 구하는 것으로 금방 바꿀 수 있다. 심지어 path가 여러 개일때 모든 path를 다 찾을 수 있다. 3단계로 나눠서 얘기하면 이를 설명할 수 있음 일단 1단계부터 설명 => 2단계로 바꾸고 => 3단계로 바꿀 것임 (1단계에서 왜 이게 답을 찾느냐가 어려움) G: 입력 그래프 n: 노드 갯수 R: 빨간 노드 집합 V0: source node dmin: 노드에 써진 숫자 빨간노드와 ..
No Activity found to handle Intent : android.intent.action.VIEW 뻘짓했네 ㅠㅠ 인텐트를 딴 클래스에서 쓰는데 왜 안되나 했다... 매니페스트에 인텐트필터 추가하고 이런거 다 필요없고... Uri.parse("tel:"+mapPOIItem.userObject.toString().split(",")[1]) "tel:" 을 넣어줍시다... (띄어쓰기도 하면 안된다고 함)
알고리즘5-2 Prim and Kruskal Algorithm의 특징 특징을 확인해나가는 과정이 중요하다. # solution to MST MST의 솔루션이 몇개냐 좋은 점: 갯수를 계산할 수 있는 답이 있다. 나쁜 점: 너무 어렵다. (학부 수준x) 답이 유일할 조건 중 충분 조건을 알아보려고 한다. (이런 경우에 답이 유일하다) (답이 유일해서 이런 경우다 X) Weight가 모두 다 다르면 답이 유일하다. ex) 답이 유일하지만 Weight가 모두 다르지 않은 경우 당연한 거 아냐? 당연한 거 아님! 어려움! 엣지가 많을 경우 1,4를 선택하는 경우가 있을 수도 있고 2,3을 선택하는 경우가 있을 수도 있다. (1,4를 선택하고 2,3을 선택하는 답이 있다면 1,2를 선택하는 답을 보여라~) 이 방법은 너무 어렵고 Prim and Kruskal Algorithm ca..
알고리즘5 - Kruskal Algorithm 내 프로그램이 정확하다는 말은 언제든지 할 수 있어야 한다. Prim알고리즘은 한 노드에서 시작해서 퍼져 나간다. 엣지를 추가한다는 점에서 유사하다. Kruskal Algorithm는 전체 그래프에서 가장 작은 엣지를 추가한다. 1,2,3을 추가한 상태이고 이제 4를 추가해야 하지만 두 개의 4 모두 추가하면 사이클이 된다. PASS 프림 알고리즘에서는 이미 들어간 노드와 안들어간 노드를 연결하면 사이클이 생기지 않았다. Kruskal 에서는 어떻게 사이클을 판단할 것인가? 같은 덩어리를 연결하면 사이클이 생긴다. 연결이 안된 노드는 하나의 덩어리라고 생각 이러면 답을 찾느냐? 성능은 어떻게 되는가? 정확성 프림 알고리즘과 마찬가지로 정답은 여러개일 수 있다. 정답 중 하나를 찾는다는 것을 증명한다. 하..
알고리즘4 Greedy Algorithms - Prim Algorithm 알고리즘을 작전별로 보자! Greedy AlgorMinimum - Spanning Treeithms 답을 찾기 위해 선택을 반복하는 알고리즘 중 비교적(?) 간단한 방법으로 선택하고 선택한 후 바꾸지 않는 알고리즘 그리디 작전을 쓴다면 가장 짧은 쪽으로 계속 간다. B>A>C>D...?? 지금은 안된다. 물론 풀리는 예도 있다. selection sort도 그리디였다. 가장 작은 걸 앞으로 보낸다. 뒤돌아보지 않는다! undirect graph에서 Minimum Spanning을 정의할 수 있다. node가 5개, edge 4개 고르면 tree가 된다. (node n개인 tree는 edge가 n-1개) Tree: Connected Acyclic Graph 모든 노드가 연결되어 있고 사이클이 없는 그래프 ..
알고리즘3-2 자료구조 리뷰2 AVL Tree BST가 보통의 경우에 성능이 좋지만, 특수한 경우에 안 좋다. = > Balanced Tree 최악의 경우에도 O(logN) 왼쪽, 오른쪽 subtree의 높이 차이가 1이하 L-R = 0, 1, -1 중에 하나 따라서 위의 오른쪽 그림은 안됨 루트에서 갈 수 있는 제일 짧은 길과 제일 긴 길 차이가 2배 이하다. 중간까지는 tree높이에 비해서 노드 수가 많기 떄문에 => 노드 갯수에 비해서 tree 높이가 작다. => O(log n) 2-3 Tree key가 1개 있고 child가 2개 있는 노드 key가 2개 있고 child가 3개 있는 노드를 섞어서 만든다. AVL tree와 결국 비슷한 얘기지만 이게 더 직관적이다. 삽입할땐 key와 key사이 가운데로 삽입되어서 위로 올라갈 ..
알고리즘3 자료구조 리뷰 이런 알고리즘이 이런 자료구조를 쓴다~를 알기 위해서! Array 연속된 주소, 동일한 type 갯수를 미리 잡아둬야 한다. 용량을 늘리려면 다른 메모리에 옮겨야 한다. int A[10] 은 int가 4byte이므로 총 40byte A:400 404 408 412 ... A[7] = 400 + 7*4 = 428 이런식으로 바로 찾아갈 수 있음 Search, Delete, Insert 입장에서 좋은 효율은 아니다. sorting이 되어있다면 Binary Search O(log N)가능하다. Stack insert / Delete만 제공한다. Search x =Push O(1) / Pop O(1) Last in, First out 나중에 들어간 게 먼저 나온다. 수식 계산에 사용 ex (3+7)*2 + (6..
카카오맵 local api - rect 사용법 ?rect="여기에 들어갈 것은 무엇인가?" 문서도 자세하지 않고, 개발자 포럼 답변도 뭔가 아리송했따. 여러번의 시도 끝에.... 결론은 나는 이렇게 했다. onMapViewMoveFinished에서 지도에서 손을 뗸 순간의 화면의 BottomLeft값과 TopRight값을 받아왔다. 그리고 각각 저장해주었다. left = mapView.mapPointBounds.bottomLeft.mapPointGeoCoord.latitude.toString() bottom = mapView.mapPointBounds.bottomLeft.mapPointGeoCoord.longitude.toString() right = mapView.mapPointBounds.topRight.mapPointGeoCoord.latitu..

티스토리툴바