C++7 --- 아래 내용을 포함하는 포트폴리오를 작성하고, 웹페이지 주소를 제출합니다. 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. [C++] STL을 이용한 우선순위 큐(priority queue) 저번 포스팅에서는 우선순위 큐와 힙에 대한 내용을 정리해 보았다. 그런데 우선순위 큐를 사용하기 위해서는 코드를 일일이 구현해야 하는 걸까? 그렇지 않다. C++에서는 STL(표준 C++ 라이브러리 Standard Template Library) 을 통해 프로그램에 필요한 자료구조와 알고리즘을 템플릿으로 제공하고 있다. 오늘은 이 STL을 이용한 우선순위 큐에 대해 알아본다. 이에 앞서 STL은 제네릭 알고리즘과 C++을 위한 데이터 구조체들의 첫 번째 라이브러리로서 만들어졌다는 사실을 짚고 넘어가면 좋을 것 같다. priority queue는 기본적으로 아래와 같은 문법으로 선언한다. #include priority_queue queue; 첫 번째 인자는 타입을 지정한다. 두 번째 인자는 컨테이너를 지.. 2022. 9. 18. [Visual Studio] wntdll.pdb 로드되지 않음 이런 오류가 발생했다. 처음 보는 에러라 검색을 해 보니 디버깅할 때 필요한 정보가 저장된 파일이 없어서 발생하는 오류라며 IDE 설정을 만져주던데, 나는 잘 실행되다가 중간에 멈춘 것이라 코드 상의 문제 같았다. 프로그램이 중단되는 곳을 보니 포인터를 delete하는 부분에서 문제가 생긴 듯 했다. 결론부터 말하면 같은 메모리 주소를 두번 delete한 게 문제였다. 멀쩡히 잘 사용하던 클래스 멤버 변수 "index"가 정의되어 있지 않다길래 어딘가 소멸을 잘못 시켰구나 생각했다. 이미 한번 삭제한 주소를 클래스 소멸 과정에서 다시 삭제한 거였다. 포인터를 사용하기 시작하니 대부분의 오류가 메모리 관리에서 발생하는 것 같다. 주의해서 사용하자. 2022. 6. 19. 이전 1 다음
