오뚝이개발자

개념 위상정렬이란 directed graph에서 꼭짓점을 방향성을 거스르지 않도록 정렬하는 방법이다. 실생활에서 대표적인 예시가 바로 선수과목(prerequisite)이다. 알고리즘 구현하는 방법은 아래와 같다. 연결성에 대한 정보를 가지고 인접리스트를 만든다. 이를 기반으로 in-degree(해당 vertex로 들어오는 선의 갯수) 정보를 담은 배열을 만든다. in-degree가 0인 vertex를 stack에 담는다. stack에서 pop하고 해당 vertex와 연결된 점들의 in-degree를 -1 한다. 3과 4를 반복하며 stack에서 pop 해줄 때마다 answer 리스트에 담으면 해당 결과가 위상정렬의 결과가 된다. 아래와 같은 그래프가 있다고 하면, in-degree(진입차수) 리스트는 아..

정렬 방법 중 가장 빠른 것은 O(nlogn)의 시간복잡도를 갖는다고 생각할 수 있다. 하지만 이보다 빠른 O(n)의 시간복잡도를 갖는 정렬방법도 있다. 바로 계수 정렬 다른 말로, 카운팅 정렬이다. 하지만 이러한 계수 정렬은 약간 제한된 조건 하에서 사용가능하다. 1 5 2 3 2 5 1 4 4 2 5 1 위와 같은 수가 나열되어있고 이를 정렬해보자. 그런데 자세히 보면, 위에서 등장하는 수의 범위가 1~5까지라는 것을 알 수 있다. 이처럼 수의 범위가 정해져 있는 경우 계수 정렬을 사용하면 효율적으로 정렬할 수 있다. 카운팅 정렬이란 말 그대로 수가 등장하는 횟수를 카운트 하는 것이다. 카운팅이 다 끝나면 크기 순서대로, 해당 수가 등장하는 횟수만큼 print해주면 된다. 위의 경우, 등장하는 수를 ..

DFS를 활용해 connected component의 갯수를 구하는 것이 필요할 때가 있다. 이럴 땐 탐색을 하면서 각 unit별로 구분을 해서 갯수를 카운트 해주면 된다. 정확히는 이를 union find 알고리즘이라고 한다. 예제를 통해 이해해보자. 아래 문제는 프로그래머스에 수록된 문제이다. programmers.co.kr/learn/courses/30/lessons/43162 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr def dfs(start, n, visited, computers): fo..

BFS(너비우선탐색)는 DFS와 함께 그래프를 탐색하는 알고리즘 중 하나이다. BFS는 큐로 구현할 수 있다. BFS는 최단거리를 찾는데 많이 이용된다. BFS는 다음과 같은 알고리즘으로 작동한다. 큐에서 하나의 노드를 꺼낸다. 해당 노드에 연결된 노드 중 방문하지 않은 노드를 방문하고, 큐에 삽입한다. 아래와 같은 그래프가 있을 때, 이를 BFS로 탐색한다고 해보자. 노드를 방문할 때 해주어야 할 것이 두가지가 있는데 하나는 방문처리를 하는 것(그래프에선 빨강색으로 표시)이고 또 다른 하나는 큐에 넣어주는 것이다. 시작노드 1번을 큐에 넣고 방문처리한다. 큐에서 노드 1을 뺀다.(뺀 노드는 위쪽에 표시하였다.) 1과 연결된 노드 중 아직 방문하지 않은 2,3 노드를 큐에 넣고 방문처리한다. 큐에서 2를..

DFS(깊이우선탐색)는 BFS와 함께 그래프를 탐색하는 알고리즘 중 하나이다. DFS는 스택으로 구현할 수 있다. 하지만, 스택을 사용하지 않고도 재귀로 충분히 구현이 가능한데 컴퓨터에서 함수 호출의 과정이 스택으로 구현되는 것을 생각해보면 이해가 될 것이다. DFS, BFS 모두 인접행렬과 인접리스트 두 가지로 구현할 수 있다. 인접행렬로 구현할 경우 특정 item에 접근해 연결성 여부를 검사하는 것은 빠르지만 무조건 O(n^2)만큼의 메모리가 필요하다. 연결리스트를 사용한 인접리스트로 구현하는 경우 메모리 사용을 줄일 수 있지만 특정 item에 접근해 연결성 여부를 검사하는 과정이 좀 느릴 수 있다. 하지만 데이터가 많지 않은 경우 접근에 필요한 시간이 많이 소요되는 것은 아니므로 연결리스트를 사용해..

Dynamic programming이란? 일반적으로, 분할정복 알고리즘과 유사하게 큰 문제를 더 작은 문제로 나누어 푸는 기법(역시 최적해를 찾는데 사용되는 경우가 많다.) 결정적인 차이점은 다음과 같다. 동적 프로그래밍의 경우 작은 문제들이 반복된다.(피보나치의 경우 f(5)를 구하기 위해선 f(4),f(3)이 필요한데 f(4)를 구하기 위해 f(3)이 다시 필요하다.) 동적 프로그래밍의 경우 작은 문제들의 답이 항상 같다는 것이다. 따라서, 위의 경우처럼 반복되는 계산을 줄이기 위해 메모이제이션(Memoization)을 사용 실제로 피보나치 수열을 구하는 함수를 구현할 때, 재귀로 구현하게 되면 반복되는 계산으로 인해 수가 커지면 실행시간이 아주 오래 걸리지만, 동적 프로그래밍으로 구현하면 금방 해결..

Greedy algorithm이란? 매 의사결정마다 정해둔 조건에 따라 가장 좋아보이는 답을 선택하는 것 Greedy algorithm(탐욕알고리즘)은 어디에 쓰이나? 주로 특정 제한조건(Constraints)을 만족해야 하는 상황에서의 최적화 문제에 사용 예) machine scheduling, bin packing, minimum spanning tree(MST) MST란? Spanning tree란 그래프의 모든 노드를 포함하는 트리이다. 이 때, MST란 edge의 가중치 합의 최소인 spannig tree이다. Shortest path problem(추후 자세히 포스팅) 다익스트라 알고리즘(Single source all destination) MST(각 방법별로 추후 자세히 포스팅) Krusc..

Divide and conquer(분할정복)이란? 다음의 세 단계를 거치는 알고리즘이다. Divide : large problem을 small subproblem으로 분할 Conquer : recursive하게 각 subproblem을 푼다 Combine : subproblem의 답을 조합해 large problem의 답을 구한다. D&C 사용 예시 [8,2,6,3,9,1,7,5,4,2,8] 리스트 내에서 최솟값, 최댓값을 찾는 문제는 다음과 같이 풀 수 있다. 먼저 large set을 두 그룹으로 나누고, 나누어진 그룹에서 다시 두 그룹으로 나누고....이러한 과정을 풀기에 아주 단순한 small set이 될 때까지 반복한다. 즉, set의 원소 갯수 n이 2개 이하가 될 때까지 하는 것이다.(분할) ..