하천을 지키는 습관! "분리수깅" | Red Black Tree | 자료구조실습 기말 과제

1. 문제 소개

 

>> 중간과제 때 정의했던 문제

 

https://chaesoong2.tistory.com/15

2022 하천 분리수거 마라톤 대회 '시뮬레이션 프로그램🏃‍' | Red Black Tree | 자료구조실습 중간과

 

간단하게 설명해보자면, 하천 분리수거 마라톤 대회가 개최된다.

- 참가자들은 출발 지점부터 도착 지점까지 마라톤을 하며 하천 쓰레기를 줍게 된다.

- 마라톤을 하며 하천 쓰레기를 주울 때마다 해당 쓰레기의 분리수거 종류에 해당하는 가산점을 받게 된다.

 

해당 마라톤 대회에서 사용할 '마라톤 시뮬레이션 프로그램'은 

원하는 만큼 시작과 끝 지점을 입력하면,

 

- 입력받은 구간의 거리가 5km ~ 30km이내인지

- 가산점은 몇 점인지

- 가산점의 최대값과 그 때의 경로는 무엇인지

- 시간은 얼마나 걸리는지

 

등을 출력받을 수 있다.

 

 

 

>> 중간과제 때 정의한 문제에 대한 생각

 

중간고사 기간 당시에는 구체적인 문제 해결 방안까지 잘 정의했다고 생각했지만,

동기들의 발표를 듣고 수업도 더 듣게 되면서 나의 프로그램을 개선해야겠다고 생각했다.

그래서 아래와 같은 질문들을 적게 되었고, 이를 개선하여 문제를 다시 정의할 것이다.

 

 

1. 마라톤에서 쓰레기 종류별 가산점을 임의로 설정하는 것이 맞을까?

 

    -> 가산점은 임의로 설정하지 말고, 쓰레기가 분해되는데 걸리는 시간을 기준으로 설정하는 게 좋을 것 같다.

 

2. 프로그램이 실제로 사용될 수 있을까?

 

    -> 하천 쓰레기는 한 번 줍게 되면 사라지므로 실제 대회에서 마라톤 참가자 모두에게 같은 환경 조건이 주어진다고 할 수 없다. 이를 개선하기 위해 "앱" 내부의 알고리즘을 짠다고 생각하고, 계속해서 삽입 삭제 이후의 데이터가 업데이트 되는 방식으로 생각해보면 어떨까?

 

3. 과연 해당 프로그램으로 인해 얻게되는 효과는 무엇인가?

 

    무형 효과 - 개량할 수 없는 수치의 효과

    유형 효과 - 수치화할 수 있는 효과, 이익 (돈)

 

    -> 마라톤 시뮬레이션으로 얻게 되는 유형 효과가 비교적 적다고 생각한다. 지속적으로 사용 가능하고 수익을 얻을 수 있는 "앱"의 형태를 생각해보면 어떨까?

 

 

 

 

다음과 같은 이유를 기반으로 문제를 다시 정의했다.

 

 

 

 

---

 

 

>> 기말과제 때 정의할 문제

 

 

하천 쓰레기 분리수거 어플 "분리수깅"

---

 

 

* 구동이 가능한 어플은 아니고, 앱 디자인만 해보았다.

 

분리수거 + 조깅 => "분리수깅"

(플로깅의 하천 버전)

 

[사용 방법]

1. 앱에는 현재 하천 쓰레기의 위치가 표시된다.

2. 사용자는 시뮬레이션 프로그램을 통해 예상 거리, 예상 시간, 예상 마일리지를 출력받을 수 있다.

- 먼저, 시작, 도착 위치를 입력한다.

- 하천의 특성 상 오른쪽 길, 왼쪽 길이 나누어져 있기 때문에 어느 길로 이동할 것인지도 사용자가 입력한다.

- 이동한 거리와 예상 소요 시간이 계산되고 사용자가 얻게 될 마일리지도 계산된다.

3. 실제로 사용자가 조깅을 하며 쓰레기를 주운 후 사진을 찍어 올리면 마일리지를 받을 수 있다.

- 쓰레기를 주웠으면 해당 하천 쓰레기 데이터도 앱 내부의 데이터 베이스에서 삭제된다.

4. 마일리지가 쌓이면 사용자는 마일리지를 본인이 원하는 쿠폰으로 교체할 수 있다.

 

 

[사용되는 앱 내부의 알고리즘 구조]

