알고리즘(Algorithm) (45) 썸네일형 리스트형 계수정렬(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) 한다는 것은 그래프내에 사이클이 있는가? 있다면 총 몇 개 존재하는가 ? 그리고 사이클에 포함된 노드의 개수는 몇 개인가.. 동적프로그래밍(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); // 무방향 그래프이니 역뱡향도 추가하였는데 방향그래프에서는 명확.. 퀵정렬(Quick Sort) 퀵정렬은 매우 효율적인 정렬 알고리즘이며 데이터 배열을 특정 규칙에 의해 분할 하면서 정렬을 하는 분할정복(Divide & Conquer) 에 기반한다. 분할단계에서는 배열은 다음과 같은 조건이 만족되도록 2개의 부분으로 나누는데 그 중 하나는 지정된 값보다 작은 값들로 다른 하나는 지정된 값보다 큰 값들로 이루어지도록 분할한다. 여기서 지정된 값을 보통 피벗(pivot)이라고 불린다. 즉, 분할되기전 배열에서 임의의 기준값이 될 피벗을 하나 선택한다. 피벗을 배열중에 어떤 놈을 선택할지는 나중에 설명하겠다. 지금은 그냥 배열에 아무값이나 선택한다고 생각하면 된다. 지금은 일단 배열의 맨 끝에 있는 놈을 피벗으로 선택한다. 다음 그림에서 ①번은 아직 정렬되지 않은 배열데이터를 나타내고 ②번은 맨 끝에 있.. 부르트포스(Brute Force) 일반적으로 SW를 개발하면서 결정 문제(decision problem), 탐색 문제(search problem), 카운팅 문제(couting problem), 최적화 문제(optimization problem), 함수형 문제(function problem) 문제등 다양한 문제해결(Problem Solving)이 필요하다. 문제해결을 위해 단순한 자료구조나 알고리즘을 이용하면 되는 경우도 있지만 한개이상의 알고리즘을 복합적으로 사용하여 풀어야 하는 경우도 많이 있다. 부르트포스(Brute Force) 란 위와 같은 다양한 문제해결을 위해 어떤 방식으로 접근할 것인가? 인데 결론 부터 말하면 문제해결을 위해 모든 가능한 경우의 수를 모두 뒤져서 해를 얻는 한마디로 좀 무식한 방법 이다. 대표적으로 어떤 해커.. 이전 1 2 3 4 5 6 다음
