Come on and look inside my head

이 글은 수중 쓰레기를 해결하는 자료구조 -(중간)의 글과 이어진다.

https://freakingeniousshawn.tistory.com/6

풀고자 하는 문제 소개

요즘 해양 쓰레기 문제가 심각한 상황이며 이를 조금이라도 해결하는 방법으로 요즘 떠오르는것이 바로, '업사이클링'이다.

업사이클링을 주제로, 문제를 설정해 보았다.

문제:  S대학교의 의류학과 김학생이 직접 업사이클 가방을 만들려고 한다. 김학생은 수중 쓰레기 데이터(CVS)를 바탕으로 플라스틱 과 캔 종류의 쓰레기가 가장 많이 발견된 순서로 데이터 정렬을 하려고 한다. 플라스틱이나 캔 항목이 있을경우 가중치 1, 둘 다 존재할 경우 가중치 2, 둘다 존재하지 않으면 가중치 0이다. 따라서 가장 가중치가 높은순으로 정렬하여 손쉽게 업사이클 재료를 수거할수 있게 된다.

사용된 데이터

문제에 가중치가 필요한 항목이 플라스틱과 캔이기 때문에, CSV파일에 플라스틱, 캔이 무조건 존재하는 데이터 파일을 선정하였다. 나의 데이터 파일을 제외한 다른 사람의 데이터 파일들을 취합하였다. 총 5개의 파일을 선정하였고, 이 모든 데이터 파일을 합쳐 약 700개의 행을 가진 데이터 파일을 구축하였다.

데이터 파일을 합치는데 사용한 코드이다.

아래에는 최종으로 합쳐 코딩에 사용된 데이터 파일이다.

문제 풀이

언어는 파이썬으로 풀이하였다. 먼저 csv파일을 읽어오고 우선순위 큐를 구현하였다. 

라인 바이 라인으로 읽어 반복하게 한후, 읽어오는 행에서 우리가 알고 싶은 플라스틱과 캔이 있는 행목 즉, 'plastics'와 'cans'항목을 확인하여 존재할 경우 큐에 우선순위와 해당 데이터의 순서가 되는 숫자를 삽입하였다.

경우는 네가지로 분류하였다.

1. 'plastics'와 'cans'항목 둘다 존재할 경우

-> 우선순위 2와 해당 데이터 순서 삽입

2. 'plastics' 항목만존재할 경우

-> 우선순위 1와 해당 데이터 순서 삽입

3. 'cans'항목만 존재할 경우

-> 우선순위 1와 해당 데이터 순서 삽입

4. 'plastics'와 'cans'항목 둘다 존재하지 않을 경우

-> 우선순위 0과 해당 데이터 순서 삽입

*중요* : 여기서 삽입된 우선순위는 가중치를 의미한다.

따라서 가중치 크기 순으로 정렬을 하여 프린트한다.

이를 구현한 코드는 아래와 같다.

결과

위와 같이 잘 분류 되었다.

이문제를 해결하므로써 김학생은 업사이클 가방을 만들기 더 수월해질 것이다. 이와 같은 문제를 잘 이용하면 다음과 같은 효과를 기대할 수있다.

앞으로 기대되는 효과

1. 플라스틱과 캔이 아니더라도 다른 항목들을 분류할 수 있으며, 이를 활용해 꼭 가방 뿐이 아닌 다양한 업사이클 제품을 만드는데 도움을 줄수 있음.

2. 말그대로 업사이클 제품의 재료를 구하는 목적으로 설정된 문제이며, 이를 개인이 아닌 업사이클 브랜드들이 이용한다면, 매년 나오는 해양 쓰레기의 양을 대폭 줄일 수 있을 것임. 

3. 업사이클 제품을 만들기 위해 일일히 수집하는 고생을 덜었으므로 업사이클 제품을 만드는 과정을 크게 단축시켜 효율을 높였고, 따라서 패션 산업을 비롯한 여러 분야에서 업사이클 활성화를  도모할 수 있게될 것임.

1. 벨만포드 알고리즘(Bellman-Ford Algorithm)이란?

