알고리즘 31

2023년을 되돌아보며

벌써 오늘만 지나면 2023이 지나간다. 어렸을땐 몰랐는데 나이를 먹으니 시간가는게 참 빠르다는게 느껴진다. 2023년을 되새겨보며 나에게 어떤 변화가 있었는지 알아보자. 개발 3월부터 직장생활을 시작하여 이제 약 9개월차 개발자가 되었다. 역시 회사 프로젝트는 개인 프로젝트보다 규모가 크기 때문에 더 신중하고 효율적인 설계가 필요하다. 그렇게 고민하다보면 내가 몰랐던 새로운 개념들을 배우게 되고 그것을 적용시키며 성장해나가게 된다. 그렇게 배운 것들 샤딩 Redis MSA 1, MSA 2 RDB에서의 PK 블로그에 기록해 둔 것은 이 정도인 것 같다. 그 외에도 Dynamo DB, Mongo DB, CQRS패턴 등도 알게되었다. 연초엔 무엇이든 할 수 있을것같고 모든 걸 알고 있다는 생각을 가지고 있었..

기타/기타 2023.12.31

[알고리즘] ICPC 2023 + 코드포스 퍼플 후기

ICPC 2023이 열렸다! 작년보다 좀 늦게 열린 것 같다. 이제 졸업했기때문에 정식으로 ICPC에 나갈 수 없어서 예선은 개인적으로 치고 본선은 Mirror Contest를 참여했다. 작년에 함께 나갔던 팀에서 내가 빠지고 다른 팀원을 구한 것 같다. 작년이랑 마찬가지로 Ilgam Rangers로 나왔다. ㅋㅋ ICPC 2023 예선 예선은 Mirror Contest도 열리지 않기 때문에 문제지만 보고 대충 코드 짜는 식으로 진행했다. 정답 여부를 확인할 수 없으니 믿음으로 가야했다. 예선에선 C, D, G, I, K를 건드렸던 것 같다. 실제로 백준에 올라온 문제로 제출해보니 D, I만 맞았다. ㅋㅋ C는 가장 쉬운 문제였는데 아마 출력 형식이 달라서 틀린 것 같다. (소숫점 출력인데 스페셜저지가 ..

[알고리즘] KUPC 2023 출제 후기

작년 KUPC에 이어 올해도 KUPC가 열렸다. 대회는 11월 4일에 있었지만 포스팅을 미루고 미루다 지금 쓰게 되었다. ㅋㅋ 올해는 졸업도 했고 회사도 다니고 해서 운영은 크게 관여를 못했고 출제와 검수 위주로 했다. 작년 운영진 중 일부가 참가한다고 해서 올해 만들어진 동아리에서 원하는 사람이 추가로 출제자가 되었다. 사진이 없었으면 심심한 글이 될 뻔했는데 제공해주신 kth990303에게 감사를 표합니다. 문제 구상 과정 다른 출제자는 모르겠지만 나는 다음을 베이스로 잡고 문제를 출제하려고 했다. 쉽덕 알고리즘, 사전지식을 사용하지 않아야한다. 직관적이고 지문이 난해하지 않아야 한다. (내가 글을 못쓰기 때문) 난이도가 어려우면 안되지만 그렇다고 올솔브도 나오면 안된다. 위 조건들을 생각하다보니 나..

[알고리즘] 현대모비스 알고리즘 경진대회 2023 본선

현대모비스 알고리즘 경진대회 본선을 다녀왔다. 대회는 삼성 코엑스에서 오프라인으로 열렸고 ICPC와 UCPC같은 알고리즘 대회처럼 티셔츠도 주고 먹을 것도 줬다. 대기업 대회라서 그런지 규모가 어마어마했다. 일반인이 참가할 수 있는 몇 안되는 대회중 하나라서 바로 연차쓰고 참가했다. ㅋㅋ 대회 전 12시에 입장시작인줄 알고 느긋하게 가다가 도착할때 돼서 문자를 보니 집결시간이 12시로 되어있었다. 그래서 삼성역에 도착하자마자 서둘렀는데 길이 복잡해서 많이 헤멨었다. 분명 여러번 왔던 곳임에도 불구하고 올때마다 새로운 것 같다. 그렇게 대회장을 잘 찾아가고 간단한 본인 인증 후에 티셔츠를 갈아입는다. 앞면엔 대회정보 뒷면엔 명언?같은게 적혀있고 소매 양쪽에 각각 현대모비스와 프로그래머스 로고가 적혀있다. ..

[알고리즘] 백준 대회 1등해서 자랑하려고 쓴 글

2023년 7월 6일에 있던 대구 소프트웨어 고등학교 경진대회 open contest에서 ps인생 처음으로 1등을 했다. 대회 공지에 난이도 분포가 브론즈~골드라고 해서 스피드런 할 생각이었는데 운 좋게 성공했다. 하도 문제를 많이 풀다보니 이렇게 된 것 같다. 내 성향이 약간 초반에 불태우는 스타일이라 쉽고 문제수가 적은 셋에 강한 것 같다. 또한 문제가 이해하기 쉬웠던 것도 한 몫한 것 같다. 딱히 더 할 말은 없는데 타임라인이라도 적어야겠다. 00:02 A AC! 항상 대회가 시작하면 A~F까지 창을 모두 띄우고 A번을 켠 후 테스트케이스부터 복사한다. 그 후 문제를 읽으며 코딩을 하는데 이번엔 2분이 걸렸다. 1학년 처리하는데 살짝 꼬였었다. 00:03 B AC! 단순 조건문 분기하는 문제였다. ..

[알고리즘] 현대모비스 알고리즘 경진대회 2023 예선

대학을 졸업한 일반인이 참가할 수 있는 몇 안되는 대회 중 하나인 현대모비스 알고리즘 경진대회에 참가했다. 이 대회가 있는걸 안게 작년이어서 2022년부터 참가했다. 2022년에는 상당히 아쉬움이 많은 대회였지만 1년사이에 정말 쾌적하고 재밌는 대회가 되었다. 2022년엔 7x등을 하여 본선에 참가하지 못했지만 올해는 정말 운좋게 진출했다. 1, 2번을 해결하고 3번 4번은 완탐으로 소량의 부분점수를 받아 41.xx점이 나왔다. 역시 잘하는 고인물들은 거의 학생부에 있어서 일반부는 상당히 청정수였다. 듣기로는 학생부는 3솔하고 4번에서 부분점수를 받는 69점정도가 커트라인이라고 한다. 일반부는 그에 비하면 상당한 차이가 난다. 2번도 상당히 느리게 풀어서 (약 2시간째에 솔브) 불안했으나 다행이다. DP..

[알고리즘] UCPC 2023 Open Contest

더 이상 UCPC에 나갈 수 없어 오픈콘테스트에 참여했다. A 체육은 코딩과목입니다. 예선 A가 가장 쉽다는 것은 전통이다. 그냥 문제에서 주어진 내용을 구현하면 된다. B 물류 창고 MST?생각하다가 트리 DP인가? 하다가 포기했다. https://codeforces.com/contest/1825/problem/D2 랑 비슷하다고 느꼈는데 에디토리얼 보니까 작은거 큰거... C 차량 모듈 제작 얘가 MST문제였다. 그래서 B는 MST가 아닐 것이라는 믿음을 가지고 포기했다. 갑자기 두 원을 포함하는 체인의 길이를 구하는 방법이 생각이 안나서 https://www.youtube.com/watch?v=25ARSNtiN5k 보고 겨우 풀었다. ㅋㅋ 여담으로 예제 3번 그림이 3개의 기어를 연결한거로 헷갈려서..

[알고리즘] 백준 3000솔브 달성

송도고 코드 마스터 2023 대회 문제가 올라오면서 백준 3000솔브를 달성했다. 코드포스나 앳코더같은 다른 ps플랫폼까지 영끌해서 4000솔브는 될 것 같다. 각잡고 알고리즘 문제풀이하기 시작한게 2021년 하반기인거같은데 약 2년만에 이정도까지 성장했다. 개인적으로 알고리즘 문제를 많이 풀면서 변화한 점은 다음과 같다. 1. 개발할때 자꾸 씹덕 자료구조나 알고리즘을 사용하게 된다. (실제로 비트집합, 값/좌표압축 등을 사용했다. 언젠간 세그먼트트리를 사용할 것이다.) 2. 코드포스/앳코더 콘테스트, 백준 대회, 프로그래머스 데브매칭, 기타 기업 대회등 대회란 대회는 모두 나가게 된다. 3. 온 세상이 알고리즘으로 보인다. 4. 알고리즘으로 밤새도록 떠들 수 있다. 이만큼 많이 풀다보니 코딩테스트는 프..

[알고리즘] smaller to larger를 사용해서 분리집합을 구현하자!

이 글에는 지극히 주관적인 내용이 많이 들어있습니다. 분리집합을 구현할 때 보통 가리키는 포인터를 옮기는 방식으로 구현하곤 한다. 하지만 이런 방법은 경로압축도 해야 하고 개인적으로 비직관적이었다. 사실 나는 재귀적인 코드와 작동 과정이 아직 완벽히 이해가 되지 않는다. 그래서 상대적으로 직관적인 smaller to larger(a.k.a 작은거 큰거)를 사용한 분리집합 구현을 소개하고자 한다. (물론 기존 방식보다 느리고 공간도 많이 사용한다.) smaller to larger라는게 애초에 집합을 합치기 위한 연산을 최적화하기 위한 기법이기 때문에 분리집합에도 사용할 수 있다. 기초적인 구조 class DisjointSet { public: vector p; vector ix; int n; } 우선 멤..

[알고리즘] Mo's 알고리즘

Mo's 알고리즘은 중국 알고리즘 대회에서 Mo Tao라는 사람이 사용한 기법으로 유명해졌다. 그래서 컴퓨터공학 다른 곳에서는 찾기 힘든 알고리즘이고 Competitive Programming에서 볼 수 있는 알고리즘이다. 어떤 알고리즘인지 알아보자. 오프라인 쿼리 mo's 알고리즘을 알기 위해 오프라인 쿼리를 알아야 한다. 무방향 가중 그래프가 주어지고 쿼리마다 a, b를 연결하는 간선을 끊고 u, v번 노드가 서로 연결돼 있는지 판정하시오. 위와 같은 문제는 주어지는 쿼리마다 해결하려고 하면 굉장히 어렵다. 하지만 간선을 연결하는 문제라면 분리집합으로 쉽게 해결할 수 있다. 그래서 처음에 쿼리를 모두 저장하고 뒤에서부터 역순으로 쿼리를 수행하면 쉬울 것이다. 이런식으로 여러 개의 쿼리를 주어진 순서대..