[백준] 5639번 이진 탐색 트리 (C++) - binary search tree
2022. 11. 21. 14:05
solving/C, C++
발상 우선 전위 탐색을 통해 얻은 tree가 주어지므로, 이를 배열에 입력받는다. 그리고 아래 그림과 같은 이분 탐색을 거치면, 후위 탐색으로 배열을 바꿀 수 있다. 전위 탐색 : root -> left -> right 후위 탐색 : left -> right -> root 이므로 순서를 바꾸어준다. 소스코드 #include #include using namespace std; int tree[10001]; void postorder(int start, int end){ if(start == end) { cout
[백준] 1991번 트리 순회 (C++) - preorder, inorder, postorder
2022. 11. 21. 02:29
solving/C, C++
발상 트리 순회에는 전위 순회 (postorder), 중위 순회 (inorder), 후위 순회 (postorder) 이 있다. 전위 순회 : node -> left -> right 중위 순회 : left -> node -> right 후위 순회 : left -> right -> node 모두 node 자신의 방문순서를 기준으로 생각하면 된다. 각각의 수도코드는 다음과 같다. void postorder{ cout char; if(node->left != NULL) postorder(node->left); if(node->right != NULL) postorder(node->right); } void inorder{ if(node->left != NULL) inorder(node->left); cout c..
[알고리즘] 그래프와 관련된 개념
2022. 11. 12. 15:51
스스로 공부하기/알고리즘
그래프 (graph) 유향 그래프, 방향 그래프 (directed graph) 루프 (loop) 다중 그래프 (multigraph) 가중 그래프 (weighted graph) 경로 (path) 단순 경로 (simple path) 연결과 강한 연결 (connectivity, strong connectivity) 순환 (cycle) 단순 순환 (simple cycle) 차수 (degree) 연결 그래프 (connected graph) 연결 요소 (connected component) 유향 비순환 그래프 (directly acyclic graph, DAG) 위상 정렬 (topological sort) 완전 그래프 (complete graph) 이분 그래프 (bipartite graph) 인접 행렬과 서로 다른..
[Javascript] 6장. 여러 자료를 한꺼번에 담는 객체
2022. 11. 11. 19:05
스스로 공부하기/Javascript
06-1. 객체란? 객체 (object) 란, 자바스크립트 자료형의 일종으로, 여러 변수와 함수 등 여러 가지 자료형을 묶은 하나의 자료형 ("복합 자료형") 자바스크립트는 객체 기반 언어이므로, 객체는 자바스크립트에서 자료를 처리하고 저장하는 기본 단위가 된다. 객체 간단히 살펴보기 var book = { title : "자바스크립트", // 자료형 : string author : "홍길동", pages : 500, price : 1500, .... }; // :와 ,으로 객체의 변수를 구분한다. 이렇게 한 개의 변수 안에 여러 가지 변수와 함수를 묶어서 저장한다. 선언방식에는 두가지가 있다. (06-2에서 다룸) ex) 회원가입 -> 회원의 정보를 "회원" 객체에 여러가지 정보를 묶어 저장하는 방식으..
[백준] 1325번 효율적인 해킹 - C++ (DFS, 그래프)
2022. 11. 10. 18:56
solving/C, C++
발상 1. 우선 그래프를 이용하는 문제인데 - A가 B를 신뢰할 경우 B를 해킹하면 A도 해킹할 수 있다는 것은, B가 부모 노드이고 A가 자식 노드인 것으로 생각하였다. B->A로 간선이 이어져서 B에서 해킹할 수 있는 자식 노드들을 모두 동시에 해킹할 수 있는 것들로 보았다. 2. DFS를 이용해 1~N까지 각 노드에서 출발했을 때 총 몇 개의 노드를 방문할 수 있는지를 계산하면 되는 문제이다. 3. dfs 함수를 int로 설정하였다. for문을 이용해 1~N까지 반복문을 설정하고, 각 node에서 출발하여 새로운 node를 방문할 때 (check값이 false인 자식 노드) ans에 해당 node에서의 dfs 값을 더하도록 했다. (해당 노드+거기에 연결된 자식 노드의 수) 4. 반환된 ans값을 ..
[백준] 11724번 연결 요소의 개수 - C++ (DFS, 그래프)
2022. 11. 10. 18:03
solving/C, C++
풀이에 https://velog.io/@polynomeer/%EC%97%B0%EA%B2%B0-%EC%9A%94%EC%86%8CConnected-Component 포스팅을 참고하였음을 밝힙니다. 발상 1. 그래프 + 주어진 그래프의 정점들을 DFS를 이용해 탐색하여 연결 요소의 개수를 밝히는 문제이다. 2. 그래프는 우선 C언어에 내장된 vector를 이용해 구현하고, 방향이 없는 그래프이므로 하나를 입력받을 때마다 v->u, u->v 두 가지 모두를 입력한다, 3. DFS를 이용하면 한 개의 연결 요소 그래프에 속한 노드를 전부 탐색할 수 있으므로, false값을 가진 node에 대해 DFS를 수행해 해당 연결 요소의 노드를 전부 탐색하고 답에 +=1을 해준다. 그리고 또 false값을 가진 node가 ..
[알고리즘] 빠른 거듭제곱 알고리즘 (bit set을 이용한 빠른 거듭제곱)
2022. 11. 1. 16:15
스스로 공부하기/알고리즘
상아탑 6주차 중 거듭제곱을 빠르게 계산하는 알고리즘 (ex. 3^2500000000....) 우선 지수를 이진법으로 표현하고, 이것을 exp로 설정 base = 밑 #include int power(base, exp) { int ret = 1; // 결과값을 1로 우선 설정 while(exp){ //exp가 존재하는 동안 = 자릿수를 모두 이동하는 동안 if(exp & 1 == 1) ret *= base; //1번째 자리가 1일 경우 ret*=base exp >>= 1; //오른쪽 옆으로 한 칸씩 이동 base *= base; //base를 제곱해줌. 이진법에 따라 자릿수 이동할 때마다 실제 숫자는 제곱 } return ret; //ret값을 반환 } 위와 같은 코드를 이용해 bit set을 응용한 빠..
[백준] 14501번 퇴사 - C++ (Bruteforce, 재귀함수)
2022. 10. 8. 18:57
solving/C, C++
발상 1. 우선 알고리즘 중 bruteforce를 이용해야겠다고 생각했다. 1~N까지 날짜 중 되는 상담을 잡았을 때의 최대 값을 구하는 것이고, A일이라면 A+1일의 상담에 걸리는 날짜부터 N까지를 다시 탐색하는 방법으로 문제를 해결하면 될 것이라고 생각했다. 2. 종료하는 분기점은 date가 N보다 클 때이다. 이 때 종료하고, 그 이전의 cost값을 v에 push해준다. 그런데 date=N+1일 때는 실제로는 직전에 시작한 상담이 마지막 날에 정확히 끝나는 것이므로, (예로, N이 7일 때, 5일에 3만큼의 상담을 했다면, date=8이 되어 종료되지만 실제로는 5, 6, 7일 3일간 상담을 하고 8로 넘어가므로 date=8도 유효한 값이다.) 이 때의 cost값도 v에 push해준 뒤 return..