벨만포드 알고리즘(Bellman-Ford Algorithm)은 한 노드에서 다른 노드까지의 최단 거리를 구하는 알고리즘이다. 가장 큰 특징은 선의 가중치가 음수일 때도 최단 거리를 구할 수 있다는 점이다. 따라서 모든 간선의 비용이 양수 일때는 다익스트라 알고리즘(Dijkstra Algorithm), 하나라도 음수인 비용이 있다면 벨만포드 알고리즘을 사용하는 것이 좋다.

그렇다면 다익스트라 알고리즘과 벨만포드 알고리즘에는 각가 어떤 특징이 있을까? 이는 아래와 같이 정리할 수 있다.

[다익스트라 알고리즘(Dijkstra Algorithm)]
1. 매번 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하여 한 단계씩 최단 거리를 구해나간다.
2. 음수 간선이 없다면 최적의 해를 찾을 수 있다. (음수 간선이 있을 때는 최적의 해를 찾을 수 X)
3. 시간 복잡도가 빠르다. (OElogV) --> 개선된 다익스트라 알고리즘 (우선순위 큐 사용)

[벨만포드 알고리즘(Bellman-Ford Algorithm)]
1. (정점 - 1)번의 매 단계마다 모든 간선을 전부 확인하면서 모든 노드간의 최단 거리를 구해나간다. (<-->다익스트라와 차이점은 매 반복마다 모든 간선을 확인한다는 것이다. 다익스트라는 방문하지 않은 노드 중에서 최단 거리가 가장 가까운 노드만을 방문한다.)
2. 다익스트라 알고리즘에서의 최적의 해를 항상 포함하게 된다.
3. 음수 간선이 있어도 최적의 해를 찾을 수 있다. (음수 간선의 순환을 감지할 수 있기 때문이다.)
4. 시간 복잡도가 느리다. O(VE)

2. Leet code 문제 풀이 : 743번 네트워크 딜레이 시간

문제 원본 링크:
https://leetcode.com/problems/network-delay-time/

(1) 다익스트라 알고리즘(Dijkstra Algorithm)을 이용한 풀이
먼저 다익스트라 알고리즘을 활용하여 푼 코드이다.
간단히 요약하면 아래와 같다.

• Q를 heapq로 구현하여 최소 힙을 빼서 dist를 구해나간다.
• 만약 dist에 node가 이미 존재시, dist에 들어있는 것이 최소 시간이므로 건들지 말고 넘어간다.
• 이렇게 dist를 구하고 나면 문제 특성상 dist에 모든 정점의 소요 시간이 들어있어야 한다.
• len(dist) == n으로 확인을 해주고, 그 후 최댓값을 리턴한다.

(2) 벨만포드 알고리즘(Bellman-Ford Algorithm)를 이용한 풀이
코드는 다음과 같으며 확인하면 위에 설명한 다익스트라 알고리즘을 이용한 풀이 코드보다 훨씬 간결하고 깔끔한 풀이가 가능함을 확인할 수 있다.

1. C++ 로 구현한 기본 그래프
간단한 그래프 구현을 해보자. 정점은 A,B,C,D로 설정하고 간선은 (A,B),(A,D),(B,D),(B,C),(C,D)로 이루어진 그래프가 있다.

위 그래프를 코드로 구현하면 아래와 같다.
(1)알고리즘 설정

(2) 알고리즘 구현

(3)결과창

2. 다익스트라 알고리즘을 설명과 코드를 구현
(1) 다익스트라(Dijkstra)알고리즘이란?
시작점과 도착점을 설정해서 최단거리를 구하는 알고리즘이다. 정점과 정점 간에는 간선이 있는데, 이 간선에 있는 가중치를 고려하여 결론을 내는 알고리즘 이기에 매우 효율적이라고 볼수 있다. 단점은 음의 가중치는 포함할수 없다는 것이다. 하지만, 우리 실제 세계에서는 모든 경로의 가중치에 음의 수치는 없기 때문에 실제로 사용하기에 아주 적합한 알고리즘이다.

