TLIANGLE PATH 문제 (0,0)부터 시작해서 아래 or 아래우측으로 이동 가능하다이동한 경로의 숫자를 모두 더한 값이최대가 되는 경로와 합을 출력하시오 구현 주의사항- 동적계획법 코드 템플릿동적계획법을 이용한 코드 작성 시에"기저사항 -> 캐시확인 -> 연산" 방식으로 작성하면 편하다 - 함수 반환 타입문제가 원하는 최대가 되는 합즉, 지금까지의 합을 반환하도록 구현하면 된다참고로, 재귀함수 특성 상 위에서 부터 합이 추가되는 것이 아닌끝에서부터 추가 되는 방식이다 (추후 확인 가능) - 기저사항N을 삼각형의 높이라고 가정하고y좌표와 x좌표로 이동을 하는 경우에높이 N-1을 초과하는 y좌표의 이동은 불가능하다그렇기에 y좌표가 N-1이 되면, 자신의 값을 반환하면서 종료해야 한다혹은 y좌표가 N이..
동적 계획법 (Dynamic Programming, DP)복잡한 문제를 작은 하위 문제들로 나누어 해결하고,그 결과를 저장해 두었다가 재활용함으로써중복 계산을 피하고 효율적으로 문제를 해결하는 알고리즘 설계 기법이다 동적 계획법 조건아래의 두 가지 조건을 모두 만족해야 한다1) 최적 부분 구조 (Optimal Substructure):큰 문제의 최적 해가 작은 하위 문제들의 최적 해를 포함하고 있는 구조2) 중복되는 하위 문제 (Overlapping Subproblems):동일한 하위 문제가 여러 번 반복적으로 나타나는 경우동적 계획법 방식1) Top-Down (재귀 + 메모이제이션):큰 문제에서 시작하여 재귀적으로 하위 문제를 해결하면서 결과를 저장하고메모이제이션을 활용한다 2) Bottom-Up (반..
주의사항미로 맵을 생성하는 경우에Prim 알고리즘을 사용하면 쉽게 맵을 생성할 수 있다 코드에 앞서기본적으로 타일은 WALL(빨강)과 EMPTY(초록)로 구분되어 있다Prim 알고리즘을 적용하기 전에y와 x의 2의 배수 위치에는 모두 WALL로 처리한다이렇게 하면 아래와 같이 된다 먼저 간선정보를 저장할 edges를 만들어준다그리고 랜덤맵을 만들기 위해서edges의 가중치를 랜덤으로 등록해서 만들어준다 그리고 다익스트라처럼 아래와 같은 세팅이 필요하다우선순위큐, 해당 정점이 포함되었는지를 체크하는 added, 해당 정점이 누구에게 발견되었는지를 위한 parent, 해당 정점에 닿는 최소 간선만을 기록하는 best 이렇게 모든 준비가 끝나면먼저 첫 번째 임의의 정점을 시작점으로 하며우선순위 큐에 넣으며 세..
PRIM 알고리즘과 KRUSKAL 알고리즘의 차이KRUSKAL 알고리즘은간선들을 정렬해서 선택하는 방식으로 진행했다PRIM 알고리즘은 간선들을 선택하는 것은 맞지만탐색처럼 하나의 정점에서 시작한다 PRIM 알고리즘과 DIJKSTRA 알고리즘의 차이임의의 하나의 시작점에서간선을 하나씩 선택해 나간다는 점은 동일하다 다익스트라는 현재 지점까지의 비용과 현재 지점부터 비용을합쳐서 계산한다반면, PRIM은 현재 지점에서 부터의 비용만을 체크해서 후보를 선정한다 사실상 코드는 거의 유사하며다익스트라처럼 우선순위큐를 사용한다 추가적으로,둘의 성격은 다르기에 서로 다른 곳에서 사용된다예를 들어서다익스트라는 여러 길 중에 최단경로를 탐색해서 사용한다PRIM은 사이클이 발생하지 않고 최단으로 한 가지 길을 만드는 데 ..
주의 사항미로 맵을 생성하는 경우에Kruskal 알고리즘을 사용하면 쉽게 맵을 생성할 수 있다 코드에 앞서기본적으로 타일은 WALL(빨강)과 EMPTY(초록)로 구분되어 있다Kruskal 알고리즘을 적용하기 전에y와 x의 2의 배수 위치에는 모두 WALL로 처리한다이렇게 하면 아래와 같이 된다 그리고 각 간선들을 vector로 push_back 해주는데여기서 각각 간선들의 가중치를 랜덤 하게 넣어준다 이렇게 준비를 마치면,vector를 sort해서 가중치가 적은 순으로 정렬한다그리고 Disjoint의 Find와 Merge를 이용해서사이클을 방지하며 길을 뚫어주면 된다 구현 코드void Board::GenerateMap_Kruskal(){ for (int32 y = 0; y edges; // edges ..
스패닝트리(ST)최소의 간선으로 모든 정점을 연결하겠다는 것을 의미한다사이클이 발생하지 않는 것이 특징이고간선 개수는 정점개수-1이 된다최소스패닝트리(MST)가중치(비용)가 최소로 되는 스패닝트리를 의미한다KRUSKAL MST 알고리즘Kruskal 알고리즘이란 그리디를 이용하는 것이 특징이다지금 이 순간에 최적인 답을 선택해 결과 도출한다는 것이다 Kruskal 알고리즘의 내부 동작은 아래와 같다1) 지금 이 순간에 가장 작은 비용들을 선택하기2) 사이클은 발생하지 않도록 해야 한다 가장 작은 비용들을 선택하기 위해서는가중치값이 작은 순으로 정렬을 해놓고 하나씩 선택을 하면 된다사이클 발생 여부를 확인하는 방법은 그룹화(집합) 개념을 이용하면 된다간선 및 정점이 추가되는 경우에서다른 그룹끼리는 사이클이 ..
집합이 필요한 경우모든 유저들이 팀번호를 부여받는 경우를 생각해 보자이러한 경우에서 유저 클래스에 teamId가 있을 것이다그리고 팀 동맹 기능이 추가된 경우에 아래와 같이 코드를 작성할 수 있다찾기 연산은 빠르지만 합치기 연산은 O(N)이 문제가 된다이러한 경우에 집합을 사용하면 효율적이다void Example(){ struct User { int teamId; // TODO }; // TODO : UserManager vector users; for (int i = 0; i users[5] users[5].teamId = users[1].teamId; // 1 // 예시 2) teamId==1인 팀과 teamId==2인 팀이 동맹 for (User& user : users) { if (user..
해시테이블배열이나 리스트는 탐색이 매우 느리다반면, 탐색이 빠른 자료구조는 이진탐색트리가 있다이진탐색트리보다 더 빠른 자료구조가 바로 해시테이블이다탐색뿐 아니라 삽입/삭제/탐색 모두 O(1) 소모된다하지만, 그만큼 공간을 많이 차지한다는 것이 단점이다 테이블 개념해시테이블을 알아보기 전 테이블과 해시 개념을 천천히 알아보자테이블이란 아파트의 우편함과 같다비록 공간을 많이 차지하지만, 삽입/삭제/탐색이 빠르다 예를 들어, 아래의 코드처럼vector의 임의접근을 활용한다면userId를 통해 쉽게 탐색을 할 수 있다그러나, 문제는 유저수가 많으면 많을수록 공간을 너무 많이 차지한다는 것이다 void TestTable(){ struct User { int userId = 0; // 1~999 string..
힙정렬힙정렬은 힙구조의 heapify를 사용하는 것이 핵심이다우선순위 큐에서 최대값 혹은 최소값을 pop 하면서 이를 활용하면쉽게 사용가능하다 힙정렬 사용예시void HeapSort(vector& v){ priority_queue, greater> pq; // O(NlogN) for (int num : v) pq.push(num); v.clear(); // O(NlogN) while (pq.empty() == false) { v.push_back(pq.top()); pq.pop(); }} 병합정렬병합정렬은 분할정복이 핵심이다분할정복 아이디어는 병합정렬뿐아니라 다양하게 활용된다 ex. 멀티스레드 병합정렬의 시간복잡도는쪼개는데 logN이 필요하다그리고 둘을 하나로 합치는데는 N이 필요하다그런데 합치는..