예상 거리, 예상 소요 시간, 예상 마일리지를 출력하는 자료구조

 

 

Red Black Tree

 

Red Black Tree에 하천 쓰레기 사진이 가지고 있는 정보 중 사진 이름과 크기를 제외한 모든 정보를 node에 입력할 것인데, 이 때 *위도를 기준*으로 값들을 insert할 것이다. insert 시, 다음과 같은 유의사항을 지켜가며 insert 해야 한다.

​

​

유의사항 1. 한정 거리 계산

​

• 만약 트리에 삽입되어 있는 데이터와의 위도 값 차이가 0.4도 이상이거나 경도 값 차이가 0.5도 이상이면 다른 지역인 것으로 간주하고 insert 하지 않는다. (한번 계산할 때 같은 지역에 있는 노드만 계산하는 것을 원칙으로 한다.)

       ㄴ 위도: 1도 - 약 111 km
       ㄴ 위도 0.4도의 경우 40km 이상의 거리이므로 매우 멀어 같은 지역의 노드라고 판단할 수 없음
       ㄴ 경도: 1도 - 약 88 km (대한민국 기준)
       ㄴ 경도 0.5도의 경우 40km 이상의 거리이므로 매우 멀어 같은 지역의 노드라고 판단할 수 없음

​

​

유의사항 2. insert하려는 노드와 다른 노드의 위도는 동일하지만 경도는 다를 경우

​

• 경도를 기준으로 하여, 새로 insert하려는 노드의 경도 값이 위도가 동일한 노드의 경도 값보다 작을 경우 새 노드를 왼쪽으로 이동시키고, 경도 값이 클 경우 오른쪽으로 이동시킴

​

​

유의사항 3. insert하려는 노드와 다른 노드의 위도, 경도가 모두 동일할 경우

​

• 쓰레기 종류의 여부까지 같다면) insert하지 않는다.

       ㄴ 위도 경도가 동일하고 쓰레기 종류의 여부까지 같을 경우 같은 데이터의 중복이라고 판단한다.

• 쓰레기 종류의 여부가 다르다면) insert 대신, 해당 노드의 데이터 값만 변경한다.

       ㄴ 예를 들어, 일반쓰레기만 1이었던 노드에 접근하여 플라스틱 쓰레기의 여부 또한 1로 변경한다.

 

 

유의사항 4. insert 시, 해당 노드가 지도를 기준으로 하천의 왼쪽에 있는지 오른쪽에 있는지 구분하여 삽입한다.

 

• 현재 과제 수행 시 사용하는 데이터로는 판별할 수 없음  

        ㄴ insert할 때 임의로 random하게 노드에 왼쪽 또는 오른쪽 정보를 넣어준다.

 

 

 

중위 순회

 

참가자가 원하는 출발지와 도착지를 설정하게 되면 search 함수를 사용하여 출발지 노드를 찾는다. 그 후 도착지 노드가 나오기 전까지 중위 순회를 진행하며 노드의 가산점을 합산하고, 위도 경도 값을 활용하여 예상 거리를 계산한다.

​

여기서 중위 순회란 left - mid - right 순으로 방문하는 순회 방법이고 Red Black Tree를 중위 순회하게 될 경우 오름차순 된 키 값을 얻을 수 있다.

​

 

예상 거리 & 시간 계산

 

거리 계산의 경우 경도, 위도 값을 사용할 것이고 소수점 둘째자리까지 반영된 값이므로 정확하지는 않지만 대략적인 거리 계산은 할 수 있을 것으로 기대된다.

중위 순회를 할 때 값을 누적해가는 방식으로 진행할 생각이며, 계산 시 아래와 같은 위도 경도 정보를 이용한다.

 

위도	경도 (우리나라 기준)
1도 - 111.195 km 1분 - 1.853 km 1초 - 30.887m	1도 - 88.804 km 1분 - 1.408 km 1초 - 24.668 m

(참고 | 1분 = 1도/60 등분, 1초 = 1분/60 등분)

​

예상 시간의 경우 성인 기준 평균 1km를 15분만에 걷는 것으로 알려져있기 때문에

예상 거리에 15분을 곱해서 계산할 것이다.

 

​

[규칙]

1. 쓰레기의 분해 시간이 오래 걸릴수록 포인트를 더 높게 한다.

 

 

이미지 출처: https://gscaltexmediahub.com/campaign/reducing-disposable-goods/

 

