끄적끄적

출처 : https://www.acmicpc.net/problem/13164 13164번: 행복 유치원 입력의 첫 줄에는 유치원에 있는 원생의 수를 나타내는 자연수 N(1 ≤ N ≤ 300,000)과 나누려고 하는 조의 개수를 나타내는 자연수 K(1 ≤ K ≤ N)가 공백으로 구분되어 주어진다. 다음 줄에는 원생들 www.acmicpc.net 그리디 티셔츠 만드는 비용이 최소가 되도록 K개의 조로 나누었을 때, 티셔츠 만드는 비용을 구해야하는 문제이다. 우선 키 순서대로 줄을 세웠다고 했으므로 정렬을 해줌 그 다음 인접 원소간의 차이를 각각 구해주고, 이를 정렬해줌 K개의 조가 있다고 하면 K-1개의 경계가 있을 것인데 비용을 최소로 한다고 했기 때문에 차이가 큰 K-1개를 제외하고 더해주면 티셔츠 만드..

출처 : https://www.acmicpc.net/problem/1052 1052번: 물병 지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번 www.acmicpc.net 그리디 water() 함수를 통해 N을 2로 계속 나눠가면서 나머지가 있으면 cnt(ex)N=5일 때 합쳐지고 난 후의 물병 개수)를 ++해준다. 나머지가 있다는 건 남게되는 물병이 있다는 뜻이기 때문 함수를 실행하고 난 후 생기는 물병의 개수가 K개 이하이면 while문을 탈출하면 되고 K개 초과이면 상점에서 물병을 하나 더 사야한다는 의미이므로 total++(상점에서 사야하는 물병의 최솟값..

출처 : https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 그리디 + 우선순위큐 주어진 숫자들을 우선순위큐에 넣고 오름차순 정렬하여 차례대로 뽑아주면서 더해주면 된다. 그래야 작은수부터 나오니까 최소 비교 횟수를 구할 수 있음. 우선순위큐 오름차순 정렬(default는 내림차순) -> priority_queue pq; * priority_queue는 힙으로 구현할 수 있다.

출처 : https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 백트래킹 -> 재귀, 가지치기 백트래킹을 사용하는 알고리즘 중 대표적인 예로 DFS가 있다. void dfs(int pos, int prev, int consonant, int vowel) 여기서 pos와 prev가 각각 필요한 이유 pos는 암호 알파벳이 적혀야 하는 위치를 나타내고, prev는 주어진 문자열에서 탐색을 시작해야하는 위치를 나타냄. 배열을 sort하는 방법 : sort(배열 ..

출처 : https://www.acmicpc.net/problem/14495 14495번: 피보나치 비스무리한 수열 피보나치 비스무리한 수열은 f(n) = f(n-1) + f(n-3)인 수열이다. f(1) = f(2) = f(3) = 1이며 피보나치 비스무리한 수열을 나열하면 다음과 같다. 1, 1, 1, 2, 3, 4, 6, 9, 13, 19, ... 자연수 n을 입력받아 n번째 피보 www.acmicpc.net dp 점화식은 문제에서 주어졌으니 그대로 쓰면 되고, dp[116]이면 int 범위를 넘어서기 때문에 long long을 사용해야 한다.

출처 : https://www.acmicpc.net/problem/1965 1965번: 상자넣기 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 www.acmicpc.net LIS(Longest Increasing Subsequence, 최장 증가 수열)와 DP를 동시에 이용하는 문제 (LIS를 구하는 방법 중 하나가 DP라고 한다.) - LIS란? 원소가 n개인 배열이 주어졌을 때, 이 배열의 원소를 뽑아 만든 부분 수열 중, 각 원소가 이전 원소보다 크며, 그 길이가 최대인 부분 수열을 의미한다. ex) {6,2,5,1,7,4,8,3} 의 LIS -> {2,5,7..

출처 : https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net dp 이미 저장되어 있는 값과(현재 날짜에서 상담을 하지 않는 경우), 현재 날짜에서 상담을 하여 저장되는 값 중 큰 값을 저장해주면 된다. cur_max 변수를 사용한 이유 -> 예를 들어 7일에 저장된 값이 60이고 그 값이 그대로 간다면 8일에 저장된 값도 60이어야 하는데, 초기값은 0이니까 대입해주는 작업 필요해서 cur_max 변수를 사용한 것

출처 : https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net bfs 각 칸에 사다리 혹은 뱀이 있을 경우 도착 좌표를 적고, 나머지는 0으로 하여 구별한다. 주사위가 1일때 부터 6일때까지 반복해주고 현재 좌표에 더해서 다음 좌표를 만든다. 다음 좌표가 100일 경우 카운트에 +1해서 출력해준다. 만약 100보다 작을 경우 먼저 다음 좌표에 사다리 혹은 뱀인지 확인해서 0이 아닌 경우 적혀있는 값으로 ..