• Day2에서 누구나 방을 만들고 링크를 공유할 수 있게 만들었다.
• 기능적으로는 다 된 셈인데, 막상 써보면 아쉬운 부분이 한둘이 아니었다.
  • 메뉴 정리해서 주문할 때 일일이 타이핑해야 한다. 복사 기능이 있으면 좋겠는데?
  • 카카오톡으로 링크 보내면 미리보기가 안 뜬다. 밋밋한 URL만 덩그러니.
  • 밤에 쓰면 눈이 부시다. 다크모드가 없으니까.
  • 옆에 있는 사람한테 링크를 공유하려면? 카톡을 보내야 하나?
  • 누군가 악의적으로 투표를 도배하면? 과금 폭탄 맞으면?
• 그래서 Day3의 목표는 "실제로 쓸 때 불편한 점을 하나씩 잡아내는 것"이었다.

큰 흐름

1. 주문 요약 복사

• 투표가 끝나면 결국 주문을 해야 한다. 그때 "짜장 3개, 짬뽕 2개..." 이걸 일일이 적고 있으면 귀찮다.
• 📋 주문 복사 버튼을 누르면 팝업이 뜨고, 두 가지 형식 중 하나를 고를 수 있다.
  • 메뉴만 복사 : 짜장면 3 / 짬뽕 2
  • 사람 포함 복사 : 짜장면 3 — 철수, 영희, 민수 / 짬뽕 2 — 지원, 하늘
• 복사하면 하단에 토스트 알림이 잠깐 뜨고 사라진다.
• 검색 키워드 : navigator.clipboard.writeText, toast notification

2. 카카오톡 미리보기 (OG 태그)

• 카카오톡에 링크를 보내면 제목, 설명, 이미지가 미리보기로 뜬다.
• index.html에 Open Graph 메타 태그를 추가했다.
• og:title, og:description, og:image 이 세 개가 핵심이다.
• Twitter Card 메타 태그도 같이 넣어서 트위터에서도 미리보기가 나온다.
• 검색 키워드 : og:title, og:description, og:image, twitter:card

3. 만료 시간 안내

• Day2에서 24시간 자동 만료를 넣었는데, 사용자 입장에서는 "이 방 언제 사라지지?"를 모른다.
• 페이지 최하단에 남은 시간을 작게 표시했다.
• 1분마다 자동 갱신되고, 남은 시간에 따라 색상이 바뀐다.
  • 6시간 이상 → 회색 (안심)
  • 1~6시간 → 주황 (주의)
  • 1시간 미만 → 빨강 (긴급)
• 투표나 사진 업로드 같은 활동을 하면 24시간이 리셋되면서 안내도 갱신된다.
• 검색 키워드 : setInterval, Date.now, 조건부 CSS 클래스

4. SEO (검색엔진 최적화)

• 구글이나 네이버에서 검색하면 이 사이트가 나오게 하고 싶었다.
• 한 작업들 :
  • sitemap.xml 생성 → 검색엔진에 페이지 구조 알려주기
  • robots.txt 수정 → 크롤러 허용 범위 설정
  • index.html 메타 태그 보강 → 제목, 설명, 키워드
  • Google Search Console 등록 → google-site-verification 메타 태그
  • 네이버 서치어드바이저 등록 → naver-site-verification 메타 태그
• 사이트 제목을 "vote-eat | 메뉴 수합(아아 하나 추가요!)"로 정했다.
• 검색 키워드 : sitemap.xml, robots.txt, Google Search Console, 네이버 서치어드바이저

5. 악의적 트래픽 방어

• Firebase는 무료 한도를 넘으면 과금된다. 누군가 자동화 도구로 투표를 수천 번 날리면?
• 두 가지 레이어로 막았다.

서버단 : Firestore 보안 규칙

• 그룹 이름 50자 제한
• 투표 항목 이름 50자 제한
• 투표자 배열 100명 제한
• 데이터 타입 검증 (문자열 필수 등)

클라이언트단 : 쿨다운

• 투표 : 2초
• 빠른 참여 : 2초
• 이미지 업로드 : 5초 + 방당 최대 20장
• 방 생성 : 3초
• useRef로 마지막 액션 시각을 추적하고, 쿨다운 중에는 버튼이 비활성화된다.
• 검색 키워드 : Firestore Security Rules, rate limiting, useRef cooldown

6. 다크모드

• 밤에 쓰면 눈이 부시다는 건 사실 처음부터 알고 있었다. 미루다가 드디어 넣었다.
• 구현 방식 :
  • CSS 변수(--bg-color, --text-color 등)로 전체 색상을 관리
  • [data-theme="dark"] 선택자로 다크모드 색상 오버라이드
  • themeUtils.js에서 테마 상태를 관리 (localStorage 저장 + 시스템 설정 감지)
  • 헤더에 ☀️/🌙 토글 버튼
• 시스템 다크모드를 감지해서 처음 접속 시 자동 적용되고, 수동으로 바꾸면 그 선택을 기억한다.
• 카드, 입력 필드, 팝업, 토글 스위치 등 모든 UI 요소에 다크모드를 적용했다. 이게 생각보다 손이 많이 갔다.
• 검색 키워드 : CSS custom properties, data-theme, prefers-color-scheme, localStorage

7. 반응형 UI 개선

• 모바일에서 쓰는 사람이 대부분인데, 작은 화면에서 깨지는 부분들이 있었다.
• 480px, 360px 브레이크포인트를 추가하고 세부 조정했다.
  • 투표 항목 헤더가 한 줄에 안 들어가면 자연스럽게 줄바꿈
  • 메뉴 이름이 너무 길면 말줄임(...)
  • 가격 행, 배지, 버튼 크기 축소
  • 터치 타겟 확대 (손가락으로 누르기 편하게)
• 검색 키워드 : media query, flex-wrap, text-overflow ellipsis, min-width 44px

8. 공유 팝업 (QR 코드 + 네이티브 공유)

• Day2에서 만든 🔗 공유 버튼은 링크 복사 한 가지뿐이었다.
• 근데 옆에 있는 사람한테 공유하려면? 카톡을 보내야 하나? QR이면 바로 스캔하면 되는데.
• 기존 버튼을 공유 팝업으로 교체했다. 누르면 3가지 옵션이 나온다.
  • 🔗 링크 복사 — 클립보드에 복사
  • ⊞ QR 코드 — 화면에 QR 표시, 옆 사람이 카메라로 스캔
  • ↗ 다른 앱으로 공유 — 카카오톡, 메시지, AirDrop 등 (모바일에서만 표시)
• QR 코드는 qrcode.react 라이브러리로 SVG 렌더링. 다크모드에서도 잘 보이도록 색상 분기 처리.
• "다른 앱으로 공유"는 Web Share API를 사용하는데, 이건 모바일 브라우저에서만 지원한다. PC에서는 자동으로 숨겨진다.
• 검색 키워드 : qrcode.react, QRCodeSVG, navigator.share, Web Share API

9. 관리자 페이지

• Firebase 과금이 걱정되면 서비스를 통째로 꺼버릴 수 있어야 한다.
• /admin?key=비밀키 URL로 접근하는 관리자 페이지를 만들었다.
• 두 가지 토글 스위치 :
  • 🌐 전체 서비스 on/off — 끄면 방 생성, 투표, 참여 모두 차단
  • 📷 사진 업로드 on/off — 끄면 업로드만 차단 (Storage 비용 절감)
• Firestore의 config/service 문서에 설정값을 저장하고, 앱 로드 시 1회 읽기.
• 끈 상태에서 사용자에게는 커스텀 점검 안내 메시지가 표시된다. 메시지도 관리자 페이지에서 수정 가능.
• 관리자 키는 .env에 저장해서 코드에 노출되지 않게 했다.
• 검색 키워드 : Firestore config document, admin panel, feature toggle, environment variable

조금 헤맸던 부분들

1. 다크모드 CSS 변수 지옥

• 처음에는 "색상만 바꾸면 되지" 했는데, 실제로는 카드, 입력 필드, 팝업, 모달, 프로그레스 바, 캐러셀 화살표 등등 전부 개별적으로 색상을 잡아줘야 했다.
• CSS 변수를 50개 넘게 만들었다. --card-bg, --border-color, --input-bg, --carousel-arrow-bg ...
• 한번 체계를 잡아놓으니 이후에 추가되는 컴포넌트도 변수만 쓰면 자동으로 다크모드가 적용되어서, 투자할 만했다.

2. Web Share API의 브라우저 호환성

• navigator.share()는 모바일 Safari, Chrome에서는 잘 동작하는데 데스크톱에서는 대부분 지원하지 않는다.
• 그래서 typeof navigator.share === "function"으로 체크해서, 지원하지 않는 환경에서는 해당 버튼을 아예 숨겼다.
• 사용자가 공유를 취소하면 AbortError가 발생하는데, 이건 에러가 아니니까 무시하도록 처리했다.

3. QR 코드 다크모드 대응

• QR 코드의 기본 배경은 흰색, 패턴은 검정이다. 다크모드에서 이러면 네모난 흰색 덩어리가 떠 있는 것처럼 보인다.
• bgColor="transparent"로 배경을 투명하게 하고, fgColor를 테마에 따라 분기시켰다.
  • 라이트모드 : #1f2937 (어두운 회색)
  • 다크모드 : #f1f5f9 (밝은 회색)

오늘 추가된 기능 정리

현재까지의 전체 기능

기술 스택

결과

👉 https://vote-eat.web.app

• Day1은 "돌아가게", Day2는 "남한테 보여줄 수 있게", Day3는 "편하게 쓸 수 있게" 다듬었다.
• 기능 자체보다는 쓰는 사람 입장에서의 편의성에 집중했다. 주문 복사, 다크모드, QR 공유 같은 건 없어도 되지만 있으면 확실히 다르다.
• 관리자 페이지까지 넣으니 과금 걱정 없이 서비스를 열어둘 수 있게 됐다. 위험하면 토글 하나로 끄면 되니까.

• Day1에서 기본 기능은 다 만들었다. 투표, 사진, 가격, 그룹까지.
• 그런데 이걸 지인이 아닌 다른 사람들도 쓸 수 있게 하려면 문제가 있었다.
  • 홈에 들어가면 다른 사람이 만든 투표방이 다 보인다. 내 방만 보고 싶은데?
  • 누군가 만든 방에 아무나 들어가서 장난칠 수도 있고, 오래된 데이터가 계속 쌓인다.
  • 사진을 원본 그대로 올리면 용량이 어마어마하다. 누가 5MB짜리 사진 10장 올리면...
• 그래서 오늘의 목표는 "모르는 사람도 편하게 쓸 수 있는 구조"로 바꾸는 것이었다.

큰 흐름

1. 이미지 자동 압축

• 사용자가 사진을 올리면 업로드 전에 자동으로 압축된다.
• Canvas API를 이용해서 최대 1920×1920px로 리사이즈하고, JPEG 품질 70%로 변환한다.
• 500KB 이하의 작은 파일은 굳이 압축하지 않고 그대로 올린다.
• 35MB짜리 사진이 300500KB 수준으로 줄어드니까 Storage 용량이 확 줄었다.
• 검색 키워드 : Canvas API, toBlob, image resize, JPEG compression

2. 공개 서비스 모드 전환

• 기존에는 홈에 들어가면 Firestore에서 전체 그룹 목록을 가져와서 보여줬다.
• 이제는 그걸 없애고, 두 가지만 보여준다.
  • "🗳️ 새 투표 만들기" 버튼 → 방 이름 입력하면 바로 생성
  • "📋 내 투표방" 목록 → 내가 만들거나 방문한 방만 표시
• "내 투표방"은 Firestore가 아니라 localStorage에 저장한다. 최대 20개까지.
• 방을 만들면 자동 저장되고, 공유 링크로 방문해도 자동 저장된다.
• 검색 키워드 : localStorage, JSON.parse/stringify

3. 링크 공유

• 투표 페이지 헤더에 🔗 공유 버튼을 추가했다.
• 누르면 현재 방 URL이 클립보드에 복사된다.
• 친구한테 카톡으로 링크 보내면 같은 방에서 바로 투표 가능.
• 이게 핵심이다. 방을 만들고 → 링크를 공유하고 → 각자 투표하고 → 끝.
• 검색 키워드 : navigator.clipboard.writeText, window.location.href

4. 자동 만료 (24시간)

• 방을 만들면 lastUsedAt 타임스탬프가 찍힌다.
• 투표하거나, 사진 올리거나, 방에 접속할 때마다 이 시각이 갱신된다.
• 누군가 방에 들어왔을 때 마지막 활동으로부터 24시간이 지났으면?
  • 투표 데이터, 사진, 그룹 문서를 전부 자동 삭제하고 홈으로 보낸다.
• 서버(Cloud Functions) 없이 클라이언트 코드만으로 구현했다.
• 검색 키워드 : Firestore serverTimestamp, Timestamp.toMillis, deleteDoc, deleteObject

조금 헤맸던 부분들

1. localStorage와 Firestore의 싱크

• "내 투표방" 목록은 localStorage에 저장하는데, 방이 만료되어 Firestore에서 삭제되면 localStorage에는 남아있다.
• 그래서 방에 접속했을 때 만료 확인 후 localStorage에서도 같이 지워주는 처리를 추가했다.
• 클라이언트 저장소와 서버 데이터의 정합성을 맞추는 게 은근히 신경 쓸 부분이 많다.

2. 만료 체크 타이밍

• 자동 만료를 서버 없이 구현하려면 "누군가 방에 접속하는 시점"에서만 체크할 수 있다.
• 아무도 안 들어오면 데이터는 24시간이 지나도 Firestore에 남아있긴 하다.
• 하지만 다음에 누군가 접속하면 그때 삭제되니까, 실질적으로는 문제없다.
• 완벽하게 하려면 Cloud Functions의 스케줄러를 써야 하는데, 무료 플랜에서는 못 쓰니까 이 정도면 충분하다고 판단했다.

3. 이미지 압축과 원본 보존 사이

• 처음에는 모든 이미지를 무조건 압축했는데, 이미 작은 파일까지 압축하면 오히려 용량이 커지는 경우가 있었다.
• 그래서 500KB 이하는 압축을 건너뛰도록 조건을 추가했다.
• Canvas API로 JPEG 변환하면 PNG의 투명 배경이 사라지는 점도 알아두면 좋다. 메뉴판 사진은 대부분 JPG라 상관없었지만.

