문제풀이/백준

[Python] 백준 20366번 풀이

우선 이 문제는 두 포인터를 활용한 문제다. 두 개의 눈사람 키 차이 중 최솟값을 구하는 문제이다. 문제 풀이를 보고 이해가 안 가는 부분이 있었는데, a, b와 사이엔 최소 2개의 원소가 있어야 그 안에서 투포인터를 돌려 a, b로 이루어진 눈사람의 키와 차이가 가장 적은 눈사람을 만들 수 있다. 정렬된 배열에서 두 포인터를 돌리므로, a

[C++] 백준 15650번 문제풀이

순열과 조합을 정리 하려 한다. 먼저 , 순열이란 서로 다른 n개중에 r 개를 선택하는 경우의수 ( 순서 상관 있다. ) 조합이란 서로 다른 n개중에서 r개를 선택하는 경우의 수 ( 순서 상관 없다 .) #define n 4 #define r 3 1. 순열 ( 순서 O, 중복 X ) int pArr[r] = { 0, }; bool check[n + 1] = { false, }; //중복 검사 void permutation(int depth){ if(depth == r){ printArray(pArr); return; } for(int i = 1; i

[C++] 백준 1149번 문제풀이

동적프로그래밍의 정의를 다시 생각하자 문제를 너무 편협적으로 보지말자, 문제 출제자는 생각보다 너그러울수도있다. #include #include using namespace std; int house[1001][3]; int main() { int N; int cost[3]; house[0][0] = 0; house[0][1] = 0; house[0][2] = 0; cin >> N; cout

[C++] 백준 1167 번 문제풀이

#include #include #include using namespace std; vectorv[100001]; bool visited[100001]; int max1 = 0; int maxnode = 0; void dfs(int cost, int start) { if (visited[start]) return; visited[start] = true; if (cost > max1) { max1 = cost; maxnode = start; } for (int i = 0; i > N; while (N--) { int..

[C++] 백준 2667번 문제풀이

DFS 할 때 더 깔끔하게 풀기 int dx[4] = { 1, -1, 0, 0 }; int dy[4] = { 0, 0, 1, -1 }; vector vec; void DFS(int x, int y) { house_cnt++; visit[x][y] = true; for (int i = 0; i = N || ny = N) continue; if (arr[nx][ny] == 1 && visit[nx][ny] == false){ DFS(nx, ny); } } } 이런식으로 dx dy 나눠서 하면 더 깔끔해 보인다. #include #include #include #in..

[C++] 백준 2579번 문제풀이++] 백준 2579번 문제풀이

이 문제를 DFS 로 풀려고 했는데 시간초과가 뜨고 DFS로 풀지 못하였다. 문제를 풀 때 DP를 써야하는데 DP의 중점은 큰 문제를 작은 문제로 분할하여 푼다. 이것을 중점으로 풀자. #include #include #include using namespace std; int main() { int cnt; cin >> cnt; int arr[300]; int now[300] = { 0, }; for (int i = 0; i > arr[i]; now[0] = arr[0]; now[1] = max(arr[1], arr[0] + arr[1]); now[2] = max(arr[2] + arr[0], arr[1] + arr[2]); for (int i = 3; i < cnt; i..

[C++] 백준 18870 번 문제풀이

이 문제를 보고 든 생각은 벡터를 두개 사용하여 하나는 그대로 다른 하나는 중복이 없고 순서대로 정렬된 벡터를 사용하여 비교하면서 출력하면 되겠다는 생각을 하고 풀었다. 벡터내에 중복이 없는 코드를 짜려면 b.erase(unique(b.begin(), b.end()), b.end()); 이런식으로 erase와 unique 를 사용하여 중복을 없애준다. 처음에 원소들을 받고 벡터를 복사 후 중복이 없고 순서대로 정렬된 벡터를 만들고 lower_bound 함수를 통해 index를 쉽게 구할 수 있었다. #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cout.tie(0); cin.tie(..

[C++] 백준 11726번 문제풀이

타일링 문제는 유명해서 잘 봐둬야 한다. 이 문제를 보고 BFS를 이용하여 풀려고 했으나 시간 초과가 떴다. 그래서 DP 를 이용하였는데 위 그림을 보면 dp[n]=dp[n-1]+dp[n-2] 를 이해 하기쉽다. 이를 코드로 작성하면 #include using namespace std; int N; int dp[1001]; int main() { ios_base::sync_with_stdio(false); cout.tie(0); cin.tie(0); cin >> N; dp[0] = 1; dp[1] = 1; for (int i = 2; i