Category: Develop

2021
0
DevelopBeakjoon

백준 12100 - 2048

https://www.acmicpc.net/problem/12100 백준 12100 - 2048문제 풀이보드를 상하좌우로 움직이면서 블록이 최대값이 나올 수 있는 경우를 찾는 문제이다. 한 보드를 상하좌우로 움직이고 원래데로 되돌린 후 다시 시도하기 위해 백트레킹 기법이 필요하다. 블록을 상하좌우중 한 방향으로 움직인다. 5번 움직이면 블록을 스캔해 최대값을 찾는다. 이전 단계로 되돌린 후 다른방향으로 움직이면서 최대값을 찾아본다. 문제 예외 처리 한번 합처진 블록은 연속적으로 합처질 수 없다. 합처지는 순서는 이동하려고 하는 쪽의 칸이 먼저 합쳐진다. 소스 코드#include <bits/stdc++.h>using namespace std;int maxValue = 0;int board[22][22];int boardSize = 0;void initBoard(int size) { for (int i = 0; i < size; i++) { for (int j = 0; j < size; j++) { cin >> board[i][j]; } }}void moveTop() { int check[22][22]; for (int col = 0; col < boardSize; col++) { for (int row = 0; row < boardSize; row++) { check[col][row] = false; } } for (int row = 0; row < boardSize; row++) { for (int col = 0; col < boardSize; col++) { int cntRow = row; int cntCol = col; if (board[cntRow][cntCol] == 0) { continue; } while (cntRow - 1 >= 0 && (board[cntRow - 1][cntCol] == board[cntRow][cntCol] || board[cntRow - 1][cntCol] == 0)) { if (board[cntRow - 1][cntCol] == board[cntRow][cntCol]) { if (check[cntRow - 1][cntCol] == false && check[cntRow][cntCol] == false) { board[cntRow - 1][cntCol] += board[cntRow][cntCol]; check[cntRow - 1][cntCol] = true; board[cntRow][cntCol] = 0; } else { break; } } else { swap(board[cntRow - 1][cntCol], board[cntRow][cntCol]); } cntRow--; } } }}void moveButton() { int check[22][22]; for (int col = 0; col < boardSize; col++) { for (int row = 0; row < boardSize; row++) { check[col][row] = false; } } for (int row = boardSize - 1; row >= 0; row--) { for (int col = 0; col < boardSize; col++) { int cntCol = col; int cntRow = row; if (board[cntRow][cntCol] == 0) { continue; } while (cntRow + 1 < boardSize && (board[cntRow + 1][cntCol] == board[cntRow][cntCol] || board[cntRow + 1][cntCol] == 0)) { if (board[cntRow + 1][cntCol] == board[cntRow][cntCol]) { if (check[cntRow + 1][cntCol] == false && check[cntRow][cntCol] == false) { board[cntRow + 1][cntCol] += board[cntRow][cntCol]; check[cntRow + 1][cntCol] = true; board[cntRow][cntCol] = 0; } else { break; } } else { swap(board[cntRow + 1][cntCol], board[cntRow][cntCol]); } cntRow++; } } }}void moveLeft() { int check[22][22]; for (int col = 0; col < boardSize; col++) { for (int row = 0; row < boardSize; row++) { check[col][row] = false; } } for (int col = 0; col < boardSize; col++) { for (int row = 0; row < boardSize; row++) { int cntCol = col; int cntRow = row; if (board[cntRow][cntCol] == 0) { continue; } while (cntCol - 1 >= 0 && (board[cntRow][cntCol - 1] == board[cntRow][cntCol] || board[cntRow][cntCol - 1] == 0)) { if (board[cntRow][cntCol - 1] == board[cntRow][cntCol]) { if (check[cntRow][cntCol - 1] == false && check[cntRow][cntCol] == false) { board[cntRow][cntCol - 1] += board[cntRow][cntCol]; check[cntRow][cntCol - 1] = true; board[cntRow][cntCol] = 0; } else { break; } } else { swap(board[cntRow][cntCol - 1], board[cntRow][cntCol]); } cntCol--; } } }}void moveRight() { int check[22][22]; for (int col = 0; col < boardSize; col++) { for (int row = 0; row < boardSize; row++) { check[col][row] = false; } } for (int col = boardSize - 1; col >= 0; col--) { for (int row = 0; row < boardSize; row++) { int cntRow = row; int cntCol = col; if (board[cntRow][cntCol] == 0) { continue; } while (cntCol + 1 < boardSize && (board[cntRow][cntCol + 1] == board[cntRow][cntCol] || board[cntRow][cntCol + 1] == 0)) { if (board[cntRow][cntCol + 1] == board[cntRow][cntCol]) { if (check[cntRow][cntCol + 1] == false && check[cntRow][cntCol] == false) { board[cntRow][cntCol + 1] += board[cntRow][cntCol]; check[cntRow][cntCol + 1] = true; board[cntRow][cntCol] = 0; } else { break; } } else { swap(board[cntRow][cntCol], board[cntRow][cntCol + 1]); } cntCol++; } } }}void returnBoard(int (*board)[22], int (*copy)[22]) { for (int i = 0; i < boardSize; i++) { for (int j = 0; j < boardSize; j++) { board[i][j] = copy[i][j]; } }}void moveBoard(int depth) { int copyBoard[22][22]; for (int i = 0; i < boardSize; i++) { for (int j = 0; j < boardSize; j++) { copyBoard[i][j] = board[i][j]; } } if (depth == 5) { for (int i = 0; i < boardSize; i++) { for (int j = 0; j < boardSize; j++) { if (board[i][j] > maxValue) { maxValue = board[i][j]; } } } return; } moveTop(); moveBoard(depth + 1); returnBoard(board, copyBoard); moveButton(); moveBoard(depth + 1); returnBoard(board, copyBoard); moveLeft(); moveBoard(depth + 1); returnBoard(board, copyBoard); moveRight(); moveBoard(depth + 1); returnBoard(board, copyBoard);}int main(void) { cin >> boardSize; initBoard(boardSize); moveBoard(0); cout << maxValue << '\n'; return 0;}

