kth990303의 코딩 블로그

2021 연세대학교 신입생 프로그래밍 경진대회 Open 2021 연세대학교 신입생 프로그래밍 경진대회 Open www.acmicpc.net Math, Constructive, Ad_hoc 문제가 엄청나게 많았던 대회 셋이다. 당시 나는 5문제를 해결하였으며, 이번 대회 역시 aru0504님이랑 함께 응시하였다. aru0504님이랑 응시하는 대회는 항상 재밌는 것 같다. aru0504님은 F번, 나는 E번을 solve하였고, 개인적으로 이번 대회에서 F번이 진짜 어렵다고 생각한다. 대회 당시 아예 건들지도 않았던 G, H번도 끝나고 해결해보았는데, G, H보다 F가 순간적인 아이디어 생각해내기엔 더더욱 어려운 것 같다. 도대체 F번 어떻게 해결하신거지 A. 추첨을 통해 커피를 받자 21866번: 추첨을 통..

그룹연습 시간과 대회 시간이 겹쳐서 응시할 생각이 없었는데, aru0504님이 응시한다고 하셔서 1~2문제만 풀어보고 넘기려다가 중간에 문제가 안풀려 오기가 생겨 도전해본 대회이다. https://www.acmicpc.net/contest/view/644 가희와 함께 하는 1회 코딩 테스트 www.acmicpc.net +) 2회 코딩테스트도 존재하며, 후기는 여기에 존재한다. https://kth990303.tistory.com/98 [210718] 가희와 함께 하는 2회 코딩테스트 후기 푹 쉴까 아니면 코테를 응시할까 고민하다가 au0504님이 3시쯤에 코테를 응시한다길래 나도 한 번 응시해본 대회이다. https://www.acmicpc.net/contest/view/658 가희와 함께 하는 2회 코..

만약 객체가 다른 객체의 테이블을 참조할 필요는 없는데, 해당 객체가 여러 가지 값을 가지고 있어야 하는 경우는 어떻게 할까? 예를 들자면, kth990303 학생과 aru0504 학생이 있다고 하자. kth990303과 aru0504는 같이 점심을 먹기로 했다. 그러기 위해선 아래 두 가지를 알아야 한다. kth990303과 aru0504는 각각 언제, 어디서 점심을 먹을지 kth990303과 aru0504는 점심으로 무엇을 먹기를 선호하는지 1번을 해결하기 위해서는 각각 일하는 장소와 시간대를 알아야할 것이다. 그러기 위해선 두 객체(Member 객체)에 이 정보들이 있어야할 것이다. 여기서 임베디드 타입이 사용된다. 2번을 해결하기 위해서는 둘이 의견을 통일하여 점심 메뉴를 골라야 한다. 그러나 둘..

그래프 탐색 유형을 연습하기 위해 찾던 중 발견한 문제이다. KOI 2019 2차대회 초등부 3번 문제이다. 진짜 초등학생들 대단한 것 같다.. https://www.acmicpc.net/problem/17616 17616번: 등수 찾기 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에 세 정수 N, M, X가 공백을 사이에 두고 주어진다. (2 ≤ N ≤ 105, 1 ≤ M ≤ min(N(N-1)/2, 5×105), 1 ≤ X ≤ N) . 다음 M 줄에는 각각 두 정수 A, B가 주어 www.acmicpc.net 처음에는 위상정렬 + 유니온파인드로 접근하다가, 연결된 컴포넌트들 중 X가 포함이 안된 컴포넌트쪽과 등수비교가 불가능함을 깨닫고 dfs로 바꿔 생각하여 해결한 문제이다. 시행착오 처음에는 위..

원티드에서 알고리즘 코딩테스트로 일정 점수 이상 획득하는 참가자에게 뱃지를 부여하는 이벤트를 개최하였다. https://www.wanted.co.kr/events/2021_dev_carnival 2021 Dev Carnival : 2021 데브 카니발 원티드가 추천하는 18개 기업에 당신의 코드를 보여주세요! SHOW ME THE CODE 코딩테스트 결과, 일정 점수 이상 획득한 지원자는 이력서 제출 시 원티드 인증 뱃지가 지원한 회사에 노출 됩니다. 채용 www.wanted.co.kr 참가기업에 IT회사로 유명한 대기업들도 꽤 보인다. 따라서 이번 코딩테스트의 난이도는 꽤 높을 것으로 생각하고 응시하였다. 주의사항 부정행위 방지 시스템을 통한 운영을 위해 웹캠을 미리 준비해주시기 바랍니다. 시험을 시작..

