문제풀이/백준

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

처음 문제를 읽고 연결요소란 말을 잘 이해 못해서 헷갈렸다. 간단히 말하면 정점 하나를 DFS 탐색 했을 때 하나의 연결요소가 생긴다 정점 하나가 DFS 탐색 했을 때 지나갔던 정점들은 그 연결요소에 해당되며 지나가지 않았던 정점들을 다시 DFS 하면서 연결요소를 찾으면 된다 DFS 기본을 구현할 줄 알면 쉽게 풀 수 있는 문제였다. #include #include using namespace std; vector vc[1001]; bool visited[1001]; void DFS(int n) { visited[n] = true; for (int i = 0; i < vc[n].size(); i++) { int check = vc[n][i]; if (!visited[check]) { DFS(check);..

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

자료구조 시간 때 배웠던 heap을 배열로 구현하는 문제였다. upheap 은 구현하기 쉬우나 downheap 할 때 구현하기 헷갈렸는데 왼쪽과 오른쪽 자식이 있는데 두 개의 자식들 중 큰 것을 parent 와 바꿔주어야 한다. 이를 표현한것이 아래의 코드이다. child = (arr[child] > arr[child + 1]) ? child : child + 1; 이것만 생각한다면 쉽게 풀 수 있는 문제였다. #include #include using namespace std; int arr[100000]; int size1 = 0; void swap(int a, int b) { int x = arr[a]; arr[a] = arr[b]; arr[b] = x; } void upheap(int n) { a..

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

이 문제를 보고 DP를 사용해야 된다는 걸 바로 알았다. DP 개념만 알고 있으면 쉽게 풀 수 있는 문제였다. #include using namespace std; int N,M; int dp[10][275]; void O(int total) { if (total == N) { M ++; return; } else if(total> cnt; while (cnt--) { cin >> N; O(0); cout

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

이 문제를 보고 queue 를 2개 사용해서 풀려고 했는데 쉽지 않았다. 오름차순과 내림차순 2개의 queue 를 사용하려고 했으나 오름차순에서 마지막 수가 내림차순의 첫 번째 수를 넘게 되면 머리가 어지러워 진다. 자료조사를 하던중 set을 알게되어 set 을 사용하여 풀었다. multi set 과 set 의 차이점은 key 값이 중복이 된다는 점이 였다. set을 알면 쉽게 풀 수 있는 문제였다. #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cout.tie(0); cin.tie(0); int cnt; cin >> cnt; while (cnt--) { int a; cin >> a..

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

이 문제는 풀때 딱히 어려운 개념은 없었다. 한가지 헷갈렸던 점은 C++은 수학이랑 다르단 점 (A/B)*B = A 가 아니란 점만 알고 넘어가자 #include #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(NULL); int arr[14]; int cash; cin >> cash; int JH = cash;//준현이가 가지고 있는 현금 int JHnum=0;//준현이가 가지고 있는 주 개수 int SM = cash;//성민이가 가지고 있는 현금 int SMnum = 0;//성민이가 가지고 있는 주 개수 for (int i = 0; i > num; arr[i..

[C++] 백준 20544 문제풀이

이 문제를 보고 DP 를 사용해야 되겠다고 생각하였다. DP 문제를 많이 다루지 못해서 이 문제는 충분히 생각한 뒤 다른 사람의 풀이를 참조 하여 코드를 해석하고 왜 이런 코드를 썼는지 이해하였다. 다음 문제를 풀땐 내가 직접 풀어보자 ... 우선 코드를 해석하였을 때 체크 해야 할것들이 여러가지가 있는데 첫 번째 도현이의 위치 두 번째 과거 허들 높이 세 번째 현재 허들 높이 네 번째 허들의 높이가 2이상인 경우가 있는가 ? 이 4개를 고려하여 동적 프로그래밍을 해야한다. #include #include #include using namespace std; long long dp[1001][3][3][2]; long long mod = 1000000007; int N; long long solve(in..

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

이 문제를 보고 2차원 하루 지났을 때 토마토가 어떻게 퍼지는지 보았는데 입력이 6 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 일 때 . Day 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 Day 2 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 1 1 1 Day 3 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 1 1 1 0 0 1 1 1 1 이런식으로 BFS 를 써야 될거 같이 생겼다. 좌표를 하나의 node 라고 생각하면 근처의 node 들을 방문한뒤 다음 node 의 근처 node들을 방문 하는 식이다. BFS 를 좌표로 표현하기 위해 pair 를 사용하여 x축 , y축을..

[C++] 백준 2630 문제풀이

문제를 보고 든 생각은 사각형을 사분면으로 생각해서 풀어야겠다고 생각했다. 사분면을 검사할때 사분면의 원소가 사분면의 제일 왼쪽 위에 있는 원소와 다르다면 , 사분면을 잘라서 다시 검사하게 만들었다. bool check 를 쓴 이유는 사분면 검사를 통과했는지 유무를 검사하기 위해 사용하였다. #include using namespace std; int arr[128][128]; int blue = 0; int white = 0; void cut(int n1, int n2,int N) { bool check = true; int index = arr[n1][n2]; for (int i = n1; i > num; for (int i = 0; i < num; i++) { for (int j = 0; j < n..