알고리즘 (54) 썸네일형 리스트형 알고리즘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를 박스에 넣는다. 박스에 넣는 것은 앞으로 처리할 일들 빈 박스가 아닌 동안 프로그램이.. 알고리즘18-2 완전 정보 게임 완전 정보 게임 (NIM GAME) : 정보가 공개되어 있어 승부가 정해져 있지만 계산할 수 없음 불완전 정보 게임 ex) 화투 놀이, 포커, 스포츠베팅 Win : 상대방이 무슨 수를 써도 반드시 이기는 방법 (하나라도) 있음 / Lose : 내가 무슨 수를 써도 못이김 9개를 받으면 내가 무슨 짓을 하더라도 진다. 배스킨라빈스 31게임이랑 같은 듯 나머지 칸에서 찾는다. 마지막칸에서는 제한없음 알고리즘18 다이나믹 프로그래밍 마지막 금화모으기 둘 중에 큰 값을 골라서 (i,j)의 코인을 더한다. 8원을 거슬려주는 방법 중 1원 동전을 한개 쓰는 방법은 8-1=7원을 거슬러주는 방법 연속으로 일할 수 없다. critical idea : 끝나는 순서를 보면된다. 1 2 3: 15만원이 최대 4: 20이 최대 5: 30이 최대 6: 30 (T9를 가져가게되면 T5를 가져가게 되고 27만원보다 전날까지 일한 것이 더 비쌈) 7. 15+25=40 8. 8번째 끝나는 일이없음 9. (20+27)=47 (T3을 가져오면 42) 10. 49 선택하지않으면 전날까지 받은 돈과 같음 p(j) = 마지막 작업과 안겹치는 작업 중 마지막 작업 (☆) 끝나는 날짜로 sorting이 되어있기 때문에 시작날짜를 넣어 binary search n개 중 k개 고.. 이전 1 2 3 4 5 6 7 다음