포인트는 아래의 표와 같다.

 

종류	일반 쓰레기	플라스틱	캔	유리	종이
분해 시간	50년 이상 (정확하지 않아서 추정함)	500년 이상	500년 이상	1000만년 이상	2-5개월
포인트	5	7	7	10	3

 

 

 

2. 쓰레기의 위치를 표시하는 방법

 

- 사실 이 부분은 현실적이지 못 할 수 있음

- 드론을 통해 쓰레기를 감지하는 쪽으로 생각하거나..., 더 효율적인 방안을 고민해봐야 할 것 같음

 

 

3. 쓰레기를 정말 주웠는지 확인하는 방법

 

- 사용자가 쓰레기를 주웠다는 인증을 하며 하천 쓰레기의 사진을 올리면, 당근 마켓의 동네 인증처럼 GPS를 이용한 현위치 파악을 통해, 해당 위치에서 주운 것이 맞는지 확인함 

 

2. 사용한 데이터 소개

원하는 데이터의 특성

위도와 경도가 같을 경우, 같은 곳으로 인지하기 때문에

서로 거리가 가까우면서도 위도 경도 값이 다양한 데이터가 좋을 것 같다고 생각했다.

 

사용한 수강생의 데이터

수강생 20명의 데이터를 사용하였고

지역에 맞게 다음과 같이 나누어 적용해보았다

 

 

data0_sb.txt

지역: 성북천

 

data1_ay.txt

지역: 안양천

 

data2_jp.txt

지역: 정평천 & 성복천

 

data3_cw.txt

지역: 창원천

 

data4_md.txt

지역:묵동천

 

 

데이터 출처 (기말평가 주소 리스트에 나와있는 수강생의 번호를 기재함)

 

1 4 5 6 9 12 13 14 15 18

20 21 24 38 43 48 49 52 58 59

 

총 20명의 수강생 데이터를 사용함

 

 

아래와같이 txt 파일로 정리되었다.

 

 

 

3. 결과 및 효과

 

>> 결과

 

Insert & Show Tree

 

해당 노드 삭제라고 적힌 노드를

아래 과정을 통해 삭제해줌

 

Delete & Show Tree

 

 

Inorder(중위순회) 진행

 

* expect_time의 경우 expect_distance값에 15를 곱하는 것이 맞으나, 

현재  expect_distance값이 너무 작아서 expect_time이 0으로 찍힘

=> 15 대신 150000을 곱함 (결과를 도출하기 위함임.)

(실제 코드에서는 15가 곱해진 값으로 잘 출력됨)

 

 

>> 코드

 

C++을 사용하여 구현해보았다.

Red Black Tree에 대한 기본적인 코드 구조 자체는 아래의 블로그를 참고하였고, 

Red Black Tree (c++) 🎄 · GitHub

 

여기에서 내가 원하는 문제 정의 방식대로 코드를 수정하여 완성시켰다.

 

아래의 블로그에 나의 최종 프로그램 코드를 업로드하였다.

 

https://chaesoong2.tistory.com/19

"분리수깅" C++ 코드 | Red Black Tree | 자료구조실습 기말 과제

 

 

---

 

>> 효과

유형 효과

- 앱에 광고를 삽입하여 쿠폰 비용을 충당하고, 수입을 얻을 수 있다.

- 제로웨이스트 상점과 협력하거나 실제 플로깅 마라톤에 앱을 적용시켜 수익을 얻을 수 있다.

 

무형 효과

- 분리수깅을 통해 환경 오염을 줄일 수 있다.

- 실제 하천 쓰레기에 대한 정보를 실시간으로 알 수 있기 때문에, 하천 쓰레기 문제에 대한 경각심을 일깨울 수 있다.

 

 

 

>> 단점

- 과제에서 사용하는 데이터의 특성 상, 해당 지역의 쓰레기 유무만 알 수 있고 쓰레기의 개수까지는 알 수 없음
- 앱의 현실성 부족 (쓰레기 현위치 파악 / 사용자의 분리수깅 확인)

-> 수강생 데이터가 아닌 이상, 광범위한 지역에서 쓰레기 현위치를 파악하는 것 자체가 쉽지 않음

-> 사용자의 분리수깅을 확인하는 것도, 일단 당근 마켓의 동네인증과 같이 GPS를 이용하는 것으로 생각했는데, 사용자가 정말 쓰레기를 줍고 처리까지 완료했는지는 확인하기 어려움