미래기술챌린지

CJ대한통운 물류기술연구소에서 운영하는 대회로, 올해로 3회째를 맞이했습니다. 상위 6개팀에게는 총 4300만원의 상금과 채용우대특전이 주어집니다. 이번 대회는 271팀이 지원했다고 합니다.

과제 개발

과제는 총 4개가 주어졌습니다. 그 중 1번 과제인 [스마트폰을 이용한 상자 체적 측정] 과제를 선택했습니다. 주요 포인트는 사진으로부터 상자를 인식하는 머신러닝 기술과 사진 좌표계를 공간좌표계로 변환하는 알고리즘이었습니다. 여기에 더해 모바일 환경에서 이 모든 것이 On-Device로 작동해야합니다. iOS 와 안드로이드를 모두 지원할 수 있도록 하고 싶었기 때문에, 웹기반 기술을 이용하여 포팅하고자 했습니다. 따라서 웹에서 머신러닝을 돌리기 위해 ONNX RunTime 을 이용했고, 이미지 처리를 위해 OpenCVjs 를 이용했습니다.

상자인식 머신러닝

머신러닝 모델 후보로는 detectron2, MRCNN, U2Net 세 가지가 있었고, 결과적으로 ONNX 포팅 문제와 모서리 추적 성능을 이유로 U2Net 을 이용하기로 결정했습니다. 다만, U2Net에서는 상자만을 따로 추출하는 것이 아니라 모든 Object를 가져오기 때문에 각 Object가 상자인지를 평가하는 알고리즘을 추가적으로 만들어야 했습니다. 성능 측면에서는 ONNX RunTime 이 WASM 을 이용하기 때문에 cpu 기준으로는 그렇게 느리진 않았지만, gpu 를 이용하는 것과 비교하면 지나치게 느렸습니다. 이를 해결하기 위한 방법으로는 webgl, webGPU 기술이 있기는 했지만, 아이폰에서는 webgl 이 지원되지 않았고, webGPU는 U2Net 모델과 호환이 되지 않았습니다. 성능측면에서는 아무래도 아쉬움이 남습니다.

공간좌표계 변환

공간좌표계로 변환하는 것은 바닥면을 대상으로만 진행했습니다. 윗면의 점은 각각 대응되는 아랫면의 점이 존재하기 때문에 우선순위는 구하기쉬운 바닥면이었습니다. 그러나 바닥면의 위상을 어떻게 알아낼지는 또 다른 문제였습니다. 그래서 바닥면의 위상구조를 알아내기 위한 방법으로 레퍼런스 이미지 인식 기능을 만들어야했습니다. 레퍼런스 이미지를 OpenCV 컨투어를 이용하여 특징을 검출해 찾아내는 것은 꽤 재미있었습니다. 그러나 위상구조의 세부항목인 거리, 각도, 초점거리, 틸트각은 상당히 골치아픈 부분이었습니다. 정말 다양한 방법을 시도해보았고 결론적으로 파라메트릭 서치를 적용하여 해결해낼 수 있었습니다. 그 이후로 실제 공간좌표계로 변환하는 과정은 기하학 구조를 이용하여 수식을 찾아내 적용했습니다. 그리고 높이를 구하는 부분은 영사점을 이용하여 측정해낼 수 있었습니다.

포팅

포팅은 기본적으로 웹뷰를 이용하려고 했습니다. 그러나 iOS 쪽에서는 골치아픈 문제가 있었습니다. userMedia 를 이용하기 위해 https 또는 file 프로토콜을 이용해야했지만, iOS의 내부 파일구조는 해당 프로토콜을 제공하지 않아 권한이 부여되지 않는 문제가 있었습니다. 그래서 필요한 JS파일을 텍스트로 불러와서 하나의 파일로 임시 주소를 부여하여 웹뷰에 띄우는 형태로 처리했습니다. 그렇게 해결이 되나 했지만, fetch 에서 CORS 문제로 U2Net 모델을 불러오지 못하게 되었습니다. 결국 U2Net 모델을 base64 인코딩하여 텍스트로 저장하여 해결했습니다.

예선

예선 때에는 간단한 프레젠테이션 발표와 함께 시나리오에 맞추어 상자의 크기를 직접 측정하여 점수를 기록했습니다. 개발환경과 차이가 있었음에도 꽤 정확하게 상자가 인식이 잘되었습니다. 그러나 막상 실제 값과 오차가 기대보다 크게 나왔습니다. 예선이 끝나고 보니 레퍼런스 크기를 잘못입력해두고 진행한 것을 뒤늦게 알게되었습니다. 만약 제대로 입력했다면 정말 정확한 값들이 나왔었기 때문에 아쉬움이 조금 남았습니다. 그래서 본선까지 남은 기간 동안에 추가 개발에 들어갔습니다. 레퍼런스 크기를 직접 입력하지 않아도 알아서 자동으로 크기를 인식할 수 있도록 하는 기능이었습니다. A4 용지에 출력되어 있다면, 그 용지 크기로 부터 자동으로 레퍼런스 크기까지 인식해줍니다.

본선

예선과 달리 본선에서는 다른 과제를 진행한 팀들과도 함께 경쟁을 해야했습니다. 즉, 결과물의 점수로 경쟁을 하는 것이 아니라 프레젠테이션에서 얼마나 높은 평가를 받을 수 있느냐가 중요했습니다. 그래서 프레젠테이션을 완전히 새로 만들었습니다. 각 과정을 구체적인 논리를 담아 근거를 추가했습니다.

시상식

최종 6팀에 선정이 되어 시상식에 참여하게 되었습니다. 당일 발표까지도 순위를 공개하지 않아서 참여하러 가면서까지도 설레는 마음이었습니다. 최종적으로 2등상인 금상을 수상하게 되었습니다.

1차 예선

1번 <증강현실 배달 안경>

간단한 식 하나면 끝나는 문제였습니다.

2번 <딸기 수확 로봇>

범위에 따라 케이스를 나누어 생각하면 어렵지 않게 스위핑으로 풀 수 있습니다.

3번 <장난감>

규칙을 떠올리면 간단하게 풀 수 있는 문제였습니다. 초기 상태에 따라 두 가지로 케이스를 나누어 시뮬레이션을 한 뒤에, KMP를 이용하여 최소 패턴 길이를 계산했습니다.

4번 <최적의 프로세스 수행 순서>

이 문제도 KMP를 조금 변형하여 활용하면 될 것 같아보였습니다. 근데 생각보다 잘 안됐고, 몇 번 틀리다가 포기했습니다.

5번

사실 3문제를 풀면 1차 예선을 통과한다는 것을 작년의 경험으로 알고 있었기에 4번을 포기하면서 5번도 포기했습니다. 다른 대회 프로젝트 마감과 소프트웨어 마에스트로 중간발표가 얼마 남지 않아서 많은 시간을 투자할 수는 없었습니다. 5번은 문제를 대충 봤을 때 어려워보였기 때문에 시간을 들여도 결과는 같았을 것이라고 생각합니다.

2차 예선

1번 <타이젠 윷놀이>

윷놀이판에서 말이 이동하는 방식을 함수로 미리 만들어두고, 최소 반복패턴을 찾으면 해결할 수 있습니다.

2번 <괄호 문자열>

스택을 이용해서 풀 수 있었습니다. 병렬로 된 연속쌍의 개수를 찾고, 그 값을 $\frac{n(n+1)}{2}$ 로 계산해서 더하기만 하면 됩니다.

3번 <루머>

이 문제는 정해가 도저히 생각이 안나서, 비트마스크를 이용하여 $O(2^n)$으로 최저 점수 45점만 받고 넘겼습니다.

4번 <막대기 연결>

이 문제 역시 정해가 생각이 안나 부분점수를 노렸습니다. $n^2$짜리 DP테이블을 만들면 오프라인 쿼리 없이도 부분점수 180점을 받을 수 있었습니다.

5번 <스마트 아파트 건설>

이 문제도 부분점수를 노렸습니다. 단순히 next_permutation 을 사용해서 부분점수 60점을 받았습니다.

본선

1번 <돌 게임>

홀짝으로부터 규칙성을 찾아서 해결했습니다. 묶음 수 N과 각 돌의 수를 모두 XOR 계산해두었고, 돌이 짝수개인 수를 계산하여 이와 홀짝을 비교했습니다.

4번 <그릇>

규칙을 찾아내서 점화식을 유도해보았습니다.

$$x_{ij}=2x_{(i-1)j} + (i-2)x_{(i-1)(j-1)}$$

위 식이었는데, 이를 통해 $$N^2$$ DP 테이블을 만들어서 진행하려고 생각했습니다. N<=5000 제한이었기에 시간복잡도 상으로 충분히 통과되지 않을까 생각했는데 왜인지 시간초과가 나왔습니다. 더 최적화된 점화식이 있는 것 같습니다. 결국 N<=400 의 부분점수만을 받았고, 아쉬움이 남아 대회가 끝날 때까지 계속 고민해보았지만, 끝내 점수를 다 받지 못했습니다.

끝

마지막 SCPC가 끝이 났고, 수상은 못했지만 본선에 참가할 수 있었던 것만으로도 충분히 만족스럽습니다.

이제 성인부 만들어주세요

소마라고 줄여서 부르기도 하는 소프트웨어 마에스트로는 SW인재양성을 위한 국가지원사업입니다. 부트캠프와 비교해보자면 소마는 실제 프로젝트를 만들고 출시하기때문에 이미 개발능력이 어느정도 갖춰진 분들이 주로 지원합니다. 노트북, 장학금, 활동비, 멘토링, 공간지원 등 연수생들에게 지원되는 혜택이 상당하기 때문에 경쟁률도 높습니다.

지원하기까지

