어제 백준이 섭종을 했답니다.그래서 추억을 남기려는 차원에서 이렇게 뒷 에디토리얼을 적어보려 합니다. 저는 총 4 문제를 출제 했었는데 모두 2023년에 진행한 제 2회 보라매컵 문제였습니다.각 문제 별로 오프 더 레코드를 이야기해보려 합니다. 1. 29695번 기지방호 (G1)저 문제는 예선을 위해 Subtask가 존재하는 문제를 구상하다가 갑자기 떠올랐습니다. Floyd-Warshall DP를 약간만 비틀면 저렇게 문제를 낼 수 있겠더라구요. 저거 출제하려고 할 때 개최하신 분께서 "그래프라 TC 촘촘하게 만들기 많이 빡셀거다" 이랬어서 TC를 엄청 열심히 만들었습니다.그런데 본 대회 진행할 때, 실제로 테케가 도중에 뚫렸었고... 그걸 무마하려 중간에 PC방 가서 해결했던게 기억납니다.다행이 본 대..

오랜만에 글을 올려봅니다."DSU 알고리즘에서 크기를 기준으로 union을 하면 O(NlogN)이 된다." 이게 Small-to-Large technique으로 전 알고 있습니다.다만 이게 왜 O(NlogN)인가는 좀 직관적으로 이해가 잘 안 갔었는데... 최근에 인사이트가 생겨 이를 공유해보고자 합니다. 자... DSU 알고리즘에서 모든 element를 Union을 할 때 생기는 시간복잡도는 "모든 element가 이동한 횟수"가 될 것입니다.그러면 각 element가 몇 번 정도 움직이는 지 파악하면 되겠죠? 그러면 각 element가 언제까지 움직여야 할까요?조금 비틀어서 생각해보면 현재 element가 속한 집합의 크기가 N이 될 때 까지가 됩니다. 현재 element a가 속한 집합의 크기가 s..

지난번 구름edu에서 진행된 대회 이후에 또 다른 대회에 참여하였습니다.지난 대회는 한동대 / 우송대 / 한밭대 이렇게 세 대학교끼리 주최하여 진행한 것 같은데,이번 대회는 전국 대학교에서 참여하였습니다. 대회 진행1. 마스코트 선별 시험 [실버 2]배열에서 K개의 element를 골랐을 때 element 간의 차이 중에서 최소 차이를 묻는 문제였습니다.정렬해서 a[i]와 a[i+K-1]의 차이를 구하여 그 중 최솟값을 구하면 되는 문제였습니다.정렬 + 그리디 유형으로 백준에서도 실버 2 정도 받았을 것 같네요.시간복잡도 : O(NlogN) 2. 개구리 점프 [골드 2]https://www.acmicpc.net/problem/1937 이 문제가 생각나는 문제였습니다.(1,1), (1,2) ,... (N,..

11월 16일에 전국 대학생 프로그래밍 경진대회가 있다길래 참여해보았습니다.다음주 ICPC 본선 전에 몸도 풀겸 참여해보았습니다.시험 환경은 비대면으로 시험을 치는 지라, Softeer에서의 HSAT과 같이 웹캠 등을 켜서 진행했습니다. 사전 테스트사전에 테스트를 쳐야하기에, 한 번 쳐보았습니다. 4문제에 6시간 정도 주어지는데 총 40분 정도 걸렸던 것 같습니다.사전에 풀었던 문제는 다음과 같았습니다. 1. UXUI 디자이너 문제 : https://level.goorm.io/exam/163020/uxui-%EB%94%94%EC%9E%90%EC%9D%B4%EB%84%88/quiz/1 구름LEVEL난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다.level.goorm.io이벤트 - 참여..

이번에 KimsaiAn 팀명으로 ICPC에 참여해보았습니다.저희 팀은 E,F,H 이렇게 총 3 문제를 풀었는데, 어떻게 풀었는지 풀어본 순서대로 복기해보려 합니다. E : 행렬 게임 처음에 어떤 문제가 쉬울지 감이 안 오다가 스코어보드에서 E번을 다들 풀기에 저희도 풀어보았습니다. 서두르느라 수식이 안 보였지만, a와 b 행렬의 값 차이의 절댓값은 칸 별로 미리 계산할 수 있어보였습니다. 그러면, 각 열 별로 a와 b 행렬의 값 차이가 제일 큰 값들도 미리 찾을 수 있겠죠? 미리 각 열 j 별로 |a[i][j] - b[i][j]| 가 제일 큰 i 위치들을 구하던지 아니면 |a[i][j] - b[i][j]| 값들을 저장해둡시다. 그리고 M개에 대해서 미리 계산을 해둔 값들로 더해주면 됩니다. 총 시간복잡도..

최근에 머신러닝 부트캠프에 합격해서 머신러닝 개념들을 다시 처음부터 공부하고 있습니다.오랜만에 LR(Logistic Regression), BCE(Binary Cross Entropy) 등을 보기 시작하니 오랫만에 옛날 친구들을 만나는 심정으로 보고 있는데, loss function이 BCE일 때에 아래와 같은 그림이 나온다고 합니다.  여기서 저는 어떻게 Binary Cross Entropy가 convex 한 성질을 가지고 있는가 궁금해졌습니다.일단 BCE를 사용한 cost function은 아래와 같이 정리가 됩니다. 일단 log 값도 있고... y_hat = a(wx+b) 인데, a 는 심지어 sigmoid function 입니다. (그래서 MSE를 사용하면 non-convex 해진다고 하죠...)..