문제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[..
문제https://www.acmicpc.net/problem/2193풀이과정쉬운 계단 수, 오르막 수를 풀어보고 나니 쉽게 풀 수 있었다. 먼저, D[1][0] 은 이친수의 조건 1규칙을 위반하기 때문에 0개였으며 D[1][1] 은 그냥 한개이다. 그 이후로 계속 생각해 본 결과 D[i][0]은 길이가 i-1인 수의 마지막 숫자가 0과 1일 경우의 이친수 개수를 더하면 됐다. 하지만 D[i][1] 의 경우는 이친수의 조건 2번을 적용하면 길이가 i-1이고 마지막 숫자가 0인 경우의 이친수의 개수와 같다는 사실을 알 수 있다. 이러한 결과를 식으로 나타내면 아래와 같다. D[i][0] = D[i-1][0] + D[i-1][1] D[i][1] = D[i-1][0] 소스코드#include using names..
문제https://www.acmicpc.net/problem/11057풀이과정쉬운 계단 수 문제와 비슷한 문제이다. D[i][j] = 숫자의 길이가 i이며 마지막 숫자가 j인 수의 오르막 수의 개수라고 정하고 규칙을 찾아봤다. 그 결과로 길이가 i, 마지막 숫자가 j인 숫자의 오르막 수의 개수는 길이가 i-1이고, 마지막 숫자가 j 이하인 숫자들의 오르막 개수를 모두 더하면 됐다. 식으로 나타내보면 아래와 같다. D[i][j] += D[i-1][k] (0#include using namespace std; #define NUM_MAX 10 // 0~9 까지의 수 (10개) #define mod 10007 int N,ans; long long D[1001][NUM_MAX]; // D[i][j] = 수의 길..
문제 출처 : https://www.acmicpc.net/problem/2309 풀이과정 아홉명의 난쟁이 중에 진짜 난쟁이 일곱명을 추려내는 문제이다. 일곱 난쟁이의 키의 합은 100이라는 사실을 이용해 풀이하면 된다. 9명 중 2명을 선택해 난쟁이가 아니라고 생각하고 나머지 7명의 키 합이 100이면 된다.9명 중 2명을 선택하는 경우의 수가 36가지 이므로 완전 탐색으로 풀었다.코드가 더러운 것 같다. 불필요한 과정을 생각해서 코드를 깔끔하게 바꾸는 연습도 해야겠다. 소스코드 123456789101112131415161718192021222324252627282930313233343536373839404142434445#include #include #include using namespace std..
문제 출처 : https://www.acmicpc.net/problem/11502 풀이과정 D[i] 를 붕어빵 i개를 팔아서 얻을 수 있는 최대 수익이라고 할 때,가능한 경우를 생각해보면 붕어빵 1개를 P[1]에 팔 경우에 남은 붕어빵의 개수는 i-1개가 되는데이 경우에 P[1]+D[i-1] 라는 생각을 할 수 있다. 하지만 D[i]는 얻을 수 있는 '최대' 수익이기 때문에 최대값만 저장해야한다. 그러므로 아래와 같은 식을 생각할 수 있다.D[i] = max(D[i],D[i-j]+P[j])이러한 식을 이용하면 쉽게 해결할 수 있다.DP문제는 많이 풀어보면 감이 온다고 했는데 점점 감이 오는거 같아 기분좋다. 소스코드 1234567891011121314151617181920212223242526272829..