C++/자료구조와 알고리듬7 7. Implementation 7.1 Implementation해커랭크3DSurface) 공간지각력 싸움.#pragma once#include using namespace std;int surfaceArea(vector> A) { int H = A.size(); int W = A[0].size(); int ResultArea = 0; for (int i = 0; i 해커랭크ClimbingTheLeaderboard) 순위를 구하는 문제. 단, 중복제거 로직이 필요한 문제. sort() -> unique() -> erase() 순서의 로직을 통해 중복 제거. 그리고 순서 비교.#pragma once#include #include std::vector climbingLeaderboard(std::vector r.. 2023. 2. 7. 6. Linked list, Hash table 6.1 Linked List Def) Linked List 각 노드가 데이터와 다음 노드의 메모리 주소를 저장하는 자료구조. Note) 장단점 장점1. 자료구조의 크기를 동적으로 조절 가능함. 장점2. 삽입, 삭제할 때 메모리 주소만 바꾸면 되므로 O(1)의 시간복잡도로 가능. 단점1. 임의 접근이 불가능함. 특정 요소에 접근하기 위해서는 O(n)의 시간복잡도로 가능. 단점2. 각 노드가 다음 노드의 메모리 주소도 저장해야 하므로 배열에 비해 공간복잡도가 늘어날 수 있음. 단점3. 연속된 메모리 공간이 아니므로, 캐시 효율성이 비교적 낮음. Note) 구현코드#include using namespace std;template class SNode {publ.. 2022. 12. 30. 5. Dynamic Programming, Backtracking 5.1 Dynamic Programming 5.1-1 Memoization Note) 기존의 피보나치 수열 코드#pragma onceint fibo(int n){ if (1 == n) { return 1; } if (2 == n) { return 1; } return fibo(n - 1) + fibo(n - 2);} Note) 기존 피보나치 수열의 코드를 도식화하면 아래와 같음. 이 경우, n의 크기가 커지면 커질수록 재귀함수의 호출 횟수가 비약적으로 늘어남. 그래서 한 번 계산된 피보나치 값은 저장해둔다면, 꽤나 큰 효과를 얻을 수 있음. 즉, 재귀함수만 사용하는 것이 아닌 저장을 위한 메모리를 적절하게 함께 사용함. 이때 저장을 위한 메모리 사용 기법을 Me.. 2022. 12. 1. 4. Graph, DFS, BFS 4.1 Graph4.1-1 그래프 Def) 그래프(Graph) 개체 간의 연결 관계를 표현할 수 있는 비선형 자료구조 ex. 도시들 간의 연결, 지하철 노선도, SNS 친구 관계도 등 Note) 결국 트리는 그래프의 한 종류이다. 즉, 트리를 추상화하면 그래프가 됨. Note) 그래프의 구성 요소 - 그래프 G = (V, E) - 정점 V(Vertex, Node) 그래프를 구성하는 기본 단위. 노드. 데이터를 저장하거나 상태를 표현 - 엣지 E(Edge, Link) 정점과 정점을 잇는 선. 간선. 방향을 가질 수도 있음. 가중치(Weight)를 가질 수도 있음. Note) 그래프 관련 용어가중치(Weight)엣지에 .. 2022. 11. 22. 이전 1 2 다음
