Deff_Dev

문제 https://www.acmicpc.net/problem/2252풀이이 문제는 위상 정렬을 사용하여 풀이했다. 위상 정렬이란 ?비순환 방향 그래프(DAG)에서 정점을 선형으로 정렬하는 것이다.위상 정렬을 사용하기 위해서는 조건이 필요하다.방향 그래프(Directed Graph)여야 한다.비순환 그래프(Acyclic Graph)여야 한다. 즉, 사이클이 없어야 한다.최소한 하나의 위상 정렬 결과가 존재해야 한다.이 문제는 위 조건에 만족하기 때문에 위상 정렬을 사용하여 풀이했다.#include #include #include using namespace std;int n, m;int degree[32001];vector vec[32001];void Topological_Sort() { queue q..

문제 https://www.acmicpc.net/problem/2161풀이이 문제는 1 ~ N 까지 이루어진 숫자들에서 특별한 규칙을 부여하여 첫 번째 숫자들을 출력 후 삭제하는 문제이다. 여기서 주어진 규칙은 다음과 같다.첫 번째 요소를 출력 후 삭제한다.이후 첫 번째 요소가 된 숫자를 맨 뒤로 옮긴다.숫자들이 남지 않을 때까지 반복한다.난 Queue를 이용하여 해당 문제를 풀이했다.#include #include using namespace std;int main() { int n; cin >> n; queue q; for (int i = 1; i

문제https://www.acmicpc.net/problem/2607 풀이 문자열 입력비슷한 문자 찾기0 번째 단어 탐색 ▶ 각 알파벳 갯수 count - 1n 번째 단어 탐색 ▶ 각 알파벳 갯수 count + 1차이점 계산같은 문자일 경우 ▶ 0문자 하나 추가 or 삭제 ▶ 1문자 하나 변경 (문자 제거 + 추가) ▶ 2 비슷한 단어라면 결과 값 + 1출력#include #include #include #include using namespace std;bool isSimilar(string target, string word) { if (abs((int)target.length() - (int)word.length()) > 1) return false; vector count(26, 0);..

문제 https://www.acmicpc.net/problem/2156풀이이 문제는 DP를 이용하여 풀이했다. 점화식dp[i-1] : i번째 잔을 마시지 않는 경우 (최댓값이 아니라면 무한으로 건너 뛸 수 있기 때문에)dp[i-2] + grapes[i] : i번째 잔을 마시고, i-1번째 잔을 마시지 않는 경우dp[i-3] + grapes[i-1] + grapes[i] : i번째와 i-1번째 잔을 마시고, i-2번째 잔을 마시지 않는 경우#include// https://www.acmicpc.net/problem/2156using namespace std;int grapes[10001] = {0};int dp[10001] = {0};int main() { int n; cin >> n; f..

문제https://www.acmicpc.net/problem/1026풀이a는 오름차순 b는 내림차순한 후, 0 ~ n 번째까지 곱하여 최소 값을 만들었다.#include#include#include// https://www.acmicpc.net/problem/1026using namespace std;bool cmp(int a, int b) { return a > b;}int main() { int n; cin >> n; vector a(n); vector b(n); for (int i = 0; i > a[i]; } for (int i = 0; i > b[i]; } sort(a.begin(), a.end()); sort(b.begin(), b.end(), cmp); int sum = 0; for (int..

문제 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..