벌써 일병5호봉 말에 다다랐다. 나는 dfs가 좀 약한 것 같다. 아래 문제를 풀면서 느꼈다. https://www.acmicpc.net/problem/13209 13209번: 검역소 3번 도시와 5번 도시를 잇는 도로와 4번 도시와 3번 도시를 잇는 도로에 검역소를 설치하면 치료제를 11 인분만 비축해도 된다. 1번 도시에 전염병이 발생할 경우 1번 도시와 3번 도시의 10명의 사 www.acmicpc.net 해결해보려다가 아직 나한테 너무 어려워, 좀 더 낮은 난이도의 문제로 연습한 후에 시도해볼 예정이다. SCC, BCC, dfs tree, segment tree 부분 또한 슬슬 기억이 가물가물하여 감을 잃은 상태인 듯 하다. scc는 사실 자연스럽게 감을 잡았다고 생각했는데, 다시 scc를 해결하..

간단한 bitmask dp이다. https://www.acmicpc.net/problem/1311 1311번: 할 일 정하기 1 N명의 사람과 N개의 일이 있다. 각 사람은 일을 하나 담당해야 하고, 각 일을 담당하는 사람은 한 명 이어야 한다. 또한, 모든 사람은 모든 일을 할 능력이 있다. 사람은 1번부터 N번까지 번호가 매 www.acmicpc.net 난 dp에 꽤 약한 편이라 bitmask+dp 문제는 플레 문제를 풀 엄두가 나지 않았다. 기본적인 bitmask_dp 문제들이 Gold I이어서 G1문제들을 손쉽게 풀 수 있을 때쯤 플레를 도전해보지 않을까 싶었는데, 이 문제를 통해 이제 나도 bitmask_dp임을 파악할 수 있는 실력과, 그 때 해결할 수 있는 능력이 꽤 괜찮음을 파악하게 됐다...

포스팅하기 귀찮아서 안하려다가, 대부분의 풀이 코드가 바텀업이어서 나같은 탑다운 고집러들을 위해 포스팅하려 한다. https://www.acmicpc.net/problem/3037 3037번: 혼란 첫째 줄에 혼란도가 C이고 길이가 N인 수열의 개수를 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net 문제 요약을 하자면, 1부터 N까지 이루어진 수열이 있는데, 오름차순이 아닌 총 순서쌍의 개수를 '혼란도' 라고 한다. N= cur) ret -= dp(cur - 1, c - cur); ret = (ret + MOD) % MOD; return ret % MOD; } dp 식이 총 3번 일어나며, dp함수의 시간복잡도는 O(C)이므로 O(3*N*C)임을 알 수 있다. 이는 충분히..

저번에 만든 회원 CRUD 프로젝트에 새로운 기능들을 추가하고 테스트코드를 돌려보았다. 기능들을 추가하면서 현재까지 내가 배운 것들을 포스팅해보겠다. @Builder, 왜 쓰는걸까? Getter, Setter를 쓰는 이유가 바로 필드변수를 함부로 수정하는 것을 방지하기 위해서인데, @Builder를 쓰는 이유 또한 그렇다. 우리는 흔히 lombok을 사용할 때, Entity 위에 @Getter를 사용하는 것은 많이 볼 수 있지만, @Setter를 사용하는 경우는 거의 보지 못했다. 나는 얼마전까지만 해도 @Setter를 사용하는 것이 테스트 코드 등 여러모로 편해서 자주 사용해왔었는데, 이 때 문제점이 발생한다. Setter 메소드를 사용하면, (lombok에서 아무런 설정을 하지 않는 이상) 다른 데서..

교내에 푼 사람이 없는 문제이면서, 흥미로우면서 좀 배울 점이 있어보일만 한 문제를 선정해보았다. https://www.acmicpc.net/problem/17469 17469번: 트리의 색깔과 쿼리 N개의 정점으로 구성된 트리가 있다. 각 정점은 1번부터 N번까지 번호가 매겨져있고, 1 이상 10만 이하의 자연수로 표현되는 색깔을 하나 갖고 있다. 루트는 1번 정점이고, 트리이기 때문에 임의 www.acmicpc.net 사실 이 문제를 풀기 하루 전에, 우리 학교 내에 정답자가 1명 생겨나 학교랭작에 아무런 도움이 되진 않았지만, 나름 배울점이 꽤 많은 문제였다. 의식의 흐름 및 해설 이제 트리 간선을 끊는다는 말만 보면 유니온파인드 및 오프라인 쿼리가 자동으로 1순위 후보에 생각날 정도가 됐다. 당연..