열심히 코딩 하숭!

1. 문제 소개 >> 중간과제 때 정의했던 문제 https://chaesoong2.tistory.com/15 2022 하천 분리수거 마라톤 대회 '시뮬레이션 프로그램🏃‍' | Red Black Tree | 자료구조실습 중간과 네이버 블로그에 써두었던 글인데 티스토리에도 남기면 좋을 것 같아서 올리게 되었다! ​ ​ ​ ​ ​ * 학교에서 수강 중인 22-2 '자료구조 실습' 수업의 중간 프로젝트에 대한 글이다. ​ ​ ​ chaesoong2.tistory.com 간단하게 설명해보자면, 하천 분리수거 마라톤 대회가 개최된다. - 참가자들은 출발 지점부터 도착 지점까지 마라톤을 하며 하천 쓰레기를 줍게 된다. - 마라톤을 하며 하천 쓰레기를 주울 때마다 해당 쓰레기의 분리수거 종류에 해당하는 가산점을 받게 ..

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이 아니라고 가정) ..

* 성신여대 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..

* 성신여대 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..

* 성신여대 22-2학기 자료구조실습 수업시간에 배운 내용을 토대로 요약 정리한 글입니다 1. 우선순위큐 & 힙 1-1. 우선순위큐 (priority queue) 정의 - 우선순위가 가진 요소들을 저장하는 큐 - 우선 순위가 높은 데이터가 먼저 나가게 됨 구현 방법 1) 배열을 이용 (오름차순) - 삽입: O(1) - 삭제: O(n) => 오래 걸림 2) 연결리스트 (내림차순) - 삽입: O(n) - 삭제: O(1) => 오래 걸림 3) 힙을 이용한 구현 - 완전이진트리를 이용한 우선순위큐 구현 - 일종의 반 정렬 상태를 유지 - 삽입: O(logn) - 삭제: O(logn) => 비교적 효율적! 1) 2)보다 훨씬 유리하다 그렇다면 힙에 대해 더 자세히 알아보자! 1-2. 힙 (heap) 정의 - 부모..

학교에서 듣는 자료구조 실습 강의 OT 시간에 자료구조에 대한 개념 review 시간만 있을 거라고 예상했는데 교수님께서 프로젝트의 주제, 관심사 등에 대한 다양한 이야기를 해주시면서 프로젝트를 위한 자세, 시각에 대해 말씀해주셨다. OT를 들으며 내가 이번 여름방학 때 참여했던 2022 교내 소프트웨어 경진대회가 떠올랐다. 프로젝트를 준비하며 2개월 남짓 우리 팀의 주제만 생각하고 집중했는데, 다른 팀들의 발표를 듣고 아이디어를 객관적으로 바라보니 앞으로 내가 어떤 마음가짐과 생각으로 프로젝트에 임해야 할지 많이 생각해볼 수 있었다. 많은 아이디어들 사이에 돋보이는 주제들이 있었는데 많은 사람들이 필요로 하는 기술인지, 정말 필요한지 생각해보고 이를 기술로 잘 구현한 것 같아 놀랐고 매우 동기부여가 되..