• (프로그래머스 코딩테스트 고득점 kit) Greedy Algorithm Level2 큰 수 만들기

    문제 어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다. 예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다. 문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의...


  • (알고리즘) Minimum Spanning Tree MST 알고리즘 - Kruskal 알고리즘

    Minimum Spanning Tree란? Minimum Spanning Tree란 Undirected Graph 내에서 Cycle이 발생하지 않는 한도 내에서 모든 vertex가 연결되있는 tree 중 weight의 합이 가장 작은 tree를 의미한다. 그렇기 때문에 무조건 Edge의 갯수는 Vertex 갯수 - 1 개이다. 어떻게 찾지? 일단 edge의 set인 A를 만들자 처음에 A가 빈 상태에서 하나씩 넣은 거다. 여기서...


  • (알고리즘) Union Find 알고리즘 강화버전 - Rank, Path Compression 사용

    기존 Rank 활용 방법 이전 포스트에서 그림으로 표현했듯이, union과 find를 계속 진행하다보면 worst case에서는 그림과 같이 나오게 된다. 그림과 같이 작은 트리가 큰 트리에 붙는 형식으로 이는 Linked List의 형태를 띄게 된다. 이것의 시간 복잡도는 O(log n) 만큼 걸리게 된다. 이를 union by rank라고 한다. Path Compression 활용 방법 다른...


  • (알고리즘) Disjoint Set 구조와 Union Find 알고리즘

    Disjoint-set 구조와 Union-Find 알고리즘이란? Disjoint set 이란 연결이 끊어진 원소들의 집합을 의미 한다. 이 데이터 구조를 위해서 Union-Find 알고리즘이 2가지 주요한 operation을 제공한다. Find : 어떤 원소가 어느 집합에 있는지 찾아준다. 주로 두개의 element가 같은 집합에 있는지 확인하는데 사용된다. Union : 2개의 집합을 하나의 집합으로 합쳐준다. 이 알고리즘은 Cycle을 찾는데...


  • (프로그래머스 코딩테스트 고득점 kit) Greedy Algorithm Level3 섬연결하기

    문제 n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요. 다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가...