봄봄.devlog

💡 Goal - 힙(Heap)에 대한 이해 - 배열을 이용한 힙(Heap) 구현 - 힙(Heap)의 삽입과 삭제 구현 힙은 우선순위 큐를 위해 만들어진 자료구조이다. 우선순위 큐에 대해서 간략히 먼저 알아보자면, 우선순위 큐 : 우선순위의 개념을 큐에 도입한 자료 구조이다. - 데이터들이 우선순위를 가지고 있고 우선순위가 높은 데이터가 먼저 나간다. - 우선순위 큐를 힙으로 구현하면 삽입/삭제의 시간복잡도가 O(logN)으로 배열, 연결리스트로 구현하는 것보다 훨씬 효율적이다. - 우선순위 큐의 이용 사례 시뮬레이션 시스템 네트워크 트래픽 제어 작업 스케줄링 힙(Heap) 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조 여러 값 중, 최대값과 최소값을 빠르게 찾아내도록 만들어진 자료구조..

💡Goal 그래프의 기본 개념 이해 그래프의 종류 구분 그래프의 표현 그래프의 탐색 그래프의 개념 노드(node)와 그 노드를 연결하는 간선(edge)을 하나로 모아놓은 자료 구조 - 즉, 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료 구조이다. ex) 지도, 지하철 노선도의 최단 경로, 전기 회로의 소자들, 도로(교차점과 일방 통행길) 등 그래프의 종류 1. 무방향 그래프(undirected graph) vs 방향 그래프(directed graph) 무방향 그래프(Undirected Graph) 무방향 그래프의 간선은 간선을 통해서 양 방향으로 갈 수 있다. 정점 A와 정점 B를 연결하는 간선은 (A, B)와 같이 정점의 쌍으로 표현한다 (A,B)는 (B,A) 동일 ex) 양방향 통행 도로 방향..

1.개념 모든 경우의 수를 전부 탐색해 보지 않고, 어떤 기준(전략)으로 순서대로 하나씩 선택해 나가는 방식. 최적의 해를 구하는 방식을 그리디 알고리즘이라고 한다. 예를 들어, 5개의 도시를 모두 한번씩만 거쳐서 여행하는 경로 중 가장 짧은 경로를 찾고 싶다고 가정하자. 가능한 모든 조합을 살표보는 방법은 5 x 4 x 3 x 2 x 1 = 120 가지 조합을 살펴봐야 한다. 10개의 도시라면 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 3628800 가지 조합을 살펴봐야 한다. 너무 많다. 그리디 알고리즘은 어떤 적절한 기준(전략)으로 도시를 순서대로 하나씩 선택해 나가는 방식이다. 예를 들어, 임의의 도시를 하나 찍은 다음, 그 도시에서부터 시작하여, 현재 도시에서 출발..