자서전

오늘 (2024년 6월 10일) 백준 다이아 5를 찍었다! 2022년 4월에 플레티넘 5로 승급하고 2년 2개월만에 승급에 성공하였다!!  정말 기쁘다!. 뇌가 확장된 것 같고 알고리즘 고수가 된 것 같아 기쁘다. HOW??? 두 가지 요인으로 승급에 성공했다고 할 수 있다. 첫 번째로 CLASS 8을 밀었고, 말 그대로 뇌의 확장이 있었다는 것도 한 몫 했다. 특히 고등학교 2학년이 되면서 플레 5까지밖에 풀지 못했던 것이 갑자기 플레 1 이하의 문제가 스르륵 다 풀려서 CLASS 8를 미는데 도움이 되었던 것 같다. 그리고 여러 어려운 알고리즘들 (HLD, FFT, Z, 블록껍질)을 배우면서 알 수 있었던 것 같다! CLASS 8은 18 자력 2 도움 (사실 도움이 아니라 개념을 배우고 응용하는 것에..

딱히 잘 한 것 같진 않은데, 무려 101점이나 올라서 승급하였다!! 민트를 복구했다. 2년 만의 복구이다. 사실 안 한 게 맞지만, 안 했음에도 지난 날의 퍼포먼스를 뛰어 넘은 것이 두개골이 확장된 것 같아 기분이 좋다. A - Wallet Exchange 만약 총 남은 개수가 짝수 개라면, 결국에 Bob의 턴에 누구든지 1개의 Wallet이 남는다. 따라서 Bob이 이기는 것은 자명하다. 마찬가지로 홀수 개라면 Alice의 턴에 누구든지 1개의 Wallet이 남는다. 따라서 Alice가 이긴다. 더보기 #include using namespace std; #define int long long void solve() { int A, B; cin >> A >> B; if ((A + B) % 2 == 1..

가장 성적이 좋았던 대회입니다. 앞으로 코드포스 혹은 앳코더를 할 때 복습 및 업솔빙 겸 풀이를 여기다 적겠습니다. 성적은 다음과 같습니다. 최종 랭킹과 Performance는 다음과 같습니다. A. Edge Checker 2 그림에서 직관적으로 보이듯이, 노드 N의 자식 l, r는 각각 N * 2, N * 2 + 1 입니다. 더보기 더보기 #include using namespace std; #define int long long int A, B; signed main() { cin >> A >> B; if (B == A * 2 || B == A * 2 + 1) cout S; for (int i = 1; i N; for (int i = 1; i > from >> to; auto fnode = m.fin..

5626번: 제단 (acmicpc.net) 5626번: 제단 첫째 줄에 가능한 제단의 수를 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net 시간 복잡도: O(N * H/2) 알고리즘: DP 말이 꼬여있어서 어렵습니다. 하지만 보면, i번째 제단과 i-1번째 제단 혹은 i+1번째 제단의 차이는 1 이상 날 수 없습니다. 이는 계단 수 문제랑 비슷한데, 변형되었습니다. 조건은 다음과 같습니다. 시작은 0이여야 합니다. 따라서 1번째 제단의 입력이 0 혹은 -1이 아니라면, 바로 0을 출력합니다. 끝 또한 0이여야 합니다. i번째 제단이 -1이 아닌 경우 i 빼고 모든 값을 0으로 초기화합니다. i번째 제단을 j로 설치하는 경우의 수는 i-1번째를 j, j+1, j-1로 설치하..

18251번: 내 생각에 A번인 단순 dfs 문제가 이 대회에서 E번이 되어버린 건에 관하여 (Easy) (acmicpc.net) 18251번: 내 생각에 A번인 단순 dfs 문제가 이 대회에서 E번이 되어버린 건에 관하여 (Easy) 욱제는 🎄포화이진트리🎄를 종이에 그렸다. 노드에 정수 가중치도 채워 넣었다. 욱제는 적당한 직사각형 영역을 잡아서, 영역 내에 있는 노드들의 가중치 합을 최대로 하고 싶다. 직사각형은 www.acmicpc.net 시간 복잡도: O(Nlog^2N) 알고리즘: 트리의 순회; 중위 순회 DP 이 문제는 생각을 잘 하면 풀리는 것 같습니다. 먼저 하나의 문제를 예시로 들겠습니다. 정수 리스트 S가 주어졌을 때, 연속 최대 부분 합을 구하는 것입니다. 이게 무슨 소리냐면, 연속한 ..

1. Barn Painting (G1) - From. USACO 2017 December Contest Gold 2번 시간 복잡도: O(N) 알고리즘: 트리 DP 말할 것 없는 간단한 트리 DP 문제입니다. DP 테이블을 다음과 같이 둡시다: ≫ dp[i][j] = i번째 노드를 j 색으로 칠할 때 경우의 수 이때, 현재 노드에 대해서 경우가 2가지 있고, 현재 노드에 연결된 노드에 대해 3가지 경우가 있습니다. 우선 현재 노드에 대한 경우를 봅시다. N-1. 이미 색이 안 칠해진 경우 N-2. 이미 색이 칠해진 경우 그리고, 연결된 노드에 대한 경우를 봅시다. I-1. 이미 색이 안 칠해진 경우 I-2. 이미 색이 칠해졌는데, 현재 노드와 색이 다른 경우 I-3. 이미 색이 칠해졌는데, 현재 노드와 색..

13907번: 세금 (acmicpc.net) 13907번: 세금 첫 번째 줄에 세 정수 N (2 ≤ N ≤ 1,000), M (1 ≤ M ≤ 30,000), K (0 ≤ K ≤ 30,000)가 주어진다. 각각 도시의 수, 도로의 수, 세금 인상 횟수를 의미한다. 두 번째 줄에는 두 정수 S와 D (1 ≤ S, D ≤ N, S ≠ D www.acmicpc.net 시간 복잡도: O(N^2logN + NK) 알고리즘: 다익스트라 최적화 예제 힌트를 보고 깨달으셨을 것입니다. 이 문제는 일반적인 최단 거리 알고리즘으로 풀어서는 안 됩니다. 따라서 저희는 이렇게 접근할 수 있습니다: "최단거리가 바뀌는 조건은 무엇일까?" 최단거리가 바뀌는 조건을 한 번 찾아봅시다. 힌트에서 보듯, 세금이 j만큼 인상할 때마다, ..

중간고사가 다가오네요. 그 와중에 PS를 하고 있습니다. 1. 숫자 박스 (G2) - KOI 2003 고등부 2번 시간 복잡도: O(N^3) 알고리즘: DP Only DP 문제입니다. dp 테이블을 다음과 같이 나타냅시다. ≫ dp[idx][a][b] = idx까지 숫자를 설치했을 때, 1번째 줄의 박스를 a개, 2번째 줄의 박스를 b개 설치했을 때 최댓값 4가지 방법이 있습니다. 1번째 줄에 a번째 박스만 설치하기 2번째 줄에 b번째 박스만 설치하기 둘 다 설치 안하기 둘 다 설치하기 여기서 3번째 경우는 항상 손해이므로 배제해서, dp 테이블을 채워나갑니다. 예외 처리를 많이 해주어야 하는 것이 포인트입니다. 더보기 #include #include using namespace std; #define ..

1. Cow Contest (G4) - From. USACO January 2008 Contest Silver 1번 시간 복잡도: O(N^2) 알고리즘: DFS 그래프 문제입니다. 순위를 특정하려면, 앞에 있다고 확신할 수 있는 소의 수와 뒤에 있다고 확신할 수 있는 소의 수가 전체 소의 수에서 1을 뺀 값이 되어야 합니다. 예를 들어, { (1, 2), (1, 3), (2, 3), (2, 4), (3, 5), (6, 4), (6, 1) } 의 입력이 주어졌을 때, node 번호를 가진 소 뒤에 있는 소들의 관계는 다음과 같습니다: 여기서 node 번호가 붙은 소 뒤에 있는 소의 수는 dfs를 통해 쉽게 구현할 수 있습니다. 또한, 앞에 있는 소들의 관계는 간선의 방향을 뒤집어 다시 dfs로 탐색합니다...

5419번: 북서풍 (acmicpc.net) 좌표 압축 + 세그먼트 트리 + 스위핑으로 풀 수 있는 문제이다. 만약 i번째 점이 좌표 (xi, yi)에 있다고 하자. 그렇다면, i번째 점으로 항해할 수 있는 점들은 yi보다 y좌표가 높고, xi보다 x좌표가 낮은 점들의 집합인 것이 자명하다. 여기서 xi보다 x좌표가 낮은 점들은 스위핑을 하며 자동적으로 구해지고, yi보다 y좌표가 높은 점들은 세그먼트 트리로 구할 수 있다. 우리는 X 좌표순으로 오름차순 정렬, 같다면 Y 좌표로 내림차순 정렬하면 스위핑을 할 수 있는 상황이 만들어진다. 정렬 순서대로 쭉 훑어나가면, i번째 좌표 기준으로 갱신된 점의 좌표는 xi보다 왼쪽에 있는 점들밖에 갱신이 안 되었기 때문에, 그저 yi보다 높은 좌표를 가진 점들만 ..