전체 글 (163) 썸네일형 리스트형 알고리즘22 SCC SCC 안에서는 다른 어느 노드든 다 이동할 수 있다. 더 이상 키울 수 없는 노드들의 집합 그 안의 노드들은 양쪽으로 reachable 사이클 = SCC는 아니지만 사이클 하나는 SCC. 일단 그냥 사이클이라고 생각하고 일단 무작정 DFS를 해보자. (cut vertex는 어디에서 시작해도 같은 결과가 나온 것과 다르게) 하지만 시작 지점에 따라 DFS tree가 다르게 나오고 전진할 수 있는 것이 여러개 있을 때 어디로 전진하느냐에 따라서 다르게 나온다. 같은 그래프지만 트리가 두개로 나올 수도! 한 트리가 여러개의 SCC를 가지고 있을 수는 있지만, 한 SCC가 여러 Tree에 나눠있지는 않다! 한 번 들어오면 다 돌기 때문에 다른 트리로 나눠질 수 없다. 한 SCC에 들어 있는 노드들이 두 개의 .. 알고리즘21-2 2배 가까이 빠르다. 기존 방법은 DFS를 통해indegree를 알아냈다. 이 방법은 directed 그래프에서 DFS하는 방법. 엣지 방향을 맞춰서 전진해야 한다. (post order로 번호) post번호가 줄어드는 순서대로 출력한다. or post번호를 계산하는 순간 노드를 출력할 수 있다. (모든 엣지가 오른쪽->왼쪽이 된다.) 사이클이 있을 수있으므로 back edge, forward edge가능 cross edge는 무조건 오른쪽에서 왼쪽으로. 왼쪽에서 오른쪽으로는 갈 수가 없다. 왼쪽부터 도는건데 밑에 노드로 있었겠지 DAG는 백엣지가 없다. 이 상태에서 알고리즘 정당화하겠다. 먼저간걸 왼쪽에 그리고 트리 order대로 그리면 무조건 이순서 (왼쪽이 번호가 작고 위로갈수록 크다) 큰번호->작.. 알고리즘21 자신의 pre번호, 자신이 올라갈 수 있는 pre번호, 자신의 subtree에서 올라갈 수 있는 pre번호 중 가장 작은 것 셋 중 하나라도 못올라가는 게 있으면 t는 cut vertex Cut Edge : 이 엣지가 사라지면 그래프가 끊어진다. 모든 엣지마다 빨간 노드를 넣는다. (엣지 하나를 끊고 2개로 나눈다.) 엣지마다 노드가 추가되었으므로 노드 = m개 엣지 = 2m개 nxm -> mxm dfs돌려서 Cut Vertex를 찾는다. 빨간 노드 중에 Cut Vertex가 있는지 찾는다. BCC (Biconnected Component) Cut Vertex의 의미가 더 크다(?) cut edge와 cut vertex를 생각해보자. cut edge는 없다. cut vertex는 있다. 이 그래프는 사실.. 알고리즘20-2 Cut Vertex connected graph에서만 정의 된다. (Vertex = Node) : 노드 s를 그래프에서 없애면 graph가 disconnect가 될 때, 그 노드를 cut vertex라고 한다. (노드와 연결된 엣지가 없어진다.) : 노드 x에서 노드 y로 가는 모든 path가 s를 통해서 지나가면 cut vertext라고 한다. 정의를 그대로 썼을 때의 시간, connected Components : O(m+n)이다. 이것을 모든 노드마다 돌려야 하므로 O(n (m+n)) = O(mn+n^2) DFS tree의 루트가 cut vertex이면 child가 두 개 이상이다. 백엣지가 서브트리 안에 있으므로 서브트리를 벗어나면 무조건 루트로 오게 된다. y는 x의 서브트리 밖에 있다. x에서 y로 가려면 루트를.. 알고리즘20 어떤 박스를 쓰느냐에 따라서 달라진다. DFS를 재귀적으로 표현하는 것이 더 편할 때도 있다. p에서 시작했다고 치면 누군가 얘를 최초 호출해주는 애가 있어야 한다, RDFS(p) 나머지는 재귀적으로 돌아간다. global 마크 배열(모두 0으로 초기화) 1이 되면 마킹하는 것 노드마다 숫자를 2개 적는다. pre = 1 / post =1 로 시작 (글로벌 변수) pre(s) 트리 or - connected인지 확인 & 노드가 n개일 때 엣지 갯수가 반드시 n-1개 (사이클을 직접 체크하지 않아도 된다.) 루트를 무조건 왼쪽 그룹에 넣고 생각해보자. 루트와 연결된 노드는 무조건 오른쪽 그룹에 있어야 함 R와 L을 잇는 백엣지만 있어야 함 (같은 사이드에 있는 back edge가 하나라도 있으면 => NO) 알고리즘19-2 Event Queue 박스를 큐로 생각하자. 이벤트 큐를 쓰는 문제를 먼저 하나 알아보자. 한 라운드에서 감염이 퍼져나간다. 상하좌우 중 2개에 감염이 있다면 나도 감염된다. 마지막에 감염이 되고 끝나는 상황을 그릴 수 있다. round마다 전체를 보고 있으므로 round 개수 x n(세로) x m(가로) (라운드 갯수는 상수가 아니기 때문에 커질 수 있다.) 이벤트 큐를 만들어둔다면? 큐에는 감염이 되어있는 칸들을 넣는다. 첫번쨰 라운드에서 감염이 되는 칸때문에 추가로 감염이 되는 칸은 이렇게 4개 밖에 없다. 추가로 감염이 될 때마다 인접한 4개만 체크해보면 다음 라운드에 감염될 칸을 알 수 있다. 추가로 감염되는 칸은 큐에 들어간다. (4개의 칸을 큐에 모두 넣는다고 하면 위와 같은 상황이 된다.?.. 알고리즘19 그래프 알고리즘 배열, 기하에 비해 직관적으로 풀기 어렵다. 친구 추천 알고리즘 등에 쓰이는 경우가 많다. 체계적으로 만드는 방식 : Graph Traversal Traversal : 그래프의 노드를 방문하는 방법 어디서 시작하는지 정하지 않는다. 어디에서 시작하느냐에 따라서 다른 알고리즘이 된다. 같은 노드를 여러번 지나갈 수 있다. 어떤 문제를 푸느냐에 따라서 뭔가를 계산한다. Traversal을 통해 그래프 안에 뭔가 구조가 만들어질 것이다. => 보통 Tree가 만들어 진다. *그래프에서 안풀리는 문제가 트리에서 풀리는 경우가 많다. (일반적인 form) 노드 s에서 시작한다. (노드 s를 정하는 방법은 문제마다 다르다.) s를 박스에 넣는다. 박스에 넣는 것은 앞으로 처리할 일들 빈 박스가 아닌 동안 프로그램이.. Google Map API 총정리 디버그용 API 디버그용 API는 구글API콘솔 오른쪽에 친절하게 나와있듯이 윈도우 기준 cmd창에 keytool -list -v -keystore "%USERPROFILE%\.android\debug.keystore" -alias androiddebugkey -storepass android -keypass android 을 입력했을 때 나오는 SHA-1 값을 패키지명과 함께 이 곳에 입력한다. 릴리스용 API (주의: 릴리스용 API는 일단 구글API콘솔에서 디버그용과 별개의 새 프로젝트를 생성해야 한다.) 안드로이드 스튜디오에서 key를 하나 생성하고 윈도우 기준 cmd창에 keytool -v -list -keystore 내 프로젝트 기준 key를 생성한 위치 ex) keytool -v -list .. 이전 1 ··· 5 6 7 8 9 10 11 ··· 21 다음
