![\"알고리즘의](\"/img/bidrum/controller-algorithm.png\")
문득 장구를 이용한 리듬 게임을 만들고 싶었다. 태고의 달인도 있는데 장구의 달인이 안 될 이유가 있을까? 그래서 군대 있을 때 계속 장구 게임을 상상만 하다가 복학하고 3학년 2학기에 캡스톤디자인 과목을 듣게 됐다.
\n3학년 2학기 캡스톤디자인 과목에서 게임 아이디어를 제시했지만, 다른 팀원들은 리스크가 너무 크다고 반대했다. 지금 막 개강했는데 하드웨어 개발부터 시작하면 십중팔구 프로젝트가 망할 것이라는 지적이였다. 반박하기에는 너무나도 맞는 말이였다. 그래서 그냥 받아들이고 "알고모여"라는 웹 어플리케이션 프로젝트를 하게 됐다. 의외로 교수님의 평가가 계속 호평이여서 손쉽게 A+를 받았다.
\n중앙대학교는 캡스톤디자인을 2번 해야 졸업이 가능하다. 그래서 4학년 1학기에도 캡스톤디자인을 해야 했는데, 이때 게임 아이디어를 다시 꺼내고 싶었다. 그러나 하드웨어도 없이 빈손으로 아이디어를 꺼낸다면 또다시 팀원들로부터 리스크 우려를 받을 것 같았다. 그래서 일단 프로토타이핑을 해서 설득해야 되겠단 판단이 들었다. 판단이 이루어졌으면 바로 실천해야 하지 않겠는가? 바로 당근마켓으로 45,000원짜리 어린이 장구를 샀고, 곧이어 아두이노랑 쿠킹호일, 그리고 몇가지 부품을 구매했다.
\n내가 만드는 게임은 단순히 타격 여부만을 인식하지 않는다. "어떤 채로 어떤 면이 타격됐는가"를 인식한다. 즉, 다시 말해 열편으로 궁편을 친다면 "궁편이 타격됐다"라는 정보가 아닌 "열편으로 궁편이 타격됐다"라는 정보가 인식된다.
\n이를 구현하려면 채에도 센서가 있어야 된다. 그리고 이 센서는 게임 본체랑 연결되어야 한다. 어떻게 연결한 것인가? 무선과 유선 두가지 방법이 있다.
\n무선과 유선 각 두 가지 방법의 장단점은 다음과 같다.
\n| \n | 무선 | \n유선 | \n
|---|---|---|
| 장점 | \n선이 걸리지 않음 | \n정확도가 매우 높고 딜레이가 낮음 | \n
| 단점 | \n너무 낮은 정확도 및 높은 딜레이 | \n선이 걸리적거림 | \n
무선 통신은 정확도가 너무 낮다는 단점이 있다. 무선으로 채의 위치를 측정한다고 가정해보자. Inpixion의 자료에서의 무선 위치 측정 시스템의 정확도와 레어턴시는 다음과 같다.
\n| \n | UWB | \nChirp (CSS) | \nBLE | \nWi-Fi | \n
|---|---|---|---|---|
| 정확도 | \n10~50 cm | \n1~2m | \n< 5 m | \n10 m | \n
| 레이턴시 | \n< 1 ms | \n< 1 ms | \n3~5s | \n3~5s | \n
정확도가 너무 낮아서 무선 위치 측정 시스템은 쓸 수가 없다. 블루투스와 와이파이는 레이턴시때문에 리듬게임 컨트롤러로 쓸 수조차 없다.
\n'그렇다면 무선이되 다른 방법을 쓰면 되는 것 아닌가?'라는 생각이 들 수도 있는데, 내 머리로는 그렇게 할 수 있는 방법이 딱히 떠오르지 않았다. 그래서 그냥 유선으로 연결하기로 하고, 걸리적거리는 문제는 나중에 해결하기로 했다.
\n자, 이제 유선으로 채의 종류를 인식하기로 했다. 장구는 두 개의 채와 두 개의 접촉면이 있다. 이 경우 가능한 경우의 수는 총 몇 가지인가? 답은 아래 표에서 볼 수 있듯 9가지이다. 두 개의 채로 하나의 접촉면을 동시에 치는 경우(아래 표에서 5번, 9번)도 고려해야 하므로 9가지이다.
\n| \n | 궁채 | \n북채 | \n
|---|---|---|
| 1 | \nX | \nX | \n
| 2 | \n궁면 | \nX | \n
| 3 | \n북면 | \nX | \n
| 4 | \nX | \n궁면 | \n
| 5 | \n궁면 | \n궁면 | \n
| 6 | \n북면 | \n궁면 | \n
| 7 | \nX | \n북면 | \n
| 8 | \n궁면 | \n북면 | \n
| 9 | \n북면 | \n북면 | \n
전기는 색깔이 없다. 접촉면에서 흐르는 전기가 궁채에서 흐르는 전기인지 북채에서 흐르는 전기인지 알 수 없다. 그렇다면 접촉면에 닿은 채가 어떤 채인지 어떻게 구분해야 할까? 필자는 FDM(주파수 분할)과 TDM(시분할)을 생각했다. 처음엔 FDM을 생각했었는데, 아두이노로 구현하기에는 난이도가 높을 것 같아 비교적 구현이 손쉬운 TDM으로 결정했다.
\n시분할 알고리즘은 매우 단순하다.
\n이를 도식도로 나타내면 다음과 같다.
\n
위를 실제 회로로 구현하기 위해서는 특정 회로를 신호로 열거나 닫을 수 있어야 한다.
\n특정 회로를 신호로 열거나 닫는 대표적인 부품은 릴레이이다. 릴레이는 일종의 스위치 역할을 하는 부품으로, 전자석을 이용하여 회로를 열거나 닫는다.
\n![\"아두이노](\"/img/bidrum/relay.jpg\")
매우 직관적이고 만들기 쉬워서 처음에 릴레이를 시도했었다. 그러나 문제가 있었다. 릴레이는 딜레이가 너무 크고(5ms) 결정적으로 딱따구리 같은 소음이 난다. 위 알고리즘을 빠르게 무한반복해야 하는 특성상 릴레이 열고닫기를 반복하니 전자석 딱딱거리는 소리가 무한히 들리는 것이었다.
\n그래서 주변 분들의 조언을 받아 트랜지스터를 이용했다. 주변 분께 딜레이가 1ms이하인 릴레이가 있나고 여쭤보니, 그 분께서 그런 릴레이는 없으니 트랜지스터를 쓰라고 답변해주신 것이 큰 도움이 됐다. 트랜지스터는 라디오 만들 때나(증폭) 쓰는 건 줄 알았는데 검색해보니 트랜지스터도 스위치처럼 쓸 수 있음을 알게 됐다.
\nNPN 트랜지스터와 저항으로 약간의 시행착오를 겪으니 잘 인식됐다. 트랜지스터를 이용한 회로는 아래와 같다.
\n![\"트랜지스터를](\"/img/bidrum/janggu_prototype_circuit_1.png\")
위 회로에서 궁채, 열채, 북편, 채편 기호는 각각의 부위에 붙은 전도체를 의미한다.
\n전기가 흘려야 하니 채와 접촉면에는 전도체 물질을 부착해야 한다. 뭘 붙일까 고민하다가 펌프 발판을 수작업으로 제작할 때 은박지를 이용했다는 글이 생각났다. 그래서 다이소에서 쿠킹호일을 사다가 붙였다. 내구성은 썩 좋은 것 같진 않았지만 꽤 잘 인식됐다.
\n![\"장구](\"/img/bidrum/janggu_prototype_1.jpg\")
사진은 위와 같다. 사진에는 보이지 않지만, 장구의 면에도 은박지가 부착되어 있다.
\n쿠킹호일과 NPN 트랜지스터, 저항, 그리고 아두이노를 이용해 장구 컨트롤러를 만들었다. 내구성은 썩 좋지 않았지만 인식은 잘 됐다. 2023년 겨울방학의 일이었다.
\n", "url": "https://blog.litehell.info/post/bidrum_and_janggu_controller_prototyping", "title": "쿠킹호일과 트랜지스터로 리듬게임 컨트롤러 만들기", "summary": "학교 캡스톤디자인 작품으로 장구 리듬게임 만든 이야기", "image": "https://blog.litehell.info/img/bidrum/controller-algorithm.png", "date_modified": "2024-07-19T12:53:12.021Z" }, { "id": "show_all_slides_of_pptx_and_convert_to_pdf_batch_operation", "content_html": "이번 학기에 데이터베이스시스템 과목을 수강하게 됐다. 이 과목의 강의자료는 교재 홈페이지에서 제공하는 pptx 파일을 이용하는데, 숨김 처리된 슬라이드도 모두 활용한다. 따라서 숨겨진 슬라이드를 모두 숨김 해제해야 했다.
\n파일이 한두개면 그냥 직접 숨겨진 슬라이드를 숨김 해제하면 된다. 하지만 강의가 시작되는 Chapter 12이후의 파일은 약 20개 정도였다. 물론 그 pptx들을 다 강의하진 않겠지만, 한두개의 파일이 아닐 것임은 확실했다.
\n이걸 어떻게 하면 일괄처리할 수 있을까?
\npptx 파일은 zip 파일이다. pptx파일을 압축 프로그램을 열면 다음과 같은 구조를 볼 수 있다.
\n![\"pptx파일을](\"/img/show_all_slides_of_pptx_and_convert_to_pdf_batch_operation/pptx_zip_structure.png\")
ppt/slides 디렉토리 내의 xml 파일들이 슬라이드를 나타내는 xml 파일이다. 숨김 처리된 슬라이드의 xml 파일을 보면 다음과 같이 루트 요소의 show 속성이 0으로 설정되어 있음을 확인할 수 있다.
![\"숨겨진](\"/img/show_all_slides_of_pptx_and_convert_to_pdf_batch_operation/hidden_slide_xml.png\")
그렇다면 ppt/slides 디렉토리 내의 xml 파일의 루트 요소에서 show 속성만 제거하면 되지 않을까?
python을 이용하면 기본으로 제공되는 라이브러리만으로 간단히 해결할 수 있다.
\n#!/bin/python3\nimport re\nfrom os import listdir\nfrom os.path import isfile, join\nfrom zipfile import ZipFile\nimport xml.etree.ElementTree as ET\n\npptx_dir = "."\n# pptx_dir 디렉토리 내에서 파일명이 .pptx로 끝나는 파일의 목록을 가져온다.\npptx_files = [f for f in listdir(pptx_dir) if isfile(join(pptx_dir, f)) and f.endswith(".pptx")]\n# ppt/slides/*.xml 패턴을 검사하기 위한 정규표현식\nslide_xml_filename_pattern = re.compile("ppt/slides/[^/]+\\\\.xml")\n\nfor pptx_file in pptx_files:\n print("Processing pptx %s " % pptx_file)\n # pptx파일을 zip 파일로 연다.\n with ZipFile(pptx_file, 'a') as zipfile:\n # ppt/slides/*.xml 형태의 파일 목록을 가져온다.\n slide_xml_filenames = [i for i in zipfile.namelist() if not slide_xml_filename_pattern.fullmatch(i) is None]\n for slide_xml_filename in slide_xml_filenames:\n print("Processing xml %s" % slide_xml_filename)\n xml = None\n # xml을 파싱한다.\n with zipfile.open(slide_xml_filename, mode = 'r') as file:\n xml = ET.parse(file)\n # 루트 요소에 show 속성이 있다면 제거한다.\n if "show" in xml.getroot().attrib:\n xml.getroot().attrib.pop("show")\n # 수정된 xml을 pptx 파일 내에 쓴다.\n with zipfile.open(slide_xml_filename, mode = 'w') as file:\n xml.write(file)위 스크립트는 디렉토리내의 pptx 파일을 열고, pptx 파일 내에서 파일명이 ppt/slides/*.xml 형태인 파일을 xml로 파상한 뒤, 루트 요소에서 show 속성을 삭제하고 다시 쓰는 것을 일괄 반복하는 스크립트이다.
사용 시에는 pptx_dir 변수값만 필요에 따라 수정하여 쓰면 된다. 위 스크립트를 실행하면 pptx_dir 변수에 설정된 디렉토리 내에 있는 pptx 파일들에서 숨김 처리된 슬라이드를 모두 숨김 해제한다.
필자는 OneNote를 쓰는데 OneNote는 인쇄물 삽입을 pdf나 docx로만 해야한다. 따라서 모든 pptx를 pdf로 변환할 필요가 있다.
\n이건 쉽다. 그냥 LibreOffice 명령어 한 줄이면 끝난다.
\nlibreoffice --headless --convert-to pdf *.pptx이상으로 여러개의 pptx 파일에서 숨김 처리된 슬라이드를 모두 일괄 숨김 해제하고 pdf로 일괄 변환하는 방법에 대해 알아보았다.
\n다른 사람들에게 도움이 됐으면 좋겠다.
\n", "url": "https://blog.litehell.info/post/show_all_slides_of_pptx_and_convert_to_pdf_batch_operation", "title": "PPTX 파일 모든 슬라이드 숨김 해제하고 PDF 변환 일괄 작업하기", "summary": "Python과 LibreOffice를 이용한 pptx 일괄 처리", "image": "https://blog.litehell.info/img/show_all_slides_of_pptx_and_convert_to_pdf_batch_operation/pptx_zip_structure.png", "date_modified": "2024-03-06T08:33:00.099Z" }, { "id": "retrospective_of_2023", "content_html": "2023년은 포스트코로나(POST COVID-19)의 해였다. 전역한 자에게 사회의 공기는 상쾌했고, 그리웠던 사람들을 오랜만에 볼 수 있어 좋았다. 그리고 2023년은 유난히 바쁜 해였다. 중요한 전공 과목들을 본격적으로 배우고, 첫 캡스톤디자인을 시작했다. 지난 날들을 되짚으며, 회고를 2023년 12월 30일쯤에 쓰기 시작했는데... 현생이 바빠서 못 쓰다가 이제서야 퇴고를 하게됐다. 두서없는 글이지만, 넓은 아량으로 읽어주셨으면 좋겠다.
\n편의상 여름방학때 한 일도 이 문단에 같이 적겠다.
\n필자는 2020년에 중앙동아리 부회장을 한 경력이 있다. 이 경력을 바탕으로 동아리연합회 분과장 보궐선거에 출마했다. 예상 외로 영화동아리에서 후보가 출마해 혹시나 하는 마음이 들었지만, 경선에서 가볍게 압승했다.
\n학생자치의 경험은 꽤 재밌었지만, 아쉬운 점도 많았다. 이에 관한 것들은 이야기거리가 많으니 차후에 별도의 글로 쓰도록 하겠다.
\n![\"ChAOS](\"/img/retrospective_for_2023/cauchaos.png\")
중앙대학교 소프트웨어학부 알고리즘 학회 ChAOS의 부회장이 되면서 디자인을 간단하게 개편했다. Bootstrap 같은 라이브러리를 쓰진 않았고 그냥 HTML과 CSS로 간단하게 작성했는데, 나름 깔끔하게 잘 뽑혔다고 생각한다. 반응형이라서 모바일에서도 잘 보인다.
\n필자는 SketchDaily references 사이트를 이용한다. 데스크톱에선 좋은데, 모바일에선 사소한 버그가 있었다. 마침 Flutter에 관심이 있어서 이 웹사이트를 앱으로 만들어보면 좋을 것 같다는 생각이 들었고, 사이트 운영자에게서 허락을 받았다.
\n\n\nHi there
\nI'm ok with you doing it as long as:
\n\n
\n- it's free
\n- no ads
\n-arto
\n
\n---- On Wed, 30 Nov 2022 07:46:30 -0700 LiteHell litehell@litehell.info wrote ---
\n\n\nDear artomizer:
\nI’m Yeonjin Shin, an user of SketchDaily reference site.
\nI usually use your SketchDaily reference site on my android phone, and it’s a good website for drawing references to me. But, I think It would be better if there is a mobile app for mobile users.
\nSo, I want to make SketchDaily reference app for mobile users. I hope you to let me know if I can make a mobile app for SketchDaily reference?
\nSincerely,
\n
\nYeonjin Shin
\nYeonjin Shin
\n
\nCSE Student; Rookie software engineerHomepage: https://litehell.info
\n
\nGitHub: https://github.com/litehell
\nEmail: litehell@litehell.info
2022년 12월 1일에 위와 같이 허락을 받고 개발을 시작했다. 그리고 2022년 6월 중에 개발을 마무리하고 그 다음 달에 첫 프로덕션 버전을 배포했다.
\n본래 앱 디자인은 다른 분께서 해주시기로 하셨으나, 불가피한 사정이 생기신 관계로 내가 직접 간단히 만들게 됐다.
\nGoogle Play에 앱을 출시하면서 느낀 점은 이것저것 정책적으로 신경써야 하는 게 꽤 많다는 점이였다. 개인정보, 청소년보호... 등등 응답해야 하는 것들이 꽤 있었고 출시 이후에도 세법이나 정책에 관한 메일이 자주 날라왔다. 애플은 내가 출시를 안해봐서 모르겠다.
\n2023년 12월 28일을 기준으로 이 앱을 설치한 사용자가 한 410명쯤 되며, 미국인이 가장 많고, 그 뒤로 인도, 멕시코, 러시아 순으로 많았다. 인터넷 없이도 작동했으면 좋겠다는 의견도 있었는데 이건 웹사이트 운영자랑 협의해야 하는 문제인지라 실현 가능할 지에 대해서 부정적이다.
\n1학기에는 알고리즘, 운영체제, 컴파일러, 소프트웨어공학, 멀티코어컴퓨팅, 선형대수학 수업을 들었다.
\n필자는 수학에 능숙하지 않은 관계로 선형대수학 수업에서 잘 따라가지 못할 것 같아 많은 걱정을 했는데 생각외로 할만했다. 행렬과 근사를 위한 수학이라는 느낌을 매우 강하게 받았고, 컴퓨터그래픽스를 위한 수학이라는 인상을 강하게 받았다.
\n운영체제 수업은 Operating Systems Internals and Design Principles 교재의 PPT를 이용한 수업으로 진행됐다. 시험은 누가 누가 더 PPT를 잘 외우는 지를 겨루는 형태였다. 내용은 컴퓨터공학도라면 꼭 알아야 하는 내용이라고 생각했지만, 시험과 수업 방식이 너무 아쉬웠다. 특히 과제에 대해 필자는 세마포어를 주제로 과제를 낸다면 세마포어를 구현하는 과제가 나와야 한다고 생각하는데, 교수님께서 세마포어를 이용하는 과제를 내서셔 아쉬웠다. 그래도 교수님께서 성격은 매우 좋으셨다.
\n소프트웨어공학에서는 다른 사람들과 함께 협업할 때 소프트웨어를 어떻게 개발하는 지, 일정 내에 복잡한 소프트웨어를 어떻게 개발하는 지, 복잡한 소프트웨어를 어떻게 하면 최대한 적은 리스크로 개발할 수 있는 지에 대해 배웠다. 수업 내용이 너무 많아서 힘들었지만 추후 회사생활에 꼭 필요하다고 생각하는 내용이였다. 다만 기존에 예정됐었던 프로젝트 과제가 취소된 것은 개인적으로 아쉬웠다.
\n멀티코어컴퓨팅은 POSIX pthread, C++ threads, Java thread, OpenMP 등 멀티코어 컴퓨팅을 구현하는 방법과, Amhdal's Law, 데이터를 각 쓰레드에 어떻게 나누어야 하는 지, 병렬 컴퓨팅에는 어떤 종류가 있는 지 등 병렬 컴퓨팅에 대한 이론을 개괄적으로 배웠다. 과제가 많이 나왔는데 필자는 과제하는 것을 좋아하는 성격인지라 재밌었다.
\n특히 멀티코어컴퓨팅 과제 보고서를 작성하면서 LaTeX을 적극적으로 이용하고, 친구한테 LaTeX를 설파했는데 확실히 논문 스타일의 공학 보고서를 쓰는 데에는 매우 유용했다. 코드를 명령어 하나로 삽입할 수 있다는 점, 그래프와 표를 삽입할 때 위치가 왔다갔다하면서 문서 레이아웃이 깨지는 문제가 없다는 점, git으로 버전 관리를 하기가 매우 용이하다는 점 등이 좋았다.
\n컴파일러 수업은 오토마타(DFA, NFA 같은 것들), 번역, 최적화 등을 개론적으로 다루었다. 컴파일러 최적화가 어떻게 이루어지는 지 간략하게 알 수 있어서 좋았다.
\n알고리즘 수업은 교수님께서 단순히 어떤 알고리즘이 있다고 암기하는 것보다는 알고리즘에 대한 접근방법과 관점을 이해시키려 한다는 느낌을 많이 받았다. 강의력이 훌륭하신 교수님이셨다.
\n중앙대학교는 졸업하려면 캡스톤디자인을 2번 이상 해야 한다.
\n\n\n\n제48조(졸업요건)
\n
\n다음 각 호의 요건을 모두 충족한 경우 컴퓨터공학전문 프로그램 졸업요건을 갖춘 것으로 한다. (개정 2012.03.01, 2013.03.01, 2015.01.01, 2016.03.01, 2018.03.01)⑦ 창의적설계, 캡스톤디자인(1), 캡스톤디자인(2) 교과목을 반드시 이수하여야 한다. 창의적설계 교과목 이수 전과 캡스톤디자인(1),(2) 교과목 이수 후에 수강한 설계학점(프로젝트학점)은 인정하지 않는다.
\n
그래서 방학때 (필자포함) 3인으로 이루어진 팀을 만들고 아이디어만 간단하게 정했다. 필자는 리듬게임을 좋아하는 지라 리듬게임을 만들자고 했었는데 토론 결과 아무래도 무난한 아이디어가 좋을 것 같다는 쪽으로 합의가 되어 알고모여라는 서비스를 만들게 됐다.
\n![\"알고모여의](\"/img/retrospective_for_2023/algogather.png\")
알고모여는 알고리즘 스터디를 목표로 하는 웹사이트이다. 필자는 앞서 언급했듯이 알고리즘 학회의 부회장이였다. 그래서 1학기때 알고리즘 문제풀이 스터디를 운영했었는데 스터디원이 문제를 풀었는지 확인하는 일이 은근 귀찮아서 봇을 만들어 돌렸었다. 그래서 이걸 아예 서비스화해서 스터디원과 스터디장이 알고리즘 스터디를 편하게 운영할 수 있는 웹서비스를 만들면 좋지 않겠느냐는 의견이 나왔고, 그 아이디어가 채택되어 웹개발을 하게 됐다.
\n나는 React와 Next.js로 프론트엔드를 개발하고, 다른 팀원은 Spring Boot로 백엔드를 개발하며, 나머지 팀원은 알고리즘 문제 채점 서버를 개발했다. Next.js를 이용한 이유는 React 개발환경 구축하는 데 들이는 시간을 단축하기 위해서이다. (다른 프레임워크도 있긴 하지만 써본 경험이 있는 프레임워크를 채택하는 것이 시간 단축에 더 유리할 것이라 판단한 것도 있었다.)
\n내가 백엔드와 프론트엔드 중 프론트엔드를 채택한 것은 백엔드를 담당한 팀원이 웹개발 경험이 별로 없어서이기 때문이다. 프론트엔드는 어느 정도의 HTML/CSS 지식과 경험을 갖추고 있어야만 (비록 미적으로 아름답지는 않아도) 그럴싸하게 완성된 결과물이 나오지만, 백엔드는 데이터베이스와 HTTP, 그리고 웹 프레임워크(e.g. Spring)에 대한 대략적인 지식만 갖추고 있어도 그럴싸하게 완성된 결과물이 나온다. 따라서 웹개발이 부족한 팀원에게는 프론트엔드보다 백엔드를 맡기는 게 더 낫겠다는 판단이 들어서 내가 프론트엔드를 맡게 됐다.
\n캡스톤 프로젝트를 하는 과정에서 JIRA 이슈 트래커를 이용하고, Pull Request에서 최소 1인 이상 Code Review해야 Merge하는 규칙을 세워 개발했는데 확실히 도움이 많이 됐다. 이슈 트래커를 이용하니 내가 지금 무슨 일을 해야하는 지 빠르게 알 수 있었고, 특히 JIRA의 칸반 보드 디자인이 직관적으로 보기가 편했다.
\n![\"알고모여](\"/img/retrospective_for_2023/algogather_code_review.png\")
![\"알고모여](\"/img/retrospective_for_2023/algogather_code_review_2.png\")
그리고 Pull Request에서 최소 1인 이상의 코드 리뷰를 강제함으로써 코드 퀼리티를 높일 수 있었다. 필자는 백엔드 개발도 어느정도 알았기에 백엔드 코드를 읽어서 머리속으로 화이트박스 테스트를 했고, 프론트엔드 개발을 담당한 팀원께서는 프론트엔드 개발 지식이 많은 편이 아니었기에 직접 PR을 checkout하고 실행하여 버그를 찾는 블랙박스 테스팅을 주로 해주셨다. 필자는 PR에서 백엔드 개발자가 놓친 부분(검증이라던가)이나 애매모호한 변수/함수명에 대한 의견을 주로 제시했고 프론트엔드 개발자는 필자가 미처 발견하지 못한 버그를 많이 찾아주셨다.
\n위와 같은 개발 과정을 통해 꽤 완성도 있는 결과물을 산출할 수 있었고 그 결과 캡스톤디자인 과목에서 A+를 받을 수 있었다.
\n컴퓨터그래픽스 수업에서는 행렬을 이용해 3D 객체가 어떻게 2D 화면에 투영되는지, 3D 공간에서의 변형(회전, 이동 등)이 행렬을 이용하여 어떻게 이루어지는 지부터 시작하여 OpenGL을 이용한 쉐이더와 기법들, 빛과 그림자, 이를 이용한 실제 OpenGL 프로그램 제작까지 했다. 컴퓨터그래픽스에 대해 무지했던더라 수업이 굉장히 재밌었고, Vertex shader와 Geometry shader를 활용한 Phong shading 등의 기법과 그림자 및 빛의 구현을 처음으로 배웠다.
\n컴퓨터통신 수업에서는 물리 레이어부터 시작해 4계층 직전까지를 다룬다. Bottom-Top 방식으로 진행되어 컴퓨터통신 구조에 대한 전체적인 통찰을 얻기에 훌륭한 강의였다. 지금까지 기껏해봐야 추상화된 TCP/IP 소켓 API만 이용해보았기에 이더넷, Wi-Fi, IP 프로토콜의 작동 원리를 배울 수 있는 컴퓨터통신 수업에서 많은 걸 얻을 수 있었다. 비록 수업은 힘들었지만, 상위 레이어가 하위 레이어를 이용하고, Peer와 peer 간에는 프로토콜(메세지 포맷)이 동일하다는 원칙 하에서 인터넷이 어떻게 동작하는 지 알 수 있었다.
\n리눅스 시스템 응용설계에서는 리눅스 커널의 소스코드를 살펴보며 리눅스의 Mutex와 같은 동시성(Concurrency) 매카니즘과 프로세스 관리, 스케쥴링이 어떻게 이루어지는 지를 배웠다. 교수님께서 리눅스에 대해 진심이라는 것을 느꼈고, 리눅스의 CFS Scheduler의 동작 원리를 배울 수 있어 좋았다.
\n머신러닝프로젝트와 패턴인식 과목에서는 머신러닝과 패턴인식에 대한 이론을 기초적인 수학에 기반하여 배웠다. 서로 다른 과목이긴 한데 교수님이 똑같으서셔 내용이 비슷했다. 머신러닝과 패턴인식이 무엇인지 몰랐던 필자에게 "머신러닝과 패턴인식은 단순히 어떠한 데이터(점)이 어떠한 구역(분류)에 해당되는 지를 선/평면(퍼셉트론)이나 통계적 방법론(패턴인식)을 이용하여 찾아내는 것이다."라는 거대한 통찰을 제시하고 이러한 통찰 하에 머신러닝과 패턴인식에 필요한 기초적인 수학과 이에 기반한 이론(퍼셉트론, 다층 퍼셉트론, 딥러닝)을 간략하게 가르치셨다. 필자는 인공지능에 대해 아무것도 몰랐기에 수업이 매우 보람찼다.
\n코딩부트캠프는 코딩테스트 보는 과목이다. 코딩테스트가 너무 쉬웠기에 그냥 졸입필수과목이라서 수강했다라는 말 외에는 딱히 쓸 말이 없다.
\n매우 바쁜 해였다. 동아리 부회장도 하고 동아리연합회 임원도 하고 캡스톤디자인도 하고 면접도 보러다니고 하루하루가 바빴다. 하루하루를 바쁘게 산 만큼 언젠가 보상이 왔으면 좋겠다.
\n", "url": "https://blog.litehell.info/post/retrospective_of_2023", "title": "2023년의 회고", "summary": "학생자치와 캡스톤디자인", "image": "https://blog.litehell.info/img/retrospective_for_2023/cauchaos.png", "date_modified": "2024-02-05T15:55:48.396Z" }, { "id": "receiving_gpl_from_fsf", "content_html": "자유/오픈소스 소프트웨어 라이선스는 MIT, BSD, Apache 등 여러가지 종류의 라이선스가 있다. 이 중 가장 유명한 카피레프트 라이선스로는 Linux, GNU, gcc 등으로 널리 알려진 GNU GPL 라이선스가 있으며, notepad++, Git, uBlock Origin, MariaDB 등의 많은 프로그램에서도 채택하고 있다. 주로 GPLv2 라이선스와 GPLv3 라이선스가 많이 쓰이는 데, GPLv2의 하단부를 읽으면 다음과 같은 문구를 볼 수 있다.
\n\n\nYou should have received a copy of the GNU General Public License along
\n
\nwith this program; if not, write to the Free Software Foundation, Inc.,
\n51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
만약 GNU GPLv2 전문을 받지 못했을 시 자유 소프트웨어 재단으로 편지를 보내주면 친절히 전문을 인쇄해서 보내준다고 써져있다. 여기서 호기심이 생겼다, 진짜로 보내줄까?
\n이런 궁금증은 나만 든게 아니었다. 외국의 개발자 mendhak이 이미 이를 시도했다. 글에 나온 바에 따르면, 진짜로 보내준다!
\n진짜로 된다는 걸 확인해보니 나도 한 번 해보고 싶어졌다. 따라서 나도 국제우편을 한 번 보내보았다.
\n먼저 주변의 우체국에 가서 국제반신우표권을 구매했다. 국제반신우표권은 수신자가 나라와 상관없이 주변 우체국에서 우표로 교환할 수 있는 일종의 교환권이다. 집 주변 가장 가까운 우체국에서는 재고가 없었기에 조금 거리가 있는 큰 우체국에 가서 1,450원을 주고 구매했다. 이 글을 읽는 여러분도 국제반신우표권을 살 생각이 있다면 미리 우체국에 재고가 있는 지 확인해보는 것을 추천한다.
\n![\"국제반신우표권의](\"/img/upu-irc-mosaic.jpg\")
(위 사진은 도장의 지역명을 삭제한 사진이다.)
\n국제반신우표권과 함께 간단한 편지를 작성했다. 그 편지의 내용은 다음과 같다.
\n\n\nDear Free Software Foundation
\nI received a software, and its license notice said,
\nYou should have received a copy of the GNU General Public License\n\n
\nalong with this program; if not, write to the Free Software
\nFoundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.However, the license was not provided with the software.
\n
\nPlesae can you provide me with a copy of GNU General Public License?I have enclosed a international reply coupon, which is can be exchanged with a stamp in a nearby post office.
\nSincerely,\nYeonjin Shin
\n
회신용 봉투를 안 넣으면 FSF 로고가 인쇄된 봉투에 담아서 줄 것 같다는 생각이 들어서 회신용 봉투는 일부러 안 넣었다. 이 편지와 국제반신우표권을 집에 있던 규격봉투(소봉투)에 집어넣고 우표를 붙였다.
\n![\"봉투와](\"/img/req_for_gpl_to_fsf.jpg\")
무게에 따라 다르겠지만, 미국으로 국제우편을 부치는 데에는 총 700원이 들었다. 사진에는 710원의 우표가 붙여져있지만, 부치는 데에는 700원이면 충분하다. (물론 무게에 따라 달라질 수 있다.)
\n위와 같이 준비한 편지와 국제반신우표권을 봉투에 넣은 뒤, 2023년 7월 7일 주변 우체통에 넣어서 부쳤다. 오랜만에 우체통에 편지를 넣으니 감희가 새로웠다.
\n![\"봉함된](\"/img/req_for_gpl_to_fsf_enveloped.jpg\")
지금(12월 7일)도 답장이 오지 않았다... 아무래도 중간에 유실된 것 같다. 그래도 혹시 만약에 답장이 오게 된다면 업데이트하겠다.
\n", "url": "https://blog.litehell.info/post/receiving_gpl_from_fsf", "title": "FSF에 편지 보내서 GPL 받아보기", "summary": "그러나 편지는 오지 않았다", "image": "https://blog.litehell.info/img/upu-irc-mosaic.jpg", "date_modified": "2023-12-07T14:19:37.603Z" }, { "id": "korean_style_award_with_latex", "content_html": "최근 알고리즘 동아리에서 주최한 대회에 운영진으로 참가했다. 대회가 마무리된 후 1,2,3등을 위한 상장을 만들어야 했는데 이때 LaTeX를 써보면 재밌을 것 같다는 생각이 들었다.
\n따라서 LaTeX을 이용해 아래와 같은 상장을 만들었다.
\nTikZ는 LaTeX에서 그림을 그릴 때 쓰는 패키지이다. 주로 pgfplots와 함께 사용하거나 그래프를 그릴 때 이용되지만 간단한 그림 정도는 그릴 수 있다.
\nTikZ에는 current page라는 특별한 노드가 있다. 이 노드는 current page.south west나 current page.west와 같이 이용되며, 페이지의 모서리를 가리키고 있다.
아래 예시를 보자. TikZ & PGF 메뉴얼 3.1.10버전의 260페이지에 있는 예시이다.
\n\\begin{tikzpicture}[remember picture, overlay]\n \\draw [line width=1mm, opacity=.25]\n (current page.center) circle (3cm);\n\\end{tikzpicture}위 예시 코드를 빌드하면 페이지의 정중앙에 반지름이 3cm인 원이 그려진다. 위 코드에서 remember picture와 overlay는 current page 노드를 사용하기 위해 필요하다.
TikZ는 \\draw arc (시작각도:종료각도:반지름) 형태의 명령어로 호(arc)도 그릴 수 있다.
cycle을 이용하면 마지막 노드에서 다시 처음 노드로 이어지는 닫힌 경로를 만들 수 있다.
예시를 보면 이해가 쉽다.
\nWithout cycle\n\n\\begin{tikzpicture}\n\\draw (0, 0) -- (1, 1) -- (2, 0);\n\\end{tikzpicture}\n\nWith cycle\n\n\\begin{tikzpicture}\n\\draw (0, 0) -- (1, 1) -- (2, 0) -- cycle;\n\\end{tikzpicture}\n위 코드를 빌드하면 아래와 같은 결과가 나온다.
\n![\"tikz](\"/img/latex_tikz_cycle.png\")
본 템플릿에서 그린 상장 테두리 장식은 호와 직선만을 이용해 그릴 수 있는 기하학적인 무늬(문방구 상장용지에서 흔히 볼 수 있는 무늬)이다. 따라서 TikZ를 잘 활용하면 상장 테두리 장식을 그릴 수 있다.
\nGitHub Gist에서도 볼 수 있다.
\n\\documentclass{minimal}\n\\usepackage{kotex}\n\\usepackage[svgnames]{xcolor}\n\\usepackage{tikz}\n\\usepackage[a4paper, top=100pt, left=80pt, right=80pt, bottom=120pt]{geometry}\n\\usetikzlibrary{calc}\n\n\\newcommand{\\thickframemargin}{40pt}\n\\newcommand{\\thickframewidth}{6pt}\n\\newcommand{\\thinframemargin}{46pt}\n\\newcommand{\\thinframewidth}{1pt}\n\\newcommand{\\framecornerradius}{30pt}\n\\newcommand{\\framecolor}{Goldenrod}\n\\begin{document}\n\\begin{tikzpicture}[remember picture, overlay]\n % thick corner\n \\draw[color=\\framecolor, line width=\\thickframewidth]\n % north west rounded corner\n ([xshift=\\thickframemargin, yshift=-\\thickframemargin-2*\\framecornerradius] current page.north west) arc (270:450:\\framecornerradius)\n -- ([xshift=\\thickframemargin, yshift=-\\thickframemargin] current page.north west) arc (180:360:\\framecornerradius)\n % north east rounded croner\n -- ([xshift=-\\thickframemargin-2*\\framecornerradius, yshift=-\\thickframemargin] current page.north east) arc (180:360:\\framecornerradius)\n -- ([xshift=-\\thickframemargin, yshift=-\\thickframemargin] current page.north east) arc (90:270:\\framecornerradius)\n % south east rounded corner\n -- ([xshift=-\\thickframemargin, yshift=\\thickframemargin+2*\\framecornerradius] current page.south east) arc (90:270:\\framecornerradius)\n -- ([xshift=-\\thickframemargin, yshift=\\thickframemargin] current page.south east) arc (0:180:\\framecornerradius)\n % south west rounded corner\n -- ([xshift=\\thickframemargin+2*\\framecornerradius, yshift=\\thickframemargin] current page.south west) arc (0:180:\\framecornerradius)\n -- ([xshift=\\thickframemargin, yshift=\\thickframemargin] current page.south west) arc (270:450:\\framecornerradius)\n % cycle\n -- cycle;\n\n\n % thin corner\n \\draw[color=\\framecolor, line width=\\thinframewidth]\n % north west rounded corner\n ([xshift=\\thinframemargin, yshift=-\\thinframemargin-2*\\framecornerradius] current page.north west) arc (270:360:\\framecornerradius)\n -- ([xshift=\\thinframemargin+\\framecornerradius, yshift=-\\thinframemargin-\\framecornerradius] current page.north west) arc (270:360:\\framecornerradius)\n % north east rounded croner\n -- ([xshift=-\\thinframemargin-2*\\framecornerradius, yshift=-\\thinframemargin] current page.north east) arc (180:270:\\framecornerradius)\n -- ([xshift=-\\thinframemargin-\\framecornerradius, yshift=-\\thinframemargin-\\framecornerradius] current page.north east) arc (180:270:\\framecornerradius)\n % south east rounded corner\n -- ([xshift=-\\thinframemargin, yshift=\\thinframemargin+2*\\framecornerradius] current page.south east) arc (90:180:\\framecornerradius)\n -- ([xshift=-\\thinframemargin-\\framecornerradius, yshift=\\thinframemargin+\\framecornerradius] current page.south east) arc (90:180:\\framecornerradius)\n % south west rounded corner\n -- ([xshift=\\thinframemargin+2*\\framecornerradius, yshift=\\thinframemargin] current page.south west) arc (0:90:\\framecornerradius)\n -- ([xshift=\\thinframemargin+\\framecornerradius, yshift=\\thinframemargin+\\framecornerradius] current page.south west) arc (0:90:\\framecornerradius)\n % cycle\n -- cycle;\n\\end{tikzpicture}\n\\fontsize{16pt}{16pt}\\selectfont 제 1 호\n\n\\vspace{32pt}\n\n\\begin{center}\n\\fontsize{48pt}{48pt}\\selectfont\n상\\hspace{1.25em}장\n\\end{center}\n\n\\vspace{50pt}\n\n\n\\fontsize{20pt}{20pt}\\selectfont\n최우수상\\hspace{\\stretch{1}}홍길동\n\n\n\\vspace{80pt}\n\n\\begin{center}\n \\fontsize{20pt}{30pt}\\selectfont\n 위 사람은 \\LaTeXe를 잘 활용하여 타의 모범이 되었으므로 이 상을 수여합니다.\n\\end{center}\n\n\n\\vspace{\\stretch{1}}\n\n\\begin{center}\n \\fontsize{20pt}{20pt}\\selectfont\n 1970년 1월 1일\n\\end{center}\n\n\n\\vspace{2em}\n\n\\begin{center}\n \\fontsize{30pt}{30pt}\\selectfont\n \\LaTeXe{} 애호가 김철수\n\\end{center}\n\n\\end{document}\n![\"한국식](\"/img/latex_korean_award.png\")
필자는 중앙대학교 공지사항을 RSS로 만들어서 구독한다. RSS로 만든 후 메신지 봇을 붙이면 알아서 알려주니 편하다.
\n그러나 최근 해당 RSS 프로그램의 테스트가 실패하는 현상이 발견됐다. 확인한 결과, 중앙대학교 SW교육원 홈페이지의 TLS 인증서 이슈였던 것으로 확인됐다. 따라서 이를 해결하기 위해 일단 실행되고 있는 Docker 컨테이너에 직접 접근해서 해당 사이트의 CA 인증서를 설치했다.
\n버그는 일단 임시방편으로 수정한 것이니 레포에는 반영되지 않았다. 따라서 테스트 실패 메일이 매일매일 내 메일함으로 전송됐다.
\n어떻게 하면 이 버그를 수정하고 잘 테스트할 수 있을까? 먼저 이 버그를 수정하려면 Dockerfile을 수정해야 한다. Dockerfile에 다음 내용을 추가하여 Docker 이미지 빌드시 CA 인증서를 복사하도록 했다. LiteHell/cau-rss 레포의 커밋 21013a3에서 확인할 수 있다.
\nCOPY swedu-cert.pem /usr/local/share/ca-certificates/swedu-cert.crt\nRUN cat /usr/local/share/ca-certificates/swedu-cert.crt >> /etc/ssl/certs/ca-certificates.crt이제 위 버그 수정도 같이 테스트해야 한다. 아래에 있는 기존의 GitHub Action으로는 이 버그 수정을 테스트할 수 없다. go test -v ./... 명령어가 빌드된 Docker 이미지 내에서 실행되는 것이 아니기 때문이다.
- name: Build\n run: go build -v ./...\n\n - name: Test\n run: go test -v ./...어떻게 하면 테스트할 수 있을까? 답은 간단하다. Docker로 테스트도 하면 된다.
\nDocker는 빌드를 여러 단계로 나누어 진행할 수 있다. 아래 예시 Dockerfile을 보자.
\nFROM node AS base\nWORKDIR /app\nADD src package.json package-lock.json tsconfig.json .\n\nRUN npm i\nRUN npm bulid\n\nCMD ["yarn", "start"]Typescript 프로젝트를 위한 간단한 Dockerfile이다. 이를 다음과 같이 여러개의 단계(stage)로 쪼갤 수 있다.
\nFROM node AS base\nWORKDIR /app\nADD src package.json package-lock.json tsconfig.json .\n\nFROM base AS deps\nRUN npm i\n\nFROM deps AS build\nRUN npm bulid\n\nFROM build As deployment\nCMD ["yarn", "start"]\n위와 같은 Dockerfile을 이용하면 Docker 빌드시 특정 스테이지까지만 빌드할 수 있다. 예를 들어 아래 명령어는 deps 스테이지까지만 빌드한다.
\ndocker build --target deps스테이지가 직선적이여야 할 필요는 없다. 다음과 같이 스테이지가 중간에 분기하도록 작성할 수도 있다.
\nFROM node AS base\nWORKDIR /app\nADD src package.json package-lock.json tsconfig.json .\n\nFROM base AS deps\nRUN npm i\n\nFROM deps AS build\nRUN npm bulid\n\nFROM build As english\nCOPY english .\n\nFROM english As deployment-international\nCMD ["yarn", "start", "--lang=english"]\n\nFROM build As korean\nCOPY korean .\n\nFROM korean AS deployment-domestic\nCMD ["yarn", "start", "--lang=korean"]위 Dockerfile의 경우 build 스테이지에서 english 스테이지와 korean 스테이지로 분기한다.
\nFROM node AS base\nWORKDIR /app\nADD src package.json package-lock.json tsconfig.json .\n\nFROM base AS deps\nRUN npm i\n\nFROM deps AS build\nRUN npm bulid\n\nFROM build As english\nCOPY english .\n\nFROM english As deployment-international\nCMD ["yarn", "start", "--lang=english"]\n\nFROM build As korean\nCOPY korean .\n\nFROM korean AS deployment-domestic\nCMD ["yarn", "start", "--lang=korean"]위 Dockerfile을 가지고 아래 명령어를 실행한다고 가정해보자.
\ndocker build --target deployment-domestic위 경우 빌드에 필요한 스테이지는 base, deps, build, korean, deployment-domestic이다. 그러나 실제로 위 명령어를 실행해보면 불필요한 english, deployment-international 스테이지도 빌드하는 것을 확인할 수 있다.
이는 도커 레거시 빌더를 이용하기 때문에 생기는 문제이다. Docker BuildKit은 사용되지 않는 스테이지를 자동으로 파악하여 불필요한 스테이지는 빌드를 생략한다. 따라서 Docker BuildKit을 설치한 후 다음 명령어로 빌드하면 필요한 스테이지만 빌드할 수 있다.
\nDOCKER_BUILDKIT=1 docker build --target deployment-domestic이제 Docker를 이용해 테스트를 하는 방법에 대해 알아보자. 다음은 cau-rss 레포의 Dockerfile 내용을 약간 수정한 예시이다.
\nFROM golang:alpine as base\nWORKDIR /app\n\nCOPY go.mod go.sum ./\nRUN go mod download && go mod verify\n\nCOPY cau_parser ./cau_parser\nCOPY server ./server\n\n# To avoid tls error from swedu.cau.ac.kr\nCOPY swedu-cert.pem /usr/local/share/ca-certificates/swedu-cert.crt\nRUN cat /usr/local/share/ca-certificates/swedu-cert.crt >> /etc/ssl/certs/ca-certificates.crt\n\nCOPY static ./static\nCOPY html ./html\n\nCOPY *.go ./\n\nFROM base as build\nRUN go build -v -o ./app ./\nCMD ["/app/app"]\n\nFROM base as test\nRUN ["go", "test" ,"-v", "./..."]\nbase 스테이지에서 의존성을 설치한 뒤 각종 필요한 파일들을 복사하고 TLS 인증서 오류 해결을 위한 CA 인증서를 복사한다. test 스테이지는 base 스테이지에서 테스트 명령어를 실행하는 스테이지이며, build 스테이지는 base 스테이지를 바탕으로 도커 이미지를 빌드하는 스테이지이다.
따라서 위 Dockerfile을 이용해 build 스테이지까지 빌드하면 도커 이미지를 만드는 것이며, test 스테이지까지 빌드하면 테스트를 실행하게 되는 것이다. 이를 명령어로 나타내면 다음과 같으며, 캐시로 인해 테스트가 진행되지 않는 것을 방지하기 위해 --no-cache 매개변수를 추가했다.
# Test\nDOCKER_BUILDKIT=1 docker build --no-cache --target test .\n\n# Build\nDOCKER_BUILDKIT=1 docker build --target build테스트 실패시 Docker 빌드 오류가 발생한다. 이를 응용하면 다음과 같이 테스트 성공시 빌드를 진행하고, 실패시 오류 메세지를 출력하는 bash 스크립트를 작성할 수 있다.
\nexport DOCKER_BUILDKIT=1\n\ndocker build --no-cache --target test .\ntest_status=$?\nif [ $test_status -eq 0 ]; then\n docker build --taget build . --tag example-application\nelse\n echo "ERROR while testing!"\nfiGitHub Action을 이용하면 다음과 같이 push시 테스트가 이루어지도록 할 수 있다.
\nname: Test\non: push\n\njobs:\n test:\n runs-on: ubuntu-latest\n steps:\n - uses: actions/checkout@v3\n\n - name: Set up Docker Buildx\n uses: docker/setup-buildx-action@v3\n\n - name: Test\n run: docker build --no-cache --target test .\n env:\n DOCKER_BUILDKIT: 1\n빌드도 잘 되는지 확인하고 싶다면 빌드하는 job을 하나 더 추가하면 된다.
\nname: Build and test\non: push\n\njobs:\n build:\n runs-on: ubuntu-latest\n steps:\n - uses: actions/checkout@v3\n\n - name: Set up Docker Buildx\n uses: docker/setup-buildx-action@v3\n\n - name: Build\n run: docker build --target build .\n env:\n DOCKER_BUILDKIT: 1\n\n test:\n runs-on: ubuntu-latest\n steps:\n - uses: actions/checkout@v3\n\n - name: Set up Docker Buildx\n uses: docker/setup-buildx-action@v3\n\n - name: Test\n run: docker build --no-cache --target test .\n env:\n DOCKER_BUILDKIT: 1\nDocker 이미지로 배포를 진행하는 경우, Docker로 테스트도 같이 진행하면 실제 배포 환경과 유사한 환경에서 테스트를 진행할 수 있다는 큰 장점이 있다. 따라서 복잡한 어플리케이션이라면 이 글을 참고해 Docker로 테스트도 같이 하는 것이 좋은 선택이 될 수 있다.
\n", "url": "https://blog.litehell.info/post/docker_for_testing", "title": "Docker로 테스트하기", "summary": "Docker로 빌드만 하지 말고 테스트도 하자", "image": "https://gravatar.com/avatar/837266b567b50fd59e72428220bf69b1", "date_modified": "2023-10-25T14:49:49.041Z" }, { "id": "fcitx5_for_101_key_keyboard_kde_laptop", "content_html": "필자는 초창기에 ibus를 썼었다. ibus는 웬만한 프로그램에서 아무 버그없이 잘 작동한다. 딱 한가지, 리브레오피스에서 공백 입력이 안 된다는 치명적인 버그만 빼면 말이다.
\n그래서 ibus 다음으로 하모니카에서 유지보수하는 nimf를 썼었다. nimf는 리브레오피스에서의 치명적인 버그는 없었지만, 엔터키를 누르면 텍스트가 사라지는 버그가 있었다. 근데 이 버그, 처음에만 짜증나지 좀 지나면 적응된다. 그래서 적응해서 쓰다가 생각해보니 '이건 좀 아닌 것 같다'싶어서 다른 입력기를 설치했다.
\n본 블로그 글은 Arch Linux를 기준으로 설명한다.
\n입력기를 바꾸기 위해 삽질하는 과정에서 한글키가 오른쪽 Alt키로 인식되는 현상을 확인했다. 분명히 아치 리눅스 설치 초기에 매핑을 했었는데, 시스템 업데이트를 하는 과정에서 원상복구가 된 것 같다. 그래서 이번에는 KDE 설정 프로그램을 이용해 한글키와 한자키를 매핑했다.
\n![\"KDE](\"/img/kde_keyboard_settings.png\")
위와 같이 시스템 설정 프로그램의 입력 장치 🠞 키보드 화면에서 오른쪽 Alt 키를 한/영 키로 만들기, 오른쪽 Ctrl 키를 한자 키로 만들기 항목을 체크하면 된다. (키보드 레이아웃에 따라 약간 다를 수 있다.) 노트북 등의 101/104키 호환 레이아웃이라면 위 과정을 반드시 거쳐야 한다.
\n본인 키보드가 101/104키인지 106키인지 헷갈린다면 키보드 키 갯수 세지말고 먼저 xev 프로그램을 설치한다.
sudo pacman -S xorg-xev그리고 콘솔 창에서 xev 프로그램을 실행한다.
\nxevxev 프로그램 창을 활성화하고 한글키랑 한자키를 눌러본다. 다음과 같이 콘솔 창에 Hangul이나 Hangul_Hanja키가 인식된 메세지가 출력되면 한/영 키, 한자 키가 정상적으로 인식되는 것이다.
\nKeyRelease event, serial 39, synthetic NO, window 0x9000001,\n root 0x79b, subw 0x0, time 1234567, (-10, 10), root:(10, 10),\n state 0x0, keycode 108 (keysym 0xff31, Hangul), same_screen YES,KeyPress event, serial 39, synthetic NO, window 0x9000001,\n root 0x79b, subw 0x0, time 1234567, (10, 10), root:(10, 10),\n state 0x0, keycode 105 (keysym 0xff34, Hangul_Hanja), same_screen YES,만약 위와 같은 메세지가 안 뜨고 Alt_R이나 Control_R이 인식된다면 위에 써진 내용에 따라 매핑하면 된다.
\n먼저, 다음 명령어를 실행해 fcitx5를 설치한다.
\nsudo pacman -S fcitx5-im fcitx-hangul/etc/environment 파일에 다음 내용을 추가한다. 입력기로 fcitx를 쓰도록 지정하는 작업이다.
GTK_IM_MODULE=fcitx\nQT_IM_MODULE=fcitx\nQT4_IM_MODULE=fcitx\nQT5_IM_MODULE=fcitx\nXMODIFIERS=@im=fcitx그 다음에 ~/.xprofile 파일에 다음 내용을 추가한다. 부팅시에 fcitx5가 실행되도록 한다.
fcitx5 -d재부팅하고 env | grep fcitx 명령어를 실행해 환경변수가 제대로 변경됐는지 확인해보자. 제대로 변경됐다면 다음과 같이 뜰 것이다.
GTK_IM_MODULE=fcitx\nQT4_IM_MODULE=fcitx\nXMODIFIERS=@im=fcitx\nQT5_IM_MODULE=fcitx\nQT_IM_MODULE=fcitx만약 환경변수가 제대로 변경되지 않았다면 ~/.xprofile 파일에서 fcitx5 -d 위에 다음 내용을 추가하고 재부팅한다. 그러면 환경변수가 정상적으로 변경될 것이다.
export $(/usr/lib/systemd/user-environment-generators/30-systemd-environment-d-generator)fcitx5-configtool 명령어를 실행하면 다음 창이 뜬다.\n![\"fcitx5](\"/img/fcitx5_settings_first_screen.png\")
위 화면에서 한국어가 안 보이면 입력기 추가버튼을 눌러서 추가한다. (입력기 추가 화면에서 한국어가 안 보이면 현재 언어만 표시 옵션을 해제하면 된다.)
\n밑에서 전역 옵션 구성하기... 버튼을 누르면 다음 화면이 뜬다.
\n![\"fcitx5](\"/img/fcitx5_global_settings.png\")
Trigger Input Method가 한/영을 전환하는 단축키 설정이다. 오른쪽의 + 버튼을 눌러 한글 키를 추가하면 된다.
\nfcitx5는 기본적으로 한/영을 전환할때 작은 툴팁을 표시한다. 거슬리면 위 화면에서 Show Input Method Information when switch input method를 체크 해제하면 된다.
\n이제 한글 입력을 버그없이 잘 할 수 있게 됐다. 끝!
\n", "url": "https://blog.litehell.info/post/fcitx5_for_101_key_keyboard_kde_laptop", "title": "한글 입력을 위한 fcitx5 설치", "summary": "KDE 노트북에서의 버그없는 한글 입력을 위한 삽질기", "image": "https://blog.litehell.info/img/kde_keyboard_settings.png", "date_modified": "2023-10-17T12:34:16.790Z" }, { "id": "webpack_and_react_ssg_3", "content_html": "전 글까지 style-loader를 썼다. style-loader는 style 태그를 동적으로 생성하여 CSS를 DOM 안에 주입하는 로더이다. 즉, style-loader를 쓰면 js 스크립트가 실행되면서 style 태그가 동적으로 생성되고, 그 태그 내에 css가 동적으로 삽입되면서 스타일이 적용된다.
\n하지만 정적 페이지로 빌드후 속도가 느린 서버로 게시하거나 스크립트 용량이 비대하면, 스크립트가 완전히 다 실행되기 전까지의 찰나동안 스타일이 적용되지 않은 깨진 페이지가 나타난다. 이런 버그를 막기 위해서는 MiniCssExtractPlugin을 이용하면 된다.
\nMiniCssExtractPlugin은 CSS를 스크립트를 통해 DOM에 주입하지 않고 별도의 CSS 파일에 저장한 뒤, 빌드시에 해당 CSS 파일을 삽입하는 link 태그를 HTML에 삽입한다. 즉 동적으로 CSS를 주입하지 않는다. 따라서 이를 이용하면 스크립트가 완전히 다 실행되기 전까지 페이지 스타일이 적용되지 않는 현상을 해결할 수 있다.
\nMiniCssExtractPlugin을 이용하기 위해서는 먼저 해당 패키지를 설치해야 한다. 다음 명령어로 해당 패키지를 설치한다.
\nyarn add --dev mini-css-extract-plugin그 다음 webpack.config.js 파일에서 다음 부분을 다음과 같이 수정한다.
// 수정 전\nmodule: {\n ...commons.module,\n rules: [\n ...commons.module.rules,\n // CSS를 빌드시 로드하도록 하면 오류가 발생한다. (Node.js 환경은 웹브라우저가 아니므로 스타일 주입 시도가 당연히 실패하기 때문이다.)\n // 따라서 css파일은 웹브라우저단에서 로드되는 번들 스크립트에서만 주입되도록 \n // src/index.tsx Webpack 설정에만 추가한다.\n {\n test: /\\.css$/,\n use: ['style-loader', 'css-loader', 'postcss-loader']\n },\n ]\n },\n plugins: [\n ...commons.plugins,\n new HtmlWebpackPlugin({\n filename: 'index.html',\n // template 속성을 추가한다.\n template: './src/index.html'\n })],// 수정 후\nmodule: {\n ...commons.module,\n rules: [\n ...commons.module.rules,\n // CSS를 빌드시 로드하도록 하면 오류가 발생한다. (Node.js 환경은 웹브라우저가 아니므로 스타일 주입 시도가 당연히 실패하기 때문이다.)\n // 따라서 css파일은 웹브라우저단에서 로드되는 번들 스크립트에서만 주입되도록 \n // src/index.tsx Webpack 설정에만 추가한다.\n // 그리고 프로덕션 빌드시에는 MiniCssExtractPlugin을 이용하여 js가 다 로드되기 전에는\n // 스타일이 적용되지 않는 버그를 해결한다.\n {\n test: /\\.css$/,\n use: [dev ? 'style-loader' : MiniCssExtractPlugin.loader, 'css-loader', 'postcss-loader']\n },\n ]\n },\n plugins: [\n ...commons.plugins,\n new MiniCssExtractPlugin(),\n new HtmlWebpackPlugin({\n filename: 'index.html',\n // template 속성을 추가한다.\n template: './src/index.html'\n })],위와 같이 수정한 후 정적 웹페이지를 빌드하면 이제 스크립트가 불러와지는동안 스타일이 적용되지 않는 문제가 해결된다.
\n", "url": "https://blog.litehell.info/post/webpack_and_react_ssg_3", "title": "Webpack과 React를 이용한 정적 웹사이트 만들기 (3)", "summary": "... + MiniCssExtractPlugin = TA-DA!", "image": "https://gravatar.com/avatar/837266b567b50fd59e72428220bf69b1", "date_modified": "2023-07-23T17:25:47.907Z" }, { "id": "creating_mastodon_instance", "content_html": "확실히 요즘 트위터는 달라졌다. 일론 머스크가 인수한 이후의 트위터는 확실히 뭔가 달라졌다. 뭔가 보여주겠다는 의지의 표출인가?
\n이런 새로워진 트위터에 적응하지 못한 사람들은 마스토돈이나 미스키 등의 ActivityPub를 구현한 분산형 SNS 인스턴스로 이주하고 있다. 국내의 이런 분산형 SNS는 대표적으로 다음과 같다.
\n\n위와 같이 서로 AcitivtyPub 등의 프로토콜을 이용해 통신하는 SNS 서비스들의 집합을 Fediverse(페디버스)라 일컬는다. 페디버스는 서버간에 서로 통신할 수 있기 때문에 다른 서버에 있는 사용자와도 소통할 수 있다. 즉, 서버 A에서 서버 B에 있는 사람을 팔로우할 수도 있다.
\n분산형 SNS이니 당연히 본인이 직접 서버를 구축하는 것도 가능하다. 따라서 직접 VPS에 마스토돈을 설치했다. VPS 운영체제로는 데비안을 택했고, 사양은 Vultr $6 VPS로 했다.
\n설치 자체는 공식 홈페이지의 문서를 따르는 식으로 진행했으나 중간중간 삽질을 약간 했다.
\n마스토돈을 설치하기 위해서는 먼저 root 계정으로 전환한다. su 명령어를 이용하면 된다.
그 다음, 의존성을 설치해야 한다. 의존성 설치 자체는 공식 홈페이지에 있는 명령어를 복사-붙여넣기하면 끝난다.
\n첫번째로 다음 명령어를 실행해 node.js v16을 설치한다.
\ncurl -sL https://deb.nodesource.com/setup_16.x | bash -그리고 다음 명령어를 실행해 PostgreSQL와 기타 다른 의존성들을 설치한다.
\napt install -y curl wget gnupg apt-transport-https lsb-release ca-certificates\nwget -O /usr/share/keyrings/postgresql.asc https://www.postgresql.org/media/keys/ACCC4CF8.asc\necho "deb [signed-by=/usr/share/keyrings/postgresql.asc] http://apt.postgresql.org/pub/repos/apt $(lsb_release -cs)-pgdg main" > /etc/apt/sources.list.d/postgresql.list\napt update\napt install -y \\\n imagemagick ffmpeg libpq-dev libxml2-dev libxslt1-dev file git-core \\\n g++ libprotobuf-dev protobuf-compiler pkg-config nodejs gcc autoconf \\\n bison build-essential libssl-dev libyaml-dev libreadline6-dev \\\n zlib1g-dev libncurses5-dev libffi-dev libgdbm-dev \\\n nginx redis-server redis-tools postgresql postgresql-contrib \\\n certbot python3-certbot-nginx libidn11-dev libicu-dev libjemalloc-dev다만 여기서 주의해야 하는 것이 있다. 시스템에 따라서 nodejs 16버전이 아닌 그보다 더 최신 버전이 설치됐었을 수도 있다.\n상관없지 않냐고? 상관있다, nodejs v16 버전이 아니면 나중에 webpack precompile 과정에서 오류가 난다.
\n설치된 nodejs의 버전은 node --version 명령어로 확인할 수 있다.
$ node --version\nv18.13.0이는 데비안 apt 레포지토리에 있는 nodejs 패키지 버전이 16보다 더 최신이기 때문에 발생한 문제이다. 이를 해결하기 위해서는 먼저 sudo apt-cache policy nodejs를 실행해 어떤 버전이 설치 가능한지 확인해야 한다.
$ sudo apt-cache policy nodejs\nnodejs:\n Installed: 18.13.0+dfsg1-1\n Candidate: 18.13.0+dfsg1-1\n Version table:\n *** 18.13.0+dfsg1-1 500\n 500 https://deb.debian.org/debian bookworm/main amd64 Packages\n 500 https://debian.mirror.constant.com bookworm/main amd64 Packages\n 16.20.1-deb-1nodesource1 500\n 500 https://deb.nodesource.com/node_16.x bookworm/main amd64 Packages\n 100 /var/lib/dpkg/status위 예시에서는 18.13.0+dfsg1-1과 16.20.1-deb-1nodesource1 버전이 설치 가능하다. 우리가 필요한 것은 nodejs v16대 버전이니 16.20.1-deb-1nodesource1을 설치할 것이다.
apt에서 특정한 버전을 지정해 설치하기 위해서는 다음과 같이 명령어를 실행하면 된다.
\n$ sudo apt install nodejs=16.20.1-deb-1nodesource1그러면 nodejs v16이 정상적으로 설치된 것을 확인할 수 있다.
\n위에서 nodejs, PostregreSQL 등의 의존성을 다 설치했으면 Yarn을 설치해야 한다. Yarn은 다음 명령어로 설치한다.
\ncorepack enable\nyarn set version classic혹시 위 명령어가 작동하지 않는다면 다음과 같이 npm을 이용해 설치할 수도 있다.
\nsudo npm i -g yarn만약 위 npm을 이용한 명령어가 npm이 설치되어 있지 않아 실행되지 않는다면 아래 명령어로 npm을 실치할 수 있다.
\ncurl -qL https://www.npmjs.com/install.sh | sh이제 Ruby를 설치해야 한다. 먼저 mastodon이라는 이름의 리눅스 계정을 생성한다.
adduser --disabled-login mastodon그리고 쉘을 지정한다. (안 하면 sudo su - mastodon 명령어가 오류날 수 있다.) 아래 명령어에서는 쉘을 bash로 지정했는데, 쉘이 무조건 bash여야 할 필요는 없다. 선호하는 쉘이 있다면 그 쉘로 지정해도 된다.
chsh -s /bin/bash mastodon이제 mastodon으로 계정을 전환하자.
\nsudo su - mastodon다음 명령어를 모두 실행해 Ruby를 설치한다.
\ngit clone https://github.com/rbenv/rbenv.git ~/.rbenv\ncd ~/.rbenv && src/configure && make -C src\necho 'export PATH="$HOME/.rbenv/bin:$PATH"' >> ~/.bashrc\necho 'eval "$(rbenv init -)"' >> ~/.bashrc\nexec bash\ngit clone https://github.com/rbenv/ruby-build.git ~/.rbenv/plugins/ruby-build\nRUBY_CONFIGURE_OPTS=--with-jemalloc rbenv install 3.0.6\nrbenv global 3.0.6Ruby 설치가 완료됐다면 bundler도 설치한다.
\ngem install bundler --no-documentRuby와 bundler 설치를 마쳤다면 root 유저로 되돌아간다.
\nexit공식 문서에서 pgTune을 쓰고 싶으면 쓰라고 나와있는데 필자는 귀찮아서 건너뛰었다.
\nPostgreSQL 설정을 위해 다음 명령어로 PostgreSQL 쉘을 띄운다.
\nsudo -u postgres psqlPostgreSQL 쉘이 띄워졌으면 다음 쿼리를 실행해서 SQL 계정을 생성한다.
\nCREATE USER mastodon CREATEDB;계정이 생성됐으면 다음 명령을 쳐서 쉘을 빠져나온다.
\n\\q이제 마스토돈을 다운로드하고 설정할 때가 왔다. 먼저 mastodon 계정으로 전환한다.
\nsudo su - mastodon다음 명령어를 실행해 최신 stable 버전의 mastodon을 다운로드한다.
\ngit clone https://github.com/mastodon/mastodon.git live && cd live\ngit checkout $(git tag -l | grep -v 'rc[0-9]*$' | sort -V | tail -n 1)이제 Ruby 의존성과 JavaScript 의존성을 설치한다.
\nbundle config deployment 'true'\nbundle config without 'development test'\nbundle install -j$(getconf _NPROCESSORS_ONLN)\nyarn install --pure-lockfile마스토돈 설정(바로 다음 문단)을 하는 과정에서 Javascript heap out of memory 오류가 발생할 수 있다. 이는 서버에 RAM이 부족하기 때문이다. 이를 해결하기 위해서는 RAM을 더 꽂거나 swap 파일을 형성하고, 그 다음 node 설정을 수정해야 한다.
\n먼저 swap파일을 생성하는 방법은 다음과 같다. 용량은 적절하게 바꾸면 된다.
\nsudo fallocate -l 2G /tmp-swapfile\nsudo chmod 600 /tmp-swapfile\nsudo mkswap /tmp-swapfile생성된 swap파일은 다음과 같이 적용할 수 있다.
\nsudo swapon /tmp-swapfile위 명령어로 적용된 swap파일은 재부팅이 될 시 다시 적용되지 않으므로 재부팅을 하면 위 명령어를 다시 쳐줘야 한다. 따라서 swap 파일을 영구적으로 적용하기 위해서는 /etc/fstab 파일을 수정해야 하나, 본 글에서는 마스토돈을 설정하는 동안에만 임시적으로 이용할 swap 파일을 생성하는 것이므로 이 파일을 수정하는 방법에 대해서 언급하지 않는다.
이제 node 설정을 바꾸어야 한다. 먼저 현재 할당한 힙 용량을 다음 명령어로 확인한다.
\nnode -e 'console.log(v8.getHeapStatistics().heap_size_limit/(1024*1024))'실행하면 다음과 같이 뜰 것이다.
\n$ node -e 'console.log(v8.getHeapStatistics().heap_size_limit/(1024*1024))'\n495.75위 용량을 참고해서 위 용량보다 적당히 더 큰 용량으로 힙 용량을 설정하면 된다. 힙 용량의 설정은 다음 명령어를 마스토돈 설정 명령어 실행 직전에 실행함으로써 할 수 있다.
\nexport NODE_OPTIONS=--max_old_space_size=800다음 명령어를 실행해 마스토돈 서버를 설정한다.
\nRAILS_ENV=production bundle exec rake mastodon:setup만약 Javascript heap out of memory 오류가 떴다면 바로 윗 문단에 따라 힙 용량 및 swap 설정을 하고 다음 명령어를 실행하면 된다.
\nRAILS_ENV=production bundle exec rails assets:precompile성공적으로 실행됐을 시 마스토돈 관리자 비밀번호가 표시될 것이다. 잊지 말고 메모하도록 하자.
\n다음 명령어를 실행한다.
\ncp /home/mastodon/live/dist/nginx.conf /etc/nginx/sites-available/mastodon\nln -s /etc/nginx/sites-available/mastodon /etc/nginx/sites-enabled/mastodon/etc/nginx/sites-available/mastodon 파일에서 example.com을 모두 자신의 마스토돈 도메인(내 경우에는 social.litehell.info)로 바꾼다. 그리고 다음 명령어를 실행한다.
systemctl reload nginx필자는 CloudFlare Origin Certificate를 쓴다. CloudFlare에서 Origin Certificate를 생성한 뒤 서버에 저장하고, /etc/nginx/sites-available/mastodon 파일에서 ssl_certificate 속성과 ssl_certificate_key를 다운받은 서버/서버 개인키 경로로 수정하면 된다.
아래 명령어를 실행한다.
\ncp /home/mastodon/live/dist/mastodon-*.service /etc/systemd/system/\nsystemctl daemon-reload\nsystemctl enable --now mastodon-web mastodon-sidekiq mastodon-streaming\n그러면 마스토돈이 실행될 것이다. 이제 즐기면 된다.
\n![\"CSS가](\"/img/broken_css_mastodon.png\")
CloudFlare를 쓰면 위와 같이 마스토돈이 깨지는 문제를 겪을 수 있다.\n이는, 무결성을 위해 HTML 내에 CSS 파일의 해시가 포함되어있는데, CloudFlare가 CSS를 자동 최적화하면서 CSS 파일이 변경되고, 이로 인해 해시가 불일치됨에 따라 웹브라우저가 CSS를 불러오지 않음으로써 발생하는 문제이다.
\n이 문제는 CloudFlare에서 Auto Minify를 비활성화하고 모든 캐시를 삭제하여 해결할 수 있다.
\n마스토돈에 혼자 있으면 외롭다. 이를 극복하기 위해서는 릴레이를 연결해야 한다. 페디버스 내에서 인스턴스는 기본적으로 게시물을 팔로워가 있는 서버에만 전송한다. 따라서 타 서버의 팔로워가 없는 인스턴스는 외로울 수 밖에 없다. 이를 극복하기 위해 릴레이가 있다.
\n릴레이는 구독하는 서버들간에 게시물을 나눈다. 릴레이에 구독된 인스턴스가 게시물을 릴레이로 보내면, 릴레이가 구독된 모든 서버들에게 게시물을 전송하는 방식이다. 따라서 릴레이내에 있는 서버간에는 팔로워가 있는지의 여부와 상관없이 게시물이 서로 공유된다.
\n한국어권 릴레이는 다음 세가지 릴레이가 있다. 이 릴레이는 모두 화이트리스트이다.
\n\n위 릴레이에 가입하기 위해서는 각 릴레이에서 요구하는 조건을 모두 만족시킨 뒤 릴레이측에 가입 신청을 하면 된다. 가입 신청 방법 및 조건은 릴레이마다 다르다. 가입 신청이 받아들여지면 릴레이 관리 페이지(/admin/relays)에서 해당 릴레이에서 안내하는 주소를 추가하면 된다. 참고로 내 경험상 개인 인스턴스라고 딱히 안 받아주진 않았다. 조건만 맞으면 받아주는 것 같으니 조건이 맞는다면 부담없이 신청해보자.
모든 릴레이가 화이트리스트인 것은 아니다. RelayList에서 Registeration이 open으로 되어있는 릴레이는 가입신청을 하지 않아도 되는 릴레이들이다. 다만 대규모 릴레이는 구독이 처리되는 데 시간이 좀 오래 걸릴 수 있다.
\n#FediBuzz Relay 서비스를 이용하면 특정 마스토돈 인스턴스의 타임라인을 릴레이를 통해 구독할 수도 있다. 해당 사이트의 안내를 따르면 특정 인스턴스의 타임라인을 구독할 수 있다.
\npublic/system 디렉토리는 용량을 많이 잡아먹는다. 다음 두 가지 방법 중 하나를 택하여 해결하면 된다.
RAILS_ENV=production ./bin/tootctl accounts prune\nRAILS_ENV=production ./bin/tootctl cache clear\nRAILS_ENV=production ./bin/tootctl media remove --days=0\nRAILS_ENV=production ./bin/tootctl media remove --prune-profiles --days=0\nRAILS_ENV=production ./bin/tootctl preview_cards remove --days=0/etc/fstab 파일 수정해서 public/system 디렉토리에 영구 마운트해버리기 (좀 무식하게 보일 수도 있지만 간단하고 직빵이다)마음에 드는 방법을 택하도록 하자.
\n", "url": "https://blog.litehell.info/post/creating_mastodon_instance", "title": "Mastodon 서버 구축하기", "summary": "6$짜리 VPS와 CloudFlare를 이용한 인스턴스 구축", "image": "https://blog.litehell.info/img/broken_css_mastodon.png", "date_modified": "2023-07-22T15:55:38.110Z" }, { "id": "min_max_heap", "content_html": "백준 이중 우선순위 큐 문제는 본 글에서 소개하는 최소-최대 힙(Min-max heap)을 구현하면 풀리는 문제이다.
\n필자는 최소-최대 힙을 시도하기에 앞서 다른 방법(최소 힙이랑 최대 힙 두개 만들기)을 시도했었으나 능력이 부족한 탓인지 실패했다. 따라서 이 방법의 정석적인 풀이방법인 최소-최대 힙을 영문 위키백과의 Min-max heap 문서을 보면서 풀었다. 이 글에서는 최소-최대 힙에 대해 설명하고 C++ 구현 코드를 제시하고자 한다.
\nHeap은 최소값이나 최대값 등을 빠르게 구하기 위해 만들어진 완전 이진 트리(Complete binary tree) 형태의 자료구조이다. 일반적으로 Heap이라고 말할 때는 보통 최대 힙(Max-heap)이나 최소 힙(Min-heap)을 의미한다. 이 중에서 최대 힙은 다음과 같이 구현된다.
\n최소 힙은 위에서 비교하는 방향만 돌려서 다음과 같이 구현하면 된다.
\n위와 같이 구현된 최대 힙에서는 항상 가장 큰 값을 가진 원소가 루트가 되며, 최소 힙에서는 가장 작은 값을 가진 원소가 항상 루트가 된다. 즉, 최대 힙을 이용하면 주어진 값들 중에서 최댓값을 빠르게 구할 수 있으며, 최소 힙을 이용하면 최소값을 빠르게 구할 수 있다.
\n그렇다면 여기서 궁금증이 하나 생긴다, 최댓값과 최소값을 둘 다 빠르게 구할 수 있는 힙 자료구조가 있을까? 이에 대한 정답은 본 글에서 소개하고자 하는 최소-최대 힙이다.
\nMin-max heap(최소-최대 힙)은 홀수번째 레벨(이하 Min-level)의 원소는 그 밑에 있는 모든 원소들보다 작거나 같은 값을 가지며, 짝수번째 레벨(이하 Max-level)의 원소는 그 밑에 있는 모든 원소들보다 크거나 같은 값을 가진다. 루트가 있는 레벨은 Min-level이다.
\n![\"예시](\"/img/min_max_heap/example.svg\")
위 예시를 보자. Min-level에 있는 원소는 그 하위에 있는 원소들보다 작은 값을 가지며, Max-level에 있는 원소는 그 밑에 있는 원소들보다 큰 값을 가진다.
\n따라서 우리는 최소-최대 힙에서 (루트는 Min-level이므로) 루트는 항상 힙의 최소값을 가지며, 2번째 레벨에 있는(루트 바로 밑 레벨에 있는) 두 원소 중 가장 큰 값이 힙의 최댓값을 나타냄을 알 수 있다.
\n최소-최대 힙의 구현은 다음과 같이 이루어진다.
\n위를 구현하기 위해서는 Push-up과 Push-down 알고리즘을 구현해야 한다.
\n예시를 들어 설명해보자. 다음 예시를 보라.
\n![\"예시](\"/img/min_max_heap/pushup/step1.svg\")
위 그래프는 유효한 최소-최대힙이다. 위 그래프의 맨 끝에 3이라는 값을 추가했다고 가정해보자. 3을 추가할 시 아래와 같이 변한다.
\n![\"예시](\"/img/min_max_heap/pushup/step2.svg\")
값을 추가하는 순간 유효한 최소-최대 힙이 아니게 된다. Min-level에 있는 6보다 더 작은 자식 3이 생기기 때문이다.
\n따라서 이 그래프를 다시 최소-최대 힙으로 만들기 위해서는 원소 3을 위로 올려가면서 적절한 위치를 찾아야 한다.\n먼저, 추가한 값인 3이 Min-level에 있는 부모(6)보다 작다. 이는 최소-최대 힙의 조건과 모순되므로 부모와 추가된 값의 위치를 서로 바꿔준다.
\n![\"에시](\"/img/min_max_heap/pushup/step3.svg\")
추가된 값이 부모와 바꿔지면서 Min-level로 옮겨졌음을 확인할 수 있다. 이제 3은 3을 루트로 하는 서브트리 내에서만큼은 무결하다. 왜나하면, 최소-최대 힙에서 루트에 있던 값은 그 밑의 모든 값들보다 작거나(혹은 루트의 레벨에 따라서, 크거나) 같아야 한다는 특징이 있는데, 이 값이 (6에서 3으로) 더 작아지는 것이 이 특징을 깨트리지 않음은 자명하기 때문이다.
\n그러나, 위 그래프는 아직도 최소-최대 힙의 특징을 만족하지 못한다. 5번째 레벨의 원소(값: 4)와 7번째 레벨의 원소(값: 5)를 보라. 5번째 레벨과 7번째 레벨은 홀수번째 레벨이므로 Min-level이다. 따라서 원소 4의 하위 원소들은 모두 값이 4보다 크거나 같아야 하고, 원소 5의 하위 원소들도 모두 값이 5보다 크거나 같아야 한다. 그러나 원소 3은 5나 4보다 크거나 같지 않다. 원소 5(혹은 4)의 하위 원소인 원소 3이 5(혹은 4)보다 작은 값을 가지므로 최소-최대 힙의 조건과 모순된다.
\n따라서 이 모순을 해결하기 위해, 원소 3을 상위의 Min-level에 있는 원소(위 사진에서 파란색으로 표시된 원소들)들과 비교하며 적절한 위치를 찾아야 한다. 원소 3을 파란색으로 표시된 원소들과 비교하여 위로 올려가며 적절한 위치를 찾은 결과는 다음과 같다.
\n![\"에시](\"/img/min_max_heap/pushup/step4.svg\")
최소-최대 힙에 값 6이 성공적으로 추가됐음을 알 수 있다.
\n따라서 우리는 이 예시가 다음과 같은 알고리즘에 따라 이루어졌음을 알 수 있다.
\n위 알고리즘을 A가 처음에 Min-level에 추가된 경우로까지 확장하면 다음과 같다.
\n위 알고리즘이 최소-최대 힙의 Push-Up 알고리즘이다. 이 알고리즘을 이용하면 원소의 추가를 구현할 수 있다.
\nPush-down은 다음과 같이 구현한다. 먼저, 아래와 같은 유효한 최소-최대 힙이이 있다고 가정하자.
\n![\"Min-max](\"/img/min_max_heap/pushdown/step1.svg\")
위 힙에서 최소값을 제거하고 최소값이 있던 자리(루트)에 8을 넣었다고 가정해보자. 그 결과는 다음과 같다.
\n![\"Min-max](\"/img/min_max_heap/pushdown/step2.svg\")
위 그래프는 유효한 최소-최대 힙이 아니다. 따라서 이 그래프를 최소-최대 힙으로 만들기 위해서는 원소들의 위치를 아래로 내려가며 조정해야 한다.
\n먼저, 위 그래프에서 원소 8은 Min-level에 있다. 따라서 원소 8의 자식(Child)과 손자(Grandchild)들중 가장 작은 값을 가진 원소를 확인한다. 이 원소는 2이다.
\n원소 2가 원소 8보다 더 작음은 Min-max heap의 조건에 모순된다. 따라서 원소 2와 원소 8의 위치를 서로 바꾼다.
\n![\"Min-max](\"/img/min_max_heap/pushdown/step3.svg\")
원소 2와 원소 8의 위치를 서로 바꾸었지만 Max-level에 있는 원소 7이 자식인 원소 8보다 더 작은 값을 가지고 있다. 이는 모순이다. 따라서 원소 7과 원소 8의 위치를 서로 바꾼다.
\n![\"Min-max](\"/img/min_max_heap/pushdown/step4.svg\")
이제 원소 2는 하위에 있는 모든 원소들보다 작은 값을 가지고, 원소 8은 하위에 있는 모든 원소들보다 큰 값을 가진다. 원소 7 위로는 Min-max heap의 조건과 모순되는 원소가 없다. 그러나 원소 7의 밑을 보라. 원소 7은 Min-level이므로 원소 7 하위의 모든 원소들보다 작거나 같은 값을 가져야 한다. 그러나 원소 6, 3, 5, 4로 인하여 이 조건이 만족되지 않는다.
\n이를 해결하기 위해 원소 7의 자식과 손자들 중 가장 작은 값을 가진 원소를 찾는다. 이러한 원소는 3이다. 원소 3으로 인하여 원소 7이 Min-level의 조건을 만족하지 않으니 원소 3과 원소 7의 위치를 서로 바꾼다.
\n![\"Min-max](\"/img/min_max_heap/pushdown/step5.svg\")
원소 7의 부모는 Max-level이므로 원소 7의 부모는 원소 7보다 더 크거나 같은 값을 가져야 한다. 그러나 부모 원소의 값은 6이므로 7보다 크거나 같은 값이 아니다. 따라서 원소 7과 6의 위치를 서로 바꾼다.
\n![\"Min-max](\"/img/min_max_heap/pushdown/step6.svg\")
이제 원소 6 위의 모든 원소들 (2, 8, 3, 7)들은 Min-level과 Max-level의 조건을 만족한다. 그러나 원소 6은 Min-level의 조건을 만족하지 못한다. 따라서 원소 6이 Min-level의 조건을 만족하도록 하기 위해 원소 6의 자식과 손자들 중 가장 작은 값을 가진 원소를 찾는다. 이 원소는 4이다. 원소 4는 Min-level인 원소 6의 손자임이도 불구하고 6보다 작은 값을 가지고 있다. 이는 모순이므로 원소 6과 4의 위치를 바꾼다.
\n![\"Min-max](\"/img/min_max_heap/pushdown/step7.svg\")
원소 6의 부모를 보자. 원소 6의 부모의 값은 5인데, 이 부모 원소는 Max-level에 있다. 이는 모순이다. 이 모순을 해결하기 위해 원소 6과 원소 5의 위치를 서로 바꾼다.
\n![\"Min-max](\"/img/min_max_heap/pushdown/step8.svg\")
이제 유효한 Min-max heap이 만들어졌음을 확인할 수 있다. 이 예시로부터 알고리즘을 도출하면 다음과 같다.
\ni라고 하자.i번째 위치에 있는 원소에 대하여 이 알고리즘을 다시 실행한다.위 알고리즘을 A가 Max-level인 경우로까지 확장하면 다음과 같다.
\ni라고 하자.i번째 위치에 있는 원소에 대하여 이 알고리즘을 다시 실행한다.i라고 하자.i번째 위치에 있는 원소에 대하여 이 알고리즘을 다시 실행한다.이제 위에서 PushUp과 Pushdown의 구현 알고리즘을 살펴봤으므로 아래와 같이 C++로 구현할 수 있다.
\n\n\n\n\n\n\n\nint heapCount = 0; // How many elements in the heap?\nint heap[1000001]; // Heap, starting from index 1\n\nvoid insertHeap(int item); // inserts an element\nvoid popMin(); // removes minimum element\nvoid popMax(); // removes maximum element\nint seekMin(); // reads minimum element\nint seekMax(); // reads maximum element\n\n/**\n * Implementation of min/max pop using push-down\n */\n\n// Picks index of largest(or smallest) child(or grandchild) of given element\nint pickLargetOrSmallestDescendantIndex(int index, bool largest) {\n int resultIndex = index * 2, resultValue = heap[index * 2];\n int candids[] = { // Children and grandchildren\n index * 2 + 1, // Right child\n index * 4, // 1st grandchild (Left child of left child)\n index * 4 + 1, // 2nd grandchild (Right child of left cihld)\n index * 4 + 2, // 3rd grandchild (Left child of right child)\n index * 4 + 3 // 4th grandchild (Right child of right child)\n };\n\n for (auto candidIndex: candids) {\n if (candidIndex > heapCount)\n continue; // If it's invalid index, continue\n\n if (largest && resultValue < heap[candidIndex]) {\n resultValue = heap[candidIndex];\n resultIndex = candidIndex;\n } else if (!largest && resultValue > heap[candidIndex]) {\n resultValue = heap[candidIndex];\n resultIndex = candidIndex;\n }\n }\n\n return resultIndex;\n}\n\nvoid pushDownMin(int index);\nvoid pushDownMax(int index);\n\nvoid pushDown(int index) {\n if (IS_MIN_LEVEL(index)) {\n pushDownMin(index);\n } else {\n pushDownMax(index);\n }\n}\n\nvoid pushDownMin(int index) {\n if (index * 2 <= heapCount) { // if has children\n int m = pickLargetOrSmallestDescendantIndex(index, false);\n\n if (m >= index * 4) { // if m is a grandchild\n if (heap[m] < heap[index]) {\n SWAP_HEAP(m, index);\n if (heap[m] > heap[m / 2]) {\n SWAP_HEAP(m, m / 2);\n }\n pushDown(m);\n }\n } else if (heap[m] < heap[index]) {\n SWAP_HEAP(m, index); \n }\n }\n}\n\nvoid pushDownMax(int index) {\n if (index * 2 <= heapCount) { // if has children\n int m = pickLargetOrSmallestDescendantIndex(index, true);\n\n if (m >= index * 4) { // if m is a grandchild\n if (heap[m] > heap[index]) {\n SWAP_HEAP(m, index);\n if (heap[m] < heap[m / 2]) {\n SWAP_HEAP(m, m / 2);\n }\n pushDown(m);\n }\n } else if (heap[m] > heap[index]) {\n SWAP_HEAP(m, index); \n }\n }\n}\n\nvoid popMin() {\n if (heapCount <= 0)\n return;\n // Removes minimum element\n heap[1] = heap[heapCount--];\n // Push down root element to make the heap valid min-max heap\n pushDown(1);\n}\n\nvoid popMax() {\n if (heapCount <= 0)\n return;\n\n int index;\n if (heapCount == 1)\n index = 1;\n else if (heapCount == 2)\n index = 2;\n else\n index = heap[2] > heap[3] ? 2 : 3;\n\n // Removes maximum element\n heap[index] = heap[heapCount--];\n // Push down to root element make the heap valid min-max heap\n pushDown(index);\n}\n\n/**\n * Implementation of insertion using push-up\n */\n\nvoid pushUpMin(int index) {\n if (index >= 4 && // if index >= 4, it must have a grandparent.\n heap[index] < heap[index / 4]) {\n SWAP_HEAP(index, index / 4);\n pushUpMin(index / 4);\n }\n}\n\nvoid pushUpMax(int index) {\n if (index >= 4 && // if index >= 4, it must have a grandparent.\n heap[index] > heap[index / 4]) {\n SWAP_HEAP(index, index / 4);\n pushUpMax(index / 4);\n }\n}\n\nvoid pushUp(int index) {\n if (index != 1) {\n if (IS_MIN_LEVEL(index)) {\n if (heap[index] > heap[index / 2]) {\n SWAP_HEAP(index, index / 2);\n pushUpMax(index / 2);\n } else {\n pushUpMin(index);\n }\n } else {\n if (heap[index] < heap[index / 2]) {\n SWAP_HEAP(index, index / 2);\n pushUpMin(index / 2);\n } else {\n pushUpMax(index);\n }\n }\n }\n}\n\nvoid insertHeap(int item) {\n heap[++heapCount] = item;\n pushUp(heapCount);\n}\n\n\nint seekMin() {\n return heap[1];\n}\n\nint seekMax() {\n if (heapCount == 1) {\n return heap[1];\n } else if (heapCount == 2) {\n return heap[2];\n } else {\n return std::max(heap[2], heap[3]);\n }\n\n}\n\nint main() {\n std::cin.tie(NULL);\n std::ios_base::sync_with_stdio(false);\n\n // How many test cases?\n int t;\n std::cin >> t;\n\n for (int i = 0; i < t; i++) {\n // How many operations?\n int q;\n std::cin >> q;\n\n // Process operations\n for (int j = 0; j < q; j++) {\n char c;\n int data;\n std::cin >> c >> data;\n\n switch(c) {\n case 'I':\n insertHeap(data);\n break;\n case 'D':\n if (data == -1)\n popMin();\n else\n popMax();\n }\n }\n\n // Print result\n int max = seekMax(), min = seekMin();\n\n if (heapCount == 0)\n std::cout << "EMPTY\\n";\n else\n std::cout << max << ' ' << min << '\\n';\n heapCount = 0;\n }\n}