C++/자료구조5 --- 아래 내용을 포함하는 포트폴리오를 작성하고, 웹페이지 주소를 제출합니다. 1. 벨만포드 알고리즘 정리 2. Leet code 문제 풀이 : 743번 네트워크 딜레이 시간 https://leetcode.com/problems/network-delay-time/ 2.1. 다익스트라를 이용한 풀이 2.2. 벨만포드를 이용한 풀이 3. 백준 문제 풀이: 1916번(옵션) https://www.acmicpc.net/problem/1916 3.1. 다익스트라를 이용한 풀이 3.2. 벨만포드를 이용한 풀이 2022. 12. 4. [자료구조] 그래프와 다익스트라(dijkstra) 알고리즘 본 글은 및 학교 강의를 참고하여 작성되었다. 그래프 표현 방법 그래프는 간단하게 세 종류로 나눌 수 있다. 무방향 그래프, 방향 그래프, 가중치 그래프가 그것이다. 무방향 그래프는 방향이 표시되지 않은 그래프, 즉 양방향으로 갈 수 있는 그래프를 말하고, 방향 그래프는 말그대로 방향이 있는 그래프이다. 마지막으로 가중치 그래프는 두 정점 간의 연결 유무뿐 아니라 연결 강도까지 나타내는 그래프로, 본 글에서 중점적으로 다루게 될 그래프이다. 간단한 예시로 전국 각지의 도시 간 도로를 연결하는 간선을 떠올려볼 수 있다. 이 경우 간선의 가중치는 도로를 이동하는 거리나 비용 등을 나타낼 수 있겠다. 그래프를 표현하는 방법은 크게 두 가지로, 인접행렬 또는 인접리스트를 사용할 수 있지만, 간선마다 다른 가중치.. 2022. 11. 27. [자료구조] DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색) 본 글은 를 참고하여 작성되었다. 그래프 탐색이란 하나의 정점에서 시작하여 모든 정점들을 한 번씩 방문하는 작업이다. DFS(depth first search, 깊이 우선 탐색)와 BFS(breadth first search, 너비 우선 탐색)는 그래프를 탐색하는 가장 고전적인 두 가지 방법이다. 이름에서 알 수 있듯이 깊이 우선 탐색은 한 방향으로 갈 수 있을 때까지 가다가 길이 끝나면 가장 가까운 갈림길로 되돌아와 다른 방향을 다시 탐색하는 방식이고, 너비 우선 탐색은 가장 가까운 정점들을 차례로 방문한 뒤 방문했던 정점들과 가장 가까운 정점들을 또다시 탐색하는 방식이다. 그림으로 한번 알아보자. 위와 같은 그래프에서 A를 시작 정점으로 깊이 우선 탐색을 한다면 순서는 이렇게 된다. A B D H I.. 2022. 11. 6. [자료구조] Big-O 표기법과 이진 탐색 트리(binary search tree) 이번 포스트에서는 이진 탐색 트리에 대해 알아본다. 를 참고하여 작성되었다. leetCode 문제풀이 이진 탐색 트리에 대해 알아보기 전에, 빅오 표기법(Big-O)에 대해 간단히 알아보자. 빅오 표기법은 특정한 알고리즘의 시간 복잡도를 표시하는 방법을 말한다. 조금 쉽게 풀이해보자. 예를 들어 어떤 알고리즘을 연산하기 위해서 T(n) = n2 + n + 1 만큼의 연산이 실행된다고 가정한다. n은 입력의 개수 또는 문제의 크기를 의미하는데, 이를테면 a번을 반복하며 1부터 a까지 곱해주는 for문이 있다고 했을 때 a를 n이라고 생각하면 된다. for(int i=1; i 2022. 9. 25. [자료구조] 힙과 우선순위 큐(heap&priority queue) 이번 포스트에서는 힙과 우선순위 큐에 대하여 알아본다. 에서 많은 부분을 참고하여 정리했다. 우선순위 큐란 무엇일까? 우선 큐는 선입선출의 원칙에 의하여 먼저 들어온 데이터가 먼저 나가는 자료구조라는 사실은 알고 있다. 그렇지만 세상에는 우선순위에 따라 순서를 변경해야 하는 문제들이 있다. 소프트웨어를 예로 들어보자. 내가 핸드폰으로 1시간짜리 플레이리스트를 듣고 있었는데, 도중에 친구에게 전화가 온다. 이때 음악이 끝나지 않았다고 해서 단순하게 순서대로 일을 처리한다면 우리는 전화를 받지 못할 것이다. 따라서 각각의 프로세스에 우선순위를 부여하여 더 중요한 프로세스가 먼저 처리되도록 해야 한다. 이때 우선순위 큐를 사용하는 것이다. 우선순위 큐를 구현하는 방법으로는 배열을 이용하거나 연결리스트를 사용하.. 2022. 9. 21. 이전 1 다음
