L.O.K

노드의 개수가 N이고 간선의 개수가 E일 때, DFS, BFS로 그래프를 완전탐색한다면 시간복잡도가 O(N+E)인 이유는 무엇일까? DFS, BFS는 완전탐색에 이용된다. 반복문으로 모든 노드를 탐색해야 하므로 시간복잡도는 최대 O(N)을 갖는다. 그럼 이제 노드 하나를 방문해보자. 여기서 부터 간선의 개수가 연산에 영향을 미친다. DFS는 재귀호출로 인접한 노드에 접근하고 BFS는 인접한 노드를 큐에 넣는다. 그러므로 DFS는 인접한 노드의 개수, 즉 간선의 개수에 따라 재귀호출이 반복되고 BFS는 인접한 노드의 개수, 즉 간선의 개수에 따라 while문이 반복된다. ( 큐가 빌때 까지 ) 그리고 여기서 방문처리가 이루어 진다. A노드를 방문하면 인접한 노드 B, C를 방문하고 B를 방문하면 인접한 노..

JAVA에서 우선순위 기준이 복잡할 때, 정렬을 위해 주로 사용하는 자료구조가 우선순위큐(PriorityQueue)이다. 우선순위큐가 내가 원하는 우선순위대로 정렬하려면, 비교로직을 우선순위큐에 전달해야 한다. 이번 포스팅은 우선순위큐에 비교로직을 전달하는 방법을 알아보겠다. 예시 정렬기준 ( 여러 단어를 3가지 기준으로 정렬한다. ) 자주 나오는 단어일수록 앞에 배치한다. 해당 단어의 길이가 길수록 앞에 배치한다. 알파벳 사전 순으로 앞에 있는 단어일수록 앞에 배치한다 1) Comparable 인터페이스 우선순위큐는 객체를 기준으로 정렬하는데, 객체가 자체적인 정렬기준을 가지고 있으면 우선순위큐가 알아서 참조하여 정렬한다. 객체가 자체적인 정렬기준을 가지려면 Comparable 인터페이스를 구현해서 c..

https://lordofkangs.tistory.com/411 [Alogorithm] 세그먼트 트리( Segment Tree ) 구간합 구하기 ( + BOJ2042 ) With Python,JAVA[Alogorithm] 세그먼트 트리 ( Segment Tree ) 프로그래밍 분야에서는 시간-공간 트레이드-오프(Trade-off) 현상이 자주 일어난다. 처리시간을 줄이면 처리공간이 늘어나고 처리공간이 줄어들면 처리시간lordofkangs.tistory.com 지난 포스팅에서 세그먼트 트리로 구간합을 O(logN) 시간복잡도로 구해보았다. 수열의 변경이 자주 일어나지 않는다면 메모리를 적게 차지하는 배열이 좋지만 변경이 자주 일어난다면 처리속도가 빠른 세그먼트 트리를 구성하는 것이 좋다. (트레이드-오프)..

