kth990303의 코딩 블로그

알고리즘 중급 스터디에서 스프라그-그런디 정리를 공부한 후에 푼 문제이다. 정말 어렵다고 생각되는 문제. 문제는 아래와 같다. https://www.acmicpc.net/problem/16889 16889번: 중복 없는 님 게임 구사과와 큐브러버가 님 게임을 하려고 한다. 님 게임은 돌 더미 N개를 이용하며, i번째 돌 더미에 있는 돌의 개수는 Ai개이다. 두 사람은 턴을 번걸아 가지면서, 게임을 진행한다. 각 턴은 돌 더 www.acmicpc.net 의식의 흐름 및 해설 선공, 후공이 나누어져 있다. 그리고 두 플레이어는 항상 최선을 다하며, 돌이 몇 개 남아있는지 모두에게 공개되어 있다. 따라서 impartial game에 속하고, 돌 더미가 여러 개이므로 스프라그-그런디 정리를 이용할 수 있다. 이..

학교 채점현황을 둘러보다가 발견한 문제. KOI(한국정보올림피아드) 2020 고등부 2차대회 문제이기도 하다. 문제는 아래와 같다. https://www.acmicpc.net/problem/20191 20191번: 줄임말 문자열 A가 문자열 B의 줄임말이라는 것은 B의 순서를 바꾸지 않고 0 또는 그 이상 개수의 문자를 지워 A를 만들 수 있다는 뜻이다. 정의에 의해서 B는 자기 자신의 줄임말임에 유의하라. 예를 들 www.acmicpc.net 요약하자면, 문자열 T를 몇 번 반복해야 문자열 S와 T의 LCS가 문자열 S일지를 파악하는 문제이다. 의식의 흐름 및 해설 처음에는 해결 방법이 떠오르지 않았다. 생각보다 어려운 문제가 아닐까? 싶어서 출처를 확인하고, 티어도 확인해보았다. 골드2 정도의 문제였..

우아한테크코스 레벨1 과정에서 데일리조끼리 객체지향과 디자인패턴 스터디를 진행하였고, 덕분에 이 책을 완독할 수 있었다 ㅎㅎ 좋았던 점 결론부터 말하자면 java 개발을 병행하면서 OOP 개념을 익히기 매우 좋았던 책이었다. 책 제목이 '디자인 패턴'이라 디자인패턴만 주구장창 공부할까봐 걱정 중이라면, 그 걱정을 저 멀리 내던져도 좋을 듯하다. 실제로 이 책은 디자인패턴에 관해서는 chapter 7에서 잠깐 소개하는 정도로 알려준다. 그 외에 chapter 2~6까지는 다형성, 추상화와 같은 oop 기초개념들을 확립할 수 있게 해주기 때문에 디자인패턴 책이라기보단, oop 책에 훨씬 가깝다고 생각한다. chapter 2 스터디 포스팅: https://kth990303.tistory.com/274?cate..

자전거 라이딩 카테고리지만, 사실상 우아한테크코스 회고나 다름없는 글. (사진이 꽤 많으니 데이터 유의하시길 바랍니다 ㅜㅜ) 샤로수길로 자전거 타고~ 우테코 방학 1일째, 브리조 데일리 슬랙에 한 글이 올라왔다. 원래 오늘 나의 계획은 알고리즘 스터디 준비하다가, 오후에 자전거 타면서 벚꽃 구경을 하려던 것이었기 때문에 이번 모임은 나가지 않을 예정이었다. 그런데 생각해보니 이왕 자전거 탈 거, 사당까지 가서 잠깐 얼굴 보고 오면 좋겠다는 생각이 들었다. 그래서 낮에는 스터디준비로 참여하지 못할 것 같고, 저녁에 잠깐 들를 수 있겠다고 전하고 오후 4시쯤, 바로 자전거를 타기 시작했다. 3월 말에 벚꽃이 만개했던 작년과 달리, 올해는 4월 초에 벚꽃이 활짝 피었다. 너도나도 다들 벚꽃과 함께 사진을 찍고..

이분매칭 (Bipartite Matching) Maximum Flow를 구하는 방법에는 Dinic Algorithm이 존재한다. 그런데, 모든 간선의 flow가 1이고, 이분 그래프 형태로만 존재한다면 bipartite Matching을 시도할 수 있다. (예를 들어 남녀가 미팅을 하며 각자가 원하는 짝을 1명씩 선택할 때, 최대 수로 성사시킬 수 있는 경우의 수는 이분 매칭으로 구할 수 있다.) 참고로 먼 옛적에는 Blossom Algorithm (1961)으로 최대 이분매칭 수를 O(EV^2)에 구했었다. 최악의 경우 O(V^4)까지 나올 수 있었던 셈. 원리가 궁금하다면 소멤 글을 참고해보자. https://www.secmem.org/blog/2020/04/18/Blossom/ 이분매칭의 시간복잡도..

