[하천 쓰레기 프로젝트] 프로젝트 개요

프로젝트 공지

이 프로젝트는 2022년 2학기 자료구조실습 중간고사 대체 발표 및 기말고사 프로젝트를 위해 진행합니다. 문의사항이 있다면 교수님(yangjunahn@sungshin.ac.kr)께 문의하시기 바랍니다.

프로젝트 주제

하천 쓰레기 처리하기

프로젝트 내용

하천 부유 쓰레기 사진 데이터를 직접 구성하고, 수강생 친구들과 공유하여 본인의 데이터 베이스를 구축합니다.
구축한 데이터 베이스를 바탕으로 원하는 문제를 정의하고, 자료구 조를 이용해 문제를 해결합니다.

프로젝트 목표

수강생들은 직접 데이터를 제작하고, 나만의 데이터를 확보합니다.
다른 사람이 작성한 다양한 데이터를 사용해 봅니다.
문제를 정의하고, 접근해 봅니다.
자료 구조 알고리즘을 실제 문제에 활용해 봅니다.

주의사항

수강생 본인의 안전을 해치는 행위나 어떠한 형태의 불법적인 요소도 발생해서는 안됩니다.

중간고사 대체 발표

발표 자료는 최대 3페이지의 PDF
발표 내용은 다음 두 가지
- 데이터 소개 : 예시, 정리 방법, 업로드 방법 등
- 문제 소개 : 문제 대상, 접근 방법 등
평가 요소 : 데이터의 양과 질, 문제의 질 등

기말고사 프로젝트 발표

발표 자료는 최대 3페이지의 PDF
발표 내용은 다음 두 가지
- 데이터 : 다른 학우들의 데이터를 어떻게 사용하였는지
- 문제 : 문제를 소개하고 해결 방법 설명
평가 요소 : 본인 데이터가 많이 쓰였는지, 많은 데이터를 활용했는지, 문제의 질과 풀이가 창의적이고 적절했는지 등

데이터 설명

사진과 csv 파일 등의 프로젝트용 데이터는 다음의 깃허브 레포지토리에서 확인 가능하다.
dapin1490/water-waste-pictures

모든 사진은 하천에서 발견되는 다양한 쓰레기를 찍은 것이다. 위에 링크된 레포지토리의 water-waste-picture 폴더에서 확인할 수 있으며 총 121장이다.
각 사진에 대한 정보(사진 크기, 쓰레기 종류 등)는 data.csv 파일에 저장되어 있다.
data.csv 파일에는 사진의 파일명, 가로 세로 크기(pixel), 위도 및 경도 좌표(GRS80 Degree), 정해진 쓰레기 분류(일반, 플라스틱, 캔, 유리, 종이) 중 각 사진에 포함된 분류의 유무 표기가 작성되어 있다.
사진 크기는 300*400부터 4032*3024까지 다양하다(원본 사진은 4032*3024 크기이고, 다른 크기는 모두 직접 축소한 것이다).

예시 사진 보기

사진 번호 1, 크기 600*800, 좌표 (37.47, 126.79), 일반 쓰레기와 플라스틱 포함

사진 번호 17, 크기 1200*900, 좌표 (37.47, 126.79), 플라스틱 포함

사진 번호 29, 크기 300*400, 좌표 (37.47, 126.8), 일반 쓰레기 포함

사진 번호 57, 크기 400*300, 좌표 (37.59, 127.02), 종이 포함

사진 번호 105, 크기 4032*3024, 좌표 (37.59, 127.02), 플라스틱 포함

문제 정의

문제에 대해 한 생각 : 하천에 쓰레기가 있으면 치워야 한다. → 누가 치우나? 시민이 치울 수는 없고 공무원들이 치울 것이다. → 공무원은 쓰레기가 있다는 것을 어떻게 아나? 민원을 받는다. → 내가 할 수 있는 것은 무엇인가? 민원 처리 시뮬레이터를 만들자.

요약 : 하천 쓰레기 민원 조회 시스템 만들기

주요 기능

민원 : 여기 쓰레기가 있어요 신고
조회 : 현재 쓰레기 신고가 가장 많은 지역 순으로 정렬, 또는 다른 정렬
민원 처리 : 누적 쓰레기 신고가 많은 분류의 쓰레기부터 순서대로 인력 파견하여, 한 분류의 민원 쓰레기를 모두 해결

구현

필요한 구현 수단 : 쓰레기 종류별 누적 민원 수와 해당 민원들을 저장할 수 있는 크기가 5인 어떠한 객체와, 각 민원들을 저장할 자료구조.

종류별 누적 민원 수와 데이터를 저장할 자료구조 : 누적 민원 수와 해당 민원을 저장할 수 있는 클래스를 만들고, 그 클래스를 이용해 크기가 5인 객체 배열 생성
- 장점 : 배열의 각 요소에 O(1)로 접근 가능. 값의 수정이 용이하다.
- 단점 : 민원을 처리하고자 할 때는 매번 최댓값을 찾아야 한다. 이 프로젝트의 경우 배열 크기가 5이므로 연산 시간은 짧지만 시간복잡도는 O(n)이기 때문에 확장성이 떨어진다.
각 민원을 저장할 자료구조 : 벡터, 맵, 우선순위 큐 등
- 벡터를 쓸 경우 : 삽입/수정/삭제가 쉽다는 것이 장점이지만 따로 정렬하지 않으면 어떤 민원을 조회하고자 할 때 O(n) 만큼 시간이 걸린다는 것이 단점.
  STL find_if() 함수를 사용할 수 있긴 하지만 다른 자료구조를 사용하면 더 나은 처리를 할 수 있지 않을까?
