Chapter 08 - 다이나믹 프로그래밍(Dynamic programming) 1. 다이나믹 프로그래밍(동적 계획법) : 메모리 공간을 약간 더 사용하여 연산 속도를 비약적으로 증가시키는 방법 1) 피보나치 수열 - 다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예 n번째 피보나치 수 = (n-1)번째 피보나치수 + (n-2)번째 피보나치수 단, 1번째 피보나치수 = 1, 2번째 피보나치 수 = 2 ① 재귀 함수를 사용한 소스코드 int fibo(int x){ if(x==1 || x==2){ return 1; } return fibo(x-1)+fibo(x-2); } int main(){ cout n; for (int i = 0; i > x; arr.push_..
Algorithm
8979번: 올림픽 (acmicpc.net) 8979번: 올림픽 입력의 첫 줄은 국가의 수 N(1 ≤ N ≤ 1,000)과 등수를 알고 싶은 국가 K(1 ≤ K ≤ N)가 빈칸을 사이에 두고 주어진다. 각 국가는 1부터 N 사이의 정수로 표현된다. 이후 N개의 각 줄에는 차례대로 각 www.acmicpc.net 문제 : 올림픽 메달 순위 구하는 문제 해설 : 맨처음엔 배열로 해보다가 그냥 정렬하는게 낫겠다 싶어서 다중 페어벡터를 선언해서 정렬함수를 이용하여 정렬을 해줬다. 근데 순위가 같은 경우가 있어서 다중 반복문을 이용해 같은 걸 찾아주었다. #include #include #include using namespace std; int n, k, ans; vector v; bool op(const pa..
Chapter 03 - 그리디(Greedy) 1. 그리디 알고리즘(=탐욕법) : 현재 상황에서 지금 당장 좋은 것 만 고르는 방법 👉 매 순간 좋아 보이는 것만 선택 👉 현재의 선택이 나중에 미칠 영향에 대해 고려X 예제 3-1 ) 거스름돈(C++) Q . 손님에게 거슬러야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수? (동전은 500원, 100원, 50원, 10원이 있다) > 가장 큰 화폐 단위부터 돈을 거슬러 줘야 함 #include using namespace std; int n;//손님에게 받은 돈 int coin[4] = { 500, 100, 50, 10 }; int ans; //거스름돈의 개수 int main() { cin >> n; for (int i = 0; i < 4; i++) ..
https://www.acmicpc.net/problem/11140 11140번: LOL 당신 친구 지민이는 지금 할 일이 없다. 그리고 매우 심심하다. 그래서 쓸데없는 짓으로 시간을 때우려고 한다. 그래서 단어 하나가 주어질 때 단어에 'lol'이 들어가도록 글자를 추가하거나 변경 www.acmicpc.net 문제 설명 : LOL이 나올 수있는 여러 가짓수를 생각해서 조건문을 만드는 문제였다. L과 L사이에 알파벳 하나가 왔을 때 결과값이 1이 나와야 되는 경우 때문에 정규표현식을 이용하려고했는데 다까먹어서 엄청 헤맸다...저게 맞는지도 모르겠음 정답이라고 떴으니까 맞는거겠지 코드 : #include #include #include using namespace std; int main() { int t..
코딩테스트 연습 - 문자열 다루기 기본 | 프로그래머스 (programmers.co.kr) 코딩테스트 연습 - 문자열 다루기 기본 문자열 s의 길이가 4 혹은 6이고, 숫자로만 구성돼있는지 확인해주는 함수, solution을 완성하세요. 예를 들어 s가 "a234"이면 False를 리턴하고 "1234"라면 True를 리턴하면 됩니다. 제한 사항 s는 길이 1 programmers.co.kr ⚠ 조심할사항! 문자열 s의 길이가 4또는 6인걸 체크하는 것이 필요..!!! 문제 꼼꼼히 보자~~ #include #include using namespace std; bool solution(string s) { bool answer = true; for (int i = 0; i < s.size(); i++) { ..
코딩테스트 연습 - 4주차 | 프로그래머스 (programmers.co.kr) 코딩테스트 연습 - 4주차 개발자가 사용하는 언어와 언어 선호도를 입력하면 그에 맞는 직업군을 추천해주는 알고리즘을 개발하려고 합니다. 아래 표는 5개 직업군 별로 많이 사용하는 5개 언어에 직업군 언어 점수를 부 programmers.co.kr 1. 문제 설명 첫번째 매개변수로 배열로 각 직업군 마다의 언어점수가 주어진다. [ "SI JAVA JAVASCRIPT SQL PYTHON C#", "CONTENTS JAVASCRIPT JAVA PYTHON SQL C++", "HARDWARE C C++ PYTHON JAVA JAVASCRIPT", "PORTAL JAVA JAVASCRIPT PYTHON KOTLIN PHP", "GAME..
코딩테스트 연습 - 두 개 뽑아서 더하기 | 프로그래머스 (programmers.co.kr) 코딩테스트 연습 - 두 개 뽑아서 더하기 정수 배열 numbers가 주어집니다. numbers에서 서로 다른 인덱스에 있는 두 개의 수를 뽑아 더해서 만들 수 있는 모든 수를 배열에 오름차순으로 담아 return 하도록 solution 함수를 완성해주세요. 제한 programmers.co.kr 🔎 풀이 과정 answer벡터에 모든 더한값을 push하고, 정렬한다. 그 후 중복을 제거해준다. => [C++] vector 배열 중복 제거 하는 법 (tistory.com) #include #include #include using namespace std; vector solution(vector numbers) { ..
코딩테스트 연습 - 약수의 개수와 덧셈 | 프로그래머스 (programmers.co.kr) 코딩테스트 연습 - 약수의 개수와 덧셈 두 정수 left와 right가 매개변수로 주어집니다. left부터 right까지의 모든 수들 중에서, 약수의 개수가 짝수인 수는 더하고, 약수의 개수가 홀수인 수는 뺀 수를 return 하도록 solution 함수를 완성해주 programmers.co.kr 🔎 문제 설명 left부터 right까지 약수의 개수가 짝수면 더하고 홀수면 빼는 방식 🔎 풀이 과정 함수하나를 만들어서 약수의 개수가 짝수면 x를 리턴하고, 홀수면 -x를 리턴하게 했다. 약수의 개수는 1부터 x까지 나머지가 0인 것을 카운트해주면 된다. #include #include using namespace st..
코딩테스트 연습 - 내적 | 프로그래머스 (programmers.co.kr) 코딩테스트 연습 - 내적 길이가 같은 두 1차원 정수 배열 a, b가 매개변수로 주어집니다. a와 b의 내적을 return 하도록 solution 함수를 완성해주세요. 이때, a와 b의 내적은 a[0]*b[0] + a[1]*b[1] + ... + a[n-1]*b[n-1] 입니다. (n은 a, b의 programmers.co.kr 쉬워서 설명 생략 #include #include using namespace std; int solution(vector a, vector b) { int answer = 0; for(int i=0; i< a.size(); i++){ answer += a[i]*b[i]; } return answer; }