작동 알고리즘은 다음과 같다.
1. 시작 정점을 정한다.
2. 시작 정점을 기준으로 각노드의 최소 비용을 저장한다.
3. 방문하지 않은 정점들 중 가장 비용이 적은 정점을 선택한다.
4. 해당 점점을 거쳐 특정한 정점으로 가는 경우를 고려해서 최소 비용을 갱신한다.
5. 3-4번을 반복하며 도착노드까지 도착한다.

위의 다익스트라 알고리즘으로 구현한 코드는 아래와 같다.

(2) 다익스트라(Dijkstra)알고리즘 코드 구현

1.DFS(Depth-First Search)란?

DFS(Depth-First Search)는 그래프의 가장 기본적인 연산인 그래프탐색을 하는 알고리즘이다. DFS(Depth-First Search)는 이름 그대로, 깊이 우선 탐색이며, 대략적인 DFS의 탐색 과정은 이러하다.

1.한 방향으로 갈 수 있을 때까지 간다.
2.더 이상 갈 수 없게 되면 가장 가까운 갈림길로 돌아간다.
3. 돌아온 갈림길부터 다른 방향으로 다시 탐색 진행한다.
(다시 되돌아 가기 위해 스택 필요)

이러한 메커니즘을 간단한 그래프 예시와 함께 확인해 보자.

2.BFS(Breadth-First Search)란?

BFS(Breadth-First Search)는 앞서 설명한 DFS(Depth-First Search)와 마찬가지로 그래프를 탐색하는 알고리즘이다.
단, 깊이 우선 탐색인 DFS(Depth-First Search)와 달리 BFS(Breadth-First Search)는 너비 우선 탐색이라는 점에서 DFS와는 차이가 있다. 대략적인 BFS의 탐색 과정은 이러하다.

1.시작 정점으로부터 가까운 정점을 먼저 방문한다.
2. 그 후, 멀리 떨어져 있는 정점을 나중에 방문한다.
(너비를 측정하기 용이한 큐를 사용하여 구현)

이러한 메커니즘을 간단한 그래프 예시와 함께 확인해 보자.

3. C++를 이용해 DFS, BFS 코드 구현해보기

앞서 설명했던 DFS와 BFS를 C++ 코드로 구현하면 아래와 같다. 간단한 설명은 주석으로 달아 놓았다.

1.DFS(Depth-First Search)의 코드 구현

2. BFS(Breadth-First Search)의 코드 구현

이 글은 업사이클로 수중 쓰레기 절감하기-(기말)과 이어집니다.

이어지는 글 링크: https://freakingeniousshawn.tistory.com/13

데이터 소개

사진은 화면에 보이는것과 같이 한장당 1개 이상의 쓰레기가 최소한 화면의 10분의 1 이상의 크기로 나오도록 사진을 찍었다. 주로 반포천과 반포한강공원에서 찍었다.

정리방법은 아래와 같이 csv 파일 형태로, 쓰레기 품목은 일반쓰레기, 플라스틱, 캔, 종이, 유리로 나누어 정리하였다.

풀고자 하는 문제 소개

요즘 해양 쓰레기 문제가 심각한 상황이며 이를 조금이라도 해결하는 방법으로 요즘 떠오르는것이 바로, '업사이클링'이다.

업사이클링을 주제로, 문제를 설정해 보았다.

문제:  S대학교의 의류학과 김학생이 직접 업사이클 가방을 만들려고 한다. 김학생은 수중 쓰레기 데이터(CVS)를 바탕으로 플라스틱 과 캔 종류의 쓰레기가 가장 많이 발견된 순서로 데이터 정렬을 하려고 한다. 단, 이 학생이 살고 있는 집의 위치보다 일정 거리가 멀면 우선순위에서 밀리는 형태로 정렬을 하려고 한다.

접근방법: 먼저 데이터파일을 검사하여 ‘플라스틱 ‘항목이나 ‘캔’항목에 1이 존재할 경우 각 항목당 가중치 1씩 더한다. 그후, 가중치가 가장 높은 순서대로 데이터를 배열한다. 단, 학생의 거주지 좌표를 기준으로, 플러스 마이너스 0.05이상 차이 날 경우 맨 뒤로 보낸다.