약 반년 전에 소프트웨어 마에스트로의 존재를 알게 되었고, 실력있는 분들과 함께 프로젝트를 할 수 있다는 점이 매력적으로 느껴져 다음 모집에 꼭 지원해야겠다고 생각했었습니다. 그런데 막상 지원을 하려니 망설여졌습니다. 프레임워크를 다루지도 못하고 쓸만한 프로젝트도 없는 상태로 지원하기에 너무 자신이 없었습니다. 그런 이유로 지원을 미루고 있다가 지원 마감날이 되어버렸습니다. 당시 특강을 듣고 있었는데, 점심시간에 동기분 한분이 소마 자기소개서를 마무리하고 계셨습니다. 그러면서 소마에 대한 이야기를 나누어보았는데 일단 서류로는 많이 거르지 않으니 지원해보라는 권유를 받고 급하게 자기소개서를 작성하게 되었습니다.

코딩테스트

이야기들었던 대로 서류만으로 탈락하는 경우는 거의 없는 것 같습니다. 그 다음 전형은 코딩테스트였습니다. 유형은 알고리즘 문제와 SQL 문제가 나오게 되고, 1차와 2차로 총 두번을 보게 됩니다. 그런데 1차 시험 당시에 시스템 네트워크 이슈로 인하여 전부 합격처리가 되어서 전원 2차 시험을 볼 수 있게 되었습니다. 대충 느끼기로는 구현/시뮬레이션을 위주로한 알고리즘 문제가 대부분이었던 것 같고, SQL 은 서브쿼리와 조인, 몇몇 함수들을 알아야 하는 문제가 나왔습니다. 제 경우에는 4+1 총 5문제 중에 2+1로 총 3문제를 맞추었다고 생각합니다. 결과를 알려주지 않아서 실제로 3문제를 맞추었는지는 확실하지는 않습니다.

포트폴리오

면접에 앞서 자신을 소개하는 포트폴리오를 만들어 제출하라는 안내를 받았습니다. 나중에 면접을 하고나서 느낀 부분이지만 다른 분들은 정말 멋지게 준비를 잘 해오셨던 것에 비하면 저는 너무 초라하게 만들어 갔던 것 같습니다. 포트폴리오는 노션으로 만들어야하고, 링크를 제출하는 방식이었습니다. 3분의 발표시간이 주어진다고 하여 프로젝트를 하나만 소개하면 되겠다는 생각을 했고, 소개하기 위한 프로젝트를 급하게 만들기 시작했습니다. 정확하게 표현하자면 기존에 만든 것을 리팩토링하고 제 강점을 살려 재디자인했습니다.

면접

면접은 양재 aT센터에서 목, 금, 토 3일에 걸쳐 진행되었습니다. 다대다 면접이었고, 제가 봤던 분과에서는 지원자 4분에 면접관 5분이었습니다. 발표 3분, 질의 9분이라고 되어있었고 4명이니까 총 48분으로 계산이 되는데 그 보다는 시간이 덜 걸린 것 같습니다. 분과마다 면접관이 다 다르다보니 분위기나 질의내용은 전부 상이한 것 같습니다. 저희 분과에서는 인성면접 위주였는데, 다른 분과에서는 기술질문이 많이 나오기도 한 모양입니다. 면접을 시작할 때 프린트된 코테문제를 지원자에게 배부했는데, 막상 코테 질문은 전혀 없었습니다.

결과

면접을 다녀와서 다른 분들에 비해 준비가 부족했다고 후회하고 있었는데 운좋게 붙었습니다. 좋은 기회를 받았으니 후회없는 1년이 되도록 열심히 참여하도록 할 것입니다. 사랑해요 소마!

JS와 캔버스로 왠지 친숙한 둥글게 말려있는 디자인의 선택상자를 만들어보았습니다.

GitHub 링크 Demo 페이지

동기

당시 만들던 웹앱 컨셉이 애플스타일이었고, 날짜 선택기를 만들 때도 최대한 그러한 분위기를 내고 싶었습니다. 캔버스를 활용해서 만드는 것에는 성공했으나 더 보편적으로 사용할 수 있도록 만들고 싶었고, 성능 개선에 대한 욕심도 났습니다. 그래서 시간이 지난 후 새롭게 만들어보자는 생각을 했습니다.

기능

최대한 기존 html사용법을 그대로 답습하여 만들 수 있도록 하는데 초점을 맞추었습니다. html의 SELECT태그를 그대로 이용하여 미려한 디자인으로 바꾸어줍니다. SELECT태그를 그대로 사용하기 때문에 만약 캔버스를 사용하지 못하는 웹환경이더라도 사용에 지장이 없습니다. "selected" 속성을 그대로 사용할 수 있으며, 전용 "infinite" 속성을 부여하면 처음과 끝이 이어져 무한히 스크롤할 수 있게됩니다. 글꼴, 글자색과 배경색상은 style을 통해 변경할 수 있습니다. onchange 이벤트도 그대로 발생하기 때문에 대부분의 경우에 SELECT 다루듯이 하더라도 괜찮습니다. 사용자는 손가락을 튕기거나, 클릭하여, 혹은 마우스 스크롤을 하여 선택할 수 있습니다.

개발과정

기존에 만들었던 코드는 스파게티를 넘어 짜파게티 상태였기 때문에 완전히 새롭게 만들게 되었습니다. 그래도 기존에 만들어 본 것을 다시 만드는 것이어서 처음처럼 어렵지는 않았습니다.

객체지향

우선 객체지향적인 관점으로 만들어야겠다는 생각을 하게 되었습니다. 몇 가지 이유가 있었습니다. 우선 한번에 여러개를 사용할 수 있도록 하고 싶었습니다. 기존 코드에서는 여러개의 요소를 동시에 사용하기 번거로운 구조였습니다. 또한 스파게티 코드가 되는 것을 막기위해 더 읽기 쉽고, 유지보수가 용이하게 코드를 작성하고 싶었습니다. 기존 코드는 버그 수정을 하려면 처음부터 끝까지 다 읽어봐야했고, 하나를 수정하면 다른 쪽에서 문제가 발생하곤 했습니다. 결론적으로 더 짜임새있고 확장성이 있는 코드를 만들기 위해서 객체지향을 이용하기로 했습니다. 자바스크립트에서 객체지향을 적용하기 위해서 클래스구조를 이용했습니다.

최적화

둥글게 말린 디자인이기도 하고, 손끝에서 움직이는 느낌을 내기 위해서는 최적화가 매우 중요했습니다. 모양이 유사하더라도 프레임이 많이 끊기면 애플의 그것과 같은 느낌이 잘 살지 않았습니다. 그래서 개발하는 동안 가장 오래 고민한 부분이 최적화였습니다. 둥근 디자인을 위한 연산과정을 줄이기 위해서 다양한 방법을 시도해보았습니다. 높이에 따른 삼각함수의 연산을 미리 전처리해두고 배열에 담아두는 방식으로 연산횟수를 줄일 수 있었고, 캔버스에서 실제 변경되는 부분만을 렌더링하는 방식으로 연산 범위를 줄일 수 있었습니다. offscreen 캔버스에 작업 한 뒤 onscreen 캔버스로 업데이트 하는 방식도 적용해두었고, 리스트를 캔버스에 한번에 그려둔 뒤 필요한 부분을 가져오는 방식을 통해 글자의 렌더링을 줄여 최적화할 수 있었습니다.

버그

폰트가 로딩되기전에 컴포넌트가 먼저 생성되어 기본 글꼴로 적용되는 문제가 있었습니다. 해당 문제는 내부에 option의 내용을 미리 작성해두고 document.fonts.ready 후에 컴포넌트가 생성되도록 하여 해결할 수 있었습니다. 한편 크로미움엔진과 애플웹킷엔진의 캔버스를 다루는 방식이 상이하여 발생하는 문제도 있었습니다. 이 문제는 무한히 스크롤이 가능해지는 "infinite" 기능을 만들 때 발생했습니다. 크로미움엔진은 캔버스의 범위 밖을 렌더링하려하면 캔버스에서 보이는 부분만 그리고 캔버스 밖은 공백으로 그렸지만, 애플웹킷엔진은 아예 범위 밖으로 넘어가지 못하게 끝자락에 맞추어 렌더링했습니다. 이는 결국 더 까다로운 애플웹킷엔진을 기준으로 맞추어 해결했습니다.

작업중

현재 preset 기능을 만들고 있습니다. 이 기능이 완성되면 날짜선택기와 같은 요소를 더 쉽게 만들 수 있게 되며, 써드파티로도 더 확장이 가능해집니다. 추후에 "disabled" 속성이나 "multiple" 속성을 이용할 수 있도록 할 예정입니다. 또한, 키보드를 통한 조작이나 시각장애인을 위한 접근성에 대해서 고민해볼 생각입니다.

입과 과정

삼성SDS에서 진행하는 특강이다보니 어떤 내용을 배울지 궁금하기도 했고, 후술하겠지만 프로자격증 취득 특전을 기대하고 지원하게 되었습니다. 지원은 구글폼을 통해서 이뤄졌고 재학증명서와 성적증명서가 필요했습니다. 지원서 작성 후에는 일정기간 입과테스트가 이루어졌습니다. 입과테스트는 알고리즘 문제를 5개 푸는 것이었는데, 당시 시험기간이었지만 며칠간의 기간을 주고 풀게 하기 때문에 크게 부담은 없었습니다. 그리고 조금 기다리다보니 입과안내 메일을 받을 수 있었습니다. 처음 구글폼으로 지원했을 때, 오프라인과 온라인을 고를 수 있도록 선택란이 있었는데 "상관없음" 을 선택했더니 오프라인으로 입과하게 되었습니다.

본사 탐방기

