전체 글 (79) 썸네일형 리스트형 계수정렬(Counting Sort) 선택정렬(Selection sort), 삽입정렬(Insertion sort), 거품정렬(Bubble sort)는 평균 시간 복잡도가 O(N^2) 이고 빠른정렬(Qick sort), 합병정렬(Merge osrt), 힙정렬(Heap sort) 은 O( n log n )이였다. 반면 계수정렬(Counting Sort)는 다른 정렬 알고리즘보다 좀 더 빠른 O(n)의 성능을 보여준다. 그럼 다른 정렬알고리즘 보다 빠르다고하니 계수정렬만 사용하면 되는거 아닌가 ? 라고 생각할 수 있는데 계수정렬은 특정 상황에서만 사용해야하는 제약이 따른다. 계수정렬 알고리즘을 살펴보자. 계수정렬은 기본적으로 원소들의 빈도를 카운트하여 정렬하는 방법이다. 빈도를 카운트하여 정렬한다는게 이해하기 어려울수 있으니 그림을 보면서 이해하.. 백트래킹(BackTracking)이란? Q. 백트래킹이란 ? 지금은 네비게이션이 잘 발달 되어 있으니 설명이 애매하지만 네비게이션도 없고 지도도 없는 세상에 왔다. A출발점에서 B 목적지까지 아무것도 없이 걸어서 또는 자전거를 타고 여행을 간다고 생각하면 일단 직관적으로 아 이쪽길로 가면 목적지에 가겠지 하고 가본다. 그런데 도착해서 동네사람들에게 물어보니 이동네는 그 동네가 아니라고 하면 선택은 다른 갈림길로 가던지 일단 왔던길을 되돌아가서 이쪽길은 절대가면 안되는길이라고 뭔가 표식을 달아 놓고 다른 길로 가는 선택을 할 수 있겠다. 물론 길을 선택하는데 앞에 강이 있거나 큰 바다가 있거나 높은 산이 있거나(제약조건) 등... 어떠한 이유로 갈수없는것들은 목숨걸고 갈필요 없이 포기하고 빨리 다른길을 선택 할 수도있다. 이리저리 이길 저길 다.. [그래프] 그래프에서 사이클 찾는 방법들(Detect Cycle in an Graph) Q. 그래프에서 사이클이 이란 ? 그래프의 특정 정점에서 출발하여 돌아다니다가 다시 처음 출발했던 곳으로 되돌아 갈 수 있으면 사이클이 있다고 한다. 그림1에서 (a)는 Tj(출발) → Tn → Tm → Tj(출발지점으로 다시 돌아옴) 으로 순환되는 사이클이 있지만 (b)는 어디에서 출발하던 출발지점으로 다시 돌아올수 있는 방법이 없다. 즉 사이클이 존재하지 않는다. [출처] https://www.researchgate.net/figure/Example-of-cyclic-and-acyclic-graphs_fig2_2431833 Q. 사이클을 찾는다는 것은? 사이클을 검출(detect) 한다는 것은 그래프내에 사이클이 있는가? 있다면 총 몇 개 존재하는가 ? 그리고 사이클에 포함된 노드의 개수는 몇 개인가.. 서로소집합(Disjoint Set) - 합집합-찾기(union–find) 서로소집합에 대한 개념은 위키백과에 너무 잘 설명되어 있어 위키백과를 기준으로 개념을 알아보자. Q. 서로소집합(Disjoint Set : 디스조인트 셋) 은 무엇인가 ? 서로소 집합이란 우선 집합이란 단어가 들어 갔으니 수학적으로 집합 개념일 것이다. 수학적으로 집합의 개념을 컴퓨터에서는 자료구조 셋(Set)으로 표현할 수 있다. 나중에 설명하겠지만 서로소집합의 자료구조는 원래 집합 자료구조인 셋(Set)과는 다르게 트리로 구성된다. 오키 그러니 집합이라 했으니 그림1 처럼 생겼겠구나 생각하면 된다. 그럼 집합은 집합인데 서로소(disjoint)는 또 무엇일까? 디스조인트란 말은 서로 공통적인 원소가 없다는 것이다. 서로서로 각자 다르다. 예를들어 그림2. 집합개념에서 좌-상단이 Disjoin sets.. 동적프로그래밍(Dynamic Programming)이란? 동적프로그래밍이란 동적계획법이라고도 부르는데 문제를 풀기위해 필요한 알고리즘이라기보다 문제를 푸는 방식을 말한다. 처음 알고리즘 공부할때 동적프로그래밍이 무엇인지 개념 잡기가 어려웠다. 개념 잡기가 어려웠던 이유는 아마 동적프로그래밍(dynamic programming ) 이름 자체의 모호함 때문이 아니였다 생각든다. 아직도 왜 동적프로그래밍이라고 부르는지 잘 모르겠지만 동적프로그래밍이 무엇인지 이해만 하면 된다. 개념 부터 설명하면 동적프로그래밍이란 ? 풀기가 복잡한 문제(complex problem)가 있다. 이 문제를 자세히 뜯어보니 큰 문제를 작은(하위) 문제(subproblems) 들로 나눌 수 있을거 같고 하위 문제들의 결과(답)를 이용하여 큰 문제를 풀려고 하는 방식이다. 복잡한 문제를 하위.. [그래프] 위상 정렬(Topological Sort) - Kahn's algorithm 방향 비싸이클 그래프(DAG, Directed Acyclic Graph) 는 보통 작업간의 우선순위를 표현하는 용도로 사용된다고 했다. 그런데 그래프에서 작업들을 어떤 순서로 해야하는지 알아야 하는데 어떻게 할 수 있을까 ? 예를들어 아래와 같은 DAG 가 있고 7부터 작업을 시작한다면 7 다음에 5를 할지 6을 할지 그 순서를 정해야 한다. 이와 같이 일어나야 할 순서에 따라 정의된 그래프 구조 상에서 선후 관계에 따라 정렬하기 위해 위상정렬(Topoligical Sort)을 이용할 수 있다. 그림 1)을 위상정렬 하면 그 순서는 7 6 5 4 3 2 1 0로 출력된다. 그럼 실제로 정렬시 작업이 우선순위에 맞는지 즉, 유효한 순서가 되기 위해서 어떤 조건을 만족해야 할까? 당연한 건데 작업의 순서는 .. [그래프] 모든 정점의 indegree 계산 방향그래프(Directed Graph) 구현에서 보다시피 모든 정점의 indegree 를 계산하는 방법은 에지가 추가될 때마다 미리 계산되어질수 있다. 예를들어 v -> w 에지가 추가된다면 w 인덱스에 indegree 의 카운트를 하나 증가 (14번 라인) 시키면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 // indegree[v] 는 정점 V의 incoming edge = indegree의 개수를 저장한다. private int[] indegree; ... public void addEdge(int v, int w) { validateVertex(v); validateVertex(w); // 무방향 그래프이니 역뱡향도 추가하였는데 방향그래프에서는 명확.. 방향그래프(Directed Graph) 구현 방향그래프(Directed Graph) 구현도 무방향 그래프(Unidrect Graph) 구현 에서 한 것과 동일하게 인접리스트와 인접행렬을 이용하여 구현할 수 있다. 차이점은 그림1 (비방향 그래프 vs 방향그래프) 처럼 방향그래프는 정점마다 연결된 에지에 화살표로 들어오고(incoming) 나가는(outgoing) 방향이 있기 때문에 구현하는데 약간 변형을 해야 한다. 인접행렬과 인접리스트를 이용하여 구현하는 상세 설명은 무방향 그래프(Unidrect Graph) 구현 을 참고하고 여기서는 무방향 그래프 구현과 차이가 나는 부분만 코드내 주석으로 설명하도록 하겠다. 인접리스트 이용하여 구현 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24.. 이전 1 2 3 4 5 6 ··· 10 다음
