문제 링크 버추얼을 돌면서 만난 문제이다. 처음에는 함수형 그래프에서 사이클을 다루는 알고리즘 floyd cycle finding을 떠올렸는데, 이내 입력을 보아하니 안 될 것 같아서 접고 수식을 정리해봤다. $G=A^nS+B\cdot \frac {A^n-1}{A-1}$이 나왔는데, $n$을 결정하는 것이 난관이였다. 식을 $n$에 대해서 정리하고 이산 로그로 구할 수 있을까라는 생각을 했고, 딱히 발전이 없던 차에 시간이 끝났다. 알고 보니 이산 로그도 풀이가 될 수 있고, 혹은 baby-step giant-step이라는 알고리즘을 사용할 수도 있었다. 사실 이산 로그를 구할 때 이 알고리즘이 들어간다. 아무튼 baby step giant step의 원리를 이해했다. 이것으로 이산 로그를 구할 수 있다..

카카오 코딩 테스트 풀이를 작성했다. 마지막 문제 빼고는 전반적으로 내가 들었던 예전 카카오 난이도보다 낮은 것 같았다. 마지막 문제는 그래도 골드 상위는 될 것 같았다. 아니면 플래 하위까지도 가능할지도 모르겠다. 암튼... 작성하기 귀찮다. 골드 6문제 세트를 200분으로 잡고 돌았다. 35분 남기고 전부 풀어서 다행이다. 사실 점점 시간이 늦어져서 마지막 두 문제는 졸면서 푼 것 같다. 벽 부수고 이동하기 단순히 BFS 두 번 돌리고 고려하면 된다. 17분 정도 걸렸다. 더보기 #include using namespace std; using ii = pair; using ll = long long; #define rep(i,a,b) for (auto i = (a); i x or x > n or 1 ..

KAKAO BLIND RECRUITMENT는 문제의 지문 / 테스트케이스 / 풀이를 비상업적, 비영리적 용도로 게시할 수 있다. 광고가 노출되지 않는 블로그에 문제 풀이를 게시하는 것은 비상업적, 비영리적 용도이다. 출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges 2022년 09월 24일 14:00 ~ 09월 24일 19:00동안 테스트가 진행되었습니다. 이 글에 나와있는 문제 제목들은 실제 제목이 없어서, 제가 문제가 요구하는 요점에 맞춰 지은 제목입니다. 질문은 언제나 환영입니다. 그... 좀 귀찮아서 마지막 두 문제만 풀었습니다. UPD - 마지막 두 개만 풀었는데도 통과했네요.. 미로 탈출(300점) 예상 난이도: 골..

Fancy Fence라는 문제를 풀었다. 더보기 스택을 이용한다는 사실을 알고 있었다. 근데 생각보다 알고 있는데도 인덱스 확인하고 설계하는게 좀 까다로웠다. 컨디션이 안 좋아서 풀이는 작성 안 하고... 풀 때 끄적인 필기만 캡쳐해서 올리겠다. #include using namespace std; using ll = long long; #define rep(i,a,b) for (auto i = (a); i h[i]) sum = (sum-c[s.top()])%MOD, s.pop(); ans += (x[i-1]-(empty(s)?0:x[s.top()]))*C(h[i]+1)%MOD*w[i]%MOD; ans += sum*w[i]%MOD + C(w[i]+1)*C(h[i]+1)%MOD; ans %= MOD; c[..

대회 알림이 6개나 올라와 있길래 할 만한 게 뭐가 있을지 찾아보다가 SNUPC OC Div.2 작년 결과를 보니 대회 우승/준우승 컷이 꽤 낮아서 우승/준우승을 목표로 잡고 참가했다. 대회가 끝났는데 아직 프리즈 이후 상황이 안 나와서 2등 아니면 3등인데 높은 확률로 3등이다. 아쉬운 점은 대회에 늦게 들어온 것과 C 코드를 다 짜고 실수 몇 개 고치다가 노트북 배터리가 부족해서 카페에서 집까지 뛰어서 충전기를 가져오느라 제출이 늦어진 점이다. 또, E에서 해서는 안되는 실수를 했던 점이 아쉽다. 양방향이여서 SPFA가 아니라 dfs 한 번으로 체크하고서 다익스트라를 돌리면 되는 거였는데 착각하고 인터넷에 있는 SPFA 코드를 찾아다가 넣고서 두 번이나 틀렸다. 대회 링크 질문은 언제나 환영입니다. ..

