분류 전체보기 (35) 썸네일형 리스트형 기타를쳐보자 https://www.youtube.com/watch?v=-80AC-SqIZQ PS 후기 모두가 그렇듯 나도 대회에 나가 문제를 풀고 상을 받는게 꿈이었다.모두가 그렇듯 나도. 아힘들어 진짜임 재밌었던 DP 모음 - 4, 심심풀이 문제 P4. 재우의 카드깡https://www.acmicpc.net/problem/28693 더보기f(i, j) = i장의 카드가 남았는데 j개의 정보를 이미 알고있을때 시행 기댓값j장의 정보를 알고있으니 당연히 i-j장 중에서 카드를 하나 뽑을 것이다. 1-1.p = j/(i-j)의 확률로 이미 아는친구를 뽑을 것이다.그러면 이미 아는 정보를 활용해서 바로 매치를 시켜버릴테니 기댓값은 p*(f(i-2, j-1)+1)이 된다. 1-2.p = (i-2*j)/(i-j)의 확률로 초면을 뽑을 것이다. 2-1.q = 1/(i-j-1)의 확률로 첫 시행과 같은 친구를 친구를 뽑는다.기댓값은 p*q*(f(i-2, j)+1) 2-2.q = j/(i-j-1)의 확률로 이미 알고 있는 친구를 뽑는다.같은 카드 두 장을 알고있.. 재밌었던 DP 모음 - 3, 심심풀이 문제 P4. 두 팀으로 나누기https://www.acmicpc.net/problem/30896 더보기A가 팀에 속한 사람의 최솟값이 반영된다.A[i]에 대해 정렬해보자. 어떻게 팀을 나누던 반드시 A[1]을 들고 있는 사람이 속한 팀이 존재한다. A를 고정할 것인데, 이미 하나는 고정되어있고그럼 상대팀의 A를 A[j]로 정한다면 일단 상대팀은 j미만의 A[i]를 지닌 친구들을 절대 가질 수 없다. 현재 팀 상황은A[1] * sum(B[1] ~ B[j-1]) / B[j] * A[j] 가 되게 된다. 이제 [j+1 ~ N]의 선수들을 잘 배치해서 최소로 만들어주면 되는데f(i, k) = [i ~ N]의 선수들로 k라는 값을 만들 수 있는가? 라는 함수를 만들어주고 f(j+1, k)가 가능한 경우에 대해서A[1].. 재밌었던 DP 모음 - 2, 심심풀이 문제 https://www.acmicpc.net/problem/24528 엄청 긴 문자열이 주어졌을 때 서로다른 서브시퀀스의 개수를 구하는 문제더보기f(c) = 현재 위치까지 봤을 때 문자 c가 가장 마지막으로 오는 유니크한 서브시퀀스의 개수라고 정의하자.만약 vi가 1이라면f(c) = sum(f(i))+1임을 바로 알 수 있다. 여기에 연산을 한 번 더 적용하면 f(c) = (sum(f(i))+1)*2 - f(c)가 된다.유니크한 문자열 뒤에 c를 이어붙인 뒤, 한 번 더 이어붙이는 것을 반복하면f(c) = (sum(f(i))+1)*vi - f(c)*(vi-1) 임을 알 수 있다.시각적으로 표현해도 쉽게 나옴 https://www.acmicpc.net/problem/17682 격자에서 텐트의 방향과 위치를.. 재밌었던 DP 모음 - 1 https://www.acmicpc.net/problem/30788 그림을 축을 기준으로 뒤집는 문제.더보기일단 n이 홀수면 뭘 해도 거울에 반사된 상태로 보이기때문에 불가능d도인 선으로 그림을 뒤집으면 2*d 만큼 각도를 조정할 수 있다.근데 세계가 뒤바껴있는 상태에서는 -2*d 만큼 작용한다.홀수 인덱스에선 2*d, 짝수 인덱스에선 -2*d를 적용하여 냅색하고 역추적해주자 https://www.acmicpc.net/problem/24099 문자열이 주어지고 문자 u 뒤에 문자 v가 오지 않도록 하는 서브시퀀스의 개수를 구하는 문제 더보기dp(i) = i번 인덱스의 문자를 끄트머리에 사용한 문자열의 개수f(c) = 문자 c를 가장 끄트머리에 사용한 문자열의 개수 dp(i) = sum(f(c))+1 조.. [BOJ] 8158. Blockade https://www.acmicpc.net/problem/8158 문제를 요약하면무방향 연결그래프에서 정점 i와 직접 연결된 간선을 모두 삭제시켰을때u -> v로 갈 수 없는 쌍의 개수를 ans(i)라고 한다.1~n에 대해 ans(i)를 구하여라. 일단 BCC를 돌려준다.정점 X에 파란색 간선을 타고 왔으면빨간 간선들이 브릿지인지만 궁금하다.브릿지면 분할하고 아니면 냅두고쪼개진 애들끼리 곱해주면끗 근황토크 전역하고 5개월이 지났다. 복학하긴 했지만 열심히 다니진 않았다. 굉장한 손해를 봤다.이번엔 걍 휴학해야겠다. 학교와 신촌연합에서 강의를 했다. 자료를 많이 만드는건 재밌었는데 너무 시간을 많이 쓰는 것 같다.좀 더 효율적으로 준비하는 방법을 연구해야겠다. 마감 전날에 술마시고 기절해서 소마 지원서를 못냈다.이제 소주는 절대 안마실것이다. https://blobnom.xyz/ Blobnom blobnom.xyz백준 땅따먹기의 개발에 참여했다.같이 개발하는 사람이 plast, pgh라서 사람들이 너무 잘한다.이용자가 많아서 기쁘다. 두 대회의 총괄을 맡았다.대회 운영은 재밌기도 한데 힘들기도 해서 빨리 넘기고 싶다. 기타를 두 대 사고, 레슨도 4개월 다녔다.아직도 잘 못한다. 연습을 많이 안한거같.. 어째서 하늘은 나를 낳고 군대를 낳았는가 반댄가? 이전 1 2 3 4 다음
