Miscellaneous

https://www.acmicpc.net/problem/6525 n*n 행렬에서 각각의 칸들이 서로 다른 행과 열에 속해있도록 n개의 칸을 선택합니다. 이렇게 선택하는 경우의 수는 총 n!개입니다. n!개의 경우의 수에 대해서 n개 원소의 총 합이 모두 같은 지를 판단하는 문제였습니다. 규칙이 있을 것 같은데, 고민해봐도 찾지 못하겠더라구요.그래서 저의 경우에는 랜덤화를 이용하여 해결했습니다. 무작위로 1만개의 수열을 생성한 뒤, 합이 일정한지를 확인했습니다. 문제해결을 하면서 랜덤화를 처음 사용하게 됐는데, 주요 함수는 아래와 같습니다.// 시드값 (time(NULL))에 대한 난수 생성mt19937 rng((unsigned int)time(NULL));// 난수 생성기를 기반으로 배열 셔플su..

AWS와 Codetree가 공동으로 주관하는 Aws x Codetree Programing Contest (이하 ACPC) 본선 대회에 다녀왔습니다. 예선예선 대회는 COEIC이라는 플랫폼에서 진행되었는데, 정해진 기간 내에 아무때나 들어가서 치룰 수 있었습니다. 4시간동안 온라인으로만 진행됐고, 총 13문제가 주어집니다.하지만 이에 대한 사전 공지가 없었어서... 대회치면서 "아니 언제끝나!", "아니 왜이리 많아!"했던 기억이 나네요.본선 진출자는 예선 top50 + 대학할당제 50으로 선정되었습니다. 정확한 점수는 기억이 안나는데, 저는 800점 조금 넘는 정도였고, 대학할당제로 본선에 진출했습니다. 사실 큰 기대는 안했는데, 막상 본선에 간다고 하니 기분이 좋더라구요ㅎㅎ 가톨릭대학교에서는 저만 ..

https://www.acmicpc.net/problem/5569 모든 경우에 대해서 탐색하려고 하면,최대 200C100의 경우의 수가 만들어지므로 시간 안에 해결할 수 없습니다.  해당 문제는 dp로 해결할 수 있습니다.현재칸에 위/왼쪽에서 왔고, 방향을 바꿀 수 있는지에 대한 여부를 기록하기 위해 dp[i][j][k][l]로 표현할 수 있습니다. i, j : 현재 칸의 인덱스k : 0이라면 왼쪽에서, 1이라면 위에서 접근l : 0이라면 방향을 바꿀 수 없고, 1이라면 방향을 바꿀 수 있음    점화식은 위 그림처럼 나타낼 수 있습니다. (파란색, 연두색)빨간색은 {i,j}에 접근하는 모든 경우입니다.이전 칸에서 한번 꺾은(방향을 바꾼) 경우엔 {i,j}에서는 방향을 바꿔선 안되고,반대로 꺾지 않은 경..

첫 회고글 입니다! 사실 올 한해 전체에 대해서 회고글을 작성하고 싶었는데, 생각해보니 딱히 상반기에는 한 일이 없더라구요..? 대신 하반기에 이것 저것 많이 해왔던 것들이 있어서, 마침 종강도 했고, 해가 지나기 전에 한번 훑어보는 시간을 갖고자 회고글을 작성합니다!  저의 2024 하반기의 카테고리는 아래와 같이 크게 3개로 나눌 수 있습니다. 1. 알고리즘2. 동아리 활동3. 3학년 2학기 1. 알고리즘 올해는 알고리즘, 정확히는 PS에 많은 시간을 쏟았습니다.지난 학기에 알고리즘설계 수업을 들으면서 SCC나 네트워크 플로우 등 재미있는 알고리즘들을 배울 수 있었고, 학교 알고리즘 동아리인 ALCUK의 부회장을 맡아 활동하면서 꾸준히 문제를 풀어왔습니다.덕분에 솔브드 티어는 쭉쭉 오를 수 있었지만,..

https://www.acmicpc.net/problem/24508  나도리를 옮기는 횟수를 최소화하려면, 일단 나도리 수가 작은 바구니부터 나도리를 옮겨 비워야 합니다. (greedy)이를 위해서는 정렬은 불가피함을 쉽게 파악할 수 있었습니다. 여기서 1. 투포인터를 쓰는 풀이와 2. 수학적으로 간단하게 푸는 풀이를 소개합니다.   1. 투포인터 풀이 나도리가 가장 많이 들어있는 바구니부터 채워줍니다. 나도리의 수를 기준으로 오름차순 정렬하여, 가장 앞에 있는 나도리부터 차례대로 가장 뒤에 있는 바구니에 넣습니다. 즉, 현재까지 나도리가 가장 적게 들어있는 바구니에 있는 나도리를 나도리가 가장 많이 들어있는 바구니에 채워넣습니다. 동시에 나도리의 이동 횟수를 기록해줍시다. 나도리를 k개 다 채웠다면, ..

https://www.acmicpc.net/problem/2716      수학 잼병인 작성자인지라... 증명이 옳은지는 모르겠습니다.. 결국 트리의 높이(최대 깊이)를 구하는 것이 문제의 key이므로,입력 string을 읽으면서 트리의 최대 깊이를 구해주기만 하면 되는 문제였습니다.   코드#includeusing namespace std;#define X first#define Y second#define rep(i,x,y) for(int i=x;i pii;typedef pair pll;typedef tuple tiii;int dx[] = { 0,0,1,-1 };int dy[] = { 1,-1,0,0 };/*----------------------*/void solve(){ string s; ..

2024 ICPC Seoul Regional 예선에서3솔 + 학교1등으로 본선에 진출하게 되었습니다. 예선에 대한 자세한 내용은 아래 포스팅에 작성해두었습니다.https://5-ms.tistory.com/19 2024 ICPC Seoul Regional 예선 후기지난 10월 26일에 열린 2024 ICPC 예선 대회에 참가했습니다. http://static.icpckorea.net/2024/first_round/scoreboard_10282200/ SpotboardSpotboard from algospot.com, wookayin and Being CSUS Programming Contest System Icons from FatCowstatic5-ms.tistory.com  대회는 일산 킨텍스 제2전시..

https://www.acmicpc.net/problem/17353레이지 프로파게이션 공부하다가 만난 문제입니다.그래서 "레이지를 쓰긴 하겠구나"는 알았지만, 어떻게 레이지를 써야될 지가 막막했습니다.도저히 고민해도 풀이가 떠오르지 않았기에, 결국 답을 봤던 문제입니다.. 일단 Lazy Propagation은 기본적으로 두가지 연산을 지원합니다.1. 구간에 대한 단일값 업데이트 쿼리2. 구간에 대한 쿼리 하지만 문제에서 주어지는쿼리는 다음과 같습니다.1. 구간에 대한 다중값(등차수열) 업데이트 쿼리2. 점에 대한 쿼리  우선 구간 업데이트입니다. 문제를 위해 구간에 대해 1,2,3,...,R-L+1씩 업데이트 해야합니다.하지만 가지고있는 연산은 단일 값으로만 업데이트가 가능합니다. 그래서 처음 생각해봤던..