넘치게 채우기

https://www.acmicpc.net/problem/16964BOJ - DFS 스페셜 저지문제 유형: DFS/BFS문제 난이도: Gold III시간 제한: 2초메모리 제한: 512MB 문제BOJ에서 정답이 여러가지인 경우에는 스페셜 저지를 사용한다. 스페셜 저지는 유저가 출력한 답을 검증하는 코드를 통해서 정답 유무를 결정하는 방식이다. 오늘은 스페셜 저지 코드를 하나 만들어보려고 한다.정점의 개수가 N이고, 정점에 1부터 N까지 번호가 매겨져있는 양방향 그래프가 있을 때, DFS 알고리즘은 다음과 같은 형태로 이루어져 있다.void dfs(int x) { if (check[x] == true) { return; } check[x] = true; // x를 방문 ..

https://leetcode.com/problems/maximum-swap/description/leetcode - Maximum Swap문제 유형: 그리디, 수학문제 난이도: Medium 문제You are given an integer num. You can swap two digits at most once to get the maximum valued number.Return the maximum valued number you can get. 정수 num을 입력받습니다. 자릿수에서 두 개의 숫자를 바꿔서 최대값의 숫자로 변환할 수 있습니다.얻을 수 있는 최대값의 숫자를 출력하시오. 풀이브루트 포스 방법과, 인덱스를 이용한 방법이 있다.브루트 포스로는, 자릿수마다 다 한 번씩 스왑해보면서 최대 값..

https://www.acmicpc.net/problem/14501BOJ - 퇴사문제 유형: 다이나믹 프로그래밍문제 난이도: Silver III시간 제한: 2초메모리 제한: 512MB 문제상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다.각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.N = 7인 경우에 다음과 같은 상담 일정표를 보자.일자1일2일3일4일5일6일7일T_i3511242P_i1020102015402001일에 잡혀있는 ..

https://www.acmicpc.net/problem/3485BOJ - Play on Words문제 유형: 그래프 이론, 오일러 경로, 오일러 회로, dfs문제 난이도: Gold III시간 제한: 1초메모리 제한: 256MB 문제Some of the secret doors contain a very interesting word puzzle. The team of archaeologists has to solve it to open that doors. Because there is no other way to open the doors, the puzzle is very important for us.There is a large number of magnetic plates on every doo..

https://leetcode.com/problems/longest-happy-string/description/?envType=daily-question&envId=2024-10-16leetcode - Longest Happy String문제 유형: 우선순위 큐, 그리디문제 난이도: Medium 문제A string s is called happy if it satisfies the following conditions:s only contains the letters 'a', 'b', and 'c'.s does not contain any of "aaa", "bbb", or "ccc" as a substring.s contains at most a occurrences of the letter 'a'...

https://leetcode.com/problems/separate-black-and-white-balls/description/?envType=daily-question&envId=2024-10-15leetcode - Separate Black and White Balls문제 유형: 투 포인터, 그리디문제 난이도 : Medium 문제There are n balls on a table, each ball has a color black or white.You are given a 0-indexed binary string s of length n, where 1 and 0 represent black and white balls, respectively.In each step, you can choos..

https://www.acmicpc.net/problem/1629BOJ - 곱셈문제 유형: 수학, 재귀, 분할 정복문제 난이도: Silver I시간 제한: 0.5초메모리 제한: 128MB 문제자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오. 입력첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. 출력첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다. 풀이거듭제곱의 끝자리수 사이클을 이용하는 방법은 느리다.대신, 분할 정복을 이용하여 문제를 풀 수 있다.따로 dp테이블같은거에 저장할 필요는 없다.한 번 이외에 추가적인 인출 및 ..

https://leetcode.com/problems/maximal-score-after-applying-k-operations/description/?envType=daily-question&envId=2024-10-14leetcode - Maximal Score After Applying K Operations문제 유형: 우선순위 큐, 그리디문제 난이도: Medium 문제You are given a 0-indexed integer array nums and an integer k. You have a starting score of 0.In one operation:choose an index i such that 0 increase your score by nums[i], andreplace num..

https://www.acmicpc.net/problem/2206BOJ - 벽 부수고 이동하기문제 유형: bfs, 최단거리문제 난이도: Gold III시간 제한: 2초메모리 제한: 192MB 문제N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한..

https://leetcode.com/problems/smallest-range-covering-elements-from-k-lists/description/?envType=daily-question&envId=2024-10-13leetcode - Smallest Range Covering Elements from K Lists문제 유형: 정렬, 슬라이딩 윈도우문제 난이도: Hard 문제You have k lists of sorted integers in non-decreasing order. Find the smallest range that includes at least one number from each of the k lists.We define the range [a, b] is smalle..