열심히 코딩 하숭!

1. 벨만포드 알고리즘 정리 [1] 벨만포드 정의 0. 알고리즘에서... 1) greedy : 선택의 순간에 눈 앞에 놓인 최적의 방안만 쫓아감 2) 분할 정복 : relax 하게 값을 갱신하며 찾아나감 ==> 벨만포드 알고리즘은 방법 2)에 해당 1. 벨만포드(Bellman-ford) 알고리즘 방법 1) 첫번째 정점을 0으로 하고 나머지 정점을 모두 무한대로 설정한다. 2) 인접한 노드로 탐색하며 값을 비교하고, 비교값이 낮다면 갱신한다. 3) 2)의 과정을 모든 노드마다 반복한다. 특징 1) 벨만포드는 다익스트라보다 덜 직관적이다. 2) 음의 가중치가 있어도 문제를 풀 수 있다. (다익스트라는 가중치가 0 or 양수일 때만 사용 가능) 주의 * negative cycle이 있으면 안 된다 (만약 있을..

https://gist.github.com/gowoonsori/a725e29ef1880f0592fe5760f4908c6b * 해당 Red Black Tree 코드를 참고하였고, 내가 원하는 문제 정의 방식대로 코드를 수정하여 완성시켰다. 코드에 대한 결과는 아래의 블로그에 설명과 함께 적어두었다. https://chaesoong2.tistory.com/21 하천을 지키는 습관! "분리수깅" | Red Black Tree | 자료구조실습 기말 과제 1. 문제 소개 >> 중간과제 때 정의했던 문제 https://chaesoong2.tistory.com/15 2022 하천 분리수거 마라톤 대회 '시뮬레이션 프로그램🏃‍' | Red Black Tree | 자료구조실습 중간과 네이버 블로그에 써두었던 chaeso..

* 성신여대 22-2학기 자료구조실습 수업시간에 배운 내용을 토대로 요약 정리한 글입니다 그래프의 개념과 최소비용 알고리즘 세가지에 대해 알아보자 1. 그래프 표현 방법 그래프의 형태 그래프는 방향과 가중치로 구분해볼 수 있다 그리고 그래프의 연결은 인접 행렬과 인접 리스트를 통해 나타낼 수 있다 인접 행렬 방향 그래프의 경우, : 행에 있는 노드(행렬에서 왼쪽 0열에 있는 노드)가 열에 있는 노드를 가리키면 가중치를 표시한다 무방향 그래프의 경우, : 서로 연결되면 가중치를 표시한다 가중치가 없는 그래프의 경우, : 연결되면 1로 표시하고 연결되지 않으면 0으로 표시한다 가중치가 있는 그래프의 경우, : 연결되면 가중치 값을 표시하고 연결되지 않으면 0으로 표시한다 (* 가중치는 0이 아니라고 가정) ..

진짜 도저히 도저히 혼자 시도하다가 안 되겠어서 내가 짠 코드와 가장 유사한 방법으로 구현하신 한 블로거분의 코드를 따라해보았다. [출처] https://kimyunseok.tistory.com/26 하... 난 언제쯤 혼자 코드를 작성해볼 수 있을까 여름 방학 때 백준 더 풀 걸 그랬다잉...~~~ 앞으로 더 노력해라 채숭아~ 암튼! 문제 - DFS와 BFS를 이용해 탐색한 결과를 출력하는 문제였다. - 내가 중요하게 생각한 부분은 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하라는 조건이었다. 이 부분에서 많이 막혔다. 정답 코드 #include #include #include #include using namespace std; int verte..

* 성신여대 22-2학기 자료구조실습 수업시간에 배운 내용을 토대로 요약 정리한 글입니다 0. 그래프 개념 그래프 표기 G = (V, E) - G: 그래프 - V: 정점의 집합 - E: 간선의 집합 Directed 그래프 - 방향이 있는 그래프 - 표기: (1, 2) -> 1이 2를 가리킴 - (1,2) 와 (2,1)은 다름 표기 V = {a, b, c} E = {(a,c), (b,a), (b,c), (c,b)} Undirected 그래프 - 방향이 없는 그래프 - 표기: {1, 2} -> 1과 2가 서로 연결됨 - {1, 2}와 {2, 1}은 같음 표기 - V = {a, b, c ,b} - E = {{a,b}, {a,c}, {b,c}, {c,d}, {a,d}} 1. BFS와 DFS란 무엇인가? BFS ..

네이버 블로그에 써두었던 글인데 티스토리에도 남기면 좋을 것 같아서 올리게 되었다! ​ ​ ​ ​ ​ * 학교에서 수강 중인 22-2 '자료구조 실습' 수업의 중간 프로젝트에 대한 글이다. ​ ​ ​ ​ ​ 0. 프로젝트 개요 ​ 1) 자료구조에 사용될 데이터 수집 : “하천 쓰레기” - 이번 프로젝트의 주제는 "하천 쓰레기" 였다. 휴대폰을 사용해 하천에 떠있는 쓰레기 사진을 찍는다. - 쓰레기 사진은 다음과 같이 csv 파일로 정리한다. ​ 2) 데이터를 사용해 해결할 수 있는 새로운 문제 정의 - 수집한 데이터를 이용해 지금까지 배운 자료구조로 해결해볼 수 있는 문제를 정의한다. ​ ​ 3) 문제 접근 방법 제시 - 자료구조를 이용해 문제를 해결하는 방법에 대해 간단히 제시한다. ​ ​ ​ ​ ​ ..

* 성신여대 22-2학기 자료구조실습 수업시간에 배운 내용을 토대로 요약 정리한 글입니다 1. Data structures augmentation 코딩 1) Rank 구현 Rank(t) : (How many Scheduled) ≤ t - 스케줄링 문제에서 가게에 손님이 왔을 때 지금 물품이 몇 개나 예약 되어 있는지, 재료가 얼마나 더 필요한지 등을 나타낼 때 이를 Rank라고 칭함 - 이후 남은 재료수 : |x| - Rank(t) (여기서 |x|는 총 개수) - 스케줄링 문제의 경우 3주차 과제 글을 참고 | https://chaesoong2.tistory.com/12 구하는 방법 - Array로 구현할 경우) index가 곧 Rank(t)가 됨 - Binary Search Tree의 경우) subtr..

https://leetcode.com/problems/balanced-binary-tree/ Balanced Binary Tree - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제 Given a binary tree, determine if it is height-balanced. For this problem, a height-balanced binary tree is defined as: a binary tree in which the left and ..

* 성신여대 22-2학기 자료구조실습 수업시간에 배운 내용을 토대로 요약 정리한 글입니다 1. 스케줄링 문제에 접근하는 이진 탐색 트리 소개 1) 이진 탐색 트리란? 이진 트리 기반의 탐색 자료구조 key (왼쪽 서브 트리) getRight()); // 재귀함수를 통해 +1을 반복적으로 하여 count } int getLeafCount() { return isEmpty() ? 0 : getLeafCount(root); } int getLeafCount(BinaryNode* node) { if (node == NULL) return 0; if (node->isLeaf()) return 1; // 1을 return 하는 부분이 총 leaf노드의 개수만큼 반복되므로 이를 통해 count를 할 수 있음 else..

https://leetcode.com/problems/insert-into-a-binary-search-tree/ Insert into a Binary Search Tree - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제 You are given the root node of a binary search tree (BST) and a value to insert into the tree. Return the root node of the BST after..