Deff_Dev

문제 https://www.acmicpc.net/problem/2583=풀이N * M 크기의 맵에 입력된 직사각형 영역을 1로 채운 다음 BFS를 이용하여 비어 있는 영역의 갯수와 크기를 구했다#include#include#include#include// https://www.acmicpc.net/problem/2583using namespace std;int M, N, K;int map[101][101] = { 0, };bool visited[101][101] = { false, };int dx[4] = { 1,-1,0,0 };int dy[4] = { 0,0,1,-1 };vector answer;void BFS(pair startPos) { queue> q; q.push(startPos); visite..

문제 https://www.acmicpc.net/problem/1253풀이이 문제는 이분 탐색 문제로, 입력된 숫자들을 오름차순으로 정렬한 후, 좋은 숫자의 갯수를 구하는 방법으로 풀이했다.#include#include#include// https://www.acmicpc.net/problem/1253using namespace std;int main() { int n; cin >> n; vector vec(n); for (int i = 0; i > vec[i]; } sort(vec.begin(), vec.end() ); int count = 0; for (int i = n - 1; i >= 0; i--) { int left = 0, right = n - 1, target = vec[i]; whil..

문제 https://www.acmicpc.net/problem/1421  풀이나무의 길이를 내림차순으로 정렬한 후, 모든 길이로 잘랐을 때, 금액을 부르트포스로 풀이했다. 반례계속 3%에서 실패가 나와, 모든 반례를 찾아봤지만, 전부다 정답이었다.문제를 다시 확인해보니 총 금액이 int 범위를 넘어 갈 수 있을거 같다고 생각했고, maxPrice의 데이터 형태를 int가 아닌 long long으로 변경했더니 맞았다.#include#include#include// https://www.acmicpc.net/problem/1421using namespace std;int n, c, w;bool cmp(int a, int b){ return a > b;}int main() { cin >> n >> c >> w..

문제 https://www.acmicpc.net/problem/1461풀이이 문제는 그리디 문제로, 절댓값이 가장 큰 책을 마지막에 갖다놓는(0으로 안돌와도 됨) 방법으로 풀이했다. 음수, 양수 값을 나눠서 벡터에 저장(음수는 양수로 변환하여 저장)하고, 절댓값이 가장 큰 값을 저장한다.각 벡터를 내림차순 정렬한다.idx 번째 값의 * 2 한 값을 sum에 더하고 idx + m하는 과정을 벡터의 크기 만큼 반복한다.이때, 가장 큰 값이 존재하는 벡터일 경우,  왕복 값이 아닌 편도 값을 먼저 더한 뒤, 3번 과정을 반복한다.#include#include#include// https://www.acmicpc.net/problem/1461using namespace std;vector plusVec;vec..

문제 https://www.acmicpc.net/problem/1058풀이직접적인 친구를 먼저 찾고 해당 친구의 겹지인을 탐색하는 방법으로 풀이했다. #include// https://www.acmicpc.net/problem/1058using namespace std;bool isFriend[51][51] = { false, };bool isCheck[51][51] = { false, };int main() { int n; cin >> n; char input; for (int i = 1; i > input; if (input == 'Y') { isFriend[i][j] = true; } } } int maxCount = -1; for (int i = 1; i

문제 https://www.acmicpc.net/problem/11724풀이BFS를 이용해 모든 노드를 탐색하고 연결 요소의 개수를 구하는 방법으로 풀이했다.#include#include#include// https://www.acmicpc.net/problem/11724using namespace std;int N, M;vector vec[1001];bool visited[1001] = { false, };void BFS(int startPos) { queue q; q.push(startPos); visited[startPos] = true; while (!q.empty()) { int target = q.front(); q.pop(); for (int i = 0; i > N >> M; int s..

문제 https://www.acmicpc.net/problem/1916풀이이 문제는 시작 지점에서 도착지점까지의 최소비용 구하는 문제로, 다익스트라, 우선순위 큐를 이용하여 풀이했다.  우선순위 큐는 가중치가 낮은 노드 먼저 탐색(그리디)하여 최소 거리를 효율적으로 찾기 위해 사용했다. #include#include#include// https://www.acmicpc.net/problem/1916#define INF 1e9using namespace std;int N, M, startPos, endPos;vector > vec[1001];void Dijk() { vector dist(N + 1, INF); priority_queue, vector>, greater>> pq; dist[startPos] ..

문제 https://www.acmicpc.net/problem/15654풀이next_permutation() 을 이용하여 조합을 구하고 해당 조합에서 순열을 구한 값들을 저장하고 오름차순으로 정렬한 후, 출력하는 방법으로 풀이했다.#include#include #include // https://www.acmicpc.net/problem/15654using namespace std;int main() { int n, m, sel; cin >> n >> m; vector vec (n); vector combination (n, true); vector> answer; for (int i = 0; i > vec[i]; } for (int i = 0; i combinationValues; for (in..