- 맵을 쓸 경우 : 삽입/수정/삭제는 벡터와 유사하게 쉽고 어떤 민원을 조회하고자 할 때는 올바른 키를 사용하면 O(1)이라는 게 장점이고, 올바른 키를 사용할 수 없을 경우 결국엔 O(n)으로 탐색해야 한다는 점 또한 벡터와 마찬가지인 단점이다.
  키는 중복되지 않으면서 사용자가 검색할 수 있어야 하기 때문에 키를 선택하는 것이 중요하다.
- 우선순위 큐를 쓸 경우 : 삽입/삭제는 가능하지만 수정이 어렵다. 탐색은 O(logn)으로 가능하다는 것이 장점이지만 이 또한 키로 사용된 정보에 한해서만 그런 것이고 키가 아닌 정보를 이용해 탐색하고자 할 경우 선형 자료구조보다 복잡하게 탐색해야 한다는 것이 단점이다.
- 정리 : 삽입/수정/삭제의 용이함은 선형 자료구조에서는 비슷하게 쉽고, 비선형 자료구조에서는 수정이 힘들지만 삽입과 삭제는 크게 다르지 않다.
  탐색은 키를 이용해 검색하는 것이 가장 효율적이고, 키가 아닌 값을 이용해 검색하고자 할 경우 별도의 조치가 필요하다. 키를 이용해 검색하는 것은 마찬가지로 키를 사용하는 자료구조에서는 대체로 O(logn) 이하로 효율적이고, 키를 사용하지 않은 자료구조에서는 O(n)이다.
  정렬은 자료구조를 정한 후에 고민해도 늦지 않다. 어떻게든 구현할 방법은 있을 것이다.

어려운 점

조회의 다양성 보장
누적 신고 수 기준 외에도 지역명 가나다순, 최근 신고 순 등 다양한 정렬을 가능하게 하고 싶다. 노드 구현은 어렵지 않다. 그 노드를 사용한 적절한 자료구조의 구현이 전혀 생각나지 않는다.
검색 기능 구현 - 다양한 검색 조건 제공하기 키를 사용하든 사용하지 않든, 키가 아닌 값을 이용한 검색은 O(n)보다 효율적인 연산을 구현하기 어렵다. 키를 이용한 탐색을 효율적으로 만들 방법은 얼마든지 있으나, 그 이외의 모든 경우가 문제다. SQL 데이터베이스를 쓰고 싶지만 그건 자료구조라고 보기 힘들지 않나? SQL을 조잡하게나마 모방할 방법을 찾아보는 것이 나을 것이다. 정 안된다면 키 이외의 값을 이용한 검색은 제공하지 않는 것도 방법이다.

구현 시안

누적 노드 클래스
- int 쓰레기 분류 번호
- int 누적 민원 수
- vector<민원 노드> 해당 민원 벡터
+ 최소한 쓰레기 분류 번호 하나를 인자로 받는 생성자
+ 누적 민원 수 변경 메소드
+ 쓰레기 분류 번호 반환 메소드
+ 누적 민원 수 반환 메소드
+ 민원 벡터 반환 메소드

민원 노드 클래스
- string 사진 파일명
- pair<int, int> 사진 크기
- pair<int, int> 좌표
- int[5] 쓰레기 유무 표시
+ 모든 멤버 변수를 입력받는 생성자
+ 각 멤버 변수별 값을 반환하는 메소드들
+ 쓰레기 유무 배열 변경 메소드

누적 민원 배열 : 크기가 5인 누적 노드 객체 배열. 각 쓰레기별 누적 민원 수와 그 민원을 관리한다. 민원 처리는 한번에 모두 처리하는 것을 전제로 하기 때문에 별도의 탐색 메소드는 갖추지 않았고, 민원을 해결할 때 민원 노드 벡터를 clear한다.
민원 노드 클래스의 몇 가지 정보를 키로 사용하는 맵들 : 파일명, 사진 크기, 좌표 등은 모두 중복 가능한 정보이므로 중복을 허용하는 멀티맵을 사용한다. 탐색 연산(민원 검색)에 사용한다.
모든 민원을 저장하는 하나의 민원 노드 벡터와 STL sort 함수에 전달할 몇 가지 compare 함수 : 각 요소별 민원 전체 정렬 조회를 위해 사용한다. 기본적인 정렬 우선순위는 좌표, 파일명, 사진 크기이며 compare 함수도 좌표 우선 정렬, 파일명 우선 정렬, 사진 크기 우선 정렬 함수로 세 가지 구현한다.

메모리의 절약을 포기하고 조회 및 탐색의 효율을 우선으로 했다. 탐색은 정렬 후 이진 탐색으로 하면 STL sort 함수의 O(nlogn) + O(logn)이므로 O(nlogn)을 보장할 수 있고 삽입은 O(1), 삭제는 검색 후 삭제를 전제로 하므로 탐색과 같다. 같은 데이터를 다른 키로 저장하는 맵을 만듦으로써 조회의 편의성과 다양성을 보완했으나 삽입/삭제/수정을 모든 컨테이너에 동일하게 처리해야 한다는 번거로움이 있다.