CodeZip

그리디 알고리즘이란?현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘 ! 탐욕법으로 얻은 해가 최적의 해가 되는 상황인지, 추론할 수 있어야 함. 수행과정1. 현재 상태에서 최선의 해 선택2. 현재 선택한 해의 적절성 검사3. 현재까지의 해 집합이 문제를 해결할 수 있는지 검사  백준 : 1715https://www.acmicpc.net/problem/1715priority queue를 활용해 가장 적은 카드묶음 순으로 뽑는다.#include #include #include #include int main(){ std::ios::sync_with_stdio(false); std::cin.tie(NULL); std::cout.tie(NULL)..

트라이문자열 검색을 빠르게 할 수 있도록 설계한 트리- N진 트리 : 문자 종류의 개수에 따라 N이 결정된다. (알파벳 N == 26)- 루트 노드는 항상 ' ' (공백) 이진 트리모든 노드의 자식 노드의 개수가 2 이하인 트리편향 이진 트리, 포화 이진 트리, 완전 이진 트리가 있다. 세그먼트 트리데이터의 구간합과 데이터 업데이트를 빠르게 수행하기 위해 고안해 낸 자료구조구간 합, 최대 값, 최소 값 등을 구할 때 이용할 수 있다!  [참고]주홍철, , 길벗(2022), p426, 435

*노드 수 V, 에지 수 E 유니온 파인드Union 연산 : 특정 2개의 노드를 연결해 하나의 집합으로 묶는 연산Find 연산 : 두 노드가 같은 집합에 속해 있는지 확인하는 연산 위상 정렬'사이클이 없는' 방향 그래프에서 노드 순서를 찾는 알고리즘사이클이 존재하면 안됨! 다익스트라'에지가 모두 양수'인 그래프에서 그래프에서 최단 거리를 구하는 알고리즘시간복잡도 : O(E logV)   벨만-포드그래프에서 최단 거리를 구하는 알고리즘.음수 가중치 에지가 있어도 가능.음수 사이클의 존재 여부를 판단할 수도 있다.시간복잡도 : O(VE) 플로이드-워셜그래프에서 모든 노드 간에 최단 경로를 탐색하는 알고리즘음수 가중치 에지 있어도 가능DP원리를 이용해 접근시간복잡도 : O(V^3) 최소신장트리그래프에서 모든 ..

너비 우선 탐색?그래프 완전 탐색 방법 중 하나.시작 노드에서 출발해 시작노드를 기준으로 가까운 노드 먼저 방문하며 탐색하는 알고리즘 노드 수 : V, 에지 수 : E 일 때시간 복잡도 : O(V+E)  구현 시 Queue 자료구조를 이용한다.  백준 1260번https://www.acmicpc.net/problem/1260#include #include #include #include std::vector> edges;std::vector visited;void DFS(int node){ if (visited[node]) { return; } std::cout queue; visited[node] = true; queue.push(node); while (!queue.empty()) { std::..

깊이 우선 탐색?그래프 완전 탐색 기법 중 하나.시작 노드에서 출발, 한쪽 분기로 최대 깊이 까지 탐색한 후, 다른 쪽 분기로 이동하여 최대 깊이까지 탐색, 이를 반복하는 알고리즘. 노드 수 : V, 에지 수 : E 일 때시간 복잡도 : O(V+E) 구현 시 재귀 함수를 이용하므로 스택 오버플로*에 주의! *스택 오버플로 : 재귀 함수가 호출 될 떄마다 스택 영역에 프레임이 쌓여 스택 메모리가 과부하를 겪는 현상.재귀 함수 사용 시 중단 조건을 정확히 설정하자. 백준 : 11724번https://www.acmicpc.net/problem/11724#include #include std::vector> edges;std::vector visited;void DFS(int node){ if (visited[..

투 포인터 2개의 포인터로 시간 복잡도를 최적화 하는 알고리즘!시간복잡도 : O(N) 슬라이딩 윈도우2개의 포인터로 범위를 지정한 뒤, 범위를 유지한 채로 이동하며 문제 해결! 투포인터와 매우 유사하다. 시간복잡도 : O(N)   투 포인터) 백준 1253번https://www.acmicpc.net/problem/1253#include #include #include int main(){ std::ios::sync_with_stdio(false); std::cin.tie(NULL); std::cout.tie(NULL); int N; std::cin >> N; std::vector vec(N, 0); for (int i = 0; i > vec[i]; } st..

배열 A의 'A[0]부터 A[i] 까지의 합'을 '합 배열 S'에 미리 저장해둔다.S[i] = S[i-1] + A[i] 나중에 구간 합을 구할 때는 구간합 = S[j] - S[i-1] 합 배열을 사용해 구간 합을 구하면 O(N) 에서 O(1)로 시간 복잡도를 크게 줄일 수 있다.!  ex) 백준 11659#include #include int main(){ int N, M; std::cin >> N >> M; std::vector Sum = std::vector(N+1,0); for (int i = 1; i > Sum[i]; Sum[i] += Sum[i - 1]; } int i, j; while (M--) { std::cin >> i >> j; std::cout

1. 어떤 알고리즘을 사용할지 문제 제한을 보고 결정한다!1억개 == 1초! ex) 시간제한 1초,   case 10000개 -> 최대 O(N^2)의 시간복잡도를 가진 알고리즘을 사용해야 한다.물론 더 빠른 알고리즘을 사용할수록 좋음. 2. 디버깅을 잘 하자!작은 단위로 구현하고 단계별로 처리해야 시간 낭비를 줄일 수 있다. 3. 메모하기!문제가 너무 길고 조건이 많아 놓치는 것이 있을 수 있다.문제를 읽으며 중요한 것은 요약해서 메모하고, 백지에 그래프든 뭐든 그려보며 생각을 정리하자.  [참고] https://zoosso.tistory.com/883 [알고리즘] 코딩 테스트 문제 풀 때, 시간 복잡도 계산해보기시간 복잡도 계산해보기 프로그램 작성 전에 어느정도 Input Data의 범위와 Logic ..

Data Assets* Filled with internal data types    - Filled through the editor* Great for smaller Pieces of information    - Handles hierarchies and displays nested information wellIdeal for smaller pieces of information    - Intended for single items but easily expanded* Smaller sets of information mean faster loading Case Examples:- Single Pieces of Information ( Enemy A, Enemy B ...) - Small Gro..

TObjectPtr과 Raw Pointer 중 어떤 것을 사용해야 할까?-> TObjectPtr를 사용하자 이유1. UE5에서는 Raw 포인터 대신 TObjectPtr를 사용하는 것을 권장하고 있다. 2. TObjectPtr은 또한 포인터가 초기화되도록 보장한다. ( 새 포인터 변수를 생성하면 nullptr로 초기화하는 것을 잊어버릴 수 있다.)  예외 -> UFUNTION() UFunction은 인자로 TObjectPtr을 받을 수 없다. 이때는 Raw Pointer를 사용해야 한다.  [참고]https://forums.unrealengine.com/t/why-should-i-replace-raw-pointers-with-tobjectptr/232781/13