오늘 추가된 기능 정리

현재까지의 전체 기능

기술 스택 (변경 없음)

결과

👉 https://vote-eat.web.app

• 이제 링크를 공유하면 누구나 방을 만들고 투표할 수 있다.
• 방은 24시간 후 자동으로 사라지니까 데이터가 쌓이는 걱정도 없다.
• Day1에서는 "일단 돌아가게" 만들었고, Day2에서는 "남한테 보여줄 수 있게" 다듬었다.
• 다음에 하고 싶은 것들 : 여러 그룹 결과 합산 뷰, 투표 마감 기능, 결과 차트 시각화, 1인 1투표 제한.
• 텍스트*

• 매일 반복되는 점심 메뉴 정하기
  • 두 테이블 이상 되는 단체가 되면 "ㅇㅇ님은 뭐 드세요?"로 시작해서 카톡이 수십 개씩 쌓인다.
  • 누가 뭘 골랐는지 정리하려면 스크롤을 한참 올려야 하고, 중간에 딴 얘기 끼면 더 혼란스럽다.
  • 결국 한 사람이 "정리해줄게"하고 엑셀이나 메모장에 수동으로 옮기는 상황이 반복된다.
  • 주문하러 갔다가 "ㅇㅇ 메뉴는 오늘 안된대요." 하면 후...
• 기존 투표 서비스의 아쉬움
  • 일반적인 투표 사이트는 후보가 미리 정해져있고 그 중에서만 고를 수 있다.
  • 그런데 우리는 후보 자체를 사용자가 자유롭게 추가할 수 있어야 했다.
  • 그리고 실시간으로 "지금 누가 뭘 골랐는지" 바로 보이면 좋겠다고 생각했다.
• 그래서 직접 만들기로
  • React와 Firebase를 사용하면 실시간 웹앱을 빠르게 만들 수 있다고 해서 도전해봤다.
  • Firebase는 써본 적 없었는데, Firestore의 실시간 리스너라는 기능이 딱 내가 원하는 거였다.

큰 흐름

• React랑 Firebase 세팅 등 세부적인 것은 검색하거나 AI에게 물으면 금방 나온다.

1. 실시간 투표

• 사용자가 이름과 메뉴를 입력하면 Firestore에 저장되고, 다른 사용자 화면에도 즉시 반영된다.
• 같은 메뉴를 고른 사람이 있으면 카운트가 올라가고, 새 메뉴면 목록에 추가된다.
• 검색 키워드 : React, Firebase Firestore, onSnapshot, increment, arrayUnion

2. 메뉴 사진 & 가격

• 메뉴판 사진을 올려서 다같이 보면서 고를 수 있다. 캐러셀로 넘겨보기 가능.
• 각 메뉴에 가격을 입력하면 가격 × 인원수로 총 예상 금액을 자동 계산해준다.
• 검색 키워드 : Firebase Storage, CSS scroll-snap, getDownloadURL

3. 그룹 기능

• 여러 팀이 동시에 독립적으로 사용할 수 있도록 그룹(방) 분리.
• 그룹이 1개면 기존처럼 바로 투표 화면, 2개 이상이면 선택 화면이 뜬다.
• 검색 키워드 : react-router-dom, useParams, Firestore subcollection

4. 배포

• Firebase Hosting으로 무료 배포. 빌드하고 firebase deploy 한 줄이면 끝.
• 검색 키워드 : Firebase Hosting, firebase-tools CLI

조금 헤맸던 부분들

1. Firebase 초기 설정

• Firebase 라이브러리를 설치하고 config 파일을 만들었는데, 투표를 눌러도 아무 반응이 없었다.
• 알고 보니 Firebase 콘솔에서 Firestore Database를 아직 생성을 안 했던 것이다.
• 생성 후에도 Missing or insufficient permissions 에러가 났는데, 보안 규칙을 테스트 모드(allow read, write: if true)로 바꾸니 해결됐다.
• Firebase는 콘솔에서 해줘야 할 설정이 꽤 있으니, 코드만 짜고 끝이 아니라는 걸 배웠다.

2. 이미지 삭제가 안 됨

• 사진 삭제 버튼을 눌렀는데 Storage에 파일이 안 지워지고 404 에러가 났다.
• 원인은 업로드할 때 파일명에 타임스탬프를 붙여서 저장했는데(1707801234_photo.png), 삭제할 때는 원본 파일명(photo.png)으로 찾고 있었기 때문.
• Firestore에 storagePath 필드를 추가해서 정확한 경로를 저장하도록 수정해서 해결했다.

3. 그룹 기능 전환

• 처음에는 단일 컬렉션(votes, menuImages)으로 만들었다가, 그룹 기능을 위해 서브컬렉션(groups/{groupId}/votes) 구조로 전환했다.
• Firestore 경로만 바뀌는 거라 로직 자체는 거의 그대로인데, 경로를 하나하나 바꾸는 작업이 꽤 많았다.
• 처음부터 확장성을 고려해서 설계했으면 좋았을 텐데, 라는 생각이 들었다. 하지만 뭐, 일단 만들고 필요할 때 바꾸는 것도 나쁘지 않다고 본다.

주요 기능 정리

기술 스택

결과

👉 https://vote-eat.web.app

• 링크 하나로 접속해서, 그룹을 만들거나 기존 그룹에 들어가서 바로 투표할 수 있다.
• 카톡 대화창에서 메뉴 정리하던 시절은 이제 안녕.
• 앞으로 추가하고 싶은 것들 : 여러 그룹 결과 합산 뷰, 투표 마감 기능, 결과 차트 시각화 등.

• 프로젝트 팀원 분이 응가 사진 분류 사전 학습된 모델과 데이터셋을 찾아주셨다.

• 무려 1500장 가량의 응가 사진이 있다...! https://universe.roboflow.com/smartgut/stool-classification-uvnqx

• Roboflow 3.0 Instance Segmentation (Fast)로 YOLOv8-seg 혹은 YOLO11-seg의 경량화 버전을 기반으로 한다.

• 그런데 우리의 목적인 7단계 분류만을 위해서는 내가 사용했던 모델인 EfficientNet-V2-S이 더 적합할 수 있겠다는 생각이 들었다.

• 그래서 위 사이트에 공개된 데이터셋을 이용하여 EfficientNet-V2-S을 학습시켜보고자 한다.

두 모델의 비교

어떤 것을 선택해야 할까요?

YOLO를 선택해야 하는 경우

• 초당 30~60프레임 이상의 실시간 속도가 중요한 경우.

• NVIDIA GPU와 같은 가속기를 사용하여 서비스 배포를 하려는 경우.

• CCTV 분석, 자율 주행, 실시간 불량 검수 등.

EfficientNet을 선택해야 하는 경우

• 이미지 전체의 특징을 파악하는 이미지 분류 작업이 주 목적인 경우.

• 학습 데이터가 적고, 모바일 기기의 CPU 환경 등 메모리 제약이 심한 곳에 배포해야 하는 경우.

• 의료 이미지 진단(질병 유무 판독)이나 정적 이미지의 카테고리 분류.

학습 시켜보자!

1. Train, Valid, Test의 이해와 활용

데이터셋은 목적에 따라 세 가지로 분리하여 관리한다.

2. 에포크와 배치

내가 몰랐던 용어 간단히 정리.

• Epoch (에포크): 전체 데이터셋을 총 몇 번 반복해서 학습할지 결정한다.
• Batch Size (배치 크기): 한 번에 몇 장의 이미지를 묶어서 처리할지 결정한다. (예: 1,500장을 16장씩 나눠서 학습) 높을수록 학습이 빠르겠지만 하드웨어 성능을 고려해서 2의 거듭제곱 중 하나로 정한다.

3. 학습 실전 프로세스 및 지표 해석

학습은 [Train 1회 -> Valid 1회]의 루프를 반복하며 진행한다. 수업 후 쪽지 시험을 보는 것과 비슷하다.

1. 확인해야 할 값: Train Loss와 Valid Loss를 비교한다.
2. 의미 분석:

• Loss가 낮아질수록 모델이 정답을 잘 맞히고 있다는 뜻이다.
• Train Loss는 계속 낮아지는데 Valid Loss가 오르기 시작하면 과적합(Overfitting)이므로 학습을 멈춰야 한다. (과적합: 대충 말하면, 이해해서 맞추는게 아니라 샘플들만 달달 외워서 맞추는 것)

3. 최종 단계: Valid 성능이 가장 좋았던 시점의 모델(best.pt)을 선택하여 마지막에 Test 데이터셋으로 최종 정확도를 산출한다.

4. 학습 후 평가 지표

음식 분석말고 대변 분석으로 바꾸었다.

Bristol Stool Scale

우선 대변의 상태를 분류하기 위한 브리스톨 대변 척도가 있다. 굳기..를 1~7단계로 나눈다. 쉽게 생각하면 1단계는 토끼똥, 7단계는 물...ㅎㅎ 4단계는 이쁜...응아다..

분석 모델

배경제거: YOLO

변기나 주변 배경을 제외하고 객체만을 탐지하기 위해 YOLOv8n-seg을 사용했다.

분류: EfficientNet-V2-S

구글의 강력한 이미지 분류 모델을 사용했다. 그런데 이건 일반적인 이미지 분류 모델이다. 응아 사진을 분류하기 위해 사전 학습된 모델은 찾지 못하였다. 그래서 라벨링한 사진으로 학습을 시키고 있다. 아직은 사진이 많이 부족하여, 있는 사진의 밝기 등을 조절하여 데이터를 뻥튀기 시킨 후 학습시켜보고 있다.

간단한 테스트

간단한 테스트용 프론트를 만들었다. 여기에 사진을 올리고 분석하기를 누르면..!

어려움

아직 분류 맞출 확률이 70% 내외로 낮은데 학습시킬 이미지가 부족하다. 음식과 달리 민감한 정보라 데이터셋이 귀하다.. 그리고 학습된 모델도 공개되어 있는 것을 아직 못 찾았다. 결국 데이터(똥...사진...)이 귀하다.. 아래 사이트에 샘플..들이있다. 샘플 사진

코드 저장소

https://github.com/zerocola355ml/food

"가장 적은 개수의 동전으로 거스름돈을 주려면 어떻게 해야 할까?"

가장 먼저 "가장 큰 단위의 동전부터 낼 수 있는 만큼 낸다"는 그리디(Greedy) 전략을 떠올릴 수 있다. 아주 직관적이며, 한국의 원화 ${10, 50, 100, 500}$나 미국의 달러 체계에서는 이 전략이 유효하다.

하지만 동전 체계가 ${1, 3, 4}$라면 어떨까?

• 목표 금액: 6
• 그리디 알고리즘: $4 + 1 + 1$ (3개)
• 최적 해: $3 + 3$ (2개)

그렇다면 "언제 그리디 알고리즘이 잘 작동할까?"라는 의문이 생긴다. 하나의 추측은 동전들이 서로 배수 관계인 것이다. 실제 대부분의 통화 시스템의 공통점을 살펴보면 떠올릴 수 있는 추측이며, 서로 배수 관계일 때 그리디 알고리즘은 잘 작동한다.

• 배수 관계라는 것은 구체적으로 10의 배수 50, 50의 배수 100, 100의 배수 500처럼 바로 다음 크기의 동전이 배수인 것이다.

• 그런데 100이 5개 이상 있으면 500으로 대체되므로 100은 최대 4개 있을 수 있다. 마찬가지로 50은 1개, 10은 4개까지 가능하다.
• 그렇다면 500없이 만들 수 있는 금액은 최대 10×4 + 50×1 + 100×4 = 490으로 500을 넘을 수 없다.
• 따라서 500이상 금액을 만드려면 반드시 500을 포함해야하며, 반복적으로 적용하면 500을 최대한 많이 포함해야한다.
• 이것이 결국 그리디 알고리즘의 선택과 일치한다.

하지만 꼭 배수 관계여야하는 것은 아니다. ${1, 5, 10, 25}$에서 25는 10의 배수가 아니지만 그리디 알고리즘이 잘 작동한다.

거스름돈 문제에서 그리디 알고리즘이 잘 작동하는 화폐 시스템을 Canonical Coin System라 부른다. 그런데 이를 판별하기 위한 필요충분조건은 배수 관계처럼 간단히 설명할 수 없다. 그 조건을 살펴보고 직관적으로 이해해보자.

1. 문제 정의

$n$가지 동전이 크기 순으로 있다. $$1 = c_1 < c_2 < \dots < c_n$$

어떤 금액 $x$를 만들 때, 그리디 알고리즘으로 구한 동전 개수를 $G(x)$, 실제 최적 동전 개수를 $O(x)$라고 하자. 이때, 모든 자연수 $x$에 대해 $G(x) = O(x)$를 만족하는 동전 체계를 Canonical Coin System이라고 한다.

2. 어디까지 확인해봐야 할까? (Kozen & Zaks의 정리)

직관적으로 생각해보면, 반례(Counterexample, $G(x) > O(x)$인 경우)가 있는 지 확인할 때 적당한 범위 안에서만 확인하면 될 것 같다. Kozen과 Zaks(1994)이 반례가 존재할 수 있는 상한선을 수학적으로 증명해두었다.

핵심 정리

그리디 알고리즘이 최적해를 보장하기 위한 필요충분조건은 다음과 같다.

"다음 범위 내에 반례 $x$가 존재하지 않는다." $$c_3 + 1 < x < c_n + c_{n-1}$$

즉, 이 범위 안에서 반례가 발견되지 않으면, 그보다 큰 어떤 숫자에서도 반례는 나오지 않는다.

증명 스케치 (Intuition)

이 증명은 귀류법(Proof by Contradiction)과 공통 동전 제거(Reduction) 아이디어를 사용한다.