0
DevelopBeakjoon

백준 1920 - 수 찾기

백준 1920 - 수 찾기문제 풀이범위 1~10만개의 숫자들 중에서 M개의 주어진 값이 존재하는지 확인하는 문제이다. 일반적인 탐색을 진행할 경우 O(N*N)의 시간복잡도를 갖게 되므로 O(logN)의 시간복잡도를 갖는 이분 탐색을 이용해 문제를 해결하도록 한다. 전체 소스#include <bits/stdc++.h>using namespace std;int binarySearch(vector<int>& arr, int value) { int begin = 0; int end = arr.size() - 1; while (begin <= end) { int mid = (begin + end) / 2; int midValue = arr[mid]; if (value == midValue) { return 1; } else if (value > midValue) { begin = mid + 1; } else { end = mid - 1; } } return 0;}vector<int> solution(vector<int> arr, vector<int> values) { vector<int> results; for (int valuesIndex = 0; valuesIndex < values.size(); valuesIndex++) { int result = binarySearch(arr, values[valuesIndex]); results.push_back(result); } return results;}int main(void) { int n, m; vector<int> arr; vector<int> values; cin >> n; arr = vector<int>(n); for (int i = 0; i < n; i++) { cin >> arr[i]; } sort(arr.begin(), arr.end()); cin >> m; values = vector<int>(m); for (int i = 0; i < m; i++) { cin >> values[i]; } vector<int> results = solution(arr, values); for (int value : results) { cout << value << '\n'; } return 0;}

0
DevelopBeakjoon

백준 2343 - 기타 레슨

백준 2343 - 기타 레슨https://www.acmicpc.net/problem/2343 문제 풀이탐색 범위는 (1~10억)이고 연산을 N번 해야 함으로 O(N) or O(NlogN)의 시간복잡도 내에 문제를 해결해야 한다. 탐색 시간을 줄이기 위해서 O(logN)시간 복잡도 내에 탐색을 끝낼 수 있는 이분탐색을 이용해 문제를 해결해야 한다. 이 문제의 함정은 조건 중 순서가 뒤바뀌면 안된다는 조껀이 있기 때문에 레슨이 들어온 순서를 sorting할 경우 틀리게 된다. begin을 1로 end를 들어온 값의 합을 준다. begin과 end 범위 내에서 이분 탐색을 진행한다. 이분탐색을 진행하면서 블루레이를 녹화할 수 있는 영상의 길이가 한 영상의 길이보다 작으면 begin을 움직인다. 블루레이에 녹화하는 갯수가 블루레이보다 총 갯수보다 작거나 같을 경우 end를 움직인다. 블루레이에 녹화하는 갯수가 블루레이보다 작을 경우 begin을 움직인다. 전체 소스#include <bits/stdc++.h>using namespace std;bool cmp(vector<int> arr, int mid, int M) { int sum = 0; int count = 1; for (int arrIndex = 0; arrIndex < arr.size(); arrIndex++) { int value = arr[arrIndex]; if (value > mid) { return true; } if (sum + value <= mid) { sum += value; } else { count += 1; sum = value; } } // 길이가 너무 짧다. begin을 늘려줘야 한다. return count > M;}int binarySearch(vector<int> arr, int N, int M) { int begin = 1; int end = 0; for (int arrIndex = 0; arrIndex < arr.size(); arrIndex++) { end += arr[arrIndex]; } while (begin <= end) { int mid = (begin + end) / 2; if (cmp(arr, mid, M)) { begin = mid + 1; } else { end = mid - 1; } } return begin;}int solution(vector<int> arr, int N, int M) { int result = 0; result = binarySearch(arr, N, M); return result;}int main(void) { int N, M; vector<int> arr; cin >> N >> M; arr = vector<int>(N); for (int i = 0; i < N; i++) { cin >> arr[i]; } cout << solution(arr, N, M) << '\n'; return 0;}

