문제풀이/백준
[C++] 백준 2606 문제풀이
벡터를 활용한 dfs 를 사용하면 쉽게 풀 수 있었다. 동적할당을 사용하여 벡터를 이용하려면 vector * a = new vector[cnt + 1]; 이런식으로 선언을 해야한다. #include #include using namespace std; bool visited[100] = { false, }; int c = 0; void dfs(vectora[],int index) { visited[index] = true; for (int i = 0; i > cnt; vector * a ..
[C++] 백준 1931 문제풀이
이 문제를 제대로 읽지 않고 풀었더니 오류가 나왔다. 최대 사용할 수 있는 회의의 최대 개수를 구해야하는데 최대 개수를 구하지 않고 개수만 구하였더니 계속 오류가 났다 이를 해결하기 위해 정렬을 해줘야 하는데 vector 에서 pair 형태로 넣고 회의가 끝나는 시간이 같다면 회의가 시작하는 시간이 더 빠른 회의를 우선으로 회의가 끝나는 시간이 다르다면 회의가 끝나는 시간이 더 빠른 회의를 우선으로 정렬하였다. #include #include #include using namespace std; vectors; bool cmp(pair first, pair second) { if (first.second == second.second) return first.first < second.first; els..
[C++] 백준 1927번 문제풀이
작년에 자료구조 수업을 들을 때 직접 heap 을 구현하였다. 이 문제도 그렇게 푸는 줄 알았는데 heap 과 관련된 자료를 검색하던중 priority_queue q; 이러한 방법을 찾게 되어 priority_queue 을 사용하여 문제를 풀었다. #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(0); priority_queue q; int n; cin >> n; while (n--) { int num; cin >> num; if (num == 0) { if (q.size() == 0)cout
[C++] 백준 1389번 문제풀이
이 문제를 보고 BFS나 DFS로 풀려고 했으나 더 좋은 방법을 찾아서 풀었다. 그 방법은 플로이드 와샬 알고리즘인데 2차원 배열에서 한 정점에서 다른 모든 정점들을 방문 할 때 최소값으로 방문하도록 하는 알고리즘이다 여기선 한칸을 이동할때 비용이 같으므로 1로 통일 하였다. 다른 문제에서 한칸을 이동할때 비용이 다르면 1이 아니라 다른 값을 넣어 해야 할 것이다. #include #include int INF = 96748532; const int MAX = 101; using namespace std; int n, m; int gp[MAX][MAX]; void func() { for (int k = 1; k > m; while (m--) { int a, b; cin >> a >> b; gp[a][b]..
[C++] 백준 1764번 문제풀이
이 문제를 풀 때 들었던 생각은 듣도 못한 사람을 vector 에 넣고 보도 못한 사람이 듣도 못한 사람의 vector 안에 있다면 듣보잡의 vector안에 넣어야 겠다고 생각했다. 보도 못한 사람이 듣도 못한 사람의 vector 안에 있는가를 알기 위해선 탐색을 해야하는데 시간이 많이 걸리기 때문에 binary search 를 이용하여 풀었다. #include #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(NULL); int N, M; cin >> N >> M; vectordb; vectordbj; while (N--) { string name; cin >> name; db..
[C++] 백준 1697번 문제풀이
문제를 보고 든 생각은 내가 숫자를 X2 또는 +1 또는 -1 을 이용하여 K에 도달하도록 만드는 것이 였다. 그러나 문제를 풀수록 멍청한 생각이였단걸 알았고 BFS를 통해 쉽게 풀 수 있었다. (내가 풀지 말고 컴퓨터를 이용하여 풀도록 하자) BFS를 배워도 그것을 떠올리고 풀기가 쉽지 않았다.... 문제를 보고 어떤식으로 풀어야겠다 이 단계에서 BFS DFS 트리 등등을 떠올릴 수 있어야 하는데 그 단계 까지 가진 못했다. 그 동안 배운 자료구조를 풀어서 정리 해봐야겠다... #include #include #include using namespace std; bool visited[1000001]; int main() { ios_base::sync_with_stdio(0); cin.tie(NULL)..
[C++] 백준 1620번 문제풀이
이 문제를 보고 든 생각은 map 이나 vetor를 이용하여 풀어야 겠다 라고 생각하였다. 구현 자체는 어렵지 않았지만 생각해야 할 것이 시간초과를 하지 않게 해야 하는데 vector나 map 을 이용할때 for 문을 가지고 첫번째 요소부터 마지막 요소까지 확인하는 것은 매우 시간(O(N))을 많이 잡아먹는다. 따라서 다른 방법을 찾아야 했는데 map 을 두개 사용하거나 map 하나 또는 배열을 이용하여 푸는 것 이였다 두가지 다 사용하여 풀었으나 여기엔 map 과 배열을 이용한 풀이를 적어놓았다. ios_base::sync_with_stdio(0); cin.tie(NULL); 이 문장을 왜 쓰는줄 몰랐는데 찾아 보니까 C++ 알고리즘을 사용할 때 시간을 줄일 수 있다고 한다. (계속 똑같은 코드여도 위..
[C++] 백준 1463번 문제풀이
이 문제를 보면서 생각했던 점은 2,3 이 나오므로 6의 배수를 고려하여 풀고 입력 받은 수를 나눠가면서 풀자 였다. 그러나 문제를 풀다보니 입력 받은 수를 나눠서 풀기엔 순서를 고려하기 어려웠다 예시에 나온것 처럼 10 -> 9 -> 3-> 1 10 -> 5 -> 4-> 2->1 위와 같이 10에서 바로 2로 나누는것이 아닌 1을 빼고 3으로 나누는것이 연산 수가 적게 나오고 16 -> 8 -> 4 -> 2 -> 1 16 ->15 ->5 -> 4 -> 2 -> 1 위와 같이 16에서 1을 빼고 나누는것이 아닌 바로 2로 나눠서 푸는것이 연산 수가 적게 나왔다. 나눠서 풀기엔 적합하지 않은 문제였다. 그래서 연산을 하면서 풀기로 하였는데 여기서 DP (동적 프로그래밍)을 사용하여서 풀어야 한다는것을 알게..