1. 가정: 가장 작은 반례가 $x$이고 $x$가 아주 큰 수라고 가정하자.
2. 논리: $x$가 충분히 크다면, 그리디 알고리즘은 당연히 가장 큰 동전 $c_n$을 포함한다.
3. 모순 유도: 3-1. 만약 최적 해($O$)에도 $c_n$이 포함되어 있다면 양쪽에서 $c_n$을 하나씩 빼버리면 $x$보다 작은 반례가 나와 모순이다. 3-2. 만약 최적 해($O$)에 $c_n$이 없다면?
4. 결론: 따라서 가장 작은 반례 $x$의 최적 해에는 가장 큰 동전 $c_n$이 절대 포함될 수 없다.
   • 가장 큰 동전을 쓰지 않고 작은 동전들만으로 합을 구성해야 하므로, $x$가 커지는 데에는 한계가 있다.
   • 그 수학적 한계선이 바로 두 큰 동전의 합인 $c_n + c_{n-1}$ 이다.

3-2.를 생각해보자. $x$는 아주 크므로($c_n + c_{n-1}$이상) 최적해($O$)의 동전 일부 또는 전체를 선택하여 $c_n$보다 크게 만들 수 있다. 그러한 조합 중 합이 가장 작은 조합을 생각해보자. 그 조합의 합을 $S$라고 하면, $S \le c_n + c_{n-1}$이다. 왜냐하면 동전 하나를 빼면 $c_n$이하이다. 거기에 동전 하나를 더한다면 가장 큰 값이 $c_{n-1}$이므로 $S \le c_n + c_{n-1}$이다. $x$가 $S$보다 크므로, 가장 작은 반례라고 한 $x$가 $x$ = $S + (x-S)$ 두 부분으로 나누어진다. $S$는 가장 작은 반례 $x$보다 작으므로 그리디 알고리즘으로 최적해를 찾을 수 있고 $S > c_{n}$이므로 $S$의 최적 해는 $c_{n}$을 포함한다. 따라서 $x$ = $S + (x-S)$의 최적 해는 $S$의 그리디 해와 $(x-S)$의 최적 해의 합으로 구할 수 있는데, $S$의 그리디 해에 $c_{n}$이 포함된다. 결국 $x$의 최적 해에 $c_{n}$이 포함되므로 3-2가 일어날 수 없고 반드시 3-1이 된다.

3. 더 효율적인 판별법 (Pearson의 알고리즘)

Kozen & Zaks의 정리는 탐색 범위를 획기적으로 줄여주었다. Pearson(2005)은 이를 개선하여 범위 안의 모든 수가 아니라 검사해야하는 후보를 추려서 다항 시간($O(n^3)$) 내에 판별할 수 있는 방법을 제시했다.

핵심 아이디어

반례는 아무 숫자에서나 뜬금없이 튀어나오지 않는다. 그리디 알고리즘이 실수를 범하는 순간은 "작은 동전들을 모아 큰 동전 하나로 바꿀 수 있는 경계" 근처이다.

Pearson은 반례가 될 수 있는 후보군(Test Set)이 두 동전의 합($c_i + c_j$)과 밀접한 관련이 있음을 밝혔다.

예를 들어 ${1, 3, 4}$ 시스템에서 $3+3=6$은 $4$보다 크다. 그리디 알고리즘이 $4+1+1$을 선택하게 만들어 최적 해($3+3$)를 깨뜨리는 결정적인 반례 후보가 된다. $3$을 모아서 $4$보다 커지는 경우가 검사할 후보가 된다.

알고리즘 메커니즘

모든 $x$를 다 뒤질 필요 없이, 아래와 같은 형태의 '위험군' 숫자들만 검사하면 된다.

1. 임의의 두 동전 $c_i, c_j$ ($1 \le i \le j < n$)를 선택한다.
2. 두 동전의 합보다 작지만, 그리디 알고리즘으로는 큰 동전을 쓰게 만드는 임계값을 계산한다.
3. 이 소수의 후보군($O(n^2)$개)에 대해서만 $G(x)$와 $O(x)$를 비교해본다.

4. 결론 및 참고 문헌

우리가 흔히 사용하는 화폐 시스템은 그리디가 통하지만, 꼭 그렇지만은 않다.

• 동전들이 서로 배수 관계라면 그리디는 항상 성립한다. (충분조건)
• 배수 관계가 아니더라도, $c_n + c_{n-1}$ 미만의 범위에서 반례가 없다면 그리디는 성립한다. (필요충분조건)

References (엄밀한 증명이 궁금하다면)

1. Kozen, D., & Zaks, S. (1994). Optimal Bounds for the Change-Making Problem.
   • 반례가 존재할 수 있는 상한선을 증명한 논문
2. Pearson, D. (2005). A Polynomial-time Algorithm for the Change-Making Problem.
   • 전수 조사가 아닌, $O(n^3)$ 알고리즘으로 판별 가능함을 증명한 논문

어떻게 동작하는 지 고민해본 적이 없는데 여기에도 여러 알고리즘이 있다.

그 중 KMP 알고리즘을 소개한다. KMP는 만든 사람들의 이름의 첫 글자를 따서 만든 이름이다.

이 글에서는 별 말이 없으면 길이 n인 Text에서 길이 m인 Pattern(n>m)을 검색하는 상황이고, i, j는 각각 Text와 Pattern의 인덱스이다.

Brute Force

먼저 Naive Algorithm이라고도 불리는 Brute Force 방법을 살펴보자.

Text와 Pattern을 제일 앞부터 한 글자 씩 비교한다.

모두 일치하면 결과에 저장하고, Pattern을 한 칸 오른쪽으로 밀어준 후, 다시 제일 앞부터 비교한다.

불일치가 발생하면 Pattern을 한 칸 오른쪽으로 밀어준 후, 다시 제일 앞부터 비교한다.

• 첫 글자를 맞춰두고 시작(i=0, j=0)

• 첫 글자 일치하여 i, j 각각 1씩 증가
• 불일치 발생

• Pattern을 한 칸 밀어주고(i = 1, j = 0) 다시 탐색 시작
• 위 과정을 반복

Brute Force의 경우 불일치가 발생하면 Pattern을 항상 한 칸씩 밀어주고 다시 Pattern의 처음부터 탐색을 시작한다.

Pattern의 마지막에서 불일치가 발생하는 경우 m번 비교를 하게 되며,

Text 길이가 n이므로 시간 복잡도는 O(mn)이다.

KMP Algorithm

Pattern을 한 번에 여러 칸 밀어주고, Pattern의 처음이 아닌 중간부터 일치 여부를 따지면 훨씬 효율적이다. 어떻게 하면 답을 놓치지 않으면서 이를 구현할 수 있을 지 KMP 알고리즘의 작동 방식을 살펴보자.

바로 구체적인 예시를 살펴보자.

예시

• i = 0, j = 0으로 시작하여 둘을 비교한다.
• Pattern의 처음부터 불일치 발생한 경우 즉, j=0에서 불일치 발생
  • i를 1 증가해준다. (i, j를 같은 위치에 둘 것이니 아래 Pattern 종이를 한 칸 오른쪽으로 밀어준다.)
  • i = 1, j = 0 이 되어 둘을 비교한다.

• i = 1, j = 0에서 시작한다.
  • 일치하는 경우 i, j 를 각각 1씩 증가하다가 불일치하면 멈춘다.
  • i = 5, j = 4에서 멈춘다.
• 불일치가 발생하고 j ≠ 0인 경우, 그 직전까지는 일치했다는 것으로, 그 정보를 최대한 이용한다.
  • 앞 뒤가 같은 최대 부분을 찾아준다. 그것을 보라색 화살표로 나타냈다.
  • 보라색 화살표 부분이 일치하므로 Pattern을 2칸 밀 수 있다.
    • 불일치 발생한 직전 j =3부터 살펴보면 j = 01, j = 23 부분이 일치한다.
    • j = 1의 B가 j = 3의 B 자리에 오는 것이므로 2칸 밀어준다.(2칸인건 화살표 길이와 별개다!)
    • Pattern을 2칸 민다는 것은 j를 2 감소 시킨다는 것이다.
    • 따라서 j = 2가 되며, i = 5, j = 2를 비교한다.
    • Brute Force에서는 1칸 밀 것을 2칸 한 번에 밀 수 있는 것이다.

• i = 5, j = 2에서 시작한다.
  • Pattern의 앞 부분(j = 0~1)은 이미 일치하므로 살펴볼 필요 없이 j = 2부터 살펴본다.
  • 시작(j = 2)부터 바로 불일치한다.
• 불일치가 발생하고 j ≠ 0인 경우, 앞 뒤가 같은 최대 부분을 찾아준다.
  • 지금은 같은 부분이 없다. (Pattern의 뒤부터 B, AB와 같은 것이 앞쪽에 있는 지 살펴보면 자기 자신 제외 없다.)
  • j = -1의 빈 문자가 j = 1의 B 자리에 오도록 Pattern을 2칸 밀어준다.
  • 즉, j 값이 2 감소하여 j = 0이 되어, i = 5, j = 0을 비교한다.

• i = 5, j =0에서 시작한다.
  • 시작부터 바로 불일치한다.
• Pattern의 처음부터 불일치 발생한 경우 즉, j=0에서 불일치 발생
  • i를 1 증가해준다. (i, j를 같은 위치에 둘 것이니 아래 Pattern 종이를 한 칸 오른쪽으로 밀어준다.)
  • i = 6, j = 0이 되어 이 둘을 비교한다.

• i = 6, j = 0에서 시작한다.
  • 일치하면 i, j 를 각각 1 증가한다.
  • i = 11, j = 5에서 멈춘다.
• 모두 일치하므로 결과에 저장한다.
  • j가 Pattern의 길이인 5가 되면 모두 일치하는 것이다.(j == m)
• 얼마나 옮길 지 정하기 위해 앞 뒤가 같은 최대 부분을 찾아준다.
  • Pattern을 2칸 밀어준다.
    • j = 02, j = 24 부분이 일치한다.
    • 따라서 j = 2의 A가 j = 4의 A 자리에 와야 하므로 Pattern을 2칸 밀어준다.
    • 즉, j는 2 감소하여 i = 11, j = 3이 된다.

• i = 11, j = 3에서 시작
  • 일치하므로 i, j 각각 1 증가
  • i = 13, j = 5에서 멈춘다
• 모두 일치(j == m)하므로 결과를 저장한다.
• 얼마나 옮길 지 정하면 위와 마찬가지로 Pattern을 2칸 밀어주게 된다.
  • 이후 일치 탐색을 하면 i 값이 n=12를 벗어나므로 모든 탐색을 종료한다.

핵심

• i는 작아지지 않는다.
• 부분 일치하는 경우 Pattern을 한 번에 여러 칸 옮길 수 있어 효율적이다.
• 부분 일치하는 경우 Pattern을 처음부터 살펴보지 않아 효율적이다.
• 시각적으로 Pattern을 미는 행위는 j 값을 감소하는 것인데, 얼마나 줄일지 미리 알고 있어야 한다.
• 매번 j를 얼마나 줄일지 계산한다면 Brute Force와 별 차이가 없다.

LPS Table

어떤 것인가

• Pattern을 얼마나 밀어야 하는 지 즉, j 값을 얼마로 줄일 지 미리 계산해둔 것을 LPS Table이라 한다.
• LPS는 Longest Proper Prefix which is also Suffix의 약자이다.
• 그러니까 앞 뒤가 같은 부분 중 가장 긴 것을 찾는다는 것이다.

위의 예시를 잠시 살펴보면

예시1

• i = 5, j = 4일 때 불일치 발생
• 마지막 일치는 j = 3인 B이고, 이 자리에 j = 1인 B가 올 것이고,
• 빨간 표시에서 다음 비교를 진행할 때 i = 5, j = 2가 되어야 한다.
• 그러니까, j = 4일 때 불일치 했다면, LPS[j - 1] = LPS[3] = 2가 되어야한다.

예시2

• i = 11, j = 5일 때 모두 일치
• 마지막 일치는 j =4인 A이고, 이 자리에 j = 2인 A가 올 것이고,
• 빨간 표시에서 다음 비교를 진행할 때 i = 11, j = 3이 되어야 한다.
• 그러니까, j = 5일 때 불일치 했다면 LPS[j - 1] = LPS[4] = 3이 되어야 한다.

ABABA의 LPS Table

• 위 예시를 잘 생각해보면, 아래와 같은 LPS Table을 만들 수 있다.
• 결국, 순서대로 A, AB, ABA, ABAB, ABABA라는 문자열을 보면서, 접두사이면서 접미사인 것 중 가장 긴 것의 길이를 기록하는 것이다.
• A랑 AB는 접두사이면서 접미사인 것이 없으므로 0.(자기 자신은 제외하고 생각한다.)
• ABA는 A가 접두사이며 접미사이므로 그 길이는 1
• ABAB는 AB가 접두사이며 접미사이므로 그 길이는 2
• ABABA는 ABA가 접두사이며 접미사이므로 그 길이는 3

Boyer Moore Algorithm

그런데, 재밌는 점이 있다.

아래 예시를 보자.

pattern의 앞 부분부터 살펴보았는데 바로 불일치하고, 이 경우 pattern을 한 칸 밀어주게 된다.

그런데 pattern의 뒷 부분부터 살펴보면 어떤가?

Text의 B와 일치하려면 Pattern에 B가 j = 0에만 있으므로 4칸을 밀어줄 수 있다.

우리가 Pattern을 오른쪽으로 밀기 때문에, Pattern의 왼쪽이 아닌 오른쪽부터 일치를 따지는 것이 더 효율적인 것이다!

이를 이용해서 만든 것이 KMP보다 일반적으로 더 성능이 좋은 Boyer Moore Algorithm이다.

다음에 기회가 되면 Boyer Moore Algorithm에 대해 소개하겠다.

오늘로 마지막 기말고사가 끝났다. 종강! 시원하다.

나는 25년 2학기에 3학년으로 편입을 했고, 10여년만에 다시 대학생이되었다.

학과 오리엔테이션도 가보고 캠퍼스에 가는 것이 설레기도 했다.

스터디 모임하며 다른 사람들 만나는 것도 재미있었고, 강의도 배울 것이 많았다.

항상 컴퓨터에 대해 더 배우고 싶었는데, 나에게 방송통신대 컴퓨터과학과는 최고의 선택지였다.

저렴하고, 전공 지식들을 탄탄한 커리큘럼대로 배울 수 있는데 다 들으면 학위까지 준다.

(물론, 교수님마다 강의력 차이는 있다. 어차피 나는 대학에서는 교재를 통해 내가 무엇을 모르는 지 알면 되고, 모르는 건 GPT와 유튜브, 구글에게 배우면 되는 것이라 생각한다. )