교육은 2주 평일동안 잠실 SDS본사 델타존에서 진행되었습니다. 오전 9시부터 오후 6시까지의 풀타임으로 진행되기 때문에 오프라인으로 참여하는 입장에서 부담스러운 부분도 있었습니다. 아침에 일어나는 건 힘들었지만 매우 만족스러운 시간이었습니다. 이럴 때 아니면 언제 SDS 본사에 가보겠어라는 생각도 있었고, 오프라인 입과자에 대한 회사의 배려도 많이 느껴졌습니다. 교육기간동안 사내식당을 자유롭게 이용할 수 있도록 중식쿠폰을 제공해주었습니다. 사내식당 규모가 생각 이상으로 상당히 컸습니다. 지하1층에서 지하2층까지 식당이 있었는데, 푸드코트 형태에 식사메뉴가 도합 20개도 넘었던 것 같습니다. 커피쿠폰도 지급되어서 식당 내부에 입점한 폴바셋에서 매일 무료 커피를 마실 수 있었습니다. 델타존 입구쪽에는 간단한 회의나 휴식을 위한 자리가 있었습니다. 첫 방문 때 안내해주셨던 분께서는 자유롭게 사용해도 된다고 말씀하셨는데 막상 함께 강의 들으시던 분들은 왠지 이용을 안하셨던 것 같습니다. 하루 정도는 SDS에 대해서 소개하는 시간을 잠깐 갖기도 했었습니다. Executive Briefing Center 줄여서 EBC 라고 하는 홍보관을 구경하면서 SDS가 개발하는 기술들을 소개받을 수 있었습니다.

강의

강의는 지급된 책과 백준사이트 그룹기능을 통해 진행되었습니다. 배운 내용을 정리하면 우선순위큐, 인덱스트리(세그먼트 트리와 유사한 자료구조), 정수론, 조합론, 그래프알고리즘, DP 정도를 다뤘습니다. 책의 내용을 한번 설명해주시고 문제푸는 시간을 가졌는데, 사실 거의 대부분의 시간은 문제푸는 시간으로 할애되었습니다. 문제풀이와 질문이 주가 되는 강의라고 보면 될 것 같습니다. 오프라인으로 진행함에도 질문이 아무도 없으시길래 다들 잘하시네 생각했었는데, 알고보니 Knox 미팅 채팅으로 조용히 질문하고 계신 것이었습니다.

프로 검정 시험

SDS 내부에는 임직원을 대상으로한 자격시험이 존재합니다. 원래 일반인을 대상으로는 시험을 보게 해주지 않지만 알고리즘 특강 수강생에게 특별히 시험기회가 주어졌습니다. 해당 자격시험에 합격하게되면 바로 임원면접으로 직행하는 채용절차가 존재하기 때문에 많은 수강생분들이 이러한 특전을 염두에 두고 특강에 참가하는 것 같습니다. 해당 시험은 4시간 동안 하나의 알고리즘 문제를 해결하면 되는 시험입니다. 시험을 보기 전에는 난이도에 대해 알지 못하여 3번의 기회동안 한문제만 풀면 되는 것이라면 쉽게 합격하지 않을까라는 기대를 했었습니다. 자세한 문제 내용은 규정상 공개할 수 없지만 1차 시험은 다익스트라를 활용한 DP문제였습니다. 대부분의 케이스에서 통과하였지만 일부 케이스에서 걸리는 것으로 보아 예외처리를 제대로 하지 못한 것으로 보였으나, 결국 시간이 끝날 때까지 해결하지 못했습니다. 2시간 뒤 불합격 문자를 수신하게 됐습니다. 문제 자체의 난이도는 체감 상 플레 중하위 정도로 느껴졌습니다. 이후의 2차 시험에서는 세그먼트 트리 활용하는 문제가 나왔습니다. 강의시간에 다뤘던 내용이 기억에 남아 어렵지 않게 접근할 수 있었습니다. 체감 난이도는 그리 높지 않았으나, 세그먼트 트리가 활용된 문제이다보니 플레 하위 정도의 난이도는 될 것 같습니다. 제 경우에는 기존에 알고리즘을 어느정도 공부한 입장이었기에 부담스러운 난이도는 아니었지만 본 특강으로 알고리즘을 처음 공부하신 분들은 난이도가 높게 느껴질 것 같다는 생각이 들었습니다. 해당 자격을 취득하려는 목적으로 특강에 지원하시는 분들은 미리 공부해가는 것이 좋을 것 같고, 강의해주시는 임직원분들은 모두 해당 자격시험 통과자들이기에 강의 중간중간 시험에 대한 조언을 잘 기억해두시는 것이 도움이 될것이라 생각합니다.

최종 후기

재미있는 시간이었습니다. 알고리즘을 정리해보면서 부족한 부분을 채울 수 있는 기회였고, 다른 분들이 열심히 코드를 짜는 것을 보면서 동기부여도 되었습니다. 본사 구경도 해봤고, 아이스크림 라떼와 사내식당 다양한 메뉴도 맛있게 먹었고, 마무리로 자격시험에 합격하여 기분좋게 마무리 할 수 있었습니다. 방학기간을 통해 알고리즘을 공부하기에 좋은 기회라고 생각하고, 욕심이 있다면 자격시험 합격을 통한 취업특전도 노려볼 수 있으니 방학기간을 알차게 보내기위한 추천할만한 프로그램이라고 생각합니다.

구내식당 후기

식권 및 커피쿠폰. 둘 다 가격 제한이 없어서 메뉴선택은 자유로웠습니다. 폴바셋 아이스크림라떼 (강추) 얼큰이 칼국수 (비추) 뼈해장국 (추천) 함박스테이크 (보통) 비빔밥 (추천) 설렁탕 (추천) 토스트 (보통) 짜장면 (보통)

LCA

두 노드의 루트로부터의 깊이를 확인합니다. 두 노드를 같은 깊이가 되도록 맞추어줍니다. 이는 더 깊은 노드에서 조상을 거슬러 올라가면 됩니다. 같은 깊이가 되었다면 공통 조상을 찾을 때까지 함께 거슬러 올라가도록 합니다.

몇가지 값을 미리 저장해두면 계산이 편리해집니다. 그래서 다음 두가지를 미리 계산하여 저장하도록 합니다. 각 노드마다 루트로부터의 깊이를 계산하여 저장합니다. 각 노드마다 거슬러 올라가는 조상목록을 순서대로 저장합니다.

깊이와 부모

void get_p(int i) {
    for(int j : v[i]) {
        if(!d[j]) {
            d[j] = d[i] + 1;
            p[j].push_back(i);
            mxd = max(mxd, d[j]);
            get_p(j);
        }
    }
}

이런 방식으로 계산하면 $$O(d)$$의 시간복잡도를 갖게 됩니다. 여기서의 d값은 최대 깊이를 의미합니다. 많은 문제에서는 이보다 더 빠른 속도를 요구합니다. 이제 더 효율적이고 빠른 방법을 알아보도록 하겠습니다.

Sparse-Table

sparse table을 이용하면, 조상목록을 거슬러가는 속도를 개선할 수 있습니다. 기본적으로 위에서 보았던 알고리즘에서는 하나씩 올라가는 방식을 선택했기 때문에 $$O(d)$$의 시간복잡도를 가졌습니다. sparse table을 적용하면 2의 거듭제곱만큼 한번에 올라갈 수 있습니다. 따라서, $$O(log{d})$$의 개선된 시간복잡도를 갖습니다.

이제 sparse table을 만드는 방법을 알아보겠습니다.

d[0] = 1;
p[0].push_back(0);
get_p(0);
for(int j = 0; 1 << j < mxd; j++) {
    for(int i = 0; i < N; i++) {
        int k = p[i][j];
        p[i].push_back(p[k][j]);
    }
}

p[i][j]는 i번째 노드의 $$2^{j}$$위 조상을 가르킵니다. 해당 반복문에서는 i번째 노드의 $$2^{j+1}$$위 조상은 i번째 노드의 $$2^{j}$$위 조상의 $$2^{j}$$위 조상이라는 것을 통해 테이블을 채워갑니다.

완성된 sparse table을 이용하여 더 빠르게 LCA를 알아낼 수 있습니다.

if(d[A] < d[B]) swap(A, B);
for(int j = 0, diff = d[A] - d[B]; diff; j++, diff >>= 1) {
    if(diff & 1) A = p[A][j];
}
if(A != B) {
    for(int j = p[0].size()-1; j >= 0; j--) {
        if(p[A][j] != p[B][j]) {
            A = p[A][j];
            B = p[B][j];
        }
    }
    A = p[A][0];
}
// LCA = A

Heavy-Light-Decomposition

흔히 HLD라고 불리는 알고리즘입니다. 아직 공부를 하지 못한 부분이기 때문에 나중에 더 공부하여 내용을 채우겠습니다 :: TBD

팩토리얼 공식

$$\left(\begin{array}{c}n\ k\end{array}\right)=\frac{n!}{(n-k)!\times k!}$$

점화식 공식

$$\left(\begin{array}{c}n\ k\end{array}\right)=\left(\begin{array}{c}n-1\ k-1\end{array}\right)+\left(\begin{array}{c}n-1\ k\end{array}\right)$$

팩토리얼 공식

먼저 이항계수의 정의에 따라 팩토리얼을 계산하여 구하는 방식입니다.

$$\left(\begin{array}{c}n\ k\end{array}\right)=\frac{n!}{(n-k)!\times k!}=\frac{n}{1}\times \frac{n-1}{2}\times \frac{n-2}{3}\times ...\times \frac{n-k+1}{k}$$

위 식을 자세히 보면, (n-1+1)부터 (n-k+1)까지 곱해주고, 1부터 k까지로 나누어 줌을 알 수 있습니다.

long long nck(int n, int k) {
    long long ret = 1;
    for(int i = 1; i <= k; i++)
        ret = ret * (n-i+1) / i;
    return ret;
}

식을 그대로 계산하지 않고 위와 같이 해석하여 적용하는 이유는 속도를 개선하고 정수범위 overflow를 최대한 늦추기 위함입니다. 한편 i로 나눌 때 나누어 떨어지는지가 신경쓰일 수도 있으나, 연속된 t개의 자연수 중에는 반드시 t의 배수가 하나씩 존재하기 때문에 항상 나누어 떨어짐을 직관적으로 알 수 있습니다. 시간복잡도는 $$O(k)$$입니다. 즉, k가 커질수록 느려지게 됩니다.

