본문 바로가기

분류 전체보기

 (145)
백준 25620 - 슬라임 키우기 (C++) 문제 문제 링크 BOJ 25620 - 슬라임 키우기 문제 요약 $N$마리 슬라임의 크기와 $Q$개의 업데이트 쿼리가 주어진다. 모든 쿼리의 적용이 끝난 후 최종 슬라임들의 상태를 출력해보자. 제한 TL : $2$ sec, ML : $1024$ MB $1 ≤ N, Q ≤ 200 000$ $0 ≤ N_i, x_i, y_i ≤ 10^9$ 알고리즘 분류 자료 구조(data structures) 우선순위 큐(priority_queue) 수학(math) 정수론(number_theory) 풀이 간단하면서도 재밌는 관찰이 필요한 문제였다. 우선 항상 최솟값 ~ $x$의 범위를 빠르게 추려내야 하므로 최솟값 우선순위 큐를 떠올려볼 수 있다. 이제 범위를 보면, $0 ≤ N_i, x_i, y_i ≤ 10^9$ 이고 각 쿼..
백준 2014 - 소수의 곱 (C++) 문제 문제 링크 BOJ 2014 - 소수의 곱 문제 요약 $K$개의 소수에서 몇 개의 소수들을 곱하여 나열할 수 있다. 이 수열의 $N$번째 수를 구해보자. 제한 TL : $2$ sec, ML : $128$ MB $1 ≤ K ≤ 100$ $1 ≤ N ≤ 100,000$ 알고리즘 분류 자료 구조(data structures) 우선순위 큐(priority_queue) 수학(math) 정수론(number_theory) 풀이 우선순위 큐를 활용하는, 웰노운스러운 문제다. 매 사이클마다 가장 작은 수( $Q.top()$ )를 가지고 입력받은 수들과 곱해주면 된다. 그렇게 뚝딱 짜고 냈더니 처음에 $MLE$ 를 한 번 맞았다. 저번에 비슷한 문제를 풀었을 땐 $K ≤ 10$ 에 $N ≤ 200,000$ 의 상한이어..
백준 23835 - 어떤 우유의 배달목록 (Easy) (C++) 문제 문제 링크 BOJ 23835 - 어떤 우유의 배달목록 (Easy) 문제 요약 $N$개의 정점으로 이루어진 트리가 주어진다. $Q$개의 쿼리를 적절히 처리해보자. 제한 TL : $1$ sec, ML : $512$ MB $1 ≤ N, Q ≤ 1,000$ 알고리즘 분류 그래프 이론(graphs) 그래프 탐색(graph_traversal) 트리(trees) 깊이 우선 탐색(dfs) 풀이 범위를 보면, $Eazy$ 버전 답게 굉장히 작다. 그냥 쿼리마다 $dfs$를 돌려 $O(QN)$의 복잡도를 가져도 널널해 보인다. $Hard$ 버전은 딱봐도 $hld$ + 세그먼트 트리일 듯 한데, 구간에 등차수열을 더하는 문제인 이 문제 를 트리 위에서 진행 한다고 생각하면 될 것 같다. 조만간 도전해 봐야지.. 전체 ..
백준 16934 - 게임 닉네임 (C++) 문제 문제 링크 BOJ 16934 - 게임 닉네임 문제 요약 문제에 정의된 별칭 규칙에 따라 $N$명의 유저의 별칭을 찾아주자. 제한 TL : $2$ sec, ML : $512$ MB $1 ≤ N ≤ 100,000$ 닉네임은 알파벳 소문자로만 이루어져 있고, 길이는 $10$을 넘지 않는다. 알고리즘 분류 자료 구조(data structures) 문자열(string) 해시를 사용한 집합과 맵(hash _ set / map) 풀이 굳이 트라이를 써먹지 않아도 해쉬 셋과 맵만으로 더욱 간단하고 효율적으로 풀이할 수 있다. 먼저 $N_i$번째 닉네임이 주어지면 $[1, 1], [1, 2], ... [1, n]$ 단위로 잘라보며 별칭이 될 수 있는지 확인한다. 만약 별칭이 될 수 있는 순간이 온다면 그 순간의 문..
백준 27925 - 인덕션 (C++) 문제 문제 링크 BOJ 27925 - 인덕션 문제 요약 $3$개의 인덕션의 온도 이동을 적절히 분배해 모든 요리를 완성하는 최솟값을 구해보자. 제한 TL : $2$ sec, ML : $1024$ MB $1 ≤ N ≤ 5,000$ $0 ≤ t_i ≤ 9$ 알고리즘 분류 다이나믹 프로그래밍(dp) 풀이 고려해야 할 상태는 결국 네 가지( 몇번째 음식 ? 현재 인덕션들 각각의 온도? ) 로 귀결된다. 이에 따라 다음과 같이 정의를 내려보자. $dp[i][x][y][z]$ : $i$번째 음식까지 요리했고, 각 인덕션의 온도 상태가 $x, y, z$일 때 답. 임의의 인덕션 $x_i$의 시점에서 $a[i + 1]$로 이동하기 위한 루트는 $+$ 방향으로 이동하거나 $-$ 방향으로 이동 하거나 둘 중 하나다. 구체..
백준 27397 - 문자열 변환과 쿼리 2 (C++) 문제 문제 링크 BOJ 27397 - 문자열 변환과 쿼리 2 문제 요약 문자열 $S$가 주어진다. $N$개의 쿼리에 대해 그에 맞는 처리를 해보자. 제한 TL : $3$ sec, ML : $512$ MB $1 ≤ len(S) ≤ 300,000$ $1 ≤ N ≤ 300,000$ $1 ≤$ $len(S)$ $*$ $count(n_2)$ $≤ 10^7$ 알고리즘 분류 자료 구조(data structures) 문자열(string) 해시를 사용한 집합과 맵(hash _ set / map) 풀이 문자열 변환과 쿼리 $1$ 과 별반 다를 게 없다. 쿼리 내용 그대로 이번엔 최대 연속 구간을 세주면 되겠다. 이 역시 세번째 제한으로 인해 복잡도가 보장된다. 전체 코드 1234567891011121314151617181..
백준 27396 - 문자열 변환과 쿼리 (C++) 문제 문제 링크 BOJ 27396 - 문자열 변환과 쿼리 문제 요약 문자열 $S$가 주어진다. $N$개의 쿼리에 대해 그에 맞는 처리를 해보자. 제한 TL : $3$ sec, ML : $512$ MB $1 ≤ len(S) ≤ 100,000$ $1 ≤ N ≤ 300,000$ $1 ≤$ 유형 $2$로 출력되는 문자의 총 수 $≤ 10^7$ 알고리즘 분류 자료 구조(data structures) 문자열(string) 해시를 사용한 집합과 맵(hash _ set / map) 풀이 쿼리 1에서 $S$를 돌아보며 일일히 바꿔주고 있으면 당연히 $TLE$ 다. 등장하는 문자가 알파벳으로 한정됨에 따라 이에 맞는 카운트 배열을 만들어 주자. $M[x] = y$ : 문자 $x$가, 현재 문자 $y$로 바뀐 상태. 쿼리 ..
백준 16587 - Hierarchical Structure (C++) 문제 문제 링크 BOJ 16587 - Hierarchical Structure 문제 요약 $N$개의 정점으로 이루어진 트리가 주어진다. $Q$개의 경로 쿼리에 대해 알맞는 답을 출력하자. 제한 TL : $3$ sec, ML : $512$ MB $1 ≤ N, Q ≤ 100,000$ $1 ≤ A_i ≤ 10^9$ 알고리즘 분류 자료 구조(data structures) 트리(trees) heavy-light 분할(heavy-light decomposition) 세그먼트 트리(segment tree) 머지 소트 트리(merge sort tree) 정렬(sorting) 누적 합(prefix sum) 이분 탐색(binary search) 풀이 쿼리의 내용을 정리하면 다음과 같이 생각할 수 있다. 두 정점을 잇는 경..

티스토리툴바