물론 방송통신대라고 해서 만만하게 볼 수 없다.

방송통신대 입학을 고민 중이시라면

저마다 입학의 목적이 다를 것이다.

1. 관련 업계 종사자가 학위 취득하기 위해
   1. 가장 많은 것 같다.
   2. 높은 학점이 아닌 졸업만이 목표라면 어려울 것 없다.
   3. 가끔 있는 출석 수업 등에만 연차를 좀 쓰면 된다.
   4. 학비도 저렴하니 이런 목적이라면 딱 맞는 선택이다.
   5. 그리고, 추후 외국의 온라인 석사 프로그램이 있는 대학에 지원할 때도 학사를 써먹을 수 있다!
   6. 그런데 기본적으로 일 하면서 높은 학점까지 받는 것은 쉽지 않다.
2. 관련 업계 취업 전 학위 취득하기 위해
   1. 종종 있으시다.
   2. 내가 이 쪽 업계 종사자가 아니기에, 독학하며 프로젝트, 포트폴리오 준비 VS 부트캠프 VS 방송통신대 학위 중 취업에 우선 순위가 어떻게 되는 지는 모르겠다.
3. 그냥 배우고 싶어서, 공부가 즐거운 경우
   1. 내가 이건데, 나에게는 최고의 선택이다.
   2. 컴퓨터 공부를 좀 더 하고 싶은데, 부트캠프는 취업용이고, 직장인인 내가 다니기도 어렵다.
   3. 그럼 독학은? 유튜브, 유데미, 인프런 등등에 좋은 강의도 많고, GPT 등을 활용하면 공부하기 좋은 시대이다. 어려운 내용 키워드 하나 씩 단편적으로 찾아보거나, 단기간에 하나의 주제, 프로젝트에 대해 공부할 때는 유데미, GPT 등을 이용하는 것도 좋다. 그동안은 그렇게 했다.
   4. 하지만, 기초 공부를 할 때는 전공 책을 종이로 보는 것이 좋다고 생각한다.
   5. 대학의 커리큘럼과 전공 서적이 내가 무엇을 모르는 지 알려주어 좋았다.
   6. 일부 출석 수업을 제외하곤 내가 듣고 싶을 때 들을 수 있어 직장인에게 최고다.
   7. 심지어 저렴하다. 한 학기에 40만원 정도였던 것 같은데 취미생활?중에서도 저렴한 편이다.
4. 이런 경우는 비추천이다.
   1. 별 다른 목표가 없거나 현실적으로 시간을 내는 것이 어려운 경우 비추천이다.
   2. 직장 다니면서 하는 것이 생각보다 시간적으로 어렵다.
   3. 하루에 강의 하나 정도는 들어야 진도가 얼추 맞다.
   4. 퇴근 후 강의 듣는 것만 해도 1시간, 교재 내용 보며 복습하고, 문제 풀고 하려면 또 적어도 1~2시간이 든다.
   5. 매일 퇴근 하고 2시간 가량 투자할 수 있을까 생각해보면 된다.
   6. 많은 경우에 이게 어렵고, 첫 학기 이후 그만두는 사람들이 아주 많다.

입학 후 꿀팁? 도움되는 정보들의 출처

대학생활 길라잡이

• 학교에서 제공하는 학교 설명서이다.
• 입학을 결정했다면 받아두고 궁금한게 있을 때 마다 이걸 먼저 확인하면 된다.
• 거의 대부분의 정보가 다 있다.

학교 공지사항

• 학교 공지사항, 학과 공지사항, 지역대학 공지사항 게시판을 즐겨찾기 해두고 하루에 한 번 확인하면 좋다. 이것만 해도 학교가 어떻게 돌아가는 지 웬만한 재학생들보다 더 잘 알 수 있다.
• 나는 가보진 못했는데 가끔 학교에서 기말 대비 특강을 제공하기도 한다.

튜터 사이트

• 입학 첫학기에만 튜터가 배정되고 튜터 사이트가 있다.
• 올라오는 대부분의 정보가 위에서 말한 공지사항이라 특별한 건 없다.
• 다만, 시험 기간에 핵심 정리 등이 올라오기도 한다. 이건 주로 각 과목 게시판에 올라오는 내용을 긁어 올려주시는데, 각 과목 게시판을 안 보는 사람들이 많으니, 그 사람들에겐 좋은 정보다.

그외 커뮤니티

• 방송통신대 커뮤니티(c-knou), 디시인사이드 갤러리, 카카오톡 오픈 채팅방이 있다.
• 다른게 더 있는 지는 모르겠다.
• 대부분 사적인 대화, 잡담(사실 똥글…)이 많아서 다 볼 필요가 없다.
• 주요 공지는 어차피 공식적인 루트를 통해 다 확인이 가능하다.
• 다만, 몇 가지 용도로 도움이 되어 가끔 들어 가보면 좋다.
  • 중고 교재 사고팔고 할 때 당근이나, 오픈 채팅방을 이용하면 좋다.
  • 시험 기간에 시험 후기들이 종종 올라온다. 특히 최근에 개설되어 기출 문제가 없을 때 이런 것들이 많이 도움 된다. 기출 위주로 볼지, 강의록까지 볼 지, 교재 구석 구석 볼 지 참고할 수 있다.
  • 공식 공지에 없는 디테일 한 것들을 알 수 있다. 예를 들면 25분*3과목 시험칠 때 75분간 시험 시간을 3과목에 자유롭게 분배할 수 있다는 것. 그럼 계산 많은 과목이랑 적은 과목을 적절히 분배해서 시험일을 정할 수 있다. 이런 정보를 미리 알 수 있다.

스터디

• 혼자 공부하는 것은 힘들 수 있다. 누군가 함께 한다는 것 자체가 큰 힘이 된다.
• 특히 온라인 중심의 대학이니 더 그렇다.
• 나는 입학 전부터 스터디가 있는 지 알아보았고, 지금은 그로스로그 스터디에 참여 중이다.
• 전공 공부부터 여러 소모임이 있어 도움이 되었고, 개발자 사람들과 만날 수 있는 것도 좋았다.
• 학교 홈페이지에 각 지역/학과별 스터디, 동아리 소개 페이지가 있다.

공부 방법

한 학기 동안 느낀 건, 결국 매일 꾸준히 해야 한다.

평소 매일 1개의 강의 집중해서 듣기 → 강의록 복습 → 교재 읽으며 복습 → 해당 워크북 풀기

시험기간에는 강의록/교재 복습 + 워크북 복습 + 기출 3년치 돌리기를 했다.

나는 하루에 강의 1개 → 후반에 2~3개 페이스로 들어서 시험 4주전 즘 완강하고 시험 공부를 시작했다.

(컴퓨터과학 개론 출석 수업을 못 가서 대체 시험 준비하느라 일찍 시작했다.)

꽤 일찍 시작한 것 같은데도 빡빡했다.

나는 지금 남들보다 비교적 시간이 많은 편이라 하루에 2~3개씩도 들었는데,

일반적으로 직장 병행하는 경우 하루 1개가 최선일 것 같다.

(그래서 다음 학기 전에 미리 공부를 좀 해두어야 할 것 같다.)

과목별 후기

자 그럼, 이번 학기에 들은 과목들의 후기이다.

원격대학교육의이해

그냥 방송통신대학교 튜토리얼 강의다. 별 것 없지만 또 들으면 도움이 된다. 밥 먹을 때 틀어두고 들으니 금방 다 들었다. 별도의 평가 등은 없다.

자료구조

제일 재미있어 보여서 이 강의부터 들었다.

강의

수업 스타일은 약간 횡설수설하는 느낌으로 호불호가 갈린다. 나는 호! 좋았다. 불호인 분들은 아마 체계적이지 않아서, 잡담(?)이 많아서일 것이다. 그리고 녹화 중 실수한 부분을 자주 언급하시는데, 아마 아무도 없는 곳에서 강의를 녹화하면 멋쩍고 어색해서 뭐라도 말해야할 것 같은 마음에 그러시는 것 같다. 나는 지루한 온라인 강의 중 교수님의 그런 농담이 있어서 좋았다. 그리고 횡설수설 하는 듯 하지만 듣다 보면 가장 중요한 본질이 느껴진달까? 그래서 좋았다. 그리고 강의 후반부로 가면 내용이 어려워지며 잡담이 줄어드시고, 녹화에도 익숙해지셨는지 설명도 점점 체계적으로 잘하신다.

교재

교재는 구어체가 섞여있다. 전반적으로 좋았다. 아쉬운 점을 뽑자면, 1. 교재에 연습 문제가 없고 2. 워크북이 없다. 3. 앞쪽 쉬운 단원은 개념 설명과 코드 설명이 엄청 자세히 되어 있는 반면 뒤쪽 어려운 단원에서는 오히려 설명이 짧다. 4. 중요한 개념인데 소개만 하고 넘어가는 경우가 있다.(ex 레드 블랙 트리) 물론 소개되어 있어서 궁금한 사람은 찾아보면 되긴 한다.

시험

어렵지 않게 나왔고 기출 풀어본 것으로 잘 대비되었다. 그런데 기출에 정답 정정이 너무 많아서… 공부할 때 조금 불편했다. 그래도 이 정도 난이도로 내주시다니 감사합니다 교수님.

컴퓨터과학개론

강의

개론이니까! 자료구조 다음에 듣기 시작했다.

두 분의 교수님이 단원을 나눠 수업을 하시는데 강의 스타일이 정반대라 재미있었다.

개론 수업 답게 광범위한 내용을 다루며, 어쩔 수 없이 설명의 깊이가 얕아서 오히려 어렵다.

높은 학점을 목표로 한다면, 다른 전공을 듣고 4학년 때 개론을 듣는 것이 효율적이고 편할 수 있다.

하지만, 그래도 개론을 통해 다양한 분야를 찍먹하기 위해 첫학기에 들었다.

교재

교재는 꽤 좋다. 방통대 교재들이 다 괜찮은 편이다. 워크북의 몇몇 문제들에 해설이 자세하고 도움이 된다.

개론이라 지면이 제한적인데도 최대한 자세히 설명하기 위한 노력들이 보인다.

나는 앞쪽 자료구조, 알고리즘까지는 쉽게 따라가다가, 운영체제부터 어? 하다가 컴퓨터 구조 단원부터 무슨 소리인가 싶었다.

사람들마다 어려운 단원이 무조건 있을 것이고, 공부량이 상당히 필요한 과목이다.

하지만, 개론을 충분히 공부했다면 확실히 다른 과목들이 쉬워진다!

이후에 컴퓨터 구조 들을 때는 개론을 들어서 훨씬 쉽게 들었다.

대체 시험 후기

아, 나는 이 과목 출석 수업 일정이 안 맞아서 대체 시험으로 봤는데, 학점 관리를 하려면 출석 수업을 가는 게 좋다.

대부분의 사람들은 출석 수업 점수가 더 잘 나온다.

최종적으로 A+를 받고 싶다면 95점 이상이 나와야한다.

즉, 형성평가+출석 수업 만점 가정하에 기말고사에서 2문제까지 틀려도 A+이다.

그런데 출석 수업 대신 대체 시험을 만점을 받는 건 생각보다 어렵다.

대체 시험에서 3문제 틀리면 A+은 날아가는 것이고, 1개만 틀려도 기말에서 1개까지만 틀려야 A+이 나와서 부담스럽다.

난 대체 시험에서 하나 틀렸는데, 틀린 문제를 확인할 수 있는 기간있어 가 보았다.

그런데 내가 전혀 생각지 못한 문제에서 엉뚱한 답이 마킹되어 있었다.

시험 태블릿이 팜리젝션이 안되는, 그러니까 펜을 쓰지만 손바닥으로도 터치가 되는 태블릿이다.

위에 문제 마킹을 하다가 손바닥으로 밑에 문제 답이 눌린 것 같다…ㅠㅠ

그래서 그 다음 부터는 한 문제씩만 뜨게 하고 펜 없이 그냥 손가락으로 마킹을 했다.

시험

교재, 워크북, 기출이 많이 도움되었다. 문제가 아주 지엽적으로 나오진 않았음에도 4문제 정도가 헷갈렸는데, 범위가 워낙 넓어서 어쩔 수 없는 것 같다.

오픈소스기반데이터분석

강의

교수님 강의 전달력이 좋으시다. 그리고 중요한 것을 중요하게 설명하신다.

그러니까, 군더더기는 빼고 핵심을 설명하시며, 실습을 중요하게 생각하신다.

강의가 개념 설명 반, 실습 반으로 이루어져 있는데 후반으로 가면 실습이 훨씬 길어진다.

강의에서 시키는 것만 해도 간단하지만 꽤 많은 실습 경험을 해볼 수 있다.

그런데 뒤로 갈수록 강의 시간이 부족하신지 실습 진행이 빠르고, 코드가 너무 길어져서 내가 안보고 쳐보기보다는 딸깍 딸깍 눌러만 보고 넘어가게 되었다.

교재

교재는 아주 두껍고 양이 많다. 설명이 친절하고 실습이 많아서 그런듯하다.

아쉬운 점은 워크북이 있으나 워크북이 교재에 대한 워크북이 아니라 마크다운과 깃허브 사용에 대한 내용이다. 교재에 단원별로 문제가 있으나 객관식5 주관식5개 정도씩으로 넉넉하지 않다. 그런데 워크북에 교재 내용에 대한 문제가 없다. 게다가 이 과목은 신규개설 과목이라 기출도 없다. 그래서 공부한 것을 연습하고 확인하기가 조금 어려웠다. 시험대비 역시 그랬다.

시험

워크북 문제와 기출이 없어 걱정했던 것에 비해 시험은 어렵지 않게 나왔다.

풀어볼 수 있는 문제는 강의 형성평가 + 교재 연습문제가 전부였다.

이 교수님은 중요한 것을 중요하게 생각하시는 것 같다.

그러니까 지엽적인 내용 없이 기본적인 내용 위주로 출제되었다.

실습을 중요시 하셔서 코드 있는 문제도 어느 정도 나왔다.

하지만, 코드 역시 기본적이고 중요한 부분만 알고 있으면 풀 수 있었다.

교재 연습 문제 주관식에 있는 코드들을 달달 외웠었는데 그럴 필요는 없을 것 같다.

