백준 1 문제 1. BOJ 5339 콜센터 - B5 설명은 귀여운 C3PO로 대체함. /~\ ( oo| _\=/_ / _ \ //|/.\|\\ || \ / || ============ | | | | | | [랜덤디펜스] 0. BOJ 23257 비트코인은 신이고 나는 무적이다 - G3 -> Fail. 배낭 문제인지 아니면 Bitmasking + DFS 인지가 계속 헷갈렸는데, 배낭 문제였다. 47분 정도 고민하다가 GG친 문제. 내일 일어나서 다시 한 번 봐야겠다. 오늘 일지는 여기서 끝.

백준 3 문제 1. BOJ 4999 아! - B5 문자열 비교 문제. 그냥 길이끼리 비교하면 되는 문제였다. 스트릭 유지용으로 푼 문제. [업다운 랜덤디펜스] (다시 시작) 태그는 기하학만 빼고 진행, 100명 이상 푼 문제를 1시간 내로 푸는 것을 목표로 하고 G5부터 시작. 2. BOJ 12025 장난꾸러기 영훈 - G5 (Solved - 08: 24) 비트마스킹 문제. 1,2,6,7만 바뀌는데 위치가 제일 뒤에 있는 순서부터 바꿀지 말지를 결정하면 된다. 그런데 홀수면 항상 맨 뒤의 1,2,6,7은 6 아니면 7로 바뀌어야 하고, 4의 배수는 아니나 2의 배수면 맨 뒤에서 두 번째가 바뀌어야 하고 ... 이러한 규칙성 때문에 그냥 K를 2로 나눈 나머지를 보고 2로 계속 나눠서 구하면 된다. 그래서..

백준 2 문제 1. BOJ 14289 본대 산책 3 - G1 분할정복을 활용한 거듭제곱 + 그래프 이론 문제. 인접행렬을 k번 거듭제곱하면 각 adj[i][j]마다 k번 이동했을 때에 i -> j로 가는 경우의 수임을 알면 쉽게 풀 수 있다. 증명도 생각해보면 어렵지 않게 가능해서 좋아하는 문제 유형이다. 2. BOJ 2485 가로수 - S4 유클리드 호제법 문제. 가로수 간의 거리를 동일하게 쪼갤 수 있는 거리 중에 최댓값을 찾고 싶으므로 결국에는 가로수 간의 거리들의 GCD를 찾으면 된다. 이를 유클리드 호제법이나 C++ 내장 함수 중 __gcd(a,b) 함수로 빠르게 찾을 수 있다. 질문게시판 기웃거리다가 찾은 담백한 실버 수학 문제. 오늘 일지는 여기서 끝.

https://www.acmicpc.net/problem/3018 3018번: 캠프파이어 첫째 줄에 MT에 참가한 사람의 수 N이 주어진다. (1 ≤ N ≤ 100) 사람들은 1부터 N까지 번호가 매겨져 있으며, 선영이의 번호는 1이다. 둘째 줄에는 E가 주어진다. (1 ≤ E ≤ 50) 다음 E개 줄에는 그날 www.acmicpc.net 문제의 조건을 요약하면 아래와 같습니다. 1. E일간 캠프파이어가 진행됩니다. 2. 선영이가 캠프파이어 참여하는 날에는 새로운 노래가 하나 만들어집니다. 그 날에는 사람들은 서로 노래들을 공유 안하고 그 노래만 부릅니다. 3. 선영이가 캠프파이어에 참여하지 않는 날에는 캠프파이어 하는 사람들끼리 본인들이 알고있는 노래들을 모두 공유합니다. 4. 문제에서는 선영이를 포함..

백준 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!!!