끄적끄적

출처 : https://www.acmicpc.net/problem/2075 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 우선순위 큐 맨 처음에 그냥 sort 사용해서 풀었는데, 메모리 초과 오류가 나서 우선순위큐 이용해서 품

출처 : https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 그리디 AAA = 100A + 10A + A 의 방식으로 접근한다. GCF ACDEB 이 경우에는 G=100 C=10 + 1000 = 1010 F=1 A=10000 D=100 E=10 B=1 이렇게 구한 다음 내림차순으로 정렬한 후에 큰 숫자부터 9.8.7.6 순으로 대입시켜줌 10000(9), 1010(8), 100(7), 100(6), 10(5), 1(4), 1(3) 어차피 다같..

출처 : https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 그리디 시작하는 시간이 빨라도 늦게 끝나면 최대 회의 수를 구할 수 없기 때문에 종료시간을 기준으로 정렬해야한다. 종료시간이 가장 빠른 회의의 종료시간을 맨 처음에 넣어주고 정렬된 스케줄을 보며 그다음 시작 시간이 지금 cur에 담긴 종료시간보다 크거나 같은지 비교해주며 진행

출처 : 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을 사용해야 한다.