UNIX시스템

강의

개발 공부하면 윈도우 말고 맥이나 리눅스를 써야할 것 같은 기분이다.

이제 까만 화면에 명령어 치며 폴더를 만들 수 있다.(고작? ㅋㅋ)

아쉽게도 강의는 내 스타일이 아니었다.

너무 많은 명령과 옵션들을 알려주셨고, 과연 이걸 다 외워서 쓰는 사람이 있을까 싶었다.

그 양에 압도되어 무엇이 중요한 것인 지 판단하기 어려웠다.

아 그리고 최근에 개정되며 네트워크, 서버 부분 빠지고 깃이 들어왔다.

나는 개정 전 내용이 더 유닉스와 잘 어울린다고 생각하고 그걸 배우고 싶었어서 아쉬웠다.

교재

교재는 리눅스 사전? 바이블? 느낌으로 체계적으로 잘 정리되어 있어 좋았다.

워크북 문제도 내가 모르는 부분 체크하기에 좋았다.

시험

교재가 사전 느낌으로 좋다고 했는데, 시험을 위해 사전을 외워야한다… 아…

교재는 시험 기간에 보다 보다 너무 지쳐서 중간에 포기하고 강의록+워크북+기출만 봤다.

이번 기말 공부량 압도적으로 이 과목이 제일 많았다.

그런데 시험 풀 때 제일 어려웠다.

지엽적인 문제가 많았다.

어려웠고 어려웠다…

컴퓨터구조

강의

무난하게 좋다. 컴퓨터가 동작하는 아랫 단(?)을 이해할 수 있어서 좋았다.

프로그램 설치할 때마다 내 컴퓨터가 32비트인지 64비트인지 확인했었는데 이제 이 의미를 알게 되었다!

그리고 컴퓨터를 설계하고 만드는 사람들이 새삼 대단해보였다.

논리 회로 만들어서 컴퓨터 처음 만든 사람은 얼마나 뿌듯했을까.

CPU 설계하는 사람들은 얼마나 천재일까 대단하다.

아 교수님이 이론적인 부분 뿐 아니라 실제 요즘 컴퓨터에 대한 이야기도 종종해주신다.

그런 점이 좋았다.

교재

좋았다. 그런데 내용 자체가 좀 어려운 부분이 있어서 그런지 이해하기 어려운 부분들이 좀 있었다.

시험

감사합니다 교수님. 기출과 워크북 문제에서 벗어나는게 없었던 것 같다.

C프로그래밍

강의

나는 이 강의 스타일이 제일 잘 맞았다.

한 슬라이드에 딱 적당한 양의 정보

• 슬라이드에 없는 부연 설명은 이해를 돕기에 아주 적절함

• 부연 설명이 없어도 시험 대비에는 무리 없음

• 실습 코드도 적절하게 띄워줌

그리고 뭔가 C를 배우니까 개발 공부하는 느낌이 팍팍 나서 기분이 좋다.

근본 있는 느낌이다.

교재

교재도 아주 좋았다. 실습 코드들이 꽤 있는데 따라 쳐보면 많은 도움이 된다.

시험

시험도 어렵지 않아서 좋았다.

기출 + 워크북에서 크게 벗어나지 않았다.

수강 계획

25-2(완료): C프로그래밍, 컴퓨터과학개론, 오픈소스기반데이터분석, 자료구조, UNIX시스템, 컴퓨터구조

26-1: 파이썬프로그래밍기초, Java프로그래밍, HTML5웹프로그래밍, 디지털논리회로, 운영체제, 알고리즘, 인공지능

26-2: 프로그래밍언어론, JSP프로그래밍, 시뮬레이션, 머신러닝, 컴파일러구성, 클라우드컴퓨팅, 딥러닝

27-1: 데이터베이스시스템, 컴퓨터그래픽스, 모바일앱프로그래밍, 소프트웨어공학, 정보통신망, 컴퓨터보안. + 1개 더 뭘 들을까 고민중

성적

성적이 확정되어 자랑 겸 인증!

음식 사진만 찍으면 칼로리와 영상소를 분석하고 기록해주는 서비스가 있으면 좋겠다. 사람들이 식단 관리, 건강 관리에 관심이 많다. 그런데 내가 먹은 음식의 칼로리를 계산하기도 어렵고, 하나 하나 기록하기도 어렵다. 정확한 계산 보다는 편리하게 적당히 계산해주는 도구가 있으면 좋겠다. 막상 시작하려고 하면 어디부터 손대야 할지 감이 안 잡히는데, 직접 이것저것 찾아보면서 삽질하는 과정을 기록해보고자 한다.

큰 그림부터 잡기

복잡해 보이지만 전체 흐름을 단순화하면 이렇다.

1. 음식 사진을 넣는다
2. 모델이 “이게 무슨 음식인지” 맞춘다
3. 음식 이름으로 영양 데이터베이스에서 칼로리·영양소를 찾는다
4. 결과를 보여준다

이 흐름만 이해하면 어디서부터 공부해야 하는지 훨씬 명확해진다.

1. 음식 이름부터 알아내기 (이미지 → 음식)

사진 분석에서 제일 먼저 필요한 건 음식 이름 분류 모델이다.

이미 커뮤니티에 완성된 사전학습 모델들이 많이 올라와 있다.

• Food-101 같은 공개 데이터셋으로 학습된 모델들
• CLIP 기반 모델들
• TIMM(PyTorch Image Models)에 있는 각종 사전학습 모델들

그냥 가져다 쓰면 된다. 음식 사진 한 장 넣으면 “파스타”, “라멘”, “치킨 윙” 같은 식으로 음식 이름이 나온다.

참고로 Food-101은 모델이 아니라 ‘사진 모음 데이터셋’이다. 하지만 워낙 유명해서 이걸로 학습된 모델들도 “Food-101 모델”이라고 부르곤 한다.

2. 음식 이름 → 영양소 데이터 연결하기

모델이 음식 이름을 뱉어주면, 이제 그걸 바탕으로 영양 정보를 찾으면 된다.

• USDA(미국 농무부) 영양소 DB
• 한국 식품 구성표(식약처, 공공데이터 포털)

사진만으로 “얼마나 담겨 있는지”는 사실 정확히 알기 어려워서, 초반에는 1인분 기준 칼로리 또는 사용자가 직접 gram 입력 방식으로 가는 게 현실적이다. 나중에는 동전이나 손가락, 젓가락, 신용카드 등 그 크기가 일정한 것과 같이 사진을 찍고, 이것들과 크기를 비교해서 추측하는 방법이 있다.

한식 데이터셋

누가 한식에 대해 미리 해둔게 있다. → 링크

오늘 해본 일

일단 이미 학습된 오픈 소스 모델 이용해서 음식 사진 넣고, 음식 이름 받아오는 걸 해보자.

Python 환경에서 transformers (Hugging Face)와 torch (PyTorch) 라이브러리를 사용한다.

라면이 먹고 싶어서, 위키백과 라면의 사진을 넣어보았다. 결과는

1. ramen 41.17%
2. miso_soup 15.13%
3. hot_and_sour_soup 11.00% 로 잘 나왔다.!

python -m venv foodenv
foodenv\Scripts\activate
pip install transformers torch pillow requests

import torch
from transformers import ViTImageProcessor, ViTForImageClassification
from PIL import Image
import requests
from io import BytesIO

class FoodClassifier:
    def __init__(self):
        # Food-101 데이터셋으로 사전 학습된 ViT 모델 로드
        # model_name을 변경하여 다른 아키텍처(ResNet, EfficientNet 등)로 교체 가능
        self.model_name = 'nateraw/food'

        print(f"Loading model: {self.model_name}...")

        # 이미지 전처리기 (Resize, Normalize 등을 담당)
        self.processor = ViTImageProcessor.from_pretrained(self.model_name)

        # 분류 모델 로드
        self.model = ViTForImageClassification.from_pretrained(self.model_name)

        # 평가 모드로 전환 (Dropout 등을 비활성화)
        self.model.eval()

    def predict(self, image_source, top_k=3):
        """
        이미지를 입력받아 상위 k개의 예측 결과를 반환합니다.
        image_source: 이미지 파일 경로(str) 또는 URL(str)
        """
        # 1. 이미지 로드
        image = self._load_image(image_source)
        if image is None:
            return

        # 2. 전처리 (Preprocessing)
        # PyTorch 텐서로 변환 및 배치 차원 추가 (C, H, W -> 1, C, H, W)
        inputs = self.processor(images=image, return_tensors="pt")

        # 3. 추론 (Inference)
        with torch.no_grad(): # 그래디언트 계산 비활성화 (메모리 절약)
            outputs = self.model(**inputs)

        # 4. 결과 후처리 (Post-processing)
        logits = outputs.logits
        probabilities = torch.nn.functional.softmax(logits, dim=-1)[0]

        # 상위 k개 확률과 인덱스 추출
        top_probs, top_indices = torch.topk(probabilities, top_k)

        results = []
        for prob, idx in zip(top_probs, top_indices):
            label = self.model.config.id2label[idx.item()]
            confidence = prob.item()
            results.append((label, confidence))

        return results

    def _load_image(self, source):
        try:
            if source.startswith('http'):
                response = requests.get(source)
                img = Image.open(BytesIO(response.content))
            else:
                img = Image.open(source)
            return img.convert("RGB") # PNG 등의 투명 채널 제거
        except Exception as e:
            print(f"Error loading image: {e}")
            return None

# --- 실행 예시 ---
if __name__ == "__main__":
    # 분류기 인스턴스 생성
    classifier = FoodClassifier()

    # 테스트할 이미지 URL (피자 이미지)
    test_img_url = "test.jpg"

    print("\nAnalyzing image...")
    predictions = classifier.predict(test_img_url)

    print("\n[Analysis Result]")
    for i, (food, conf) in enumerate(predictions):
        print(f"{i+1}. {food}: {conf*100:.2f}%")

깃헙

코드 기록용

참고할 만한 링크들

https://data.vision.ee.ethz.ch/cvl/datasets_extra/food-101/ https://aihub.or.kr/aihubdata/data/view.do?currMenu=115&topMenu=100&aihubDataSe=data&dataSetSn=74 https://github.com/Cheng-K/FoodNet/tree/main https://github.com/Nikhilchakravarthy1303/FoodCalorieEstimation

• 반복 구매하는 품목들
  • 주기적으로 사는 물건들은 저렴한 딜이 떴을 때 미리 사두는 편이다.
  • 이를 위해 헬로프라이스, 폴센트를 앱으로 설치해 사용중이다.
• 기존 서비스의 아쉬움
  • 그런데 이 서비스들은 육아용품을 전문적(?)으로 다루지 않는다.
  • 육아용품 딜은 네이버의 맘카페에 제일 많이 올라온다.
  • 그런데 여기에는 바이럴 게시글도 상당히 많이 올라오고, 애매한 가격의 딜도 많이 올라온다.
  • 그래서 필요한 물건 키워드 알림을 해두면 공해 수준으로 알림이 많이 온다.
• 디지털 디톡스
  • 계속해서 울리는 알림, 하지만 대부분이 쓸모없는 알림
  • 어떻게 하면 꼭 필요한 알림만 받을 수 있을까
• +최근 셀레니움 이용하는 수업을 들었어서 한 번 써먹어 보고 싶다는 생각!

큰 흐름

• 사실 큰 흐름이 전부이다. 구체적인 방법은 검색하거나 AI에게 물으면 나오기 때문에, 굳이 여기 더 적을 필요는 없을 것 같다.

1. 스크래핑

• 셀레니움을 이용하여 게시글 제목과 링크, 조회수, 댓글 수, 좋아요 수, 게시 날짜 등을 스크래핑한다.
• 검색 키워드 : Selenium, XPath/CSS Selector, sqlite3

2. 알림 보내기

• 내가 원하는 키워드, 조회수, 댓글 수, 좋아요 수로 필터링하여 텔레그램 메신저로 알림을 받는다.
• 검색 키워드 : Python-telegram-bot

3. 자동화하기

• 오라클 클라우드 무료 계정을 이용해서 서버에서 주기적으로 스크래핑을 실행하고 알림을 보낸다.
• 검색 키워드 : Oracle Cloud Free Tier (VM), Ubuntu, Crontab

조금 헤맸던 부분들/세부 내용

• 사실 다 하고 나서 보면 별 것 아닌 것들만 있어서… 정리할게 별로 없다.

1. 스크래핑

• 네이버 카페 게시판 구조가 최근(?), 언제인지 바뀐 것 같다.
• iframe이 무엇인 지 정확히 모르는데, 예전에는 게시판이 iframe 내부에 불러졌던 것 같다.
• 지금은 그렇지 않은데 네이버 카페 크롤링, 네이버 카페 스크래핑 등으로 검색하거나 AI에게 물으면 예전 기준으로 나오는 경우가 있다.
• 결과가 잘 안 나와서 로그인 문제인 줄 알고 삽질을 하다가, 그냥 직접 html 구조 보고 셀레니움으로 스크래핑하니까 해결이 되었다.
• 스크래핑한 정보는 db에 모으고, 30일 보관하도록 한다.
• 조회 수, 댓글 수, 좋아요 수로 필터링하여 진짜 핫딜만 필터링하고, 사용자가 설정한 키워드가 포함된 글을 필터링할 수 있게 한다.

2. 알림 보내기

• 찾아보니 텔레그램이 가장 간편한 것 같다.
• 이 부분은 그렇게 어려운 지점이 없었다.
• 텔레그램 봇 토큰은 코드에 노출되지 않게 해야한다. 안 그러면 나처럼 다시 발급받아야한다.

3. 자동화하기

• 내 컴퓨터를 항상 켜둘 순 없으니까, 대신 항상 켜져있을 서버가 필요하다.
• 오라클 클라우드가 무료로 사용 가능하대서 이걸로 하기로 했다.
• 영어만 가득한 사이트라 거부감이 들 수 있으나 사용법을 잘 정리해둔 글들도 많고, GPT도 잘 알려주니 시키는대로 하면 된다.
• 서버에 우분투를 올리고, 크롬 등 필요한 것들을 설치한 후, 한 시간마다 코드가 돌아가도록 했다.
• 유닉스 수업 들은 걸 써먹으니 좋았다.!

