성장하는 서버 개발자 도라프의 블로그 성장하는 서버 개발자 도라프의 블로그

https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 문제 요약 민규가 N장의 카드를 사려고 하고 1,2,3,...N 장의 카드팩 가격이 주어진다. 민규는 가장 많은 돈을 지불하여 N장의 카드를 살 것이다. 카드팩의 조합으로 민규가 지불하게 될 돈을 구해라 풀이 민규가 각 카드를 사용하는 방법은 다음과 같다. 1. 그 카드로만 지불한다. 2. 카드와 다른 카드를 합쳐서 지불한다. 2장의 카드를 구매한다고 가정해보자. 2장의 카드는 2장 카드팩을 구매하는 경..

https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 문제 요약 길이가 N인 오르막의 수를 10007로 나눈 나머지 출력 풀이 길이가 2인 오르막 수를 구하는데 마지막 숫자가 9인 것을 생각해보면, 09,19,29,...99 까지 세어준다. 그런데 09,19,...89까지의 개수는 마지막 숫자가 8의 갯수와 똑같다. 따라서 점화식은 dp[i][n] = dp[i-1][n] + dp[i][n-1] 이 되어야 한다. 위..

DFS : 깊이 우선 탐색 그래프 전체를 탐색하는 방법 중 하나. 시작점부터 다음 branch로 넘어가기 전에 해당 branch를 완벽하게 탐색하고 넘어가는 방법. 스택이나 재귀함수를 사용하여 구현(코딩테스트에서는 보통 재귀를 사용) 재귀함수로 사용하여도 시스템 스택에 쌓이게 되므로 스택이라고 생각할 수 있다. 시작 정점의 한 방향으로 갈 수 있는 곳 까지 깊이 탐색한다.(가면서 지나가는 것들을 하나씩 담는다) 가다가 더 이상 갈 곳이 없으면 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아온다. 다른 방향의 정점으로 탐색을 계속 반복하며 결국 모든 정점을 방문한다. 가장 마지막에 만났던 갈림길의 정점으로 되돌아가서 다시 깊이 우선 탐색을 반복해야하므로 후입 선출 구조의 스택을 사용한다. 알고리즘 시작..

문제 출처 : https://www.acmicpc.net/problem/9084 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net 문제 우리나라 화페, 특히 동전의 단위로는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. (1원짜리 30개) 또는 (10원짜리 2개와 5원짜리 2개) 등의 방법이 가능하다. 동전의 종류가 주어질 때에 주어진 금액을 만드는 모든 방법을 세는 프로그램 작성 입력 t : 테스..

Map, Hash_Map 톺아보기 1.1 시퀀스 컨테이너와 연관 컨테이너 STL 컨테이너는 크게 시퀀스 컨테이너와 연관 컨테이너로 나눈다. 시퀀스 컨테이너는 vector, list, deque와 같이 순서 있게 자료를 보관한다. 연관 컨테이너는 어떠한 Key와 짝을 이루어 자료를 보관한다. 그래서 자료를 넣거나 빼고 찾을 때는 Key가 필요하다. 1.2 연관 컨테이너 연관 컨테이너로 map, set, hash_map, hash_set이 있다. 이것들은 Key로 사용하는 값이 중복되지 않은 때 사용한다. 만약 중복되는 key를 사용할 때는 컨테이너 앞에 "multi"를 붙인 multi_map, multi_set, hash_multimap, hash_multiset을 사용한다. 1.2.1. map, set과..

다이나믹 프로그래밍(Dynamic Programming, DP) 여러개의 하위 문제를 푼 후 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘 하나의 문제는 단 한 번만 풀도록 하는 알고리즘 ex) 분할 정복 기법으로 피보나치 수열을 구현한다고 생각해보자. 피보나치 수열에서 f(4)를 계산할 때 f(2)를 중복 계산하는 비효율이 발생한다. 다이나믹 프로그래밍은 다음의 가정 하에 사용할 수 있다. 1. 큰 문제를 작은 문제로 나눌 수 있다. 2. 작은 문제에서 구한 정답은 그것을 포함하고 있는 큰 문제에서도 동일하다. 메모이제이션 사용. 메모이제이션이란? 이미 계산한 결과는 배열에 저장함으로서 나중에 동일한 계산을 해야 할 때는 저장된 값을 단순히 반환하기만 하면된다. ex) 다이나믹 프로그래밍(동적 계..

다이나믹 프로그래밍 문제집에 속한 문제를 풀고있습니다 참고: https://www.acmicpc.net/workbook/view/7319 문제집: 0x10강 - 다이나믹 프로그래밍 (BaaaaaaaaaaarkingDog) www.acmicpc.net 문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 시간제한: 1초 풀이 A(n) - A(n-1), 즉 n-1을 만드는 모든 경우 각각에 대해 그 뒤에 1을 더하는 것과 - A(n-2), 즉 n-2를 만드는 모든 경..

https://school.programmers.co.kr/learn/courses/30/lessons/42862 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr lost와 reserve를 문자열로 배열을 받고 그것을 vector에 push 해줘야 한다. 문자열을 받아서 숫자인지 확인하는 방법 if (lost_arr[i] != ',') { lost.push_back(lost_arr[i]); } 여분이 있는 학생한테 옷을 빌리면 그 학생은 더 이상 옷을 빌려줄 수 없으므로 여분이 있는 학생에서 제외해야한다. erase(remove(v.begin(),v.end..