0
DevelopBeakjoon

백준 3015 - 오아시스 재결합

백준 3015 - 오아시스 재결합https://www.acmicpc.net/problem/1920 문제 해설입력되는 값이 총 50만개이다. 이 문제는 O(N) or O(NlogN)의 시간복잡도를 갖고 해결을 해야하는 문제이다. 현재 값을 이전 값과 비교해가면서 문제를 해결 하는 방식이다. 스택의 역할은 서로불 수 있는 값의 쌍을 저장하기 위한 역할을 한다. 스택내의 값은 점점 작은 값이 추가 되야 한다. 들어오는 값이 top보다 클 경우 들어오는 값보다 큰 값이 나타날 때까지 pop을 진행하면서 pop을 진행할 때 해당 인원수 만큼 값을 더해준다. 같은 값이 들어올 경우을 어떻게 해결하는 것이 이 문제의 어려운 점이다. 자료구조 pair를 이용한다. first에는 사람의 키를 second에는 같은 키인 사람의 수를 저장한다. 키가 같은 사람이 들어올 경우 같은 키를 갖는 사람만큼 값을 추가해주고 사람수를 + 1 해주고 해당 키를 다시 push해준다. 소스 코드#include <bits/stdc++.h>using namespace std;long long solution(vector<int> heights) { stack<pair<int, int>> st; long long result = 0; for (int heightsIndex = 0; heightsIndex < heights.size(); heightsIndex++) { int height = heights[heightsIndex]; while (!st.empty() && height > st.top().first) { result += st.top().second; st.pop(); } if (!st.empty()) { if (st.top().first == height) { pair<int, int> temp = st.top(); st.pop(); result += temp.second; if (!st.empty()) { result += 1; } st.push({height, temp.second + 1}); } else { result += 1; st.push({height, 1}); } } else { st.push({height, 1}); } } return result;}int main(void) { int numOfPeople; vector<int> heights; cin >> numOfPeople; for (int peopleIndex = 0; peopleIndex < numOfPeople; peopleIndex++) { int height; cin >> height; heights.push_back(height); } cout << solution(heights) << '\n'; return 0;}

0
DevelopBeakjoon

백준 - 수학

백준 - 수학수학 문제 이름 링크 정리여부 비고 1085 직사각형에서 탈출 https://www.acmicpc.net/problem/1085 1644 소수의 연속합 https://www.acmicpc.net/problem/1644 1712 손익분기점 https://www.acmicpc.net/problem/1712 1722 순열의 순서 https://www.acmicpc.net/problem/1722 1978 알파벳 https://www.acmicpc.net/problem/1978 1990 소수인팬린드롬 https://www.acmicpc.net/problem/1990 2292 벌집 https://www.acmicpc.net/problem/2292 2839 설탈배달 https://www.acmicpc.net/problem/2839 2960 에라토스테네스의 체 https://www.acmicpc.net/problem/2960 10819 차이를 최대로 https://www.acmicpc.net/problem/10819 순열, next_permutation 10950 A+B - 3 https://www.acmicpc.net/problem/10950 10952 A+B - 5 https://www.acmicpc.net/problem/10952 11021 A+B - 7 https://www.acmicpc.net/problem/11021 11022 A+B - 8 https://www.acmicpc.net/problem/11022

0
DevelopBeakjoon

백준 - 비트마스킹

백준 - 비트 마스킹비트 마스크 문제 이름 틀린 횟수 정리여부 비고 2064 IP 주소 토크나이징, 비트 연산 11723 집합 기본유형

0
DevelopBeakjoon

백준 - 유니온 파인드