결과

https://github.com/zerocola355ml/naver_cafe_crawler

온라인 리눅스 실습 사이트 + 간단한 리눅스 환경 세팅의 필요성

• 유닉스 수업을 들으면서 실습과 과제를 위해 리눅스를 설치해야했다.
• 아쉽게도 수업에 실습이 없어서 책을 보며 스스로 해야했다.
• 처음에는 교재에 있는대로 가상머신을 깔고 록키 리눅스를 설치했다.
• 그런데 매번 가상 머신을 키는 것이 번거로웠고, 노트북 없이 외출했을 때 태블릿이나 폰으로 간단한 실습을 하고 싶었다.
• 심지어 과제를 하는데 가상 머신의 리눅스에 한글 입력이 안되었고, 붙여넣기도 안되어서 한글로 된 텍스트 예시를 입력하지 못하는 불상사가 생겼다.
• 구글과 AI들의 도움을 받아 반나절 끙끙거렸지만 과제에 주어진 한글을 입력하지 못했다.
• 결국 다른 방법으로 리눅스를 설치하고 홧병이 가라 앉았고, 과제를 금방 끝낼 수 있었다.
• 시행착오의 결과를 정리해본다.

결론 먼저

• 간단한 실습들은 온라인에서 작동하는? 터미널이 있고 퀴즈도 있으니 활용하세요.
• 윈도우에서 가장 간단하게 리눅스를 사용하는 방법은 WSL 우분투를 쓰는 겁니다.

온라인 리눅스 실습 사이트

• 명령어들에 대한 설명 + 곧 바로 쳐볼 수 있는 실습 + 복습 퀴즈 → 잘 외워진다!
• 찾아본 사이트들은 아래와 같습니다.

리눅스 연습 사이트 비교 및 정리

비교

• Linux Survival: 리눅스가 처음이라면 가장 쉽게 시작할 수 있는 대화형 튜토리얼입니다.
  • 이 사이트는 처음부터 끝까지 다 해보았는데, 리눅스 처음할 때 정말 도움이 많이 되었다. 강의 듣는 것 보다 훨씬 낫다.
• Webminal: 실제 터미널 환경에서 직접 명령어를 입력하며 실습하고 싶은 사용자에게 적합합니다.
  • 이건 아직 조금만 해보았는데, vi 편집기 설명과 실습이 정말 잘 되어있다.
• Linux Journey: 리눅스 이론과 시스템 전반에 대한 깊이 있는 지식을 체계적으로 쌓고 싶은 사용자에게 유용합니다.
  • 이건 아직 못해봤다. 나중에 해보고 좋으면 내용을 추가할게요. 명령어 뿐 아니라 리눅스의 역사에 대한 이야기들도 있더라구요.

윈도우에서 리눅스 설치하는 가장 편리한 방법

윈도우에서 리눅스를 쓰는 다양한 방법 비교

윈도우에서 WSL 우분투 설치 방법

wsl --install 하나로 끝입니다.

단계 1: 관리자 권한으로 PowerShell 실행

• 시작 메뉴에서 PowerShell을 검색
• Windows PowerShell 또는 Windows Terminal을 마우스 오른쪽 버튼으로 클릭하고 '관리자 권한으로 실행'을 선택

단계 2: 설치 명령어 입력

• PowerShell 창에 다음 명령어를 입력하고 Enter를 누릅니다.

  wsl --install

  잠깐! 만약 기본 Ubuntu가 아닌 다른 배포판(예: Debian)을 설치하고 싶다면, 먼저 wsl --list --online으로 목록을 확인한 후, wsl --install -d <배포판 이름>을 사용하시면 됩니다.

단계 3: 재부팅

** 단계 4: Ubuntu 초기 설정 (계정 생성) **

• 재부팅 후, Ubuntu 콘솔 창이 자동으로 실행되거나, 시작 메뉴에서 wsl 앱을 실행

• 최초 실행 시, 다음과 같이 계정 설정을 진행합니다.

  1. 사용자 이름(username) 입력 후 Enter
  2. 암호(password) 입력 후 Enter (입력 시 화면에 아무것도 표시되지 않으니 주의)
  3. 암호 재확인(re-type password) 후 Enter

이제 설정이 완료되었으며, 명령어 입력 대기 상태(프롬프트)가 나타나면 WSL2 기반의 Ubuntu 환경을 즉시 사용할 수 있습니다.

** 단계 5: 설치 확인 및 관리 명령어 (선택 사항) **

• 설치된 WSL 버전 확인:

  wsl -l -v

  VERSION 항목에 2가 표시되면 WSL 2로 잘 설치된 것입니다.

• Ubuntu 실행:

  wsl -d Ubuntu

• 모든 WSL 종료:

  wsl --shutdown

• Splay 트리와 기본 연산(zig, zig-zig, zig-zag)에 대해 소개했다.

• zig-zig 연산을 할 때 x-p 회전보다 p-g 회전을 먼저 하는 것에 대한 의문을 제기했다.

• p-g 연산을 먼저하면 아래와 같은 장점이 있음을 구체적인 예시를 통해 확인해보았다.

  • 극단적으로 치우친 경우 트리가 더 균형잡힌다.
  • 접근한 노드의 서브트리가 훨씬 루트에 가깝게 올라온다.

• 잠재함수와 관련 용어를 소개하고 구체적인 예시에서 확인해보았다.

  • size(x): 노드 x의 서브트리에 속한 노드 개수(자신 포함)
  • rank(x) = log₂(size(x)): 로그의 밑은 1보다 크면 얼마이든 상관 없다.
  • 잠재함수 Φ = Σ rank(x): 트리 전체의 “숨은 비용”, 트리가 균형잡히면 작아지고, 치우치면 커진다.
  • 분할상환비용 = 실제 비용(실제 회전 수) + 잠재함수 변화량

  ---

본론

Access Lemma

루트 노드가 root인 트리에서 노드 x를 splay 하는 분할상환비용은 ** 3(rank(root) - 3rank(x)) + 1 ** 이하이다.

• x를 splay 한다는 것은 splay 기본 연산을 반복적으로 적용하여 x를 루트까지 올린다는 것이다.
• 위 결과를 rank 가 아닌 size를 이용해 나타내고, ** big-O** 표기법을 이용하면 분할상환비용이
• O(log(size(root)/size(x)))* 임을 알 수 있다.
• 아래 증명을 시작하기 전에 분할상환비용 = 실제 비용(실제 회전 수) + 잠재함수 변화량 임을 기억하자.

잠재함수 변화량 분석

zig 연산

회전 전                회전 후
----------------------------------------------------
      p                  x'
     / \             / \
    x   C              A'  p'
   / \                 / \
  A   B                 B'   C'

• ** rank(node) ** 는 node 자신을 포함하여 그 아래에 있는 모든 노드의 개수에 로그를 취한 값이다.

• 그런데 A, B, C는 zig 연산 전, 후에 아래에 달린 것?이 그대로임을 알 수 있다.

• 그러니까 p, g만 rank가 변한다.

• 따라서 (잠재함수 변화량 ΔΦ )

