알고리즘 공부 및 문제 풀이 (317) 썸네일형 리스트형 [c++] 백준 15649 N과 M (1) 백준 단계별로 풀어보기 [백트래킹] N과 M (1) https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net [풀이] dfs 완전 탐색 기법을 이용해서 풀 수 있는 백트래킹 문제이다. 1~n 까지의 자연수 중에서 길이가 m인 수열을 모두 구해 출력해야 하는데, visited[] bool 배열을 선언해 방문했는지 여부를 체크하고 방문하지 않았으면 list 배열에 해당 숫자를 저장한다. count가 m과 같아지면 m 길이의 수열을 만족하는 것이므로 출력을.. [c++] 백준 11047 동전 0 백준 단계별로 풀어보기 [그리디 알고리즘] 동전 0 https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net [풀이] n개의 종류의 동전을 적절히 이용해서 가치의 합이 k가 되게하는 최소 동전의 개수를 구하는 문제이다. 오름차순으로 동전의 가치값을 입력했고, 최소 개수를 구하기 위해서는 가장 큰 가치값부터 시작해서 k를 채워나가면 된다. 따라서 그리디 알고리즘에 해당하고, k / val[n.. [c++] 백준 11399 ATM 백준 단계별로 풀어보기 [그리디 알고리즘] ATM https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net [풀이] 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값은 Pi가 가장 작은 사람 순으로 돈을 인출할 때 구할 수 있다. 따라서 그리디 알고리즘이 적용되는 문제이므로 입력받은 Pi를 오름차순으로 정렬 후 누적합을 구하여 구할 수 있다. [코드] #include #include int main() { int num; std::cin >> num; int* wait_time .. [c++] 백준 1427 소트인사이드 백준 단계별로 풀어보기 [정렬] 소트인사이드 https://www.acmicpc.net/problem/1427 1427번: 소트인사이드 첫째 줄에 정렬하고자하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net [풀이] 입력받은 수 n을 쪼개 배열에 저장한 뒤 sort 함수를 이용해 정렬한다. 이때, 내림차순으로 정렬하기 위한 cmp 함수를 정의하여 sort 함수의 인자로 전달한다. [코드] #include #include bool cmp(const int& a, const int& b) { return a > b; } int main() { int n, cnt=0; std::cin >> n; int arr[10]; while (n != 0) { .. [c++] 백준 1436 영화감독 숌 백준 단계별로 풀어보기 [브루트 포스] 영화감독 숌 https://www.acmicpc.net/problem/1436 1436번: 영화감독 숌 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타 www.acmicpc.net [풀이] 시리즈에 들어가는 숫자는 666-1666-2666-3666-4666-5666-6660-6661 ... 와 같이 증가한다. 모든 수에 대하여 "666"이 들어가면 count 값을 증가시키고 count 값이 n과 일치할 때의 수를 출력해주면 된다. 이를 위해 숫자를 to_string을 통해서 문자열로 변환하고, find 함수를 이용하여 ".. [c++] 백준 3052 택시 기하학 백준 단계별로 풀어보기 [기본수학 2] 택시 기하학 https://www.acmicpc.net/problem/3053 3053번: 택시 기하학 첫째 줄에는 유클리드 기하학에서 반지름이 R인 원의 넓이를, 둘째 줄에는 택시 기하학에서 반지름이 R인 원의 넓이를 출력한다. 정답과의 오차는 0.0001까지 허용한다. www.acmicpc.net [풀이] 유클리드 기하학과 택시 기하학에서 두 점 사이의 거리에 대한 서로 다른 정의를 하고 있음을 이해해야한다. 문제 설명에서도 나와있듯이 택시 기하학은 두 점 (x1, y1), (x2, y2) 에 대해서 두 점 사이의 거리를 |x1-x2|+|y1-y2| 로 정의하고 있으므로 한 점에서 모두 같은 거리에 있는 점으로 이루어지는 원에 대해서도 유클리드 기하학에서 말하는.. [c++] 백준 1181 단어 정렬 백준 단계별로 풀어보기 [정렬] 단어 정렬 https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net [풀이] string을 저장하는 배열을 만들고, 길이가 짧은 순으로, 만약 길이가 같다면 사전 순으로 정렬한다. cmp 함수에 이와 같은 조건을 정해주고 sort 함수 세번째 인자로 전달해준다. 정렬 후 같은 단어가 있다면 한 번만 출력하도록 continue를 걸어준다. [코드] #include #include bool cmp(const std.. [c++] 백준 10814 나이순 정렬 백준 단계별로 풀어보기 [정렬] 나이순 정렬 https://www.acmicpc.net/problem/10814 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 www.acmicpc.net [풀이] 같은 조건인 경우(위 문제에서는 같은 나이) 입력된 순서대로 출력되는 정렬인 stable_sort를 사용한다. [코드] #include #include typedef struct { int age; std::string name; }Person; bool cmp(const Person& a, const Person& b) { return a.age .. 이전 1 ··· 35 36 37 38 39 40 다음