빠르게 성장하는 개발자

1. 힙(Heap) 이란? 여러 개의 값 중에서 가장 크거나 작은 값을 빠르게 찾기 위해 만든 이진 트리짧게 힙(Heap)이라고 줄여서 부르기도 한다. 힙은 항상 완전 이진트리의 형태여야 한다.출처 : 나무위키 1. 완전 이진트리?포화 이진트리 ( 모든 잎의 level 이 동일한 이진트리. 잎이 아닌 노드들은 모두 2개의 자식을 갖는 트리 ) 를 오른쪽 leaf 부터 제거해서 얻어진 트리. 2. 시간 복잡도데이터의 삽입과 삭제에는 O(log(N))O(log(N))O(log(N))의 복잡도가 소요된다고 한다. 3. 우선순위 큐와 힙일반적인 큐(Queue)는 First in-First Out 구조입니다.즉, 어떤 부가적인 조건 없이 먼저 들어온 데이터가 먼저 나가는 구조였습니다.하지만 우선순위 큐(Prior..

1. DP (Dynamic Programming)?큰 문제를 작은 문제로 ‘쪼개어’ 생각하는 것크게 위에서부터 아래로 문제를 쪼개서 내려가는 Top-down 방식과, 아래에서부터 더해 올라가는 Bottom-up방식이 있다.DP의 전형적인 유형이 몇 가지 있고, 평범한 배낭문제도 그 중 하나에 속한다.2. 평범한 배낭문제생각하기가 힘들어서 검색의 힘을 빌렸다. 그런데 검색을 안했으면, 내 머리로는 절대 생각해 내지 못했을 것 같다.DP에서 알고리즘의 벽을 느끼고 있다.완전히 이해하고 작성하는 글이다.문제는 백준 12865 평범한 배낭 글의 예제를 사용하도록 하겠다. 3. 준비과정이차원 배열이 필요하다. 이차원 배열에는 각 상황에 대한 가치의 최대값을 저장한다.예를 들어 배낭에 들어갈 수 있는 총 무게가 7..

1. 다익스트라 알고리즘이란 무엇인가?MST 다음에 배워서 MST와 비슷한가? 싶었지만 약간 다른 다익스트라!MST는 모든 정점을 잇는 간선이 하나씩 존재해서 모든 정점을 다 이었다면, 다익스트라는 시작정점에서 끝정점으로 가는 경로 중에 가중치가 제일 적은 값을 고르는 알고리즘이다!이 때 특징은 ‘유향’ 그래프, 즉 A → B로는 갈 수 있지만 반대로 B → A로는 가지 않는 ‘방향’ 이 주어지는 그래프라는 것이다. 2. 다익스트라 알고리즘 python 으로 구현하기1. V개의 노드를 방문할 때마다 V개의 인접 노드에 대해서 검사하는 방식→ Prim 알고리즘과 유사한 방식, 시간복잡도가 O(V^2)로 큰편이다.T = int(input()) for tc in range(1, T+1): N, E = map(..

저번에 Prim 알고리즘을 포스팅 하면서, 최소신장트리(MST)에 대해서 작성한 적이 있었다.Kruskal도 Prim과 마찬가지로 MST를 구하는 다른 방법에 해당한다.신장트리: n개의 정점으로 이루어진 무방향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리MST (Minimum Spanning Tree): 신장트리를 구성하는 간선들의 가중치의 합이 최소인 신장 트리1. Kruskal 알고리즘이란?Prim 알고리즘을 간단하게 복습해보자면, 임의의 점을 골라서 시작한다 .key값이 최소인 점을 탐색한다 그 점으로부터 도달할 수 있는 지점에 대한 최소 key값을 갱신한다. → 모든 지점을 방문할 때까지 1. 2.를 반복한다.Prim 알고리즘을 공부하다 보면, 이런 생각이 들 수도 있다.💡그냥 가중..

1. 서로소..?중학교 수학시간에 ‘서로소’ 라는 개념을 들어본 적이 있는가?영어로 (disjoint). 즉, 교집합이 없는 서로 다른 두 집합을 서로소 라고 부른다. 그렇다면, 지금 배우고 있는 python으로 서로소 (이하 ‘상호배타집합’ ) 을 어떻게 구할 수 있을까?2. idea0. 상호배타집합에 필수적인 연산 Make-Set(x) : x가 자신을 가리키도록 초기화 하는 것.Find-Set(x) : x의 대표 요소가 있으면, 대표 요소를 가리키도록 타고 올라 가는 것Union(x,y) : x,y를 하나의 집합으로 합친다 ⇒ 즉, x,y 집합중에 대표자를 새로 정하는 것.1. 연결리스트 먼저 단순하게 ‘연결리스트’로 표현해 볼 수 있을 것이다.2. 트리 다음으로는 트리가 있다. 리스트 배열을 사용하..

신장트리: n개의 정점으로 이루어진 무방향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리MST (Minimum Spanning Tree): 신장트리를 구성하는 간선들의 가중치의 합이 최소인 신장 트리 Prim 알고리즘Kruskal 알고리즘Dijkstra 알고리즘첫 번째로 Prim 알고리즘에 대해서 알아보려고 한다. 1. Prim 알고리즘의 기본 원리하나의 정점에서 연결된 간선들 중에서 하나씩 선택하면서 MST를 만들어 나간다.임의 정점을 하나 선택해서 시작한다.선택한 정점과 인접한 정점들 중 최소 비용의 간선이 존재하는 간선을 선택한다.모든 정점이 선택 될 때까지 1~2를 반복한다. 서로소인 2개의 집합(2 disjoint-sets) 정보를 유지한다.트리 정점들(tree vertices) :..

1. 백트래킹(Backtracking)과 DFS의 차이어떤 노드에서 부터 더이상 가능성이 없는 노드를 따라가지 않음으로 시도의 횟수를 줄인다.⇒ 이 과정을 (Prunning, 가치치기) 라고 부른다.백트래킹의 과정상태 공간 트리의 DFS 를 실시한다.각 노드가 유망한지를 점검한다.만일 노드가 유망하지 않으면, 부모 노드로 돌아가서 검색을 계속한다.백준의 N과 M문제가 대표적임 Uploaded by N2T

1. 퀵 소트?퀵소트는 주어진 배열을 분할하고 - 각각은 정렬한다.분할한다는 점에서 merge sort와 닮아 보이지만, 다른 점은 ‘병합’ 과정이 필요하지 않다는 것이다!!why? ⇒ merge sort는 각각을 분할하고 끝! 이지만, quick sort는 pivot을 중심으로 작은 것은 왼편, 큰것은 오른편에 두는 과정을 거치기 때문이다. 2. pivot 고르기결국 quick sort의 핵심은 pivot 고르기! 라고 할 수 있겠다.시간복잡도는 O(nlogn)O(nlogn)O(nlogn) 이지만, 최악의 경우 O(n2)O(n^2)O(n2) 가 될 수 있다.예를 들어 이미 정렬이 되어있는 리스트에, 리스트의 첫 원소를 pivot으로 설정하면?? → 최악의 경우가 발생하여 문제 풀이시에 시간초과를 경..