BOJ 썸네일형 리스트형 백준 11403 / 경로 찾기 말 그대로 경로를 찾는 문제다. 진짜 기초적인 그래프 문제 DFS와 BFS를 사용하여 풀 수 있다. DFS 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980#include #include #include #include #include using namespace std; int d[101];int ans[101][101];int arr[101][101];int n;vector a; void check(int num, int now) { for (int i = 0; i > n; for .. 백준 1012 / 유기농 배추 BFS를 이용한 가장 기본적인 문제기 때문에 나중에 한번 더 풀어봐야 겠다. BFS문제 배추가 있는 곳을 큐에 넣지말고 맵을 서치하면서 하나씩 큐에 넣고 인접한 것들에 서치값을 -1로 만들면서 확인하면 된다. 코드 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485#include #include #include #include using namespace std;int n, m, w;int map[51][51];int d[51][51];int dx[] = { 1,-1,0.. 백준 1389 / 케빈 베이컨의 6단계 법칙 (케빈 베이컨이 나오는 영화들을 많이 봤는데, 그 중 제일 재밌었던 건 일급살인이다.) BFS 연습문제 인접리스트로 문제를 해결했다 코드 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121#include #include #include #include #include using namespace std; .. 백준 1010 / 다리 놓기 M개 중에 중복없이 N개를 고르는 경우의 수 : MC(콤비네이션)N 해결법은 생각해내기 쉽지만 문제는 수의 범위다. 0 백준 2225 / 합분해 다이나믹 프로그래밍 문제 이것도 어렵다. d[k][n]이 k개의 수로 n을 완성한 경우의 수라고 하자. ㅇ+ ㅇ + ..... + ㅇ + ㅇ = n(ㅇ의 개수가 k) 여기서 마지막 ㅇ를 L라고 가정했을때 점화식은 d[k][n] = 시그마(d[k-1][n-L]) 항상 점화식을 세울때 변수의 범위를 생각하여야 한다. 여기서 변수는 L이므로 L의 범위는 0 k; for (int i = 1; i 백준 1699 / 제곱수의 합 다이나믹 프로그래밍 문제. 점화식은 i^2이 N을 구성하는 어떠한 한 제곱수라고 가정할때 D[N] = min (D[N-i^2]) +1 어렵다. 코드 123456789101112131415161718192021222324#include#include#include using namespace std; int main() { int n; int cnt = 0; cin >> n; int d[100001]; d[0] = 0; for (int i = 1; i 백준 1912 / 연속합 다이나믹 프로그래밍 연습문제. 어렵다. 생각해내기가 어렵다. 머리를 싸매고 여며봤는데 생각이 안나 결국 해결방법을 찾아보았다. 방법은 이러하다. 입력된 배열 말고 다른 배열을 하나 만든다 (D 배열이라 가정) D배열엔 그 인덱스까지 더한 최대값을 적어놓는다. 예) 그리고 D 배열에 들어있는 성분 중 가장 큰 수를 출력한다. 코드 123456789101112131415161718192021222324252627282930313233343536373839#include #include#include using namespace std; int arr[100001];int d[100001]; int main() { int n; cin >> n; for (int i = 0; i > arr[i]; } d[0] =.. 백준 14002 / 가장 긴 증가하는 부분 수열 4 LIS 문제 이번엔 길이만 출력하는 것이 아니라 수열 그 자체를 출력해야하는 문제다. 넘나 어려웠다. https://naivep.tistory.com/9 여기서 배열을 하나 더 만들어, d의 값이 어느 인덱스의 값 때문에 변하는지 적어놓는 것이다. 그 후 완성된 수열의 가장 끝에 위치할 성분부터 v[i]에 적힌 인덱스 값으로 이동하여 벡터 안에 집어넣는다. 그 후 벡터를 sort한 후 출력하면 끝. 코드 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869#include #include #include #include #incl.. 이전 1 ··· 6 7 8 9 10 다음
