본문 바로가기

Problem Solving/Baekjoon Online Judge (Gold)

 (70)
백준 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$로 바뀐 상태. 쿼리 ..
백준 20501 - Facebook (C++) 문제 문제 링크 BOJ 20501 - Facebook 문제 요약 $N$명의 친구 관계 정보가 주어진다. $Q$개의 쿼리에 대해 그에 맞는 답을 출력하자. 제한 TL : $1$ sec, ML : $1024$ MB $2 ≤ N ≤ 2,000$ $1 ≤ Q ≤ 500,000$ 알고리즘 분류 비트 집합(bit set) 비트마스킹(bitmask) 풀이 $B[2000][2000]$의 배열에 담아 쿼리 당 $N$번의 연산을 수행하면 $O(NQ)$로 시간 초과를 피할 수 없다. 친구 관계를 이진수로 간단히 표현할 수 있으므로 $B[2000][⌈2000 / 64⌉]$를 가지고 mask로 처리하면 $O(NQ / 64)$ 의 복잡도로 해결할 수 있다. 아래 코드는 직접 mask로 구현한 것과 C++ STL의 bitset 을..
백준 13701 - 중복 제거 (C++) 문제 문제 링크 BOJ 13701 - 중복 제거 문제 요약 $N$개의 수가 주어진다. 이들 중 반복되는 수를 제외하고 남은 수들을 모두 출력해보자. 제한 TL : $5$ sec, ML : $8$ MB $1 ≤ N ≤ 5,000,000$ $0 ≤ A_i < 2^{25}$ 알고리즘 분류 비트 집합(bit set) 비트 마스킹(bitmask) 풀이 메모리 제한과, 주어지는 수의 개수 및 범위가 아주 인상적인 문제이다. $⌈5,000,000 / 64⌉$ 개의 long long 변수를 가지고 mask를 해도 좋지만, C++ STL의 bitset을 이용하면 더욱 간단히 처리할 수 있다. 자세한 정보는 아래를 링크를 참고하자. std::bitset 전체 코드 1234567891011#includeusing names..

티스토리툴바