[Alogorithm] 세그먼트 트리 ( Segment Tree ) 프로그래밍 분야에서는 시간-공간 트레이드-오프(Trade-off) 현상이 자주 일어난다. 처리시간을 줄이면 처리공간이 늘어나고 처리공간이 줄어들면 처리시간이 늘어나는 현상이다. 세그먼트 트리(S lordofkangs.tistory.com 지난 포스팅에서 세그먼트 트리를 알아보았다. 세그먼트 트리는 수열의 변경이 잦은 경우 구간합을 빠른속도로 구할 수 있는 알고리즘이다. 세그먼트 트리는 재귀호출로 구현되며, 파라미터로 구간과 구간합이 저장된 노드의 위치를 받는다. 이번 포스팅에서는 원하는 구간의 합을 구하는 로직과 세그먼트 트리를 UPDATE하는 로직을 알아보겠다. 원하는 구간의 합 구하기 세그먼트 트리는 각 노드에 구간의 합이 들어가 있..

이분 그래프(Bipartite Graph)란, 서로 다른 두 집합의 노드 간 연결로 이루어진 그래프이다. 같은 집합의 노드 사이에는 간선이 존재하지 않는다. 예를 들어, 사람-취미 관계를 나타내는 그래프라고 해보자. 위 그래프의 노드는 사람집합, 취미집합 두 가지로 나뉜다. 관계를 나타내는 간선은 사람과 집합 사이에 있어야 한다. 사람과 사람, 취미와 취미 사이에 간선이 있어서는 안 된다. 이렇듯, 이분 그래프는 서로 다른 집합 사이의 네트워크를 나타낼 때 사용된다. 연령별 선호 영화 , 어플 이용자와 동네정보로 동네친구 찾기 서비스 그리고 전력회사와 전력소비자로 전력공급 네트워크도 구성할 수 있다. 고로, 이분 그래프는 같은 집합에 있는 노드 사이에 간선이 있으면 안 된다. 지훈이의 취미가 축구인데, ..

프로그래밍 분야에서는 시간-공간 트레이드-오프(Trade-off) 현상이 자주 일어난다. 처리시간을 줄이면 처리공간이 늘어나고 처리공간이 줄어들면 처리시간이 늘어나는 현상이다. 세그먼트 트리(Segement Tree)는 공간을 늘리고 시간을 줄인 알고리즘이다. 5 8 7 3 2 5 1 8 9 8 7 3 세그먼트 트리가 필요한 이유는 수열의 구간합 테이블을 더 빠른속도로 구현하기 위함이다. 노드의 개수가 N일때 구간합테이블을 배열로 구성하면 N개의 노드가 필요하지만 시간복잡도는 O(N)이다. 반면 세그먼트 트리로 구성하면 최대 4xN개 노드가 필요하지만 시간복잡도는 O(logN)이다. ( 4xN개의 노드가 필요한 이유는 밑에서 다루어 보겠다. ) 그러므로 수열의 변경이 자주 일어나 구간합테이블이 자주 변경..

위상정렬은 방향그래프를 한 정렬이다. 위 그래프는 작업 간 의존관계를 표현한다. 작업C는 작업B와 작업E가 완료되어야 처리가 가능하다. 그래프는 의존관계는 표현하지만 어떤 작업부터 처리해야 하는지 알려주지는 않는다. 위상정렬(Topology Sort) ◎ 알고리즘 위상 정렬의 조건은 하나이다. ☑︎ 전처리 작업이 완료된 순서대로 작업이 진행되어야 한다. 이를 어떻게 구현할까? 방향그래프는 방향을 가진 간선을 가지고 있다. 노드로 들어오는 간선의 개수를 진입차수라고 한다. 작업C는 진입차수가 2이다. 간선① : 작업B ➠ 작업C 간선② : 작업E ➠ 작업C 작업B가 완료되면 작업B는 간선①을 제거한다. 작업E가 완료되면 작업E는 간선②를 제거한다. 작업C는 진입차수가 0이된다. 그럼 큐에 들어가서 선입선출..

현실은 복잡하다. 수많은 싸이클이 존재하고 비효율이고 무질서하다. 그러므로 우리는 싸이클을 제거하고 효율높은 질서를 찾아야 한다. 그래프는 여러 개의 신장트리(Spanning Tree)를 갖는다. 신장트리(Spanning Tree)란? 모든 노드가 연결되면서 사이클이 존재하지 않는 그래프를 의미한다. 여러 신장 트리 중 가장 비용이 적은 신장트리를 최소신장트리라고 부르는데, 최소신장트리를 구하는 대표적인 알고리즘이 크루스칼 알고리즘(Kruskal Algorithm)이다. 크루스칼 알고리즘(Kruskal Algorithm) 크루스칼 알고리즘은 두 가지 조건이 충족되어야 한다. 1) 최소비용이어야 한다. ( 정렬을 활용한 그리디 알고리즘 ) 2) 싸이클이 존재하면 안 된다. ( Union-Find 알고리즘으..

싸이클(Cylce)은 '순환'을 의미한다. 일반적으로 싸이클은 좋지 못한 현상이다. 자칫 무한 루프에 빠질 수 있고 순환을 이루는 개체간의 종속성이 올라간다. 간선을 의존관계라고 생각해보자. A는 C에 의존하고 C는 B에 의존하고 B는 A에 의존한다. 종속성이 커질수록 결합도가 올라가 유지보수가 어려워진다. 그러므로 그래프가 싸이클이 있는지 여부를 판단하는 알고리즘이 필요하다. 1) 무방향그래프에서 사이클 찾기 ( Union-Find 알고리즘 ) 2) 방향그래프에서 사이클 찾기 ( DFS 탐색 알고리즘 ) 간선에 방향이 없으면 무방향그래프, 있으면 방향그래프이다. 이번 포스팅에서는 무방향그래프에서 싸이클을 찾아보겠다. Union-Find 알고리즘 사용하기 [Algorithm] Union-Find 알고리즘..

서로소 집합(Disjoint Sets)이란? 공통원소가 없는 두 집합을 의미한다. 이는 그래프(Graph) 구조에서 '연결성' 정보를 제공한다. 4세대 아이돌 8명이다. 우리는 8명을 그룹별로 구분하여 '연결성'을 자료구조로 남기고 싶다. 이때, 서로소 집합 자료구조를 사용할 수 있다. 8명은 각 팀의 리더에게 소속된다. 리더는 나이가 많은 사람이다. 서로소집합의 자료구조는 각 멤버의 리더정보를 담고 있다. ◎ 서로소집합 자료구조 멤버 사쿠라 카즈하 홍은채 가을 안유진 장원영 키나 새나 리더 사쿠라 카즈하 홍은채 가을 안유진 장원영 키나 새나 ◎ Union-Find 알고리즘 ( 서로소 집합 구현 ) 처음에는 각 멤버의 리더는 본인이다. 아직 어떤 연결도 없는 상태이다. 그래프에서 연결은 '간선'이다. 여..