문제풀이

[C++]2020 KAKAO BLIND RECRUITMENT 1번문제

딱히 어려운 개념은 없고 문제만 똑바로 읽으면 풀 수 있는 문제였다. 테스트케이스 5번이 자꾸 오류가 났는데 테스트케이스의 string 길이가 1이였다... 하나만 유독 이상할 땐 특이한 케이스를 생각해보자 #include #include using namespace std; int solution(string s) { int answer = 10000000; if(s.length()==1)answer=1; else{ for(int i=1;i

[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

[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