문제 링크 질문은 언제나 환영입니다. 풀이 더보기 지그재그의 조건을 생각해보자. 지그재그는 인접합 2~3개 정도의 원소만 보면 된다. 지그 다음에는 재그 그 다음에는 지그... 따라서 지그 또는 재그의 상태끼리 다 묶어서 관리하면 계산량이 $10^{500}$ 가까이에서 훅 줄어서 reasonable해 질 것이다. 그리고 지그와 재그를 표현함에 있어서 그 자리의 숫자들도 당연히 관리해야 할 것이다. 지그/재그 상태와 자리 숫자가 같아도 몇 자릿수인지에 따라 달라질 것이다. 그래서 자릿수도 관리하고... $M$의 배수라고 하니까, 좀 고민하다가 보면 $M$으로 나눈 나머지를 잘 써주면 좋겠다 싶은데, 이 정보도 함께 관리하면 되겠다. $U(i,j,k):=i$자리에서 증가세로 숫자 $j$에 도달했을 때, 나머..

어제 저녁에 고층 빌딩을 열어서 읽다가 잠들었다. 그래서 일어나자마자 풀고 풀이를 적었다. 글 [BOJ 1328] 고층 빌딩 요즘 학교 OJ에다가 USACO 문제들을 번역해서 하나 둘씩 올리고 있다. 어제는 해커컵 예선 A번 번역한 거에다가 TC를 추가하고 정답 코드를 재채점 돌렸다. 그런데 웬걸, 서버가 터졌다. 아침에 일어나니 다시 잘 돌아가고 있길래 재채점을 다시 돌렸다. 웬걸, 다시 터졌다. 호스팅 업체의 문제인지, OJ의 문제인지 뭔지 모르겠다. 고작 코드 2개 재채점 돌리는데 터지다니... 그래서 Mountain Climbing을 오늘 올리려고 했는데 아직도 못 올리고 있다. P2 짜리를 하나 풀었는데... 구현만 몇 시간 걸린 것 같다. 힘들다... 아무래도 깔끔하게 다시 풀어볼 필요가 있다..

문제 링크질문은 언제나 환영입니다.3가지 풀이법이 나오네요. 글에는 없는 자신만의 풀이법이 존재하신다면 알려주세요!두 가지 풀이법은 $O(n^3)$짜리 풀이이고, 한 가지 풀이법은 $O(n^2)$짜리입니다.풀이더보기문제에서 구해야 하는 것은 조건을 만족하는 배치의 수입니다.세세한 배치의 성질들에 대해 알아볼 방법은 떠오르지 않고, 작은 케이스부터 풀다 보면 패턴이 보이기 때문에 동적 계획법을 시도해볼 수 있습니다. 3차원 동적 계획법$B(x,y,z):=x$개의 빌딩 중 왼쪽에서 $y$개, 오른쪽에서 $z$개만 보이는 경우의 수위와 같이 정의하는 것은 아주 자연스럽습니다. 점화식을 도출할 때는 $B(x-1,\cdots )$와의 관계를 우선 생각 해봅시다.새로 생긴 가장 긴 막대기를 어디다 꽂아 넣을지를 고..

문제 링크 질문은 언제나 환영입니다. 풀이 더보기 딱히 발상이 어려운 문제라고 보기는 힘들다. 특별한 알고리즘이 있는 문제도 아니다. 그냥 열심히 풀면 풀리는 문제다. 중요한 관찰은 하나뿐이다. 동적계획법처럼 귀납적으로 무-팰린드롬을 확장시키려는 시도를 해야 한다. 이 때, 확장하는 경계로부터 2칸 정도만 고려해도 충분하다. 왜냐하면 길이가 4 이상인 팰린드롬은 이미 길이가 2 이상인 팰린드롬을 포함하고 있기 때문이다. 예를 들어, $2$와 무-팰린드롬인지 알고 있는 $432$를 이어 붙이는 상황에서는 $2432$를 확인할 필요가 없는 것이다. 왜냐하면 $43$이 애초에 팰린드롬이 아니기 때문이다. 따라서 $24$와 $243$을 확인하는 것으로 충분하다. 이 관찰을 통해서 풀이를 이끌어 낼 수 있다. 무..