$$\left(\begin{array}{c}n\ k\end{array}\right)=\left(\begin{array}{c}n\ n-k\end{array}\right)$$

만약 n-k가 더 작다면 위 식에 따라 k와 바꿔줄 수 있습니다.

long long nck(int n, int k) {
    k = min(k, n-k);
    long long ret = 1;
    for(int i = 1; i <= k; i++)
        ret = ret * (n-i+1) / i;
    return ret;
}

점화식 공식

만약, 이항계수를 m번 구해야하는 문제가 주어진다면 위에서 작성한 팩토리얼 코드로는 $$O(mk)$$의 시간복잡도를 갖게 될 것입니다. 이렇게 m번 반복하여 계산하는 문제가 주어질 때는 점화식으로 접근하는 것이 유리합니다.

$$\left(\begin{array}{c}n\ k\end{array}\right)=\left(\begin{array}{c}n-1\ k-1\end{array}\right)+\left(\begin{array}{c}n-1\ k\end{array}\right)$$

이항계수의 점화식은 파스칼의 삼각형을 통해서도 확인할 수 있으며, 조합을 통해 직관적으로 이해할 수도 있습니다. 조합으로 생각해보면, n개 중 k개를 선택할 때의 경우의 수는 한개를 무조건 포함하는 경우의 수와 한개를 무조건 비포함하는 경우의 수를 계산하는 것과 같습니다. 한개를 무조건 포함한다면 n-1개 중 k-1개를 선택하는 상황이 되고, 한개를 무조건 비포함하면 n-1개 중 k개를 선택하는 상황이 됩니다.

long long nck(int n, int k) {
    k = min(k, n-k);
    if(k == 0) return 1;
    if(k == 1) return n;
    long long ret = nck(n-1, k-1) + nck(n-1, k);
    return ret;
}

이렇게 코드를 구성한다면, 시간복잡도가 $$O(n^2)$$가 됩니다. 시간복잡도를 보면 팩토리얼 접근법보다 더 느리다는 것을 알 수 있습니다. 그럼에도 굳이 점화식으로 하는 이유는 메모이제이션을 적용하기 적합하기 때문입니다. 메모이제이션을 사용하게 된다면, 연산을 몇번 반복하더라도 $$O(n^2)$$의 시간복잡도로 유지됩니다.

vector<vector<long long>> nck_(SIZE, vector<long long>(SIZE/2, -1));
long long nck(int n, int k) {
    k = min(k, n-k);
    if(k == 0) return 1;
    if(k == 1) return n;
    long long &ret = nck_[n][k];
    if(ret == -1) ret = nck(n-1, k-1) + nck(n-1, k);
    return ret;
}

이항계수의 값이 커지면서 정수형의 overflow를 겪게 되기 때문에 일반적으로 문제에서는 mod값을 주고, 나머지를 구하도록 시킵니다. 또한 편의를 위해 n값에 따라 메모이제이션 배열의 크기를 자동으로 조절하게 해준다면 아래의 코드가 됩니다.

int mod = 1e9+7;
vector<vector<long long>> nck_;
long long nck(int n, int k) {
    int s = nck_.size();
    if(n-3 > s) nck_.resize(n-3, vector<long long>((n>>1)-1, -1));
    k = min(k, n-k);
    if(k <= 1) return k?n:1;
    long long &r = nck_[n-4][k-2];
    if(r == -1) r = (nck(n-1, k-1) + nck(n-1, k)) % mod;
    return r;
}

여기서 메모이제이션에 사용한 공간복잡도를 생각해본다면, 시간복잡도와 마찬가지로 $$O(n^2)$$이라는 것을 알 수 있습니다. n값이 작을 때에는 문제가 없지만, 값이 커지면 메모리 제한에 걸리게 됩니다.

다시, 팩토리얼

팩토리얼 공식에 메모이제이션을 적용한다면 공간복잡도가 $$O(n)$$이 되어 메모리를 절약할 수 있게 됩니다. 방법은 팩토리얼 값들을 미리 배열에 담아두는 것입니다.

vector<long long> fac_(SIZE, -1);
long long fac(int x) {
    if(x <= 1) return 1;
    long long &ret = fac_[x];
    if(ret == -1) ret = fac(x-1) * x;
    return ret;
}
long long nck(int n, int k) {
    return fac[n] / fac[n-k] / fac[k];
}

이 코드는 n이 작을 때는 잘 작동하지만, n이 커지면 overflow가 발생합니다. 합동식에서 나눗셈이 성립하지 않기 때문에 mod값을 그냥은 적용할 수 없습니다. 그렇기 때문에 합동식의 역원을 찾아야 하고, 이는 페르마 소정리를 통해 해결할 수 있습니다.

페르마 소정리

$$N^{p-2}\times N \equiv 1\space (mod\space p)$$

페르마 소정리를 통하여 N으로 나누는 것과 $$N^{p-2}$$를 곱해주는 것이 합동식에서는 동치라는 것을 확인할 수 있습니다. (p가 소수임을 가정) 이를 곱셈의 역원이라고 하고, 이 역원들 역시 메모이제이션으로 배열에 담아두면 mod를 이용할 수 있게 됩니다. 한편, mod값은 알고리즘 문제에서 보편적으로 $$10^9+7$$ 과 같이 큰 수로 주어집니다. 단순하게 $$N^{p-2}$$에서 N을 하나씩 곱해주기만 한다면, 그것만으로 1초가 넘을 수 있습니다. 그래서 거듭제곱 알고리즘을 이용합니다.

long long x = 1;
for(int i = p-2; i; i /= 2) {
    if(i % 2 == 1) x *= N;
    N *= N;
}

속도개선을 위해 비트연산을 적용할 수도 있습니다.

long long x = 1;
for(int i = p-2; i; i>>=1) {
    if(i&1) x *= N;
    N *= N;
}

이 거듭제곱 알고리즘으로 1부터 n까지의 팩토리얼과 그 역원의 배열을 만드는 것을 코드로 작성한다면,

int mod = 1e9+7;
vector<long long> fac_(n+1), fac_i(n+1, 1);
for(int i = 0; i <= n; i++) fac_[i] = i ? i * fac_[i-1] % mod : 1;
long long x = fac_[n];
long long &t = fac_i[n];
for(int m = mod-2; m; m >>= 1, x = x * x % mod) if(m&1) t = t * x % mod;
for(int i = n; i >= 0 && i; i--) fac_i[i-1] = i * fac_i[i] % mod;

위와 같은 코드가 될 것이고, 이를 통해 이항계수를 계산하는 것은 간단합니다.

long long nck(int n, int k) {
    return fac_[n] * fac_i[k] % mod * fac_i[n-k] % mod;
}

여기에 n값에 따라 자동으로 메모이제이션 크기를 조정하도록 한다면, 다음의 코드가 완성됩니다.

int mod = 1e9+7;
vector<long long> nck_, nck_i;
long long nck(int n, int k) {
    int s=nck_.size();
    if(n>=s) {
        nck_.resize(n+1), nck_i.resize(n+1,1);
        for(int i=s; i<=n; i++)
            nck_[i]=i?i*nck_[i-1]%mod:1;
        long long x=nck_[n];
        long long &t=nck_i[n];
        for(int m = mod-2; m; m>>=1, x=x*x%mod)
            if(m&1) t=t*x%mod;
        for(int i=n; i>=s && i; i--)
            nck_i[i-1]=i*nck_i[i]%mod;
    }
    return nck_[n]*nck_i[k]%mod*nck_i[n-k]%mod;
}

여기서 주의할 점은 자동으로 메모이제이션 크기를 조정하도록 했지만, n이 점차 증가하는 식을 입력받으면 오버헤딩이 크게 발생하게 됩니다. 따라서 편의를 위해 이 코드를 이용한다면, 입력받을 n의 최대값으로 미리 한번 실행시켜둘 필요가 있습니다. 한편 모듈러를 이용하는 식이므로, n값이 mod값보다 큰 경우에는 사용할 수 없습니다. 마지막으로 시간복잡도와 공간복잡도는 $$O(n)$$이 되는데, k값이 충분히 작다면 $$O(k)$$로 구하는 게 더 빠릅니다.

문제 추천

백준 13977 - 이항 계수와 쿼리 백준 6591 - 이항 쇼다운 백준 20296 - 폰친구

코드포스를 시작한 이유

올해 여름 다양한 알고리즘 대회에 참가해보았지만 예선부터 떨어지는 아쉬운 결과만이 남았습니다. 남은 대학 1년동안 더 공부해서 다음 해에는 꼭 대회 수상을 해보고 싶다는 생각을 했고, 백준으로 어느정도 문제를 풀고나서 코드포스로 대회연습을 해보려고 시작했습니다.

코드포스 첫인상

문제가 영어로 주어져있어서 처음엔 부담스러웠지만 어려운 영어는 아니어서 크게 문제되지는 않았습니다. 한편 백준과 다르게 코드포스에는 페널티 점수가 있었습니다. 페널티로 인해 틀리지 않고 빠르게 풀어야하다보니 문제를 분석하고 코드를 작성할 때 집중하게 되었고, 이것 자체로도 공부가 됐다고 생각합니다.

코드포스와 솔브드 티어

아직 블루라서 고티어에서는 어떤지 모르겠지만, 지금 느끼기로는 코드포스와 솔브드 티어는 크게 관련성이 없다고 생각합니다. 기본 알고리즘 몇개정도와, 언어 사용법만 잘 익혀두면 코드포스를 시작하기에 문제는 없는 것 같습니다. 개인적으로 솔브드 티어가 낮더라도 코드포스 티어는 높은게 가능하겠다는 생각입니다.

코테/대회와 코드포스

