일기 (사실 근황임) (52) 썸네일형 리스트형 2023년 4월 2일 일기 감기 걸려서 조금 쉬다 왔습니다. 다들 감기 조심하세요. 대회 리뷰 포스팅은 계속 밀릴 예정입니다. 정체 모를 텍스트 파일이 있어서 날렸는데 대회 문제 풀이 임시 저장본이었네요. test.txt로 저장한 제 잘못입니다. 저번 주 화요일에는 icpc 팀원들과 저녁을 먹었습니다. 이 글 작성 시점에서 우리 학교에는 잘 하는 사람이 없기 때문에 수상 가능성은 0에 가깝습니다. (저를 제외하고 코포 블루 레이팅 이상 유저가 없습니다) 그리고 저는 올해가 마지막 기회이기 때문에 중간에 팀원이 도망가는 상황이 발생하면 매우 곤란해집니다. 때문에 실력보다는 신뢰와 성실함을 기준에 두고 팀원을 선정하였습니다. (허락받지 않아 이름 대신 학번을 기재합니다) 두 친구 모두 신뢰와 성실함을 겸비하고 있습니다. 20 친구는 .. 2023년 3월 24일 일기 BOJ 3878번 - 점 분리 널리 알려진 풀이는 구현이 복잡한 편이다. 나의 풀이는 ccw + brute force 풀이인데 엄밀하게 증명하지는 않았다. 그림 그려보면 대충 맞는 것 같은데 확실하지는 않다. 반례 발견하면 제보 부탁드립니다. 절대 놀고 있지는 않은데 대회 리뷰 포스팅이 많이 밀렸다. 이 글 작성 시점으로 5개가 밀렸고 이번 주말 대회까지 참가하면 7개가 밀리는 셈이다. 지금까지 지켜온 다음 두 가지 원칙 때문에 계속해서 밀리고 있다. 참가한 순서대로 올린다. 모든 업솔빙을 마친 후 올린다. 현재 skku K번에서 병목이 발생하였고 이 때문에 나머지 포스팅도 밀리고 있다. 2주 내로 올려보려고 노력 중이다. 그 대신 단계별과 CLASS를 조금 밀었다. 단계별은 8단계 남았고 CLASS는 .. BOJ 25015번 - 아이싱 25015번: 아이싱 C++17, C++14, C++20, C++14 (Clang), C++17 (Clang), C++20 (Clang) www.acmicpc.net notorious coincidence 문제집에서 찾은 문제이다. 19862번과 동일한 문제인데 아쉽게도 19862번은 작성 일자 기준으로 레이팅을 주지 않는다. 하지만 루비 문제 치고 풀이가 간결하다기에 아래 블로그에서 풀이를 공부하고 풀어 보았다. https://dsstar.tistory.com/49 https://justicehui.github.io/ps/2020/09/16/BOJ19862/ 그런데 코드가 전혀 이해되지 않았다. 심지어 두 번째 블로그는 코드에 사소한 오류가 있는데 복붙 방지용인 듯 하다. 몇 시간 동안 생각해보아도 이.. BOJ 2156번 - 포도주 시식 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 정말 기초적인 dp 문제인데 반례를 한참 동안 못 찾아서 반성할 겸 포스팅한다. 다음과 같은 배열 A를 정의하자. A[i] = i번째 포도주의 양 다음과 같이 점화식을 세우면 WA를 받는다. dp[i] = max(dp[i - 2], dp[i - 3] + A[i - 1]) + A[i]; 사실 이 점화식은 2579번과 동일한 점화식이다. 2579번에서는 i번째 계단을 밟기 전에 (i - 1)번째 또는 (i - 2)번째 계단을 반드시 밟아야 한다는 조건이 있다. 하지만.. BOJ 26101번 - 링크와 스타트 2 26101번: 링크와 스타트 2 첫째 줄에 N(4 ≤ N ≤ 400)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100 www.acmicpc.net 귀찮기 때문에 구체적인 풀이는 작성하지 않을 것이고 힌트만 몇 개 남긴다. HINT 1 더보기 knapsack dp와 bitset 태그가 붙어 있음에 주목하자. HINT 2 더보기 먼저 26607번을 풀어 보자. 잘 모르겠다면 에디토리얼을 참고하자. HINT 3 더보기 26607번을 bitset으로 풀어 보자. HINT 4 더보기 그 다음에는 21844번을 풀어 보자. 잘 모르겠다면 에디토리얼을 참고하자. HINT.. 2020 ACM-ICPC Seoul Regional Asia Regional - Seoul 2020 www.acmicpc.net 서론 실제로 참가하였던 대회이기도 하고 풀어볼 만한 문제도 많아 보여서 최대한 업솔빙하였다. B - Commemorative Dice 단순 구현 C - Dessert Café 임의의 두 아파트 단지를 잇는 경로 사이에 존재하는 candidate site는 good place이다. 임의의 아파트 단지에서 dfs를 돌리면 모든 good place를 찾을 수 있다. 간선의 가중치는 필요하지 않다. E - Imprecise Computer 각 round의 결과에 대하여 D[i]의 값은 다음과 같이 결정된다. if (i - 1) vs i의 결과가 동일 if i vs (i + 1)의 결과가 동일 D[i] = 0 else D[i] = 1 e.. 2023년 1월 13일 일기 겨울 숲의 초대 이후로 거의 한 달 동안 대회 참가와 업솔빙만 반복하면서 지냈다. 이제 모든 업솔빙이 끝나서 조금 여유가 생겼는데 그 대신 글이 많이 밀렸다. 작성 예정인 글 목록은 다음과 같다. Good Bye, BOJ 2022! (G번 H번) 나는코더다 2022 송년대회 Open Contest Hello 2023 제1회 보라매컵 예선 Open Contest 2020 ACM-ICPC Seoul Regional 보드게임컵 (참가 예정) Hello, BOJ 2023! (참가 예정) 막상 적어보니 많지는 않다. 아무튼 연말에 어려운 대회가 쏟아져 나와서 업솔빙이 정말 오래 걸렸다. 특히 나는코더다 업솔빙이 힘들었는데 덕분에 cht와 dnc opt는 잘 배웠다. 내일은 보드게임컵에 참가하고 서울로 일찍 올라간.. BOJ 19089번 - 파일 합치기 4 19089번: 파일 합치기 4 프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T개의 테스트 데이터로 이루어져 있는데, T는 입력의 맨 첫 줄에 주어진다.각 테스트 데이터는 두 개의 행으로 주어지는데, www.acmicpc.net Garsia-Wachs algorithm 또는 Hu-Tucker algorithm으로 풀이할 수 있다. 나는 Garsia-Wachs algorithm으로 풀이하였다. 원본 논문보다는 이 논문을 보는 것을 권장한다. 알고리즘 자체는 간단한데 다음 두 단계를 N - 1번 반복하면 된다. (i) Locate the rightmost R.M. pair of entries. Let that be p_i-1, p_i. (ii) Next locate the first en.. 이전 1 2 3 4 5 6 7 다음
