SUAPC 대비 할 일 DP 실력 올리기 ✔ Gold V 14728 벼락치기 ✔ Gold II 2662 기업투자 ✔ Gold V 17845 수강 과목 ✔ Gold IV 4781 사탕 가게 Codeforce Blue 찍기 위해 할 일 DP 실력 올리기 ✔ Si

나는 내가 생각해도 심각한 정도의 DP 부족인데, 최근 열린 Codeforce Div 3에서 간단한 DP 문제를 BFS로 삽질하다가 40분 날리고 충격에 빠졌다.그래서 곧 있을 SUAPC와 각종 대회들에서 팀원들 발목은 잡지 않으려고 DP 연습을 하고 있다.월요일부터

최소 스패닝 트리를 그려서 해결하는 기초 문제다. 모든 별을 잇는 트리의 선분 길이를 출력하라는 문제인데 그냥 평범하게 구현해서 출력하자.여기서는 간선의 비용이 아닌 정점의 좌표가 주어지므로 잘 가공해서 간선으로 만드는데 $O(N^2)$이 들고, $N = 100$이기

정답 비율이 지나치게 낮은 것이 눈에 띕니다. 그리고 그럴 만 합니다.이 문제는 정렬 후 순회하면서 $O(N)$에 처리하는 그리디의 전형적인 유형입니다. 그러나 정렬하는 과정이 생각이 많이 필요하고, 코드는 단순하나 생각이 단순하지 않은 문제입니다. 근데 풀고 나면 엄

아니 이게 참... 제목이... 파루빗토가 8비트라고 합니다. 알고 싶지 않았습니다.원래는 제목 때문에 올리기는 싫었는데 이걸 어렵게 푸시는 분들이 많아서 올려봤습니다.문제로 주어진 수식이 8진수 사칙연산이고, 그걸 10진수로 변환해서 더하고, 다시 8진수로 변환합니다

5월 월간 향유회 C번 문제입니다.이건 이분탐색이 정해입니다. ㄹㅇ.구간 l, r이 주어질 때, 그 구간 내부에서 R과 B를 찾아야 합니다.R을 나타내는 인덱스 a, b와 B를 나타내는 인덱스 c, d가 있을 때, $a<b<c<d$인 a, b, c, d

5월 월간 향유회 B번 문제입니다.우선 문제를 보면 머리가 아픕니다. 저는 조합론을 별로 안 좋아합니다. 그래도 문제를 봅시다.만약 고등학교 때 확률과 통계를 배웠다면 비슷한 문제를 내신에서 풀어봤을 것입니다.어떤 한 사람의 위치에서 출발해서 모든 사람의 위치를 방문하

5월 월간 향유회 A번 문제입니다. 나머지 정리를 배웠다면 다음 식을 구성할 수 있습니다.$N = mq + R$따라서 $N - R$이 나누어 떨어지도록 하는 $m$을 찾으면 됩니다.단, $R$이 나머지여야 하므로 $m > R$ 이어야 합니다.$N-R$의 약수를 구하고,

길이가 N인 수열에서 4가지 쿼리를 적절하게 처리하는 문제입니다.구간 덧셈, 구간 곱셈, 구간 변경 연산과 구간 합을 출력하는 쿼리가 들어있습니다.구간 덧셈과 곱셈, 그리고 변경은 전부 update() 연산이고, lazy하게 처리하는 방법이 조금 떠올리기 어렵습니다.그

일단 이 문제는 $O(N^2/64)$로 뚫린다고 합니다. Bitset으로 날먹할 수 있습니다.스위치의 값은 0과 1 중 하나라는 점이 중요 포인트입니다. query() 가 합을 구하도록 되어 있으니 구간 합 세그트리를 구성해야 합니다. lazy는 boolean 값을 담

https://www.acmicpc.net/problem/12844레이지 프로퍼게이션을 쓰는 연습 문제입니다.XOR 연산은 합 연산과 다르게 구간 s, e에 대해 (e-s+1) 이 홀수일 때만 노드에 lazy를 xor해주면 됩니다.0^a = aa^a = 0x^

세그먼트 트리는 무궁무진한 활용이 가능한 자료구조입니다. 레이지 프로퍼게이션은 그 활용 중 하나로 레이지 세그와 함께라면 백준의 많은 문제들을 해결할 수 있습니다.대부분 알고리즘의 기본적인 최적화 원리는 다음과 같습니다.반복되는 연산을 줄이고, 겹치는 건 한 번만 계산

요약 : 코딩을 못해도 시간을 박으면 누구나 풀 수 있다. 근성으로 가능한 플레 I 문제다! 근데 오래 걸린다.완전 수학 문제였는데 예제 입력과 출력이 잘 나와 있어서 풀기까지 시간은 많이 걸렸지만 틀렸습니다를 받진 않았다.교양 시간에 풀기 시작했는데 중간에 너무 많은

아이디어성 문제라고 생각했는데 구현도 헷갈리고 어려웠습니다. 중간에 LIS라고 착각해서 이상한 길로 빠지기도 하고, 어떻게든 해설은 안 보려고 했지만 결국 멘붕와서 해설을 보게 만들었던 문제...아무튼 기본 아이디어는 스스로 떠올렸기 때문에 그나마 만족합니다.일단 이

= (\[코드

길이가 3인 LCS의 개수를 구하는 문제다. 이 문제는 길이가 3인 LIS를 구하는 문제로 치환할 수 있다.그러므로 길이가 3인 LIS를 구하는 방법을 생각해보자.길이가 3인 부분수열의 중앙값을 고정하고, front, middle, back 형태로 생각하자.front는

스위핑의 어려움을 알려주는 문제라고 생각한다. 2차원 평면 위의 점 75000개를 순서대로 쓸어내려가면서 각 점마다 $O(logN)$으로 처리하는 문제다.어떤 섬에 대해서 그 섬보다 y좌표가 작고, x좌표가 큰 섬만 방문이 가능하다. 가장 먼저 생각나는 방법은 $O(N

C, Java, Python이라는 세 단어에 주목했어야 한다... 진짜 그것밖에 못 쓸 줄은 몰랐지13일 토요일에 진행되었던 예선에 참가했다.나는 종로 지점에서 참가했는데, 자리에 앉자마자 진짜 코딩하는 자리는 아니라는 느낌이 팍 왔다.모니터부터 본체까지 굉장히 맘에

리프 노드부터 업데이트하는 세그트리를 만들 줄 아십니까? 라고 물어보는 문제다. 구간 합 구하기에서 update() 함수를 Top-down으로 만들었다면 이 문제에서는 0의 특수성 때문에 리프 노드부터 작동하도록 해야 한다.두 방법 모두 구현해보면 세그트리의 숙련도가

중위 순회에 대해 물어보는 문제다. 이진 트리에서 중위 순회는 left -> parent -> right 순서로 탐색하는 방법이다.문제에서는 일반적인 중위 순회가 아닌 유사 중위 순회에서의 이동 횟수를 물어보고 있다.유사 중위 순회는 다음과 같이 진행된다.일반적인 중위