본문 바로가기

글

 (479)
[C++] 27723번 Karl's shopping https://www.acmicpc.net/problem/27723 26/01/12 84주차 랜덤 마라톤 H번으로 나왔던 문제다. 최대유량 문제이다. 문제 접근 방식: 문제에서 주어진 내용은 다음과 같다. 물품이 $N$개 주어져있고, 물품을 결제할 수 있는 수단(상품권, 쿠폰 등등, 편의상 바우처라고 하겠음)이 $M$개가 주어져 있음. 또한, 바우처의 금액(예를 들자면 상품권 금액)이 $B_{i}$로 주어지고, 물품의 가격이 $A_{i}$로 주어짐. 그리고 각 바우처가 어떤 물품을 살 수 있는지의 정보 또한 주어짐. 그랬을 때, 물품을 모두 살 때 드는 "현금"의 최소 비용을 문제에서는 묻고있다. 물품을 모두 살 때 드는 현금의 최소 비용은 (물건 금액의 총 합) - (바우처를 최대한 사용했을 때의..
[26/01/09] 신년 계획 수립 및 슥사 수료 후기 오늘 SCSA 25기를 수료했습니다~! 나 자신에게 박수를....더불어 성적 우수상을 받았습니다! (25기 과정 평가 중 2등을 했습니다) 정말 슥사.... 다사다난한 일이 많았죠...먼저 3개월 간 토요일까지 남아주시면서까지 강의해주신 호선 강사님한테 감사하다고 이야기하고 싶습니다.사실 알고리즘을 많이 했다고 하긴 했지만, 정작 "구현"은 취약한 저였습니다.때문에 구현 중심인 삼성 코테를 잘 할 수 있을까 내심 걱정을 많이 했었습니다. 다행히 호선 강사님의 스파르타식 지도가 많은 도움이 되었습니다.시간을 재고 긴박하게 구현하는 연습들이 저에게 큰 실력 향상을 가져다 주었습니다.그리고 겸손함을 가지게되는 계기가 되었습니다. 알고리즘을 처음하는 사람들이 많았는데 실력이 빠르게 오르는 모습들을 보고 자극을 ..
[25/12/31] 한 해를 마무리하며 이번 년도는 참으로 다사다난한 한 해였습니다. 딱 1년 전의 저는 SSAFY합격을 하여 입과를 앞두고 있는 상황이었습니다. 그 때 까지만 해도 지금처럼 좋은 취업 결과를 얻을 수 있을 것이라는 생각을 할 수 있었을까요. 막연한 불안감이 항상 저를 감싸고 있었고, 워낙 취업 시장이 안좋다 안좋다 라고 들은 만큼 부담감도 심했습니다. 그저 싸피에서 열심히 공부하고, 좋은 성과를 내자, 그런 마음을 가지고 있었습니다. 가장 큰 부담감은 역시 금전적인 부담이었죠... 어쨌든 그렇게 싸피에서 1월, 2월, 3월, ... 한 달 한 달을 보내며 기업 지원을 마구 했습니다. 물론 저는 제가 하고싶은 일이 우선이었기 때문에 처음엔 지금까지 했던 알고리즘과 관련한 기업들을 마구 썼죠. 서류에 탈락하고 면접에 탈락하니 조..
[C++] 14398번 피타고라스 수 https://www.acmicpc.net/problem/14398 25/12/03 이분 매칭 문제이다. 그래프 모델링을 잘 해봐야한다. 문제 접근 방식: 나무 막대끼리 서로 매칭시키면 그 간선마다 피타고라스 쌍이 하나씩 만들어짐을 알 수 있다. 예를 들어, $3$과 $4$ 길이의 나무 막대를 서로 매칭시키면, $5$짜리의 쇠막대를 이용할 수 있다. 쇠막대는 개수가 무한개이므로 결국 나무막대 2개가 한 쌍을 이루게 된다. 따라서, 나무 막대들을 어떻게 2개의 그룹으로 분할할지가 가장 큰 고민이었다. 첫번째로 든 생각은, 나무막대를 하나 더 복사해서 매칭을 시키자하는 거였지만, 이미 사용한 막대는 다시 사용할 수 없기 때문에 최대 매칭을 잘못 구할 수 있다. 이를 막기 위해 간선을 잘 연결하려고 해도 ..
[C++] 16590번 KMP https://www.acmicpc.net/problem/16590 25/12/13 이분 매칭 문제이다. 그래프 모델링을 잘 해보자. 문제 접근 방식: 문제를 요약하면 다음과 같다. 이름 N개가 주어지고, 문자열 쿼리가 주어질 때 마다, 이름의 이니셜을 최대 사람 당 한 번씩 사용하여 해당 문자열을 만들 수 있다면 YES, 아니면 NO를 출력하면 된다. 예를 들어, Donald Knuth, Vaughan Pratt, James Hiram Morris 세 이름이 주어졌으면, KMP는 YES이다. (Knuth, Morris, Pratt 이므로) 최대 유량을 사용해도 되고 이분 매칭을 해도 좋으나, 그래프 모델링은 거의 유사하다. 예제 입력 1과 2의 그래프 모델링은 다음과 같다. 따라서 사람의 이니셜을..
[C++] 6786번 Blood Distribution https://www.acmicpc.net/problem/6786 25/12/14 최대 유량 기초 문제이다. 모델링을 잘 하는 것이 관건이다. 문제 접근 방식: 문제를 정리하면 다음과 같다. 1. 모든 RH- "피"는 RH+, RH- "사람" 상관 없이 줄 수 있음.2. O형 "피"는 A, B, AB, O "사람" 상관 없이 줄 수 있음.3. A형 "피"는 A, AB "사람" 상관 없이 줄 수 있음.4. B형 "피"는 B, AB "사람" 상관 없이 줄 수 있음.5. AB형 "피"는 AB형 "사람"에게 줄 수 있음. 따라서, 일종의 이분 그래프처럼 "피"에서 "사람"으로 향하는 그래프를 모델링 할 수 있다.그림으로 그리면 다음과 같다. 이때 간선의 용량을 정해야 한다. 소스에서 각 피로 향하는 간선의 ..
[25/08/23] 제7회 고려대학교 MatKor Cup: 2025 Summer, The FinAL 검수 후기 검수 후기를 미루고 미루고 미뤄뒀다가 이제서야 작성합니다.사실 바빠서 이번에는 검수를 안하려고 했습니다.왜냐하면 회사에서 교육을 받고 있는 중이여서 검수를 할 틈이 없었기 때문입니다. 근데 갑자기 먼저 동우님께서 검수할 수 있냐고 선 연락이 오시길래, 검수자 인원이 많이 적은가보다 하고 생각했습니다.저는 교육 들어가는 21일 이후부터는 아예 검수 참여가 불가능 하다고 못박은 채로 이야기를 했습니다. 근데 머... 당연히 세팅이 완료되어있는 문제는 반절도 안되있었고, 그 마저도 그 당시 문제 상황과 완성된 문제 상황을 비교했을 때 대부분이 바뀌어있는 문제들이 대다수였습니다. 결론은 21일 이전에 검수를 한문제도 못했습니다.아는 사람들은 알겠지만, 맷코식 대회 출제는 대회 한달 전 쯤부터 거의 매일 검수자와..
[25/11/29] 2025 경희대학교, 단국대학교 shake! 예선 검수 후기 오랜만에 검수 후기를 올립니다.이번년도 8월에 열렸던 마지막 맷코컵 이후에 다시 한번 검수를 하게 되었습니다.검수를 하게 된 특별한 이유는 없습니다.그냥 해보고 싶었는데, 마침 검수진을 모집한다고 해서 지원했고 검수진으로 들어갔습니다.지금은 회사에서 교육을 받고 있는 중이기 때문에 딱히 돈에 대한 욕심이 없기도 했었고, 오히려 돈을 받으면 모든 문제를 다 검수해야한다는 부담이 있었기 때문에 돈을 받지 않는 형태로 검수를 했습니다. 모든 문제를 전반적으로 보긴 했지만, 제가 검수를 한 문제는 H, I번을 제외한 A, B, C, D, E, F, G, J번입니다. 각 문제 별로 코멘트를 남겨보고자 합니다. [A번] 포도주 상인처음에 지문을 봤을 땐 최대 "이익"을 구하라고 문제에 적혀있었습니다.아무래도 "매출..

티스토리툴바