• • = rank(x') + rank(p') - rank(x) - rank(p)**
• • = rank(p') - rank(x)**
• • ≤ rank(x') - rank(x) ** 이다.

• 왜냐면, 변화 전 후에 루트 노드의 rank는 일정하며, 트리에서 루트 노드의 rank가 가장 크기 때문이다.

zig-zig 연산

회전 전                          회전 후(올바른 zig-zig)
----------------------------------------------------
          g                              x'
         / \                            / \
        p   D                          A'  p'
       / \                                / \
      x   C                              B'  g'
     / \                                    / \
    A   B                                  C'  D'

• 마찬가지로, 노드 x에 zig-zig 연산을 했을 때 잠재함수 변화량에 대한 부등식을 x에 대한 rank로 나타내보자.

• ΔΦ*

• • = rank(x') + rank(p') + rank(g') - rank(x) - rank(p) - rank(g)**
• • = (rank(p') - rank(p)) + (rank(g') - rank(x))**
• • ≤ 3(rank(x') - rank(x)) - 2 ** 이 되는데 설명이 필요할 것이다.

• 1) 첫번째 등식에서 g, x' 이 루트노드로 ** rank(g) = rank(x') ** 이라 상쇄되어

• ΔΦ*

• • = rank(p') + rank(g') - rank(x) - rank(p) **

• 2) ** rank(p), rank(p') ** 을 ** rank(x), rank(x') ** 으로 표현하자. 자식의 rank 값이 더 작으므로 ** rank(x) ≤ rank(p), rank(p') ≤ rank(x') ** 이므로

• ΔΦ*

• • ≤ rank(x') + rank(g') - rank(x) - rank(x) **
• • = rank(x') + rank(g') - 2rank(x) **

• 3) ** rank(g') ** 을 ** rank(x') ** 로 표현하자. 먼저, 산술기하 부등식에 의해

• • log₂a + log₂b ≤ 2log₂((a+b)/2)** 임을 알 수 있다. 그런데 ** size(x) + size(g') ≤ size(x') **이므로
• • rank(x) + rank(g') = log₂(size(x)) + log₂(size(g')) ≤ 2log₂((size(x) + size(g') / 2) ≤ 2log₂(size(x') / 2) = 2log₂(size(x')) - 2 = 2rank(x') - 2

• * 따라서 ** rank(g') ≤ 2rank(x') - rank(x) - 2** 이고 이를 2)에서 구한 식에 적용하면

• ΔΦ*

• • ≤ rank(x') + rank(g') - 2rank(x) ≤ 3rank(x') - 3rank(x) - 2

• *

zig-zag 연산

은 zig-zig과 비슷하므로 생략하겠다. 결과는 마찬가지로 ** ΔΦ ≤ 3rank(x') - 3rank(x) - 2**

splay 분할상환비용

zig의 분할상환비용

• zig은 회전 1회이므로 실제 비용 1
• zig의 ** ΔΦ ≤ rank(x') - rank(x)**
• zig의 **분할상환비용 ≤ 1 + rank(x') - rank(x) ≤ 1 + 3(rank(x') - rank(x))
• *

zig-zig의 분할상환비용

• zig-zig은 회전 2회이므로 실제 비용 2
• zig-zig의 ** ΔΦ ≤ 3rank(x') - 3rank(x) - 2**
• zig-zig의 **분할상환비용 ≤ 3(rank(x') - rank(x))
• *

zig-zag의 분할상환비용

• zig-zig과 마찬가지로
• zig-zag의 **분할상환비용 ≤ 3(rank(x') - rank(x))
• *

결과적으로 spaly 분할상환비용

• x노드를 루트까지 올리기 위해 zig, zig-zig, zig-zag을 반복적으로 적용할 때,
• 이번 스텝에서 rank(x')이 다음 스텝에서의 rank(x)가 된다.
• 따라서 중간 항들은 모두 소거가 되고,
• x를 루트까지 올리기 위한 분할상환비용 즉,
• 각 스텝에서 연산의 분할상환비용의 합 은
• ** 3(rank(root)-rank(x)) + 1** 이하이다.

증명을 완료했다... 다 쓰고 검색해보니까 Velog도 latex 문법으로 수식을 쓸 수 있구나...

다음에는

• splay 트리의 다른 재밌는 성질들을 알아볼까?
• B트리 계열의 트리에 대해 살펴볼까?
• 외울게 많아 어려운 UNIX, 리눅스를 어떻게 공부하면 좋을지 고민해볼까?

참고 문헌

• Sleator, D. D., & Tarjan, R. E. (1985). Self-adjusting binary search trees. Journal of the ACM (JACM), 32(3), 652–686.

서론

의문

Splay 트리의 zig-zig 연산은 x-p 회전보다 p-g 회전을 먼저 하는데, 그 이유는 뭘까? (접근하는 노드를 x, 그 부모를 p, p의 부모 즉, x의 조부모를 g라 하자)

사실 x-p 회전 → p-g 회전으로 해도 결국 x는 루트로 잘 올라간다. 그래서 “직관적으로 어색한 p-g 회전을 먼저 하는 이유는 무엇일까?” 하는 의문이 든다.

GPT, Perplexity, Gemini 등 여러 AI에게 물어보고 검색도 해보았는데 명쾌한 답을 듣지 못했고, 나름대로 이해한 것을 정리해본다. (지금 생각해보면, 얘네가 최선의 답을 해주었고, 그 당시 나의 이해가 부족했다.)

Splay Tree란 무엇인가?

→ 이 글의 핵심인 zig-zig 연산의 순서가 왜 그러한가에 대해 궁금하시면 skip하고 본론으로 가세요.

Splay Tree 특징

접근한 노드를 항상 루트로 끌어올림(Splaying, 한번 접근한 노드는 다음에 또 접근할 확률이 높다는 생각)

최근에 접근한 노드 주변을 빠르게 접근 가능하게 최적화

명시적 균형 정보를 저장하지 않아도 amortized O(log n) 성능 보장

Splay Tree의 회전

Splay Tree에서 루트까지 노드를 올릴 때 사용하는 회전 연산은 크게 3가지

노드를 zig-zig 또는 zig-zag 회전으로 루트 또는 루트 바로 아래 올때까지 올린다.

루트 바로 아래에 위치하게되면 zig 연산을 해서 루트로 올린다.

회전 원칙은 목표 노드가 위로 올라오게, 이진 검색 트리 구조가 유지되도록 하면 된다.

1. Zig:

x가 루트 바로 아래에 있는 경우

한 번 회전으로 x를 루트로 올림

** 예시 **

** zig 회전(x-p) 전 **

      p
     / \
    x   C
   / \
  A   B

** zig 회전(x-p) 후 **

      x
     / \
    A   p
       / \
      B   C

2. Zig-Zig:

x와 p가 같은 방향으로 내려가 있을 때 (x가 왼쪽 자식의 왼쪽 자식 OR 오른쪽 자식의 오른쪽 자식)

p-g 회전 → x-p 회전 순서로 루트로 올림

** 예시 **

** zig-zig 회전 전 **

          g
         / \
        p   D
       / \
      x   C
     / \
    A   B

** zig-zig step1: p-g 회전 **

          p
         / \
        x   g
       / \ / \
      A  B C  D

** zig-zig step2: x-p 회전 **

          x
         / \
        A   p
           / \
          B   g
             / \
            C   D

3. Zig-Zag:

x와 p가 반대 방향으로 내려가 있을 때 (x가 왼쪽 자식의 오른쪽 자식 OR 오른쪽 자식의 왼쪽 자식)

x-p 회전 → x-g 회전 순서로 루트로 올림

** 예시 **

** zig-zag 회전 전**

          g
         / \
        p   D
       / \
      A   x
         / \
        B   C

** zig-zag step1: x-p 회전 **

          g
         / \
        x   D
       / \
      p   C
     / \
    A   B

** zig-zag step2: x-g 회전**

          x
         / \
        p   g
       / \ / \
      A  B C  D

본론

직관적 이해

Splay 트리의 목적은 단순히

• 접근한 노드를 루트로 끌어올리는 것뿐아니라
• x의 서브트리 깊이를 줄이는데 유리함
• x 주변 노드까지 가는 경로가 많이 치우친 경우 이를 완화해줌

p-g 회전을 먼저해야 아래의 목적도 달성할 수 있다.

p-g 회전을 먼저 하면 유리함

• x-p 회전 후 x-g 회전 하는 경우: 두 번의 회전을 하면 x는 2레벨 올라오지만, x의 서브트리 중 올라가지 못하는 것이 있을 수 있다.
• p-g 회전 후 x-p 회전 하는 경우: 두 번의 회전을 하면 x는 2레벨 올라가고, x의 서브트리는 적어도 1레벨 올라간다. zig-zag 역시 마찬가지다. 따라서 x를 루트까지 올리면 x의 서브트리는 그 레벨이 대략 절반이 된다.

즉, p-g 회전을 먼저해야 x의 서브트리 깊이를 줄이는데 유리하다.

p-g 회전 후 x-p 회전

회전 전                          회전 후(올바른 zig-zig)
----------------------------------------------------
          g                              x
         / \                            / \
        p   D                          A   p
       / \                                / \
      x   C                              B   g
     / \                                    / \
    A   B                                  C   D

x의 서브 트리 A, B는 각각 2레벨, 1레벨 올라갔다.

x-p 회전 후 x-g 회전

회전 전                          회전 후(잘못된 zig-zig)
-------------------------------------------------------
          g                              x
         / \                            / \
        p   D                          A   g
       / \                                / \
      x   C                              p   D
     / \                                / \
    A   B                              B   C

x의 서브 트리 A, B는 각각 2레벨, 0레벨 올라갔다.

예시

            7
           /
          6
         /
        5
       /
      4
     /
    3
   /
  2
 /
1

위 트리에서 1을 노드까지 올린다고 해보자.

잘못된 zig-zig(x-p 회전 후 x-g 회전) 적용

          1
           \
            7
           /
          6
         /
        5
       /
      4
     /
    3
   /
  2

1이 루트로 가긴 하지만, 치우침이 별로 개선되지 않고, 1의 서브트리는 여전히 깊다.

올바른 zig-zig(p-g 회전 후 x-p 회전) 적용

    1
     \
      6
     / \
    4   7
   / \
  2   5
   \
    3

1이 루트로 가고, 치우침이 개선되고, 1의 서브트리 깊이가 적어진다. p-g 회전을 먼저하고 x-p 회전을 하면 7, 5, 3 노드처럼 삐죽 삐죽한 구조가 생기는데, 이게 치우침을 개선해준다.

그래서 그게 진짜 더 좋은거야?

그러면 이제, 의문이 든다. 뭐 대충 말고 진짜 더 좋은게 맞냐? p-g 회전을 먼저했을 때 불리한 노드도 있을 수 있고, 치우침이 완화가 약한 경우도 있을 수 있지 않냐? 사실 그렇다. 그럼에도 p-g 회전 먼저하는게 정말로 더 유리해요. 를 설명하려면 결국 Splay Tree가 amortized O(log n) 임을 보이면 된다.

Access Lemma와 잠재함수

Splay Tree의 놀라운 점은 명시적 높이 제한이 없음에도 불구하고 amortized O(log n) 성능을 보장한다는 것이다.

이를 증명하는 핵심은 Access Lemma와 잠재함수다.

용어 정리

• size(x): 노드 x의 서브트리에 속한 노드 개수(자신 포함)
• rank(x) = log₂(size(x)): 로그의 밑은 1보다 크면 얼마이든 상관 없다.
• 잠재함수 Φ = Σ rank(x): 트리 전체의 “숨은 비용”

예시1: 균형 잡힌 트리

        7
       / \
      3   3
     / \ / \
    1  1 1  1

(편의상 노드의 값이 아닌 노드의 size를 표기함) 

이때, size의 합은 7+(3+3)+(1+1+1+1)=17이고 rank의 합 Φ은 log₂(7×3×3×1×1×1×1)=log₂63이다.

예시2: 치우친 트리

            7
           /
          6
         /
        5
       /
      4
     /
    3
   /
  2
 /
1
(편의상 노드의 값이 아닌 노드의 size를 표기함) 

이때, size의 합은 7+6+5+4+3+2+1=28이고 rank의 합 Φ은 log₂(7×6×5×4×3×2×1)=log₂5040이다. 치우친 트리일수록 잠재 함수 Φ의 값이 커지는 것을 알 수 있다.

잠재함수

잠재함수는 마치 ** 대출 ** 같다.

• 현재 트리가 얼마나 균형잡혀있는 지 측정하는 함수이다
• 치우칠수록 증가하고 균형잡힐수록 감소한다.
• 트리가 매우 치우쳐있고 깊이 있는 노드를 탐색해야하는 경우, 이 노드를 루트로 올리기는데 많은 회전(실제 비용)이 발생한다.
• 하지만 이 과정에서 트리가 균형이 잡히면서 잠재함수(대출)이 감소하여 회전 비용을 상쇄할 수 있다.
• 따라서 분할상환비용 = 실제 비용(실제 회전 수) + 잠재함수 변화량 으로 정의된다.

예시

** 초기 상태 **

            7
           /
          6
         /
        5
       /
      4
     /
    3
   /
  2
 /
1

잠재함수 Φ = log₂(7×6×5×4×3×2×1)=log₂5040 여기에서 zig-zig을 한번 해보자.

** zig-zig 1회 **

            7
           /
          6
         /
        5
       /
      4
     /
    1
     \
      2
       \
        3

이 경우 잠재함수 Φ' = log₂(7×6×5×4×3×2×1)이며 회전은 두 번 했다(p-g, x-p)

따라서 잠재함수 변화량(Φ'-Φ)은 0이고, 분할상환비용 = 2 + 0

** zig-zig 2회**

            7
           /
          6
         /
        1
         \
          4
         / \
        2   5
        \
         3

이 경우 잠재함수 Φ'' = log₂(7×6×5×4×2×2×1)이며 회전은 두 번

따라서 잠재함수 변화량(Φ''-Φ')은 log₂(2/3)이고, 분할상환비용 = 2 + log₂(2/3)이다. 잠재함수 변화량이 음수인데, 트리가 더 균형잡히게 변했다는 뜻이다.

** zig-zig 3회**

    1
     \
      6
     / \
    4   7
   / \
  2   5
   \
    3

이 경우 잠재함수 Φ''' = log₂(7×6×4×1×2×1×1)이며 회전은 두 번 따라서 잠재함수 변화량변화량(Φ'''-Φ'')은 log₂(1/10)이고, 분할상환비용 = 2 + log₂(1/10)이다. 마찬가지로 잠재함수 변화량이 음수, 트리가 더 균형잡히게 변했다.

** 모두 합치면 ** 1을 루트로 끌어올리기 전인 초기 상태와 마지막 상태를 비교하면, 회전은 6번 일어났고, 잠재함수 변화량을 모두 더하면 0+ log₂(2/3)+log₂(1/10) 이다.

따라서 모든 분할상환비용을 더해주면 6 + log₂(2/3)+log₂(1/10)이다.

Access Lemma 증명 개요(아이디어)

분할상환비용 = 실제 비용(실제 회전 수) + 잠재함수 변화량

• 잠재함수 변화량이 작다면, 실제 회전이 많은 경우(치우친 트리)가 있더라도 모든 분할상환비용을 더할 때 이를 만회할 수 있다.
• 잠재함수를 계산할 때는 각 노드의 서브트리 개수를 세면 된다.
• 그런데 비교 전 후의 달라진 부분만 비교 하면 변화량을 알 수 있다.
• 그렇다면 zig, zig-zig, zig-zag의 경우로 케이스를 나누어, 서브트리가 달라진 부분을 비교하면 잠재함수 변화량을 계산할 수 있고, 적당한 부등식을 세워 상한을 잡을 수 있다.

사용되는 수학적 아이디어

• 적당한 부등식을 잡을 때는 루트의 rank가 다른 노드의 rank보다 크거나 같다는 자명한 사실이 사용된다.
• 고등학교 수열 단원에서 부분 분수 기억나는가? 쭉 더하면 제일 앞, 뒤만 남고 서로 상쇄되어 사라지던 것. 잠재함수의 변화량을 더할 때 이렇게 쭉 상쇄되는 성질(텔레스코핑)을 이용한다.
• 로그의 합에서 부등식을 만들 때 산술 평균, 기하 평균을 비교한 a+b >= 2√ab 부등식이 사용된다.

다음에는

• 실제 Access Lemma를 증명을 살펴보자.
• 그 전에, 이제 다시 zig-zig 회전 전 후 그림을 봐보자.
• 잠재함수 변화량을 계산하려면, rank가 달라진 노드가 누구인지 쨰려보며 된다.
• 그게 보이면, 이제 약간의 수학적 식 조작만 들어가면 Access Lemma를 증명할 수 있다.

회전 전                              zig-zig 회전 후
----------------------------------------------------
          g                              x
         / \                            / \
        p   D                          A   p
       / \                                / \
      x   C                              B   g
     / \                                    / \
    A   B                                  C   D

참고 문헌

• Sleator, D. D., & Tarjan, R. E. (1985). Self-adjusting binary search trees. Journal of the ACM (JACM), 32(3), 652–686.

** 시간표 자동 생성 기능 개선 **

• 자동 배치 성능을 개선했다!
• 기존에는 그냥 OR-Tools의 CP-SAT Solver를 그대로 사용했다
• 그런데 경험적으로 1학년 과목을 미리 수동으로 고정하고 자동 배치를 돌리면 더 나은 결과가 나온다.
• 그 이유는 1학년의 경우 과목의 선택권 없이 모두 같은 과목을 듣기 때문에 어느 과목도 하나의 슬롯에 들어갈 수 없다.
• 따라서 무조건 서로 피해야하고, 이 과목들을 미리 고정해두면, 연산을 줄일 수 있다.

최대 클릭 기반 최적화

• 아 그렇다면, 전체 과목을 분석해서, 어느 두 과목도 한 슬롯에 들어가지 못하는 과목들이 있다면, 그 과목을 우선 배정하면 좋지 않을까?
• 그런 과목들을 모았을 때 가장 큰 집합을 찾아야겠다.
• 아, 이거 그래프에서 최대 클릭 수라고 했던 것 같은데!
• 그래서 최대 클리 수 탐색하는 알고리즘을 찾아서 해당 과목들을 먼저 고정해버리고 자동 배치하도록 하였다.

어라 성능이?

• 최대 클릭 수 과목을 고정하고 OR-Tools CP-SAT Solver 를 돌리니까 성능이 더 나빠졌다.
• 왜 그런지 생각해보니, 미리 고정할 때, 어떤 슬롯에 고정하는 지가 되게 중요한 부분인데, 임의로 고정하다보니, Solver가 제 성능을 발휘하지 못했다.
• 그러니까 사전에 고정한 것이 힌트가 아닌 제약이 되어 버린 것.
• 그래서 사전 배치를 필요하면 수정할 수 있게 하고, 초기의 힌트로만 제공하고 Solver를 돌렸다
• ** 성능이 좋아졌다!**
• 사용자가 학생별로 하루에 치르는 최대 과목 수와 하루에 치르는 어려운 과목의 수의 최댓값을 설정한다.(테스트 예시는 둘다 2개 과목)
• 이때, 해당 값을 가지는 학생들의 총합이 최적화해야할 값으로 적을수록 좋다.
• 각각 10번씩 돌렸는데 기존에는 908명, 개선 후에는 851명으로 약 6% 개선되었다.
• 퍼센티지가 엄청나진 않지만, 이미 좋은 툴을 직접 개선할 수 있다는게 신기하다.

앞으로 할 것

• 자동 생성 기능 개선(목적함수 우선순위 가중치 방식 -> 사전식), 뭐가 더 좋을까?
• 프론트엔드 데이터 로드 방식 백엔드 중심 API로 바꾸기
• 시간표 생성 페이지 접속 시 필수 설정 안했으면 메세지 후 리디렉트
• 각종 조건의 출력 데이터 형식 일원화하기
• 듣기평가 커스텀시 시간표 생성에 반영되지 않는 문제 해결하기
• 선택 설정들 기본 값은 빈 값으로 바꾸고, 사용자가 원하면 필수 설정에서 자동 생성하는 기능, 추가로 편집할 수 있는 기능
• 학생 충돌 추가시 2개 말고 n개를 동시에 충돌로 입력할 수 있게 하기
• 특정 과목 불가한 슬롯 설정 기능 추가하기
• 과목 정보 넣으면 반영해서 듣기평가 충돌, 교사 충돌 자동으로 넣을 지, 수동이 편할 지 고민
• 목적 함수 작동 방식 바꾸기(가중치 없이 합 -> 우선 순위 방식)
• 시험 시간표 작성 시 고려 사항 우선순위 사용자 지정 기능 추가하기
• 시험 시간표를 사용자가 원하는대로 수정하는 기능 추가하기
• 시험 장소 배치 시 듣기 평가 한 층 따로 쓰게 하는 옵션
• 시험 감독 자동 배정 기능 추가하기

** 시간표 자동 생성 기능 개선 **

• 사용자가 시간표에 배치할 경우 자동으로 저장되게 개선함
• 사용자가 일부 과목 미리 배치 후, 자동 배치 기능 적용할 수 있게 개선함
• 자동 배치 후, 일부 수정할 수 있도록 개선함
• 자동 생성 시, (속도)-(균형)-(고품질) 선택하게 하기

앞으로 할 것

• 자동 생성 옵션 드롭다운이 시간표에 가리는 문제 해결
• 자동 생성 기능 개선(추가된 조건들 반영 잘 되었는지 check)
• 자동 생성 기능 개선(목적함수 우선순위 가중치 방식 -> 사전식), 뭐가 더 좋을까?
• 자동 생성 기능 개선(OR-Tools 모델에 데이터 전처리(휴리스틱)해서 품질 향상)
• 프론트엔드 데이터 로드 방식 백엔드 중심 API로 바꾸기
• 시간표 생성 페이지 접속 시 필수 설정 안했으면 메세지 후 리디렉트
• 각종 조건의 출력 데이터 형식 일원화하기
• 듣기평가 커스텀시 시간표 생성에 반영되지 않는 문제 해결하기
• 선택 설정들 기본 값은 빈 값으로 바꾸고, 사용자가 원하면 필수 설정에서 자동 생성하는 기능, 추가로 편집할 수 있는 기능
• 학생 충돌 추가시 2개 말고 n개를 동시에 충돌로 입력할 수 있게 하기
• 특정 과목 불가한 슬롯 설정 기능 추가하기
• 과목 정보 넣으면 반영해서 듣기평가 충돌, 교사 충돌 자동으로 넣을 지, 수동이 편할 지 고민
• 목적 함수 작동 방식 바꾸기(가중치 없이 합 -> 우선 순위 방식)
• 시험 시간표 작성 시 고려 사항 우선순위 사용자 지정 기능 추가하기
• 시험 시간표를 사용자가 원하는대로 수정하는 기능 추가하기
• 시험 장소 배치 시 듣기 평가 한 층 따로 쓰게 하는 옵션
• 시험 감독 자동 배정 기능 추가하기

** 시간표 자동 생성 기능 개선 **

• 처음에 자동으로 시간표 생성하는 기능을 만들었고, 이때는 많은 부분이 하드코딩되어 있었고 누락된 제약 조건들이 있었다.
• 이 부분들을 모두 개선하였다.
• 최근에 개발한 웹에서 사용자가 그리드에 배치할 때와 같은 제약조건, 설정값을 불러와서 자동 생성하도록 개선하였다.

앞으로 할 것

• 자동 생성 기능 개선(추가된 조건들 반영 잘 되었는지 check)
• 자동 생성 기능 개선(일부 과목 미리 배치된 경우 반영하기)
• 자동 생성 기능 개선(목적함수 우선순위 가중치 방식 -> 사전식)
• 자동 생성 기능 개선(OR-Tools 모델에 데이터 전처리(휴리스틱)해서 품질 향상)
• 프론트엔드 데이터 로드 방식 백엔드 중심 API로 바꾸기
• 시간표 생성 페이지에 자동생성 기능 연동
• 자동 생성 후 편집할 수 있게
• 드래그 앤 드롭으로 사용자가 배치한 시간표 데이터 저장하기
• 기존에 있던 자동생성과 신규 페이지 통합
• 시간표 생성 페이지 접속 시 필수 설정 안했으면 메세지 후 리디렉트
• 각종 조건의 출력 데이터 형식 일원화하기
• 듣기평가 커스텀시 시간표 생성에 반영되지 않는 문제 해결하기
• 선택 설정들 기본 값은 빈 값으로 바꾸고, 사용자가 원하면 필수 설정에서 자동 생성하는 기능, 추가로 편집할 수 있는 기능
• 학생 충돌 추가시 2개 말고 n개를 동시에 충돌로 입력할 수 있게 하기
• 특정 과목 불가한 슬롯 설정 기능 추가하기
• 과목 정보 넣으면 반영해서 듣기평가 충돌, 교사 충돌 자동으로 넣을 지, 수동이 편할 지 고민
• 목적 함수 작동 방식 바꾸기(가중치 없이 합 -> 우선 순위 방식)
• 시험 시간표 작성 시 고려 사항 우선순위 사용자 지정 기능 추가하기
• 시험 시간표를 사용자가 원하는대로 수정하는 기능 추가하기
• 시험 장소 배치 시 듣기 평가 한 층 따로 쓰게 하는 옵션
• 시험 감독 자동 배정 기능 추가하기

** 시간표 생성 페이지 **

• 시간표 그리드와 학생 부담 패널 표 너비 맞추기

데이터 로드 방식 개선이 필요하다.

• 사용자가 직접 그리드에 과목을 배치할 때 과목 배치 가능성을 따지는 것은 프론트엔드
• 자동생성을 눌렀을 때 제약 조건을 추가하는 것은 백엔드에서 데이터를 읽고 있다.
• 한 프로젝트에서 동일한 JSON 데이터 파일을 두 가지 방식으로 로드하고 있다.
• 프론트엔드에서는 JavaScript fetch API로 파일을 직접 읽어온다.
• 브라우저에서 바로 처리하므로 단순하고 빠르지만, 교사나 학생 정보 같은 민감 데이터가 포함되어 있어서 위험 요소가 될 가능성이 있다.
• 백엔드에서는 Python DataLoader 클래스를 통해 같은 파일들을 로드한다.
• 같은 기능을 하는 중복 로직이 있다.
• 느려지더라도 백엔드 중심 API로 개선해야할까?

앞으로 할 것

• 프론트엔드 데이터 로드 방식 백엔드 중심 API로 바꾸기
• 자동 생성 기능 개선(추가된 조건들 반영)
• 자동 생성 기능 개선(OR-Tools 모델에 데이터 전처리(휴리스틱)해서 품질 향상)
• 자동 생성 기능 개선(일부 과목 미리 배치된 경우 반영하기)
• 시간표 생성 페이지에 자동생성 기능 연동
• 자동 생성 후 편집할 수 있게
• 드래그 앤 드롭으로 사용자가 배치한 시간표 데이터 저장하기
• 기존에 있던 자동생성과 신규 페이지 통합
• 시간표 생성 페이지 접속 시 필수 설정 안했으면 메세지 후 리디렉트
• 각종 조건의 출력 데이터 형식 일원화하기
• 듣기평가 커스텀시 시간표 생성에 반영되지 않는 문제 해결하기
• 선택 설정들 기본 값은 빈 값으로 바꾸고, 사용자가 원하면 필수 설정에서 자동 생성하는 기능, 추가로 편집할 수 있는 기능
• 학생 충돌 추가시 2개 말고 n개를 동시에 충돌로 입력할 수 있게 하기
• 특정 과목 불가한 슬롯 설정 기능 추가하기
• 과목 정보 넣으면 반영해서 듣기평가 충돌, 교사 충돌 자동으로 넣을 지, 수동이 편할 지 고민
• 목적 함수 작동 방식 바꾸기(가중치 없이 합 -> 우선 순위 방식)
• 시험 시간표 작성 시 고려 사항 우선순위 사용자 지정 기능 추가하기
• 시험 시간표를 사용자가 원하는대로 수정하는 기능 추가하기
• 시험 장소 배치 시 듣기 평가 한 층 따로 쓰게 하는 옵션
• 시험 감독 자동 배정 기능 추가하기

** 시간표 생성 페이지 **

• 학생 부담 표시 패널 추가
• 날짜별 배치 가능한지 판단하는거랑 학생 부담 분석 패널에 중복 코드 리팩토링
• 해당 슬롯에 배치 불가한 경우, 해당 날짜에 배치 불가한 경우 시각적 피드백 분리

앞으로 할 것

• 시간표 그리드와 학생 부담 패널 표 너비 맞추기
• 자동 생성 기능 개선(추가된 조건들 반영)
• 자동 생성 기능 개선(OR-Tools 모델에 데이터 전처리(휴리스틱)해서 품질 향상)
• 자동 생성 기능 개선(일부 과목 미리 배치된 경우 반영하기)
• 시간표 생성 페이지에 일부 과목 배치 후 자동 생성기능
• 시간표 생성 페이지에 자동생성 기능 연동
• 자동 생성 후 편집할 수 있게
• 드래그 앤 드롭으로 사용자가 배치한 시간표 데이터 저장하기
• 기존에 있던 자동생성과 신규 페이지 통합
• 시간표 생성 페이지 접속 시 필수 설정 안했으면 메세지 후 리디렉트
• 각종 조건의 출력 데이터 형식 일원화하기
• 듣기평가 커스텀시 시간표 생성에 반영되지 않는 문제 해결하기
• 선택 설정들 기본 값은 빈 값으로 바꾸고, 사용자가 원하면 필수 설정에서 자동 생성하는 기능, 추가로 편집할 수 있는 기능
• 학생 충돌 추가시 2개 말고 n개를 동시에 충돌로 입력할 수 있게 하기
• 특정 과목 불가한 슬롯 설정 기능 추가하기
• 과목 정보 넣으면 반영해서 듣기평가 충돌, 교사 충돌 자동으로 넣을 지, 수동이 편할 지 고민
• 목적 함수 작동 방식 바꾸기(가중치 없이 합 -> 우선 순위 방식)
• 시험 시간표 작성 시 고려 사항 우선순위 사용자 지정 기능 추가하기
• 시험 시간표를 사용자가 원하는대로 수정하는 기능 추가하기
• 시험 장소 배치 시 듣기 평가 한 층 따로 쓰게 하는 옵션
• 시험 감독 자동 배정 기능 추가하기

** 시간표 생성 페이지 **

• 우선 순위 휴리스틱 함수 버그 수정(충돌 횟수 계산 시, 학생 충돌 누락되던 것 수정)
• 우선 순위 휴리스틱 함수 버그 수정(학년별 같은 과목으로 설정했을 때, 학생 충돌 누락되던 것 수정)
• 과목 배치 화면에서 과목별 카드에 수강 인원 표시 추가
• 과목 배치 가능 여부 함수 버그 수정(학년별 같은 과목으로 설정했을 때 학생 충돌 누락 버그)

앞으로 할 것

• 하루 최대 과목 수 설정되어 있다면, 실시간으로 날짜별 하루 응시 과목 수 분포 띄워주면 좋을 듯
• 드래그 앤 드롭으로 사용자가 배치한 시간표 데이터 저장하기
• 일부 과목 배치 후 자동 생성기능
• 기존에 있던 자동생성과 신규 페이지 통합
• OR-Tools 모델에 데이터 전처리(휴리스틱)해서 효율 높이기
• 시간표 생성 함수에 추가 설정들 반영하기
• 시간표 생성 페이지 접속 시 필수 설정 안했으면 메세지 후 리디렉트
• 일부 배정해두고 나머지 자동 생성하는 기능
• 시간표 생성 페이지에 자동생성 기능 연동
• 각종 조건의 출력 데이터 형식 일원화하기
• 듣기평가 커스텀시 시간표 생성에 반영되지 않는 문제 해결하기
• 선택 설정들 기본 값은 빈 값으로 바꾸고, 사용자가 원하면 필수 설정에서 자동 생성하는 기능, 추가로 편집할 수 있는 기능
• 학생 충돌 추가시 2개 말고 n개를 동시에 충돌로 입력할 수 있게 하기
• 특정 과목 불가한 슬롯 설정 기능 추가하기
• 과목 정보 넣으면 반영해서 듣기평가 충돌, 교사 충돌 자동으로 넣을 지, 수동이 편할 지 고민
• 목적 함수 작동 방식 바꾸기(가중치 없이 합 -> 우선 순위 방식)
• 시험 시간표 작성 시 고려 사항 우선순위 사용자 지정 기능 추가하기
• 시험 시간표를 사용자가 원하는대로 수정하는 기능 추가하기
• 시험 장소 배치 시 듣기 평가 한 층 따로 쓰게 하는 옵션
• 시험 감독 자동 배정 기능 추가하기

** 시간표 생성 페이지 **

• 어떤 과목을 먼저 배치하면 좋을지 판단하는 휴리스틱 함수를 만들었다.
• 위 함수는 다른 과목과 충돌하는 횟수, 사용 가능한 슬롯 수, 어려운 과목 여부, 시험 시간을 고려하여 만들었다.
• 이를 이용하여 수동으로 배치하는 사용자에게 지금 어떤 과목을 우선 배치하는 것이 좋을 지 알려주도록 했다.
• 추후 이 함수를 이용하여 OR-Tools 모델 생성 전 우선순위를 처리해서 데이터를 넣어주면 더 고품질의 시간표가 나오지 않을까?

앞으로 할 것

• 우선 순위 휴리스틱 함수 충돌 과목 개수 점검
• 과목 배치 화면에서 과목별 리스트에 수강 인원도 나오면 좋겠다
• 하루 최대 과목 수 설정되어 있다면, 실시간으로 날짜별 하루 응시 과목 수 분포 띄워주면 좋을 듯
• 드래그 앤 드롭으로 사용자가 배치한 시간표 데이터 저장하기
• 일부 과목 배치 후 자동 생성기능
• 기존에 있던 자동생성과 신규 페이지 통합
• OR-Tools 모델에 데이터 전처리(휴리스틱)해서 효율 높이기
• 시간표 생성 함수에 추가 설정들 반영하기
• 시간표 생성 페이지 접속 시 필수 설정 안했으면 메세지 후 리디렉트
• 일부 배정해두고 나머지 자동 생성하는 기능
• 시간표 생성 페이지에 자동생성 기능 연동
• 각종 조건의 출력 데이터 형식 일원화하기
• 듣기평가 커스텀시 시간표 생성에 반영되지 않는 문제 해결하기
• 선택 설정들 기본 값은 빈 값으로 바꾸고, 사용자가 원하면 필수 설정에서 자동 생성하는 기능, 추가로 편집할 수 있는 기능
• 학생 충돌 추가시 2개 말고 n개를 동시에 충돌로 입력할 수 있게 하기
• 특정 과목 불가한 슬롯 설정 기능 추가하기
• 과목 정보 넣으면 반영해서 듣기평가 충돌, 교사 충돌 자동으로 넣을 지, 수동이 편할 지 고민
• 목적 함수 작동 방식 바꾸기(가중치 없이 합 -> 우선 순위 방식)
• 시험 시간표 작성 시 고려 사항 우선순위 사용자 지정 기능 추가하기
• 시험 시간표를 사용자가 원하는대로 수정하는 기능 추가하기
• 시험 장소 배치 시 듣기 평가 한 층 따로 쓰게 하는 옵션
• 시험 감독 자동 배정 기능 추가하기