다른 대회들과 코드포스를 비교하자면 코드포스는 수학적인 아이디어를 생각하도록 하는 문제가 많았습니다. 다른 대회에서는 고급 알고리즘을 사용할 줄 아는지 묻는 문제가 나온다거나, 구현이 복잡한 문제가 나오거나 하기도 하는 것과 비교하면 코드포스는 수학문제에 더 가까웠습니다. 대회중에서는 구글 코드잼 쪽이 가장 유사한 느낌이었고, 기업 코딩테스트와는 완전히 다른 느낌이었습니다. 코딩테스트를 준비하시는 분이라면 굳이 코드포스를 할 필요는 없는 것 같습니다.

하면서 깨달은 것

앞에 쉬운 문제는 글 안읽고, 예제부터 보는게 더 빠릅니다. 많이 못풀더라도 빠르게 풀기만하면 점수가 많이 오릅니다. 빨리 푸는 측면에서 자체개발 QuickCoder 덕을 좀 봤습니다.

향후 목표

민트로 떨어지지 않고 퍼플로 등반하기!

문제 구성도 재미있었고, 운좋게 1등도 하여 상품도 받게 되었습니다. 다른 학교에 비해 우리 학교가 알고리즘에 대해 관심이 낮은 것 같다고 생각하고 있었는데, 내년에도 그 후에도 계속 대회가 계속되어 학교 학생분들이 알고리즘 풀이에 더 많이 관심을 가졌으면 하는 생각이 듭니다. 한편으로 시험기간임에도 재미있는 대회를 준비해준 주최측에 감사하게 생각합니다.

아래 이미지는 출제자 블로그 갈무리. 출처 : https://kth990303.tistory.com/400

1번 문제

인접 사각형 최대 개수 문제 stringstream 을 이용하여 int 값으로 파싱하여 주었고, 순차적으로 읽어들이며 좌우의 인접을 확인해주었습니다. 그리고 직전 층수와 이번 층수간에 인접한 경우를 따로 체크하여 더해주었습니다.

2번 문제

날씨 예측문제 반복 단위인 l 값이 주어지면, 나머지가 0~l-1 인 날짜의 비오는 날과 비오지 않는 날을 각각 더하여 주고, 더 큰 값을 더해주는 전략으로 계산했습니다.

3번 문제

색상을 부여하여 최소 수정횟수 구하는 문제 3x3 의 9개의 영역을 만들어 "2번문제" 처럼 색상값을 각각 더하여 주고, 주어진 조건에 맞으면서 수정횟수가 최소인 때를 고르는 방식으로 해결하고자 했습니다. 그러나 진행과정에서 오류가 발생하였고, 이 문제를 마지막에 풀었었기 때문에 시간적으로 여유가 없는 상태에서 새로 로직을 짜지 못하고 결국 문제를 해결하지 못했습니다.

4번 문제

이진트리에 규칙을 부여하여 가능한 가짓수를 계산하는 문제 트리DP 같아보였지만, 고민하다가 그냥 브루트포스 DFS로 풀었습니다.

기대하던 본선참가 상품은 LG 엑스붐 Go 스피커였습니다. 블루투스로 연결해보니 연결이 잘되었고, 휴대용치고 소리도 괜찮아 맘에 들었습니다. 또 준비해주신 간식거리도 맛있게 먹었고 재미있는 경험이었습니다.

11/30 결과 발표

면접은 가지 못하게 되었습니다. 3번은 확실히 틀렸고, 1번과 2번은 맞게 해결했다고 생각하고, 4번은 브루트포스로 풀어서 채점방식이나 시간제한에 따라 일부 부분점수를 받았을 것이라고 생각합니다. 아쉽긴하지만 좋은 경험이었고 내년에도 이런 좋은 기회가 있었으면 좋겠습니다.

STL 헤더

C++의 장점은 유용한 STL을 이용할 수 있다는 점입니다. 이 STL을 이용하려면, 물론 헤더를 include 해야합니다. iostream, vector, string, algorithm 등 유용한 것이 많은데, 이를 GCC계열 컴파일러에서는 하나로 모아둔 헤더가 존재합니다.

#include <bits/stdc++.h>

대부분의 경우에 위와 같이 한줄만 입력하면 해결이 됩니다. 그러나 환경에 따라 개별적으로 헤더파일을 추가해야하는 경우도 있습니다.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
...

한편, stl을 사용하기 위해서 std라는 namespace를 계속 사용해주어야하는데 이를 생략하려면 다음 한줄을 추가해주면 됩니다.

using namespace std;

I/O 속도개선

입출력에 걸리는 시간을 줄이는 방법이 존재합니다.

먼저 sync_with_stdio를 해제해주면, cin과 cout의 속도가 크게 향상됩니다.

std::ios_base::sync_with_stdio(false);

대신 scanf/printf를 cin/cout 과 같이 쓰지 못하게 됩니다. 정확히는 쓰지 못한다기 보다는 순서가 꼬이는 오류가 발생할 수 있고, 또 멀티쓰레드 환경에서는 사용하지 않는 것이 좋다고 합니다.

cout 출력버퍼를 cin 동작과 묶어주는 것을 해제하면 속도가 조금 빨라집니다. 보통 테스트케이스가 많은 경우에 효과가 높아집니다.

std::cin.tie(NULL);

다만 부분점수를 받을 수 있는 경우에는 출력버퍼를 수동으로 비워줘야 합니다. 그럴 때는 줄바꿈을 endl 로 바꿔주면 됩니다. 이는 SCPC대회 공식 권장사항이기도 합니다.

std::cout << endl;

지금까지 내용을 요약하면 다음과 같습니다.

#include <bits/stdc++.h>
using namespace std;
ios_base::sync_with_stdio(false);
cin.tie(NULL);

입출력

cin으로 받는 입력은 굉장히 편리합니다.

int N, M, K;
cin >> N >> M >> K;

한줄을 문자열로 받을 수도 있습니다.

stirng S;
getline(cin, S);

cout을 통한 출력도 편리합니다.

int N = 37;
cout << N << "\n";

소수를 출력할 때, 자리수를 지정해줄 수 있습니다.

double d = 1.234567;
cout.precision(3);
cout << fixed;
cout << d;

출력 글자수를 맞춰줄 수도 있습니다.

cout.width(n);

출력 글자수를 맞출 때, 빈칸을 채울 문자를 정할 수 있습니다.

cout.fill('*');

벡터

C++에서는 배열을 더 쉽고 유용하게 사용할 수 있게 해주는 vector 컨테이너가 존재합니다.

vector 선언방법

담을 변수의 자료형을 꺽쇠안에 입력합니다.

vector<int> v;

크기를 지정하여 만들어 줄 수도 있습니다.

vector<int> v(10);

배열과 달리 변수로 크기를 설정해도 괜찮습니다.

int size = 10;
vector<int> v(size);

초기값을 정해줄 수도 있습니다.

int size = 10;
vector<int> v(size, 3);

이차원 벡터를 만들 수도 있습니다.

vector<vector<int>> v;

이차원 벡터의 크기 지정은 좀 번거로울 수 있습니다.

vector<vector<int>> v(10, vector<int>(5, 3));

벡터에 값을 추가해줄 수 있습니다.

v.push_back(37);

벡터의 크기를 확인할 수 있습니다.

v.size();

벡터를 초기화 해줄 수 있습니다.

v.clear();

벡터 크기를 재지정해줄 수 있습니다.

v.resize(37);

벡터의 예상크기를 지정하면 효율이 좋아집니다.

v.reserve(37);

resize 함수의 경우에는 기존값을 초기화하지 않기 때문에, 초기화를 같이 해주어야 하는 경우에는 clear 를 먼저 사용해야합니다. 또한 위와 같은 이유로 이차원 벡터의 크기를 조정할 때, clear없이 resize하는 경우 런타임에러가 발생할 수 있습니다. 사례

vector 활용

오름차순 정렬

sort(v.begin(), v.end());

내림차순 정렬

sort(v.begin(), v.end(), greater<int>());

사용자 설정 정렬

bool cmp(int a, int b) return a < b;
sort(v.begin(), v.end(), cmp);

정렬된 경우 이분탐색 (크거나 같은 값)

lower_bound(v.begin(), v.end(), 37);

정렬된 경우 이분탐색 (더 큰 값)

upper_bound(v.begin(), v.end(), 37);

순차탐색 (같은 값)

find(v.begin(), v.end(), 37);

이분탐색에서 찾는 값이 없는 경우

if(lower_bound(v.begin(), v.end(), 37) == v.end()) {
    // no such value
}

조합 탐색 (사전순)

