자서전

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

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로 탐색합니다...

제목에서 알 수 있듯이, LIS 문제를 O(N log N)의 시간복잡도로 세그먼트 트리를 이용하여 풀 수 있다. 예제로 9 9 5 4 6 1 3 7 10 2 라는 입력이 주어진다고 해보자. 여기서 LIS는 무엇일까? LIS = { 5, 6, 7, 10 }, 혹은 { 4, 6, 7, 10 }, 혹은 { 1, 3, 7, 10 } 등으로, 길이는 4이다. 우리는 만약에 N >= 10,000 이상의 입력이 들어온다면, O(N^2)의 dp 알고리즘으로는 풀 수 없으므로, O(N log N) 의 풀이를 알아야 한다. 그리고 우리는 세그먼트 트리를 활용한 구간 최댓값을 구하는 것으로 이를 풀 수 있다. 예제를 예로 들겠다. 배열 요소가 저장된 배열을 S라 할 때, S는 다음과 같이 표현된다. S 9 5 4 6 1 3..

안녕하다. 나는 Problem Solving, 리버싱, 등을 취미로 하는 박종휘라고 한다. 내가 자서전(Tistory)를 만든 이유는 이러하다. > 1. 미래의 내가 현재의 나의 모습을 성찰하기 위해 > 2. 내가 과거의 나의 모습을 성찰하기 위해 > 3. 나의 의견을 다른 사람의 의견과 대조해서, 더 나은 나를 만들기 위해 애초에 3번 이유는 이 자서전을 만든 이유 중 10%정도도 되지 않기 때문에, 자서전에는 독백어조로 된 글이 많을 수 있다. 읽는 이의 입장에서 불편할 수 있지만, 양해하기 바란다. 중요 일정 2024년: 놀기 Contact Hypixel: I am like 18 hours online, you can reach me. Discord: __readfsqword