백준 유니온 파인드유니온 파인드 문제 이름 틀린 횟수 정리여부 비고 1717 집합의 표현 1976 여행가자 4195 친구 네트워크 10774 저지 10775 공항

0
DevelopBeakjoon

백준 - 최소 스패닝 트리

백준 최소 스패닝 트리최소 스패닝 트리 문제 이름 틀린 횟수 정리여부 비고 1196 최소 스패닝 트리 최소 스패닝 트리 기본 유형 9372 상근이의 여행 17472 다리 만들기 2 삼성, 최소 스패닝 트리

0
DevelopBeakjoon

백준 - 투 포인터

백준 - 투 포인터투 포인터 문제 이름 틀린 횟수 정리여부 비고 1484 다이어트 1806 부분합 2003 수들의 합 2 기본 유형 2230 수 고르기

0
DevelopBeakjoon

백준 - 백트래킹

백준 백트래킹백트래킹 문제 이름 링크 정리여부 비고 1987 병든 나이트 https://www.acmicpc.net/problem/1987 2580 스도쿠 https://www.acmicpc.net/problem/2580 4574 스도미노쿠 https://www.acmicpc.net/problem/4574 6603 로또 https://www.acmicpc.net/problem/6603 9663 N-Queen https://www.acmicpc.net/problem/9663 16987 계란으로 계란치기 https://www.acmicpc.net/problem/16987

0
DevelopBeakjoon

백준 - 이분탐색

백준 이분탐색이분 탐색 문제 이름 링크 정리여부 비고 1920 수찾기 https://www.acmicpc.net/problem/1920 1939 중량제한 https://www.acmicpc.net/problem/13397 2110 공유기 설치 https://www.acmicpc.net/problem/2210 2343 기타레슨 https://www.acmicpc.net/problem/2343 O 겁나 많이 틀림 2792 보석상자 https://www.acmicpc.net/problem/2792 O 중요! 다시 풀어보기 2805 나무자르기 https://www.acmicpc.net/problem/2805 2869 달팽이는 올라가고 싶다 https://www.acmicpc.net/problem/2869 3020 개똥벌레 https://www.acmicpc.net/problem/3020 10815 숫자카드 https://www.acmicpc.net/problem/10815 10816 숫자카드2 https://www.acmicpc.net/problem/10816 13397 구간 나누기2 https://www.acmicpc.net/problem/13397

0
DevelopBeakjoon

백준 - BFS

백준 BFSBFS기본 유형 문제 이름 틀린횟수 정리여부 비고 c++ java python 1260 DFS와 BFS 기초 O 1953 팀 배분 0 O 이분 그래프 2178 미로 탐색 최단 거리 O O O 전체 문제 문제 이름 틀린횟수 정리여부 비고 c++ java python 1012 유기농 배추 2 O 1194 달이 차오른다, 가자 1 O 1260 DFS와 BFS 기초 O O 1600 말이 되고픈 원숭이 5 O 1707 이분 그래프 4 O 1726 로봇 1 O 1939 중량제한 3 O 1953 팀 배분 0 O 이분 그래프 O 1963 소수 경로 0 O 1967 트리의 지름 2 O 2146 다리 만들기 5 O 2178 미로 탐색 최단 거리 O O O 2206 벽 부수고 이동하기 5 2251 물통 0 2234 성곽 0 2468 안전 영역 2 2573 빙산 3 2583 영역 구하기 1 2589 보물섬 0 2606 바이러스 0 2644 촌수 계산 0 2667 단지번호 붙이기 4 2933 미네랄 5 5014 스타트와 링크 1 5213 과외맨 6 5427 불 2 6087 레이저 통신 0 6593 상범 빌딩 1 7576 토마토 1 9019 DSLR 4 9205 맥주 마시면서 걸어가기 3 9372 상근이의 여행 1 12886 돌 그룹 1 15558 점프 게임 11 16236 아기 상어 4 O bfs를 통해 거리구하기 16397 탈출 5 16933 벽 부수고 이동하기3 6 16959 체스판 여행 1 0 17471 게리맨더링 4 O 조합, bfs, 삼성 17836 공주님을 구해라 5 18809 Gaaaaaaaaaarden 0 조합, bfs, 삼성

0
DevelopBeakjoon

백준 - DFS

백준 DFSDFS(깊이 우선 탐색) 문제 이름 틀린횟수 정리여부 비고 c++ java python 1260 DFS와 BFS 1325 효율적인 해킹 9466 텀 프로젝트 10026 적록색약 15649 N과 M(1) 15650 N과 M(2) 15651 N과 M(3) 15652 N과 M(4)