Storage Gonie

cmath의 pow는 double형을 기본적으로 반환한다는 것을 알아두자. double형으로 반환되는 것을 사용하고 싶지 않다면, pow의 결과값을 int형으로 변환해주거나, 직접 구현할 수 있다. # cmath의 pow 사용하는 방법 #include #include using namespace std; int main() { cout

10으로 나누어가며 10으로 나눈 나머지를 찾으면 뒷자리부터 한자리씩 분리할 수 있음. #include using namespace std; int main() { int a = 1352; while(a != 0){ cout

문제 풀이 자세한 풀이 : https://ldgeao99.tistory.com/398 # C++(비재귀 방식으로 구현) #include #include #include using namespace std; int check[300000]; // 99999일 때 9^5 * 5 = 295245 이므로 그냥 300000으로 함. // 다음 방문할 번호 구하는 함수 int get_next(int num, int p) { int next = 0; while(num != 0){ next += pow(num%10, p); num /= 10; } return next; } int main() { // check 배열 초기화 memset(check, 0, sizeof(check)); int node, p; cin >> ..

문제 풀이 자세한 풀이 : https://ldgeao99.tistory.com/398 # C++(dfs탐색을 재귀 구현으로 푼것) #include #include using namespace std; int arr[1001]; // 인접 리스트 bool check[1001]; // 인접 리스트 void dfs(int node); int main() { int t; cin >> t; while(t--){ int v; cin >> v; // 정보를 입력받아 원소가 1개인 인접 리스트 생성 for (int i = 1; i > a; arr[i] = a; } // 다음 테스트 케이스를 위한 초기화 memset(check, false, sizeof(check)); // 탐색이 진행된 횟수 카운트 int ans = ..

break를 사용하면 가장 가까운 범위에 있는 for문만 멈출 뿐 바깥 for문은 계속된다. #include using namespace std; int main() { for (int i = 0; i < 4; i++){ for (int j = 0; j < 3; j++){ if (j == 0){ cout

문제 풀이 자세한 풀이 : https://ldgeao99.tistory.com/398 # C++(색을 모두 칠해준 다음, 모든 간선의 양끝 정점 색을 비교함 => 비효율적) #include #include using namespace std; vector arr[20001]; // 인접 리스트 int color[20001]; // 중복방문을 막기위한 check 배열, 단 방문시 색을 저장함 void dfs(int node, int c);// DFS탐색을 진행하며 1, 2를 번갈아가며 정점에 색칠하는 함수 int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); // 테스트 케이스의 개수 입력받기 int k; cin >> k; whi..

문제 풀이 자세한 풀이 : https://ldgeao99.tistory.com/398 # C++ #include #include using namespace std; vector arr[1001]; // 인접 리스트 int check[1001]; // 중복방문을 막기위한 check 배열 void dfs(int node); // DFS 탐색함수 int main() { // cin, cout 속도 빠르게 하기 ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); // 정점의 개수 n과 간선의 개수 m 입력받기 int n, m; cin >> n >> m; // 연결된 두 정점들에 대한 정보를 받아서 인접리스트 생성 for(int i = 0; i < m; i..

개념을 적용한 문제풀이 # 이진트리의 프리오더, 인오더, 포스트오더 순서를 출력하는 문제 - https://www.acmicpc.net/problem/1991 - 코드상에서 3가지 방법의 차이는 출력을 언제 하는가의 차이이다. - 알파벳을 숫자화 해서 A : 0, B : 1, C : 2, ... i의 값으로 사용하고, 2차원 배열로 A[i][0] = 왼쪽 자식 값, A[i][1] = 오른쪽 자식 값을 저장하는 방식으로 트리를 저장하였음. 자식이 없는 경우 -1을 넣어주어 재귀호출이 끝나도록 하였음. * 이진트리의 순회는 왼쪽 자식과 오른쪽 자식의 값을 구분해 가지고 있는게 출력하기 편함. # 트리의 부모 찾기 - https://www.acmicpc.net/problem/11725 - DFS, BFS 두 ..

트리의 순회(Tree Traversal) - 트리도 그래프이기 때문에 DFS와 BFS 방식 모두 가능하다. - 그런데 트리에서만 가능한 아래의 3가지 방법이 있다.(각각의 차이는 루트 노드의 방문을 언제 하냐의 차이) - 이진트리에서는 아래의 3가지 방법이 모두 가능한데, 자식이 여러개인 트리에서는 '프리오더'와 '포스트오더'만 가능하다. 그 이유는 자식이 여러개인 트리의 경우, '인오더 방식'에서 출력이 어느 부분에 위치해야할지 가늠할 수 없기 때문이다. 프리오더 루트 L R 루트 children 인오더 L 루트 R 포스트오더 L R 루트 루트 children # Pre-order(전위순회) * 그래프의 DFS와 순서가 같음. 1) 루트노드 방문 2) 왼쪽 자식 노드를 루트로 하는 서브 트리를 프리오더..

트리의 개념 # 트리(Tree) - 자료구조의 일종으로 '사이클이 없는 그래프'를 Tree 라고 함(이 이유로 임의의 두 정점 사이의 경로는 오직 1개이다) 따라서, 정점의 개수는 V개이고, 간선의 개수는 V-1개 이다. - 트리는 임의의 두 정점 간의 경로가 오직 1개이기 때문에, BFS를 이용하여 찾아낸 그 경로가 바로 최단거리가 된다. - 주의할점이 있는데 (True) "Tree" 이면 "정점의 개수는 V개이고, 간선의 개수는 V-1개 이다." (False) "정점의 개수는 V개이고, 간선의 개수는 V-1개 이다." 이면 "Tree"이다. 그 이유는 아래와 같은경우 정점이 6개이고, 간선이 5개인데 사이클이 있어서 트리라고 볼 수 없는 반례가 존재하기 때문이다. (True) "정점의 개수는 V개, ..