넘치게 채우기

https://www.acmicpc.net/problem/15666BOJ - N과 M(12)문제 유형: DFS, 재귀, 백트래킹문제 난이도: Silver II시간 제한: 2초메모리 제한: 512MB 문제N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.N개의 자연수 중에서 M개를 고른 수열같은 수를 여러 번 골라도 된다.고른 수열은 비내림차순이어야 한다.길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다. 입력첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다. 출력한 줄에 하나씩 문..

https://leetcode.com/problems/find-kth-bit-in-nth-binary-string/description/leetcode - Find Kth Bit in Nth Binary String문제 유형: 비트 조작, 재귀, 문자열 처리문제 난이도: Medium 문제Given two positive integers n and k, the binary string Sn is formed as follows:S1 = "0"Si = Si - 1 + "1" + reverse(invert(Si - 1)) for i > 1Where + denotes the concatenation operation, reverse(x) returns the reversed string x, and invert..

https://www.acmicpc.net/problem/18405BOJ - 경쟁적 전염문제 유형: bfs, 그리디문제 난이도: Gold V시간 제한: 1초메모리 제한: 256MB 문제NxN 크기의 시험관이 있다. 시험관은 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 바이러스가 존재할 수 있다. 모든 바이러스는 1번부터 K번까지의 바이러스 종류 중 하나에 속한다.시험관에 존재하는 모든 바이러스는 1초마다 상, 하, 좌, 우의 방향으로 증식해 나간다. 단, 매 초마다 번호가 낮은 종류의 바이러스부터 먼저 증식한다. 또한 증식 과정에서 특정한 칸에 이미 어떠한 바이러스가 존재한다면, 그 곳에는 다른 바이러스가 들어갈 수 없다.시험관의 크기와 바이러스의 위치 정보가 주어졌을 때, S초가 지난 후에 (X,..

https://leetcode.com/problems/count-number-of-maximum-bitwise-or-subsets/description/leetcode - Count Number of Maximum Bitwise-OR Subsets문제 유형: dfs, 재귀, 브루트 포스, 백트래킹, 완전탐색, 비트마스킹문제 난이도: Medium 문제Given an integer array nums, find the maximum possible bitwise OR of a subset of nums and return the number of different non-empty subsets with the maximum bitwise OR.An array a is a subset of an array ..

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'...