전체 글63 [C++] 그래프 표현 본 게시글은 "Competitive Programmer's Handbook"을 보며 임의로 해석하며 공부한 내용입니다. 알고리즘에서 그래프를 나타내는 몇가지 방법이 있다. 데이터 구조의 선택은 그래프 사이즈와 알고리즘이 동작하는 방법에 달려있다. 1. 인접 리스트 표현 - 노드 x개, 엣지 x개 그래프의 각 노드 x에는 x의 엣지가 있는 노드로 구성된 인접 리스트가 할당된다. 인접 리스트를 설계하는 방법은 벡터의 배열을 선언하는 것이다. vector adj[N]; 예를 들어, 아래의 그래프는 다음과 같이 설계할 수 있다. adj[1].push_back(2);// 1 > 2 adj[2].push_back(3); // 2 > 3 adj[2].push_back(4);// 2 > 4 adj[3].push_bac.. 2021. 7. 19. [BOJ/백준] 1904번 - 01타일 단계별로 풀어보기 > 동적 계획법 1 > [3단계] 1904번 문제 링크 : https://www.acmicpc.net/problem/1904 문제 요약 1. 주어진 문제에 대한 규칙을 찾아 점화식을 세운다. 입력 복사 예제 입력 1 >> 출력 : 5 4 CODE #include using namespace std; #define ll long long #define mod 15746 const int mxN=1e7; ll term[mxN+1]; ll dp(int n) { if(n==1) return 1; if(n==2) return 2; if(term[n]!=0) return term[n]%mod; else { term[n] = dp(n-1) + dp(n-2); return term[n]%mod; } .. 2021. 7. 11. [BOJ/백준] 9461번 - 파도 단계별로 풀어보기 > 동적 계획법 1 > [4단계] 9461번 문제 링크 : https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 문제 요약 1. 주어진 문제에 대한 규칙을 찾아 점화식을 세운다. 입력 복사 예제 입력 1 >> 출력 : 3 16 2 6 12 CODE #include using namespace std; long long term[1000]; long long dp(int n) { if(n == 0 or n == 1 or n == 2) re.. 2021. 7. 9. [BOJ/백준] 11399번 - ATM 단계별로 풀어보기 > 그리디 알고리즘 > [3단계] 11399번 문제 링크 : https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 문제 요약 1. 주어진 수에 대한 합의 최솟값을 구하기 위한 방법을 생각한다. 입력 복사 예제 입력 1 >> 출력 : 32 5 3 1 4 3 2 CODE #include using namespace std; #define endl "\n" int main() { int n; cin >> n; int t[1000]; for(int i=1; i> t[i.. 2021. 7. 2. [BOJ/백준] 1931번 - 회의실 배정 단계별로 풀어보기 > 그리디 알고리즘 > [2단계] 1931번 문제 링크 : https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 문제 요약 1. 그리디 알고리즘을 사용하는 대표적인 스케쥴 문제 입력 복사 예제 입력 1 >> 출력 : 4 11 1 4 3 5 0 6 5 7 3 8 5 9 6 10 8 11 8 12 2 13 12 14 CODE #include using namespace std; #define endl "\n" #define pb push_back #define mp make_pair typedef pair p; vector v; bool cmp(p a.. 2021. 7. 2. [BOJ/백준] 11047번 - 동전 0 단계별로 풀어보기 > 그리디 알고리즘 > [1단계] 11047번 문제 링크 : 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 문제 요약 1. 그리디 알고리즘을 사용하는 대표적인 동전 문제 입력 복사 예제 입력 1 >> 출력 : 6 10 4200 1 5 10 50 100 500 1000 5000 10000 50000 예제 입력 2 >> 출력 : 12 10 4790 1 5 10 50.. 2021. 6. 25. 이전 1 2 3 4 5 6 7 ··· 11 다음 728x90 반응형
