Algorithm 검색 결과

해당 글 214건

[백준] 알고리즘 3-1일차 다이나믹 프로그래밍

1. 11726번 : 2 x n 타일링 문제 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 2xn 타일링 문제는 큰 문제에서 작은문제로 어떻게 만들것인가가 중요한데, 오른쪽 끝에 타일을 붙여서 모양을 만든다고 생각하면 가로가 1인경우와 2인경우로 나눌 수 있다. 즉 오른쪽에 가로가 1인 타일을 붙이면 총 가로가 N일때, 남은 부분은 N-1의 크기가된다. 마찬가지로 2로 N-2가 된다. 점화식을 주석에 있는 것처럼 세워준후 문제를 해결한다. #include #include using namespace std; int dp[1001]..
Algorithm/정리 2021. 8. 7. 18:10

[백준] 알고리즘 3일차 다이나믹 프로그래밍

큰 문제를 작은 문제로 나눠서 푸는 알고리즘 1. 겹치는 작은 문제 ex) 피보나치 수 Fn = Fn-1 + Fn-2 - 큰 문제와 작은 문제를 같은 방법으로 풀 수 있다. - 문제를 작은 문제로 쪼갤 수 있다. 큰문제 = 작은 문제 2. 최적 부분 구조 - 문제의 정답을 작은 문제의 정답에서 구할 수 있다. - 문제의 크기에 상관없이 어떤 한 문제의 정답은 일정하다. 즉 다이나믹 프로그래밍은 두 가지를 만족한다. - 2를 만족하기에 같은 문제는 구할 때마다 정답이 같다. - 정답을 구했으면 배열에 저장한다. - 메모하는 부분을 메모제이션이라고 한다. - 모든 문제를 풀어야 한다. - 모든 문제는 1번만 풀어야 한다. 방법 문제를 푸는데 필요한 재귀식인 점화식을 구해야한다. 문제를 작게 만드는 방법을 찾..
Algorithm/정리 2021. 8. 7. 14:39

[백준] 알고리즘 1182번 - 부분수열의 합문제

문제 https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 소스코드 #include #include using namespace std; int n, s,ans=0; vector v; void go(int index, int sum) { if (index == n) return; if (sum + v[index] == s) { ans++; } go(index + 1, sum); go(index + 1, sum + ..
Algorithm/brute force 2021. 6. 11. 19:32

[백준] 알고리즘 10971번 - 외판원 순회 2문제

문제 https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 소스코드 #include #include using namespace std; int arr[11][11]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n; cin >> n; vector v(n); for (int i = 0; i < n; i++..
Algorithm/brute force 2021. 6. 10. 18:41

[백준] 알고리즘 10819번 - 차이를 최대로문제

문제 https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 소스코드 #include #include using namespace std; vector v; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n; cin >> n; for (int i = 0; i > x; v.push_back(x); } sort(v.begin()..
Algorithm/brute force 2021. 6. 10. 17:43

[프로그래머스] LV1 - 신규 아이디 추천문제

문제 https://programmers.co.kr/learn/courses/30/lessons/72410 코딩테스트 연습 - 신규 아이디 추천 카카오에 입사한 신입 개발자 네오는 "카카오계정개발팀"에 배치되어, 카카오 서비스에 가입하는 유저들의 아이디를 생성하는 업무를 담당하게 되었습니다. "네오"에게 주어진 첫 업무는 새로 programmers.co.kr 소스코드 #include #include using namespace std; string solution(string new_id) { for (int i = 0; i < new_id.size(); i++) { if ('A'
Algorithm/programmers 2021. 6. 10. 15:40

[프로그래머스] LV1 - 음양 더하기문제

문제 https://programmers.co.kr/learn/courses/30/lessons/76501 코딩테스트 연습 - 음양 더하기 어떤 정수들이 있습니다. 이 정수들의 절댓값을 차례대로 담은 정수 배열 absolutes와 이 정수들의 부호를 차례대로 담은 불리언 배열 signs가 매개변수로 주어집니다. 실제 정수들의 합을 구하여 re programmers.co.kr 소스코드 #include #include using namespace std; int solution(vector absolutes, vector signs) { int answer=0; for(int i=0;i
Algorithm/programmers 2021. 6. 10. 15:30

[코테정리] C++ vector 기법

vector 요소의 중복 값 제거 sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end()); 1. 정렬을 한다. 2. 연속된 숫자를 쓰레기 값 즉 벡터의 뒷부분으로 보낸다. (unique) 3. 중복된 요소가 모여있는 부분들을 삭제한다.(erase) vector 최댓값 최솟값 인덱스 구하기 int max=*max_element(v.begin(),v.end()); int min=*min_element(v.begin(),v.end()); int max_index=max_element(v.begin(),v.end())-v.begin(); int min_index=min_element(v.begin(),v.end())-v.begin();
Algorithm/코테정리 2021. 6. 7. 22:42