문제https://www.acmicpc.net/problem/1003풀이과정오늘 문제 푸는 날인지 모르고 있다가 급하게 푸느라 조금 쉬운 문제를 풀었다. 피보나치 함수를 fibonacci(N) 이라고 두고 재귀로 구하는 함수가 주어지는데 이 때 fibonacci(0)과 fibonacci(1)이 몇 번 호출되는지 구하면 되는 문제이다. 그냥 호출될 때마다 배열에 숫자를 올려서 나중에 출력했다.소스코드#include using namespace std; int cnt[2]; int fibonacci(int n) { if (n == 0) { cnt[0]++; } else if (n == 1) { cnt[1]++; } else { return fibonacci(n - 1) + fibonacci(n - 2); }..
문제https://www.acmicpc.net/problem/1463풀이과정기본적인 DP 문제 중 하나이다. D[i] = i를 1로 만드는 데 필요한 최소 연산 횟수라고 놓고 경우의 수를 생각해보니 아래와 같았다. i가 3으로 나누어 떨어질 경우 D[i/3] + 1 i가 2로 나누어 떨어질 경우 D[i/2] + 1 i에서 1을 빼는 경우 D[i-1] + 1 이렇게 총 세 가지이며 세 가지의 경우 중 최소값을 찾으면 된다.소스코드#include using namespace std; #define MAX 1000001 int D[MAX]; int solution(int N) { if (N==1) return 0; if (D[N] > 0) return D[N]; D[N] = solution(N - 1) + 1..
문제https://www.acmicpc.net/problem/2667풀이과정DFS로 이차원 배열을 모두 탐색하며 끊기는 부분마다 단지번호를 주면 된다. 앞에서 풀었던 DFS를 이용해 이분 그래프의 개수를 출력하는 문제와 비슷하게 풀면 될 것 같아서 그렇게 풀어봤다. 이런 문제는 DFS,BFS 구현에 대해 아무런 지식이 없을 때 절대 못 풀었었는데 이제는 조금 감이 오는 것 같아서 좋다.소스코드#include #include #include #include using namespace std; vector a[26]; int visited[26][26]; int dx[4] = { 0,0,1,-1 }; int dy[4] = { 1,-1,0,0 }; int n; int ans[25 * 25]; // n 최대값..
문제https://www.acmicpc.net/problem/2331풀이과정먼저 문제에서 주어진 규칙대로 벡터에 수열을 생성했다. 그리고 주어진 규칙대로 만들어진 수가 이미 수열에 존재하면 그 수가 존재하는 index 까지의 개수를 출력되도록 만들었다.소스코드#include #include #include using namespace std; vector D; int A, P; int solution(int A) { D.push_back(A); while (1) { int next_num=0; while (A != 0) { next_num += pow(A % 10, P); A /= 10; } for (int i = 0; i < D.size(); i++) { if (D[i] == next_num) retu..
문제https://www.acmicpc.net/problem/10451풀이과정순열 그래프에서 순열 사이클의 개수를 구하는 프로그램을 만드는 문제이다. 문제를 보면 dfs를 활용하는 기본적인 문제로 볼 수 있으며, 이제는 기본적으로 dfs를 구현할 줄 알게 됐고 실행이 잘 안되면 생각하며 고쳐갈 수 있게 되었다.문제는 dfs로 탐색을 하며 끊어지는 부분이 나오면 개수를 하나씩 추가하는 식으로 풀었다.이차원 벡터와 chk[]를 int형으로 두고 풀었는데 굳이 이차원 벡터를 쓸 필요도 없을 것 같고 chk[]는 bool형으로 쓰는 게 더 가독성이 높을 것 같다. 다음에 dfs 문제를 풀 때는 bool형으로 써야겠다.그리고 fiil() 함수를 통해 벡터를 다시 0으로 초기화 해주고 memset()을 이용해 ch..
문제https://www.acmicpc.net/problem/1707풀이과정주어진 그래프가 이분 그래프인지 아닌지 출력하는 문제이다. 먼저 이분 그래프란 무엇인지 찾아보니 모든 노드를 빨강색 혹은 파랑색으로 칠하는데 같은 색을 가진 노드는 서로 인접하지 않는 위치에 존재하는 그래프이다.이분 그래프인지 아닌지 판별하는 방법은 dfs나 bfs로 그래프를 탐색하며 노드를 색칠하고 색칠되어 있는 노드를 방문할 경우 인접한 노드와 같은 색깔이면 이분 그래프가 아니라고 판별할 수 있다.소스코드#include #include #include using namespace std; vector a[20001]; int color[20001]; void dfs(int node, int c) { color[node] = c..
문제https://www.acmicpc.net/problem/9935풀이과정처음에는 문자열을 처음부터 ans라는 문자열 변수에 하나씩 넣어가며 문자열 끝부터 폭발문자열의 길이만큼의 chk_str을 만들어 폭발문자열과 비교하고 같으면 substr을 통해 ans 문자열에서 폭발문자열을 제거하는 식으로 해결하고자 했다. 하지만 제출결과는 시간 초과가 났다. 그 이유를 살펴보니 입력되는 문자열의 최대길이는 백만이고 시간제한이 1초이므로 시간복잡도 O(N) 정도로 해결해야하는 문제였다.그래서 다시 생각해서 새로운 알고리즘을 생각했다. 입력 문자열을 순차적으로 ans 문자열 변수에 넣는다.만약 넣는 문자가 폭발문자열의 끝 문자와 같다면폭발문자열의 길이만큼 ans 문자열을 검사한다ans의 끝 쪽이 폭발문자열이면 폭발..
문제https://www.acmicpc.net/problem/1260풀이과정DFS와 BFS 구현에 대한 기본적인 문제이다. DFS는 벡터를 이용해 구현했고, BFS는 큐를 이용해 구현하였다. 문제에서 방문할 수 있는 정점이 여러개일 경우에는 정점 번호가 작은 것을 먼저 방문한다는 조건을 주었기 때문에 DFS와 BFS를 실행하기 전에 인접 리스트를 정렬 시켜줬다.소스코드#include #include #include #include using namespace std; int N, M, V; vector a[1001]; bool chk[1001]; void DFS(int node) { chk[node] = true; cout > V; for (int i = 0; i < M; i++) { int x, y; ..
[백준] 11724번 연결 요소의 개수
문제https://www.acmicpc.net/problem/11724풀이과정먼저 문제를 풀기 전에 연결요소에 대한 개념을 찾아봤다. 연결 요소란 1~N까지 정점으로 이루어져있는 그래프가 나누어 존재할 경우 각각의 그래프를 연결 요소라고 한다. 연결 요소에 속한 모든 정점은 연결하는 경로가 있어야 하며, 다른 연결 요소에 속한 정점과 연결하는 경로가 있으면 안된다.아래 그림을 참고하면 쉽게 이해할 수 있다. 이러한 연결 요소의 개수를 세는 방법은 DFS를 이용하여 구현했다. DFS를 이용해 1부터 탐색을 시작하며 DFS(1) 이후에 check[i]가 false로 나오면 연결요소가 하나 더 있다는 뜻으로 해석했다.소스코드#include #include using namespace std; vector a[..