백준 2문제 1. BOJ 14897 서로 다른 수와 쿼리 1 - P2 Mo's Algorithm을 활용하는 문제. 그저께 공부한 것과 더불어 Mo's를 좀 더 공부해보기 위해서 풀어보았다. 다행이 이제 코드 안 보고도 구현할 수 있게 된 것 같다. 대충 값 압축을 하면 시간초과가 나서 좀 생각을 해야했는데, 그냥 map 등으로 이미 전에 나왔던 값이면 제일 처음으로 나왔던 자리로 mapping 시키는 자료구조를 만들고, 거기서 counting을 하는 방법으로 구현했다. 좀 더 공부해봐야지. 2. BOJ 1377 버블 소트 - G2 정렬해서 푸는 문제. 처음에는 LIS나 세그먼트 트리로 풀리지 않을까 싶었는데 아니었다. 코드를 분석하다보면 코드가 한 번 돌 때마다 뒤에 있는 원소가 앞으로 최대 한 칸씩만 ..

백준 1문제 1. BOJ 2024 선분 덮기 - G3 그리디 + 스위핑 문제인데... 세그로 풀어버렸다. 처음에는 나도 그리디 + 스위핑인 것 같긴 했는데, 이런 류의 문제들(특히 스위핑)을 잘 몰라서 어떻게 풀지를 몰랐고. 결국에는 그냥 세그로 풀었다. 접근은 간단하다. 0부터 시작해서 0 이하의 좌표에서 시작하는 선분 중 끝 점이 제일 큰 값을 고른다. 다음에 전에 고른 값 이하의 좌표에서 시작하는 선분 중 끝 점이 제일 큰 값을 계속 고른다. 이를 계속 반복하다가 더 이상 값이 갱신이 안 된다거나 아니면 M을 넘기면 종료한다. 다들 Happy New Year!!!

백준 4문제. 1. BOJ 10451 순열 사이클 - S3 순열 사이클 분할 기본 문제. 순열 사이클 분할이라는 태그가 무엇인가 싶어서 한 번 풀어보았다. 그런데 문제는 그냥 DSU로 풀려서 이 태그가 도대체 무엇일까라는 의구심이 더 강해지는 문제였다. 2. BOJ 27280 이기적인 목봉 체조 (Easy) - G3 DP 문제. 예전에 실제 대회에서 어떻게 푸는지 감도 안왔던 문제. 이러한 DP 문제를 의외로 풀어본 경험이 없어서 업솔빙 했다. 미리 구간에 대한 힘을 계산을 다 해두고 DP를 돌리는 아이디어가 나한테는 신기했다. 이렇게 올해 설날 때 봤던 문제를 한 해의 마지막 날에 풀게되어 나름 마무리하는데 의미있는 문제. 3. BOJ 13547 수열과 쿼리 5 - P2 Mo's Algorithm 문제..

백준 1문제 1. BOJ 24263 알고리즘 수업 - 알고리즘의 수행 시간 2 - B4 스트릭용 수학 문제. 코드가 너무 단순해서 그냥 시간복잡도를 계산하면 된다. 오늘 일지는 여기서 끝.

백준 2문제 1. BOJ 17220 마약수사대 - G4 BFS 문제. 문제의 정의에 따라서 마약의 원산지는 in-degree가 0인 노드들부터 시작하므로 가능한 원산지들부터 모두 BFS를 돌려보면 된다. 단, BFS를 돌릴때 검거된 노드들은 탐색하지 않는 방향으로 구현해야한다. 이 외에는 딱히 특이한 점은 없는데 N이 좀 더 크게 만들면 더 좋았을 것 같다. 2. BOJ 17398 통신망 분할 - P5 오프라인 쿼리 + DSU 문제. 끊어진 간선들을 전부 받아서 마지막까지 안 끊어진 간선들을 DSU로 엮어준다. 그 다음에 끊어진 간선들을 역순서대로 다시 이어주면 DSU로 풀린다. [모두의 랜덤 디펜스] - 중급 코딩테스트 (B2 ~ G4) 시험시간 : 60분, 실제 : 52분만에 올솔 Solved : 3..

[모두의 랜덤 디펜스] - 삼성 코딩테스트 (S1 ~ G1) 시험시간 : 180분, 실제 : 70분만에 올솔 Solved : 2/2 1. BOJ 13335 트럭 - S1 그냥 큐를 활용한 시뮬레이션 문제. 큐를 활용해서 각 시간마다 어느 차가 들어올 수 있는지를 시뮬레이션 하면 된다. 최대 걸리는 시간이 O(NW)일텐데 충분히 시간내에 돌아간다. 2. BOJ 23288 주사위 굴리기 2 - G3 빡구현 및 시뮬레이션 문제. 그래프야 뭐 BFS + Flood-fill을 해서 같은 숫자의 값들이 연속적으로 어떻게 붙여있는지를 파악하면 되어 어렵지 않았다. 그리고 시뮬레이션을 그냥 돌려도 될만한 K값이라 어렵지 않을 것 같았는데... 주사위 굴리는 구현이 제일 어려웠다. 첫 주사위 기준으로 동서남북을 잡아서 ..