이번 체스미션은 Level 1의 화룡점정이나 다름없었다. 레벨 1에 있는 마지막 미션이자, 가장 요구사항이 복잡한 미션이기 때문이다. 1~3단계는 체스 게임을 콘솔로 구현하는 것이었고, 4~5단계는 웹 UI, db연결로 이어하기 기능까지 구현하는 것이었다. 다만, 여기서 웹을 Spark Java으로 만들도록 요구사항이 주어졌다. 아마 스파크 자바에 대한 이해를 높이기 위한 미션이라기보단, api를 설계하고 DAO와 그에 따른 테스트 작성을 경험시키게 해보려는 미션이라 생각된다 ㅎㅎ 내 체스 PR은 여기서 확인할 수 있다. 1~3단계 PR: https://github.com/woowacourse/java-chess/pull/287 4~5단계 PR: https://github.com/woowacourse/j..

우아한테크코스 7주차가 순식간에 지나갔다. 어떻게 보면 가장 바쁜 주차가 아닌가 싶으면서도, 어떻게 보면 가장 술을 많이 마신 주차가 아닐까 싶다. (후에 이유를 서술하겠다 ㅎㅎ) 사실상 7주차는 하루종일 페어와 체스 협업미션하는 데에 시간을 대부분 투자했기 때문에 이 글 내용의 대부분은 슬로와의 미션 회고가 차지할 것 같다. 체스 미션 시작 전, 월요일에는 우아한테크코스 크루들은 보통 일요일이나 월요일에 주로 쉴틈을 느낀다고 한다. 이번 체스미션은 예외지만, 보통 미션이 주어지면 금요일까지 pr을 제출하고 토요일~일요일에 리팩토링하면 일요일~월요일에는 자기개발이나 휴식을 취할 수 있기 때문이다. 나는 이 점을 이용해 일요일, 그리고 월요일에 알고리즘 스터디 일정을 잡아놨다! (너무 바빠져버렸다... 과..

호호 스터디에서 Chapter 6: DI와 서비스 로케이터를 듣기 전에, 미리 책을 읽고 공부한 내용을 기록한 포스팅이다. DI와 서비스 로케이터 각 객체들을 사용하기 위해선 어떤 방법이 좋을까? 아무 생각없이 객체를 생성하고 의존하게 될 경우, Chapter 5에서 배웠던 DIP(의존 역전 원칙), OCP(개방 폐쇄 원칙), SRP(단일 책임 원칙) 등 SOLID 원칙을 어기게 되고, 변경에 유연하지 못한 코드가 만들어질 확률이 높다. 특히, 순환 의존이 발생할 경우, 요구사항이 수정되거나 변경될 경우 모든 객체의 코드를 수정해야 될 수도 있다. 이번 시간에는 DI(Dependency Injection), 서비스 로케이터를 이용한 객체 사용 방법에 대해 알아보도록 하겠다. Service Locator ..

알고리즘 중급 스터디에서 과제로 해결해야 했던 문제. 포인트를 놓쳐 생각보다 굉장히 많이 삽질했다. 문제는 아래와 같다. https://www.acmicpc.net/problem/24520 24520번: Meet In The Middle 첫 번째 줄에 마을의 수 $N$, 약속의 수 $K$가 주어진다. $(1 \le N, K \le 100\,000)$ 이어지는 줄부터 $N-1$개의 줄에 도로 정보를 나타내는 세 정수 $u$, $v$, $w$가 주어진다. $u$번 마을과 $v$번 마을 사이에 www.acmicpc.net 의식의 흐름 및 해설 N이 10만이기 때문에 DFS O(N)으로 모든 노드를 훑으면 시간초과이다. 따라서 특정 노드만 확인해주면 되는데, 정점들 사이의 거리는 LCA로 O(logn)에 구할 ..

이번 블랙잭 미션이 끝났다! 확실히 자동차 경주 미션, 로또 미션에 비해선 난이도가 올라간데다가, 리뷰어님께서 굉장히 많이 핀초리 피드백을 해주셔서 포스팅할 거리도 정말 많았다. (1단계 conversation 115개, 2단계 conversation 116개로 총 200개가 넘는 피드백 ㅎㅎ) 블랙잭 미션 주 내용 - Dealer, Player의 중복 로직을 줄이기 위해 interface 또는 abstract class를 익히고 활용해보는 시간을 가졌다. - 또한, 블랙잭 결과(Blackjack, Bust, Hit 등)에 따른 다양한 상태를 객체로 만들어 사용하는 상태패턴 또한 맛볼 수 있었다. 많은 피드백 중에서 내가 인상깊게 배운 점들을 뽑아서 정리해보려 한다. 전체 피드백은 여기서 볼 수 있다. ..