- 데이터 공유 방법

<사진파일>

구글 드라이브에 전체 공개로 파일을 업로드 하였다. 직접 찍은 사진 파일들을 한개의 폴더에 모아 놓았다.아래의 링크를 타고 들어가 다운로드를 받으면 zip파일 형태로 다운로드가 되고, 사진 파일들을 확인할 수 있다.다.https://drive.google.com/drive/folders/1STLytURZHq2JoAuQ75RW8lPZrqbRuY8w?usp=sharing 

<CVS파일>

수중 쓰레기 사진데이터를 정리한 CSV파일이다. 아래에 구글 드라이브 링크로 들어가 확인 및 다운로드가 가능하다.

https://drive.google.com/drive/folders/1pQZi_PjQoMHMeyM_YbT59-AVToAQNvts?usp=sharing 

1. AVL tree란?
AVL tree를 설명하기에 앞서, BST(이진탐색트리)에 대해 알고 있어야 하는데,이는 이전에 내가 작성 했던 글을 참고하면 BST에 대해 간단히 알수 있다.

이 블로그의 이전글 링크 :
이진탐색트리(BST) +(LeetCode 98, 99, 700, 701 풀이) - https://freakingeniousshawn.tistory.com/m/4

BST(이진탐색트리)는 큰 문제점이 있다. 바로 트리가 치우친 모양,바로 한쪽으로 노드가 쏠린 형태가 될 수가 있다. 한 쪽으로 지나치게 치우친 트리는 가장 효율적인 탐색 트리를 추구하는 자료구조의 궁극적 목표와는 먼, 매우 비효율적인 형태이다. 이를 방지하기 위해서는 균형잡힌 모양의 트리가 가장 이상적인데, 이러한 트리를 우리는 Balanced binary tree라고 한다.

Balanced binary tree의 구조를 가지기 위해서 쓰이는 유용한 자료구조가 바로 AVL tree다.

AVL tree는 몇가지 특징이 있는데, 아래와 같다.

1. 이진 탐색 트리의 속성을 가진다.
2. 왼쪽, 오른쪽 서브 트리의 높이 차이가 최대 1이다.
3. 높이 차이가 1보다 커지면 회전(rotation)을 통해 균형을 맞춰 높이 차이를 줄인다.
4. 삽입, 검색, 삭제의 시간 복잡도가 O(log n)이다.

군형이 무너진 트리는 크게 LL,RR,LR,RL의 경우로,
LL(left left)일때는 우회전 적용, RR(right right)일때는 좌회전 적용, LR(left right)일때는 LL의 형태로 만들고 LL해법으로 풀고 RL(right left)일때는 LR과 같은 메커니즘이지만 반대방향으로 해결하면 된다.

AVL Tree를 더 전문적으로 알아보고 싶다면 아래 링크들을 참고하자.
https://www.geeksforgeeks.org/avl-tree-set-1-insertion/

https://www.geeksforgeeks.org/avl-tree-set-2-deletion/

2. AVL tree 코딩
앞서 AVL tree에 대해 열심히 설명했으니 직접 프로그래밍 해보자.

Rank 구현

AVL tree 구현

3. Leet code 110번 문제 풀이

문제 원본 링크:
https://leetcode.com/problems/balanced-binary-tree/

문제 설명:
이 문제의 요점을 간단하게 말하면, 해당 트리가 Balanced Binary tree 인지 그냥 Binary Tree 인지 검사하는 문제이다.
검사하려는 해당 트리의 모든 노드들은 Balanced Binary tree 여야 하니까 차례대로 내려가면서 검사하면 된다.
isBalanced()로 해당 노드가 Balanced Binary tree 인지 판별하고, height()에서 노드 깊이 구하고, 이를 비교해서 Left로 보낼지 Right로 보낼지 결정한다.

위 의견들을 종합해서 구현하면 아래 코드와 같다.