do {
    // 
} while(next_permutation(v.begin(), v.end());

문자열

새로운 문자열

stirng str;

크기 확인

str.size();

문자열 찾기

str.find("asdf");

문자열을 찾을 수 없는 경우

if(str.find("asdf") == string::npos) {
    // cant find
}

맵 / 셋

새로운 map 과 set 생성

map<string, int> m;
set<int> s;

값 추가

m["asdf"] = 1234;
s.insert(1234);

값 존재 확인

m.count("asdf");
s.count(1234);

맵에서 값 확인

m["asdf"];

값 제거

m.erase("asdf");
s.erase(1234);

주의할 점은 map에서 대괄호로 값을 확인하려고 하면, 없던 값이 새로 생길 수 있습니다. 이런 경우 메모리와 속도 측면에서 손해가 발생하며 오류 발생의 가능성이 있으니, 값의 존재만을 확인한다면 map에서도 count를 사용해야 합니다.

큐 / 우선순위큐

큐 생성 / 우선순위큐(내림차순) 생성

queue<int> q;
priority_queue<int> pq;

푸시

q.push(37);
pq.push(37);

팝

q.pop();
pq.pop();

값 확인 - 주의

q.front();
pq.top();

우선순위큐를 오름차순으로 만들기

priority_queue<int, vector<int>, greater<int>> pq;

우선순위큐를 사용자 설정 기준으로

struct cmp{bool operator()(int a, int b){return a < b;}}
priority_queue<int, vector<int>, cmp> pq;

한편 스택을 이용한다면 stack 컨테이너도 존재하지만, vector를 사용해도 문제되지 않습니다.

그 외

최대값

max(a, b);

최소값

min(a, b);

문자열을 정수형으로

stoi("37");

정수형을 문자열로

to_string(37);

문자열을 여러개의 정수형으로

int A, B, C;
stringstream ss("123 456 789");
ss >> A >> B >> C;

지난 11월 12일 LG CNS 에서 진행한 코드몬스터 채용연계형 대회에 참가한 후기입니다. 이 대회를 통해 예선과 본선을 거쳐 최종면접만으로 취직이 가능하고, 무려 2년까지도 유예기간으로 기다려주겠다는 다른 곳에서는 볼 수 없는 혜택이 주어집니다. 얼마전 카카오 기술면접에서 쓴맛을 본 입장에서, 또 졸업까지 1년 이상 남아있는 입장에서 정말 매력적인 조건이 아닐 수 없습니다. 현재 글은 본선의 후기가 아닌 예선후기입니다.

예선 전반에 관하여

문제는 4문제, 시간은 3시간이 주어졌습니다. 특이하게도 시간복잡도를 주요 평가대상으로 여기지는 않는 것으로 보입니다. 4문제 모두 동일하게 시간제한이 10초로 되어있었습니다. 문제내용 상 10초가 필요할 만큼 범위가 넓거나 시간복잡도가 크지도 않았습니다. 문제의 전반적인 느낌은 다른 대회들보다 브루트포스를 중심으로 풀어나가야 한다는 것이었습니다. 제 경우에는 4문제 모두 예제 테스트케이스는 통과했지만, 전체 테스트케이스 채점결과는 공개되지 않았기 때문에 실제로 얼마나 맞추었는지는 알 수 없었습니다. 그래도 예선은 통과했으니 어느 정도는 맞춘 것 같습니다. 문제의 내용은 공개하지 못하게 되어있기 때문에 간략한 설명으로만 갈음하도록 하겠습니다. 또한 제대로 맞추었는지 확인도 불가능했기에 난이도 표기는 하지 않았습니다.

1번문제

구슬을 배치하는 문제였습니다. 배치에 대한 우선순위 조건이 몇가지 주어졌습니다. 처음에는 그리디 문제라고 생각해서 규칙을 발견하기 위해 시간을 썼습니다만.. 시간제한이 10초에다가 문제 조건의 범위가 매우 작다는 것을 뒤늦게 확인했습니다. 그래서 next_permutation 을 활용한 조합을 이용하여 브루트포스로 문제를 해결했습니다.

2번문제

다수의 멀티탭에서 전력제한에 맞게 전자기기를 제거하는 문제였습니다. 멀티탭의 연결구조는 트리구조로 생각할 수 있었습니다. 먼저, 자식노드에서부터 부모노드로 올라가며 멀티탭에 걸리는 부하를 계산했습니다. 이후 제거할 기기 개수 계산도 비슷하게 자식노드에서 부모노드로 올라갔고, 다만 최대값으로 갱신하며 계산했습니다.

3번문제

부분문자열 연속매칭 시 최소길이의 최대값을 구하는 문제였습니다. unordered_set 을 이용하여 레퍼런스 문자열의 모든 subsequence 를 해싱해둔 후에, DP로 처리하여 계산했습니다. 그리고 항상 고민되는 부분이지만, unordered_set 과 set 에서 고민을 많이 했습니다. 일반적으로 unordered_set이 set보다 빠른 것으로 알려져 있지만, 코드포스에서 문제를 풀면서 알게 된 것은 set 이 더 빠른 경우도 많다는 것입니다. 더 자세히 공부해야할 것 같지만, 일단은 C++ STL 의 set 은 문자열 길이가 길어지면 해싱함수가 더 복잡해지는 것으로 알고 있고, 개수가 많아져 해시충돌이 빈번해지면 레드블랙트리로 구성된 set이 더 효율적으로 작동한다고 알고 있습니다. 당시에는 그냥 unordered_set 을 이용했지만 어느 것을 사용하는게 맞았는지 아직도 잘 모르겠습니다..

4번문제

루트노드에 따라 부모자식역전현상 횟수를 구하는 문제였습니다. "부모-자식" 관계를 배열로 저장해두었고, 루트노드에서 BFS 돌려서 역전 횟수를 계산했습니다.

본선일정

본선은 11월 26일 마곡에 위치한 LG 사이언스파크에서 오프라인으로 진행된다고 합니다. 대회 오프라인 참가가 처음이기도 하고, 본선 참가 축하 상품을 지급한다고 하는데 어떤 것일지 기대됩니다. 본선에서는 테스트케이스 통과여부 정도는 알 수 있게 해주면 좋을 것 같습니다.

세그먼트 트리

세그먼트트리는 데이터가 다수 주어지고 구간 연산을 반복적으로 하는 경우에 주로 사용합니다. 대표적인 예시로 구간합을 계산하는 경우를 들 수 있습니다. 물론 구간합을 구하는 것은 누적합 Prefix-Array를 통하여 더 쉽게 계산할 수도 있습니다. 그러나 누적합을 사용하면 값을 변경할 때 $$O(N)$$ 시간이 걸리게 되어, 빈번한 값 변경이 있는 경우에 적합하지 않습니다. 그래서 보통 세그먼트트리는 빈번한 값 변경을 동반하는 경우에 자주 쓰이게 됩니다. 세그먼트트리는 구간을 두개의 하위구간으로 나누고, 다시 각 구간을 두개의 하위구간으로 나누는 것을 반복하여 최종적으로 각 원소로 나누어질 때까지 나누고, 이진트리에 값을 미리 계산해두는 자료구조입니다. 이로 인하여 메모리 측면에서 데이터의 두배만큼 공간을 차지하게 됩니다. 메모리를 더 사용하는 대신, 구간값 계산에는 $$O(logN)$$이 걸리고, 값 갱신에는 $$O(logN)$$이 걸립니다. 앞서 이야기한 누적합으로 계산을 한다면, 구간합 계산에는 $$O(1)$$이 걸리고, 값 갱신에는 $$O(N)$$이 걸립니다. 갱신이 없는 경우라면, 메모리측면에서도 속도측면에서도 세그먼트트리보다 누적합이 더 적합합니다.

작성방법

세그먼트 트리를 구성하고 사용하기 위해서는 보통 3가지 함수를 만들어 사용하게 됩니다.

init 함수

세그먼트트리의 초기형태를 구성합니다

update 함수

값을 갱신합니다

query 함수

구간값을 반환합니다

init 함수

세그먼트는 배열 또는 벡터에 값을 저장합니다. 해당하는 구조의 크기를 정해주어야합니다. 배열의 크기를 정확히 계산하면, $$2^{\lceil log_2N\rceil +1}$$ 입니다. 이를 시프트연산을 적용하여 계산하면 다음과 같이 작성할 수 있습니다.

seg.resize(2 << (int)ceil(log2(N)));

메모리에 여유가 있고, 쉽게 작성하고 싶다면 그냥 4배로 해도 됩니다. 세그먼트트리가 요구하는 크기는 $$4N$$을 넘지 않습니다.

seg.resize(N << 2);

크기를 지정해주었다면, init 함수를 실행시키면 됩니다.

init 함수는 다음과 같습니다.

void init(int node, int s, int e) {
    if(s == e) seg[node] = v[s];
    else {
        int m = (s + e) / 2;
        init(2 * node, s, m);
        init(2 * node + 1, m + 1, e);
        seg[node] = seg[2 * node] + seg[2 * node + 1];
    }
}

이분탐색과 유사한 방식으로 구간을 재귀적으로 분할합니다. 배열을 이진트리로 활용하여, 좌측자식 노드는 $$2\times node$$ 이고, 우측 자식노드는 $$2\times node+1$$ 입니다. init함수를 실행할 때, node는 1이고, s는 0이며, e는 N-1입니다.

update 함수

값을 변경해주는 update함수도 init함수와 유사합니다.

void update(int node, int s, int e, int idx, int val) {
    if(idx < s || e < idx) return;
    if(s == e) seg[node] = val;
    else {
        int m = (s + e) / 2;
        update(2 * node, s, m, idx, val);
        update(2 * node + 1, m + 1, e, idx, val);
        seg[node] = seg[2 * node] + seg[2 * node + 1];
    }
}

update함수를 실행할 때, node는 1이고, s는 0이며, e는 N-1입니다. idx는 변경해줄 값의 인덱스를 의미하며, val은 변경값을 의미합니다.

query 함수

query함수를 통해 구간값을 가져올 수 있습니다.

int query(int node, int s, int e, int left, int right) {
    if(right < s || e < left) return 0;
    if(left <= s && e <= right) return seg[node];
    int m = (s + e) / 2;
    return query(2 * node, s, m, left, right)
        + query(2 * node + 1, m + 1, e, left, right);
}

query함수를 실행할 때, node는 1이고, s는 0이며, e는 N-1입니다. left와 right는 포함구간을 의미합니다.

요약코드

세그먼트트리를 실용적으로 빠르게 사용할 수 있는 코드입니다.

int seg_size = 0;
vector<long long> seg, seg_;
void init_(int n, int s, int e) {
    if(s == e) {seg_[n] = seg[s]; return;}
    int a = n << 1, b = a + 1, m = (s + e) >> 1, k = m + 1;
    init_(a, s, m), init_(b, k, e);
    seg_[n] = seg_[a] + seg_[b];
}
void update_(int n, int s, int e, int i, long long d) {
    if(i < s || e < i) return;
    if(s == e) {seg_[n] = d; return;}
    int a = n << 1, b = a + 1, m = (s + e) >> 1, k = m + 1;
    update_(a, s, m, i, d), update_(b, k, e, i, d);
    seg_[n] = seg_[a] + seg_[b];
}
long long query_(int n, int s, int e, int l, int r) {
    if(r < s || e < l) return 0;
    if(l <= s && e <= r) return seg_[n];
    int a = n << 1, b = a + 1, m = (s + e) >> 1, k = m + 1;
    long long A = query_(a, s, m, l, r), B = query_(b, k, e, l, r);
    return A + B;
}
void init() {
    seg_size = seg.size();
    int z = 2 << (int)ceil(log2(seg_size));
    seg_.resize(z);
    init_(1, 0, seg_size - 1);
}
void update(int i, long long d) {
    seg[i] = d;
    update_(1, 0, seg_size - 1, i, d);
}
long long query(int l, int r) {
    return query_(1, 0, seg_size - 1, l, r);
}

레이지

앞서 본 세그먼트 트리는 한번에 하나의 값을 변경했습니다. 그러나 특정구간의 값을 한번에 바꾸게 된다면 효율성이 떨어지게 됩니다. 그런 경우에 사용할 수 있는 것이 Lazy-Propagation 입니다. 레이지세그는 구간의 값을 갱신할 때, 바로 값을 반영하지 않고, 레이지 배열에 담아둡니다. 그리고 해당 구간의 값을 확인해야 하는 경우에만 몰아서 업데이트를 해줍니다. 기존 세그먼트 트리에서 M개의 값을 변경한다면 $$O(MlogN)$$이 걸리게 되지만, 이러한 방식으로 몰아서 갱신한다면 $$O(logN)$$ 시간만에 가능합니다. 기존 init, update, query 외에도 propagate함수가 필요하고, 각 함수가 조금씩 변경되지만 큰 변화는 없습니다.

int seg_size = 0;
vector<long long> seg, seg_, lazy_;
void prop_calc(int n, int s, int e, long long x) {
    int a = n << 1, b = a + 1;
    seg_[n] += x * (e-s+1);
    if(s != e) lazy_[a] += x, lazy_[b] += x;
}
long long seg_calc(long long A, long long B) {
    return A + B;
}
void propagate_(int n, int s, int e) {
    if(!lazy_[n]) return;
    int a = n << 1, b = a + 1;
    prop_calc(n, s, e, lazy_[n]);
    lazy_[n] = 0;
}
void init_(int n, int s, int e) {
    if(s == e) {seg_[n] = seg[s]; return;}
    int a = n << 1, b = a + 1, m = (s + e) >> 1, k = m + 1;
    init_(a, s, m), init_(b, k, e);
    seg_[n] = seg_calc(seg_[a], seg_[b]);
}
void update_(int n, int s, int e, int l, int r, long long d) {
    propagate_(n, s, e);
    if(r < s || e < l) return;
    int a = n << 1, b = a + 1, m = (s + e) >> 1, k = m + 1;
    if(l <= s && e <= r) {prop_calc(n, s, e, d); return;}
    update_(a, s, m, l, r, d), update_(b, k, e, l, r, d);
    seg_[n] = seg_calc(seg_[a], seg_[b]);
}
long long query_(int n, int s, int e, int l, int r) {
    propagate_(n, s, e);
    if(r < s || e < l) return 0;
    if(l <= s && e <= r) return seg_[n];
    int a = n << 1, b = a + 1, m = (s + e) >> 1, k = m + 1;
    return seg_calc(query_(a, s, m, l, r), query_(b, k, e, l, r));
}
void init() {
    seg_size = seg.size();
    int z = 2 << (int)ceil(log2(seg_size));
    seg_.resize(z), lazy_.resize(z);
    init_(1, 0, seg_size - 1);
}
void update(int l, int r, long long d) {
    update_(1, 0, seg_size - 1, l, r, d);
}
long long query(int l, int r) {
    return query_(1, 0, seg_size - 1, l, r);
}

문제 추천

백준 12844 - XOR xor 특성과 함께 세그먼트를 변형하여 사용하는 기본 문제

백준 7578 - 공장 2022 SCPC 2차예선 2번 - 반협동게임 에서도 나왔던 교차확인 문제

백준 1168 - 요세푸스 문제 2 쿼리를 변형하여 해당 순서를 가져오는 문제

뼈대 생성

vector<int> u(len);
for(int i = 0; i < len; i++) {
    u[i] = i;
}

u라는 벡터를 만들어서 분리집합을 구현합니다. 벡터의 값은 소속된 집합을 나타냅니다. 벡터의 값을 인덱스와 동일하게 맞춰주어 초기화합니다. 현재 상태에서 모든 원소는 서로 연결되어있지 않은 상태입니다.

ufind

int ufind(int& k) {
    int& ret = u[k];
    if(ret == k) return k;
    ret = ufind(ret);
    return ret;
}

ufind함수는 원소가 소속된 집합의 번호를 반환합니다. u[k] = k 가 될때까지 재귀적으로 반복합니다.

연결확인

int A = ufind(a);
int B = ufind(b);
if(A == B) {
    // connected
}

ufind 결과가 서로 동일하다면 같은 집합에 소속되어 연결되어 있음을 알 수 있습니다.

연결하기

u[ufind(a)] = ufind(b);

위와 같은 코드를 이용하여, 원소를 연결해줄 수 있습니다.

개념

우선순위큐를 두 개를 만들고, 인덱스를 통하여 하나처럼 다룹니다. Pop 할 때 유효한 데이터인지 확인합니다.

구조

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> minPQ;
priority_queue<pair<int, int>> maxPQ;
vector<int> isAlive;
int cnt = 0;

최대값을 반환하는 maxPQ와, 최소값을 반환하는 minPQ를 만들어둡니다. isAlive 벡터를 만들어두고 유효한 값인지 저장합니다. 우선순위큐를 pair로 구성하고 second에는 isAlive의 인덱스값을 주도록 할 것입니다.

Push

minPQ.push(make_pair(x, cnt));
maxPQ.push(make_pair(x, cnt));
isAlive.push_back(1);
cnt++;

양쪽 모두에 push하도록 합니다.

Max 값

if(!maxPQ.empty()) {
    maxPQ.top().first; // Max 값
}
else {
    0; // 비어있음
}

Min 값

if(!minPQ.empty()) {
    minPQ.top().first; // Min 값
}
else {
    0; // 비어있음
}

Max Pop

if(!maxPQ.empty()) {
    isAlive[maxPQ.top().second] = 0;
    maxPQ.pop();
    while(!maxPQ.empty() && !isAlive[maxPQ.top().second]) {
        maxPQ.pop();
    }
    while(!minPQ.empty() && !isAlive[minPQ.top().second]) {
        minPQ.pop();
    }
}

maxPQ의 top의 isAlive 값을 0으로 변경하고, pop을 진행합니다. 그리고 다음 top의 isAlive를 검사하여 유효하지 않다면 pop합니다. minPQ에 대해서도 마찬가지입니다.

Min Pop

if(!minPQ.empty()) {
    isAlive[minPQ.top().second] = 0;
    minPQ.pop();
    while(!maxPQ.empty() && !isAlive[maxPQ.top().second]) {
        maxPQ.pop();
    }
    while(!minPQ.empty() && !isAlive[minPQ.top().second]) {
        minPQ.pop();
    }
}

maxPQ에서 pop하는 것과 유사하게 진행됩니다.

문제 추천

백준 7662 - 이중우선순위큐

배열처럼 사용하기

32비트 정수형인 int를 사용하여 32개의 bool값을 저장할 수 있습니다. 정확히는 unsigned int 형을 사용해야 32개의 비트를 모두 사용할 수 있습니다. 만약 signed int 형을 사용한다면 signed-bit 하나를 제외한 31개까지만 사용해야 합니다. 이렇게 정수하나를 배열처럼 사용하게되면 메모리를 매우 효율적으로 사용할 수 있습니다.

비트 연산에는 AND연산, OR연산, XOR연산, SHIFT연산이 주로 사용됩니다. AND연산자, OR연산자, XOR연산자는 각각 &, |, ^ 에 대응되고, 쉬프트 연산자에는 << 와 >> 가 있습니다.

값 저장

unsigned int arr;
arr |= 1 << k; //k 번째 항목 1저장
arr &= ~(1 << m); //m 번째 항목 0저장

값 확인

arr >> k & 1; //k 번째 항목의 값

값 토글

arr ^= 1 << k; //k 번째 항목 값 토글

활용

완전탐색 문제에서 활용되기도 합니다. 1인 경우 선택하고 0인 경우 비선택한다면, 0부터 해당비트수가 전부 1이 될때까지 탐색하여 해결할 수 있습니다. 아래 문제는 다양한 방법으로 해결이 가능하지만, 이러한 개념을 응용하여 더 쉽게 풀 수 있습니다. 백준 16938 - 캠프 준비

더 많이 저장하기

unsigned long long 자료형을 사용하면 한번에 64개의 값을 저장할 수 있습니다. 혹은 정수를 배열로 묶어서 사용하는 방법도 있습니다.

unsigned int arr[10] = {0}; //32개씩 10개를 묶어서 320개 항목 저장가능
arr[k >> 5] |= 1 << (k & 31); //k 번째 항목에 1 저장
arr[k >> 5] &= ~(1 << (k & 31)); //k 번째 항목에 0 저장
arr[k >> 5] >> (k & 31) & 1; //k 번째 항목의 값
arr[k >> 5] ^= 1 << (k & 31); //k 번째 항목 값 토글

연산 최적화

비트연산은 매우 빠르기 때문에 적절하게 사용해주면 연산속도를 개선할 수 있습니다.

홀짝 판별

if(num & 1) {
    // odd
}
else {
    // even
}

2의 거듭제곱으로 나누기

int divByTwo = num >> 1;
int divByFour = num >> 2;
int divByEight = num >> 3;

2의 거듭제곱의 나머지 계산

int remByTwo = num & ((1 << 1) - 1);
int remByFour = num & ((1 << 2) - 1);
int remByEight = num & ((1 << 3) - 1);

'올림' 을 기준으로 2로 나누기

int ceiled = (num >> 1) + (num & 1);

카카오 1차 코딩테스트

우선 시험환경은 "프로그래머스" 플랫폼을 활용한 환경이었고, 이 플랫폼에서 문제를 푼 경험이 있어서 불편함은 없었습니다. solution 함수를 주고 매개변수로써 input을 주고 ouput을 return하는 방식이었습니다. 문제는 총 7문제였습니다. 문제의 자세한 내용은 저작권 상 공개하면 안된다고 하여, 대략적인 분류와 체감 난이도만 간략히 적도록 하겠습니다.

1번 문제

구현문제입니다. 문제 난이도는 실버정도인것 같습니다.

2번 문제

그리디문제입니다. 그리디 특성 상 난이도는 사람마다 다르게 느낄 것 같습니다. 제 생각에는 실버 상위 ~ 골드 하위 정도로 예상합니다.

3번 문제

문제 내용이 너무 복잡해 보여 나중에 풀기로 미루었다가, 시간이 남지 않아 풀지 못했습니다.

4번 문제

분할정복 문제입니다. 문제 난이도는 골드정도인것 같습니다.

5번 문제

구현할게 많아보여 나중에 풀기로 미루었다가, 시간이 남지 않아 풀지 못했습니다.

6번 문제

그리디문제입니다. 사실 앞 문제들이 구현만 많고 재미는 없다 생각하고 있었는데, 이 문제는 그래도 재미있었습니다. 문제 난이도는 골드일 것 같습니다.

7번 문제

문제를 제대로 읽은 것은 아니지만, 대충봤는데도 어려울 것 같아보였습니다. 시간이 없어서 풀지 못했지만, 아마 시간이 있었어도 못 풀지 않았을까 생각합니다.

이렇게 1번 2번 4번 6번 총 4개밖에 풀지 못해 떨어졌다고 생각하고 있었습니다.

그런데 통과했습니다.

카카오 2차 코딩테스트

CS테스트

결론부터 말하자면 크게 망했습니다. CS를 책으로 공부하기에는 시간이 없어서 인터넷 요약본을 검색해서 읽어봤지만, 그런 요약본으로는 커버되지않는 꽤나 세부적인 내용이 문제로 나왔습니다. 내용은 당연히 자료구조, 알고리즘, 네트워크, 운영체제(리눅스), 데이터베이스로 나왔습니다.

REST API 코테

2차 코딩테스트는 REST API를 사용하여 문제를 해결하는 방식으로 1차 코딩테스트와는 상이한 유형의 시험이었습니다. 카카오 통계자료에 의하면 1차는 C++이 주로 선택되었고, 2차는 Python이 주로 선택되었다고 합니다. 다수의 선택에는 이유가 있을 것이라고 생각해서 Python을 선택했고, 작년 기출로 연습해보니 파이썬을 많이 선택하는 이유를 알것 같았습니다. 코드를 미리 준비해도 괜찮다고 하여, 작년 기출로 연습한 코드를 다듬어 REST API 코드를 미리 짜두었습니다.

시험 당일, 미리짜두었던 REST API 코드에서 약간의 문제가 발생했으나 적당히 수정하여 해결할 수 있었습니다. 그러나 진정한 문제는 파이썬 숙련도였습니다. 파이썬에 미숙하다보니 온갖 다양한 오류를 겪었습니다. 오류 속을 헤매다보니 어느새 시험 종료 30분 전이 되었습니다. 채점에도 시간이 꽤 오래걸렸는데, 채점 시간만 약 20분 정도 걸렸던 것으로 기억합니다. 마감 25분전에 코드를 수정하고 채점했는데, 마감 5분전에 처음으로 점수를 받게 되었습니다. 0점으로 마감하지 않게 되어 기쁘긴 했지만 845점이라는 100등을 한참 벗어나는 점수였습니다. 더 빨리 코드를 짰다면 최적화도 시도해볼 수 있었을 텐데, 최적화는 해보지도 못한 것이 아쉬움으로 남았습니다.

결과 발표

의외로 붙었습니다.

카카오 1차 면접

서류

먼저 면접이 진행되기 전에 간단한 서류를 제출하게 되었습니다. 제출기한은 면접 전 일주일 정도로 주어졌습니다. 프로젝트를 기술하거나 포트폴리오를 제출할 수 있었고 간단한 자기소개 문항이 있었습니다. 이를 계기로 포트폴리오를 만들어 보았습니다. 만들어본 웹앱에 대한 소개를 하는 내용입니다. http://godjh.dothome.co.kr/portfolio/

면접

면접은 비대면으로 구글 Meet를 통한 화상면접이었습니다. 면접은 기술면접으로 CS에 대한 질문으로 시작되었습니다. 제 경우에는 CS에 대한 기초부터 부족한 상태였기 때문에 제대로 된 답변은 거의 하지 못했습니다. 제가 제대로 답변을 했다면 꼬리를 무는 질문을 받았을 것 같은데, 답변을 하지못해 꼬리를 무는 질문을 받지도 못했습니다. 또한 2차 코딩테스트에 대해서도 이야기할 시간이 주어졌습니다. 2차 코딩테스트에서 최적화를 시도도 하지 못한 제 경우에는 역시 달리 할 수 있는 말이 없었습니다. 이건 2차 코딩테스트를 잘 수행하지 못한 부분도 감점요소인 것 같았고, 한편으로는 브루트 포스로 구현한 부분에 대한 설명이라도 유연하게 잘 해야했던 것 같습니다. 전반적으로 계속 엇나가는 듯한 면접시간이 지나갔고, 한시간으로 예정된 면접이 40분 만에 끝이나게 되었습니다.

결과

예상대로 1차면접에서 탈락하게 되었습니다. 사실 면접까지 오게된것도 운이 좋았다고 생각합니다. 이번에는 떨어졌지만 다음 기회에는 더 준비된 상태로 다시 도전할 생각입니다.

솔브드 시스템이 알고리즘 공부에 동기부여가 되는 것 같습니다. 티어 시스템도 점수를 쌓는 재미가 있고, 스트릭을 채우는 것도 재미있습니다.

앞으로 9월 24일에는 카카오 1차 코딩테스트가 있고, 넘어가는 25일 새벽 2시에는 페이스북 해커컵 라운드2가 있습니다. 새벽 2시부터 5시라니 시간이 좀 가혹하긴 하지만 25일은 일요일이니까..

물론 본격적인 개발툴은 아니기에 일반 개발용은 절대 아닙니다. 목적부터가 PS나 CP 를 염두에 두고 만들었기 때문입니다.

기능으로는 코드 단축어, 괄호 자동화, 블록 인덴트 및 블록 주석, 자동 변수 생성, 컴파일, 코드 컬러테마, 코드 및 출력파일 저장이 있습니다.

나름 개발툴이어서 다크모드도 넣어봤습니다.

코드 단축어

가장 먼저 추가하기로 생각했던 기능이고 가장 핵심이라고도 볼 수 있습니다. 타이핑하기 귀찮은 코드를 대충쓰면 자동으로 완성되는 기능입니다. 물론 자동으로 완성되면서 커서의 위치가 가장 필요한 곳으로 알맞게 이동하게 됩니다. 예시로 반복문을 들 수 있겠습니다. @fori 라고 4글자만 입력하면 i를 기준으로 작동하는 for문이 완성됩니다. 꼭 i여야할 필요는 없습니다. @for 뒤에 문자를 하나 더 입력하면 그 문자를 기준으로 for 문을 만들어 줍니다. 일단 반복문이 작성이 되면, for(int i = 0; i < ; i++) 의 형태가 될 텐데 이 때의 커서의 위치를 i 의 한도를 정하는 영역 (부등호의 뒤) 에 위치시키게 했습니다. 그리고 이어지는 { } 중괄호는 띄어쓰기와 알맞은 들여쓰기가 알아서 맞춰지게 했습니다. 반복문이 아니더라도 내가 자주 쓰는 문법들에 대해서 자동으로 변환할 수 있도록 만들어 두었고, 사용자가 커스텀하여 추가할 수도 있게 할 것입니다. 한편 치환해주어야 하는 문자가 많아지면 많아질수록 속도의 저하가 일어날 수 있을 것이라고 생각해서 Trie 구조를 적용하였습니다.

블록 인덴트 및 블록 주석

대다수의 IDE 에서 이미 있는 기능이기도 합니다. 영역을 선택하고 TAB키를 누르면 해당 블록 인덴트를 한단계 높이고, SHIFT-TAB을 눌러서 인덴트를 한단계 낮출 수 있습니다. 유사하게 영역을 선택 후 / 키를 눌러서 해당 블록을 주석으로 만들고, SHIFT-/ 를 눌러서 주석을 해제할 수도 있습니다.

자동 변수 생성

cin을 통해 입력받을 때, 타입을 지정해주면 전역변수를 자동으로 만들어 주는 기능입니다. 알고리즘 문제들은 스택메모리를 아끼기 위해 혹은 단순히 편리성 때문에 힙메모리에 변수들을 올리는 경우가 많은데, cin 을 작성할 때 전역변수 선언을 함께 시키면 편하겠다는 생각에 만들었습니다. cin >> int N >> int M; 과 같이 입력하면 정수형 전역변수 N, M 이 자동으로 생성이 되어 따로 만들어 줄 필요가 없어집니다.

컴파일

jdoodle에서 제공하는 컴파일 rest API를 이용했습니다. https://www.jdoodle.com/ JS 단에서는 CORS 제약으로 인하여 API 연결이 되지않아 무료웹호스팅의 유일한 희망인 php를 이용했습니다.

사용해보기

아래 링크를 통해 사용할 수 있습니다. http://godjh.dothome.co.kr/quickcoder/ 알아두면 편리한 단축키 기능도 있습니다. ctrl + E 또는 command + E 키를 누르면 stdin을 입력하는 창이 뜨게 되고, 다시 한번 더 단축키를 누르면, 컴파일이 진행된다. ctrl + S 또는 command + S 키를 누르면 코드를 저장할 수 있고, shift 키를 함께 누른다면 output.txt 을 받을 수 있습니다. 기존 파일을 열고자 한다면, ctrl + O 또는 command + O 를 누르고 파일을 선택하면 됩니다.