Now Loading ...
-
-
다익스트라 알고리즘
다익스트라 알고리즘
다익스트라 알고리즘이란, 가중치가 음수가 아닌 그래프에서 임의의 한 노드로부터 다른 모든 노드들로의 최소 거리를 구하는 알고리즘입니다.
알고리즘의 각 단계는 다음과 같습니다.
출발 노드 : K,
노드 a 에서 노드 b 까지 거리 : distance[a][b]
1. 각 노드로의 최소 거리를 저장할 배열 dist를 만들고, 값을 INF로 초기화 시킵니다. dist[K]의 경우 0을 저장합니다.
(INF란 해당 타입이 지원하는 가장 큰 값, 또는 단순히 매우 큰 값입니다.)
2. 현재 노드 K와 연결된 다른 임의의 노드 N이 있을 경우, dist[N]의 값과 dist[K] + distance[K][N]의 값을 비교하여, 후자의 값이 더 작을 경우, dist[K]의 값을 dist[K] + distance[K][N]로 업데이트 합니다.
3. 현재 노드 K와 연결된 모든 노드들에 대하여 단계 2를 수행합니다.
4. 현재 노드 K와 연결된 노드들 중 거리가 가장 짧은 노드로 이동하여 단계 2 ~ 3을 진행합니다.
5. 모든 노드를 방문할 때까지 이를 진행합니다.
예시
다음과 같은 임의의 방향 그래프가 있습니다. 노드 1로부터 다른 노드들로의 최소 거리를 구해보도록 하곘습니다.
i
dist$[i]$
1
0
2
INF
3
INF
4
INF
현재 노드 1과 연결된 노드가 2와 3이 있습니다. 여기서 이 두 노드로의 최소 거리를 구해보도록 하겠습니다.
먼저 현재 노드 1에 대하여 연결된 각 노드에 대해 다음의 비교를 진행해 줍니다. 예를 들어 노드 2의 경우,
dist$[2]$(현재 저장된 노드 2로의 최소거리) 와, 노드 1까지의 최소거리와 노드 1부터 노드 2까지의 거리의 합 ( dist$[1]$ + distance$[1][2]$ ) 을 비교합니다.
지금의 경우, dist$[2]$ 는 INF 의 값을 가지고 있기 때문에, dist$[1]$ + distance$[1][2]$ ( 0 + 2 = 2 ) 의 값으로 업데이트 됩니다.
노드 3도 마찬가지로 dist$[3]$ (INF) > dist$[1]$ (0) + distance$[1][3]$ ( 3 ) 이므로 dist$[3]$의 값도 3으로 업데이트 됩니다.
i
dist$[i]$
1
0
2
2
3
3
4
INF
이제 노드 1과 연결된 노드 2로 이동하여 같은 단계를 반복합니다.
노드 2와 연결된 노드 3에 대하여, 노드 1에서 노드 3으로 가는 거리가 더 짧은지, 아니면 노드 1에서 노드 2를 거쳐 노드 3으로 가는 거리 더 짧은지 확인합니다.
dist$[3]$ (3) 의 값과 dist$[2]$ (2) + distance$[2][3]$ (4) 를 비교했을 때, 전자의 값이 더 작으므로, dist$[3]$의 값은 그대로 유지됩니다.
노드 2와 연결된 노드 4의 경우, dist$[4]$의 값은 INF로 저장되어 있어, dist$[2]$ (2) + distance$[2][4]$ (5) 의 값이 저장됩니다.
i
dist$[i]$
1
0
2
2
3
3
4
7
노드 3으로 이동하여 똑같이 수행합니다.
기존에 저장된 dist$[2]$의 값과 현재 노드 3을 거쳐 노드 2로 가는 것 중 어느 것으 더 짧은지 비교합니다.
dist$[2]$ (2) < dist$[3]$ (3) + distance$[3][2]$ (4)의 값을 비교하였을 때, 전자의 값이 더 작으므로, dist$[2]$의 값은 유지됩니다.
다음으로 연결된 노드 4와도 비교하는데,
dist$[4]$ (7) 의 값과 dist$[3]$ (3) + distance$[3][4]$ (6) 의 값 중 전자의 값이 더 작으므로, dist$[4]$의 값은 그대로 유지됩니다.
최종적으로 각 노드로의 최소 거리는 다음과 같습니다.
i
dist$[i$
1
0
2
2
3
3
4
7
p. 1753 최단경로
문제
방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.
입력
첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.
출력
첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력한다. 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다.
제가 다익스트라 알고리즘을 알게 해준 아주 고마운 문제입니다….
보통 다익스트라 알고리즘을 구현할 때 자주 사용되는 것이 우선순위 큐 입니다.
기존의 그래프 탐색 방법인 bfs와 비슷하게, 방문한 노드를 큐에 저장하여 탐색을 진행합니다.
그러나 조금 다른 점은 우선순위 큐에 각 노드와의 거리를 -기호를 붙여 음수의 형태로 저장합니다. 그렇게 될 경우, 절댓값이 가장 작은 값, 즉 가장 거리가 짧은 노드가 우선순위 큐의 top에 위치하게 되어, 그래프 탐색을 진행합니다.
코드는 다음과 같습니다.
Code
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
#define MAX 20001
#define INF 210000000
int V,E,K;
vector<pair<int,int>> graph[MAX];
priority_queue<pair<int, int>> pq;
int _min[MAX];
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> V >> E >> K;
while(E--){
int u, v, w;
cin >> u >> v >> w;
graph[u].push_back({v,w});
}
for(int i = 1; i <= V; i++) _min[i] = INF;
pq.push({0, K}), _min[K] = 0;
while(!pq.empty()){
int cur = pq.top().second;
int distance = -pq.top().first;
pq.pop();
for(int i = 0; i < graph[cur].size(); i++){
int next = graph[cur][i].first;
int nextDistance = graph[cur][i].second;
if(_min[next] > distance + nextDistance)
_min[next] = distance + nextDistance, pq.push({-_min[next], next});
}
}
for(int i = 1; i <= V; i++){
if(_min[i] == INF) cout << "INF" << '\n';
else cout << _min[i] << '\n';
}
}
메모리
시간
9184 KB
88 ms
사실 이 문제는 제가 굉장히 애를 썼던 문제였습니다. 처음 봤을 때는 쉬운 문제겠구나 싶었는데, 생각보다 어떻게 해야할 지 애를 먹었습니다… 그러던 중 다익스트라 알고리즘을 알게 되었고, 간단히 풀 수 있었습니다…
p. 1916 최소비용 구하기
문제
N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다.
입력
첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다.
그리고 M+3째 줄에는 우리가 구하고자 하는 구간 출발점의 도시번호와 도착점의 도시번호가 주어진다. 출발점에서 도착점을 갈 수 있는 경우만 입력으로 주어진다.
출력
첫째 줄에 출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 출력한다.
위의 p. 1753 최단경로 문제와 같은 문제입니다. 여기서 다른 점은 위의 문제는 모든 노드로의 최소 경로를 구했다면, 이 문제는 특정 노드로의 최소 경로를 구하면 되는 문제입니다. 코드는 다음과 같습니다.
Code
#include<iostream>
#include<vector>
#include<queue>
#define MAX 1001
#define INF 210000000
using namespace std;
int N, M, start, _end;
vector<pair<int, int>> buses[MAX];
priority_queue<pair<int, int>> pq;
int smallest[MAX];
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> N >> M;
while(M--){
int cost;
cin >> start >> _end >> cost;
buses[start].push_back({_end, cost});
}
for(int i = 1; i <= N; i++)
smallest[i] = INF;
cin >> start >> _end;
pq.push({0, start}), smallest[start] = 0;
while(!pq.empty()){
int cur = pq.top().second;
int cost = -pq.top().first;
pq.pop();
if(cost > smallest[cur]) continue;
for(int i = 0; i < buses[cur].size(); i++){
int next = buses[cur][i].first;
int nextCost = buses[cur][i].second;
if(smallest[next] > nextCost + cost)
smallest[next] = nextCost + cost, pq.push({-smallest[next], next});
}
}
cout << smallest[_end];
return 0;
}
메모리
시간
4744 KB
28 ms
-
호시노 애니메이션 (5)
진행 상황
3인칭 카메라
에셋 스토어의 무료로 주어지는 Starter Assets을 사용하였습니다.
기본적으로 캐릭터의 점프, 이동과 마우스 회전에 따른 카메라 회전 기능이 스크립트로 제공되어 덕을 많이 보았습니다.
하루만 더 빨리 알았더라면..
애니메이션
캐릭터의 기본적인 자세는 다음과 같이 실제 게임 내에서 사용되는 애니메이션을 사용하였습니다.
확실히 제공된 애니메이션을 사용해보니 제가 만들려고 시도한 것보다 훨씬 자연스러워서 보기 좋았습니다.
다리 모션 구현
그러나 문제점이 있었습니다.
바로 제공되는 애니메이션의 수가 그리 많이 않았다는 것입니다.
제공되는 애니메이션은 위가 끝이었고, 움직임과 관련된 애니메이션은 밑의 앞으로 뛰는 애니메이션만 존재헀습니다.
제가 원하고자 하는 바는 캐릭터는 한 방향을 조준을 유지하되, 이동 방향에 맞추어 알맞은 다리 모션을 취하도록 하고 싶었습니다.
그래서 저는 언리얼 공부 중 알게된 믹사모라는 오토 리깅 사이트에서 필요한 애니메이션을 구하였습니다.
이 사이트에서는 다양한 애니메이션이 존재해서, 제가 원하는 애니메이션을 어렵지 않게 찾을 수 있었습니다.
그러나 위 사진을 보시면 아시겠지만, 믹사모 사이트는 캐릭터 모델을 업로드하면 이를 자동으로 리깅을 해주지만, 총기는 적용이 되지 않는다는 한계가 있었습니다.
.
.
곰곰이 생각을 해보았는데, 결국 제가 여분의 애니메이션을 구한 이유는 총구는 한곳을 유지하되 이동 방향에 따른 다리 모션을 구하기 위함이었습니다.
그래서 유니티에 아바타 마스크라는 것을 사용했습니다. 아바타 마스크는 애니메이션을 캐릭터의 특정 부위에만 적용시킬 수 있게 도와주는 역할을 합니다. 캐릭터의 상체 부분은 제공되는 애니메이션이 적용되고, 하체 부분은 제가 따로 구한 애니메이션이 적용되도록 하였습니다.
에임 상,하 구현
다음으로 제가 원하는 것은 카메라 상하 각도에 맞춰 캐릭터 조준 모션 또한 위아래로 변환되게끔 하고 싶었습니다.
유니티에 blend Tree 라고 언리얼 엔진에서의 blend space와 같은 역할을 가진 것이 있었습니다.
언리얼 엔진에서의 경험을 되살려 따로 구현하는데는 어렵지 않았습니다. 헛되지 않았구나
Pitch라는 float형 변수를 만들었고, 값은 Starter Assets에서 제공되는 카메라 스크립트에서 카메라 높이 값을 가져오게끔 하였습니다.
제공되는 기본 사격 자세에서 척추 뼈들의 회전값을 변경시켜 위, 중간, 아래를 조준하는 세가지 모션을 만들었습니다.
.
총기의 뼈대가 손 뼈대에 귀속되어 있는 것이 아닌, 캐릭터와 독립된 개체로서 존재했습니다…
위와 같이 총기 뼈대와 캐릭터 뼈대가 같은 부모를 가지고 있어, 애니메이션의 각 키프레임마다 총기의 회전 값은 물론, 위치 값까지 함께 수정해주어야 했습니다.
그렇다고 현재 총기의 뼈대를 수정하여 손에 귀속되도록 하고자 하였으나, 이 경우 기존에 제공되던 모든 애니메이션의 총기 뼈대 값을 다시 설정해야 했기에 번거로웠고, 총기 뼈대의 XYZ축도 이상하게 적용되어 있어, 단순히 총기가 앞으로 향하게 하는데도 XYZ 회전값을 모두 수정해주어야 했습니다..
이래도 문제, 저래도 문제, 제가 선택한 방법은 바로, 노가다.
아직 유니티에 대한 지식이 그리 많지 않던 저는 노가다를 통해 각각의 모션을 만들었습니다.
머리가 나쁘면 몸이 고생한다는데, 몸이 좋아서 다행입니다.
.
.
그 외에도, 조준 기능, 조준 시 카메라 줌인 등등 필요한 기능은 Starter Assets의 스크립트를 수정하여 구현하였습니다.
진행 상황 영상
Game_project
· 2024-08-20
-
호시노 애니메이션 (4)
여행을 다니는 동안 곰곰히 생각해보았습니다.
역시나 가장 큰 문제는 모델링. 모델링이 가장 힘든 작업이었는데, 과연 내가 다른 캐릭터들도 모델링을 할 수 있는가.
할 수는 있겠지만 시간이 너무 오래 걸릴 것 같다고 생각이 들었습니다.
그래서 생각해낸 점은 게임 어플 내에서 사용되는 3D 모델을 사용하는 것.
넥슨 게임 IP 사용가이드
이를 읽어보니, UGC ( 2차 창작물 )을 통해 금전적 이득을 얻으면 안되고, 비영리 목적을 위해 게임을 제작하고자 하는 경우 넥슨 고객센터에 개별적으로 문의를 넣으면 된다고 합니다.
저는 개인 공부, 심심풀이를 목적으로 게임을 제작하고, 이후 결과물을 배포하여 상업적으로 사용할 생각이 없기 때문에, 문의는 필요 없을 것 같습니다.
본격적으로 핸드폰을 데스크탑과 연결해서 블루아카이브 파일을 가져와서 모델링을 추출해보겠습니다.
찾아보니 이 과정에 Asset Studio라는 프로그램이 사용된다고 합니다.
https://github.com/Perfare/AssetStudio/releases
여기서 다운 받아주고, .bundle 형식의 파일을 가져와보았습니다.
텍스처 파일, mesh 파일, 애니메이션 파일들이 보이는데 추출을 진행하면,
이런 파일들이 나타났는데, .fbx 파일과, 텍스처 이미지 파일이 있습니다.
블렌더에서 먼저 .fbx 파일을 가져와서 실행해본 결과 정상적으로 작동되어, 언리얼 엔진으로 추출을 진행했습니다.
.
.
.
근데 문제가 있었는데, 추출을 진행하면 언리얼 엔진 프로그램 자체가 작동되질 않았습니다.
원인을 찾아봐도 도저히 알 수가 없었는데, 그래서 저는 유니티 엔진에서 .fbx 파일을 가져와 보았습니다.
결과는 성공 !
캐릭터 모델은 물론, 게임에서 사용되는 애니메이션 파일 또한 제대로 작동되는 것을 볼 수가 있었습니다.
.
.
아무래도 게임 제작을 유니티로 진행해야 할 것 같습니다..
다시 처음부터 배워야 한다는 점이 아쉽지만, 큰 틀은 언리얼 엔진과 비슷할 것 같고, 다른 캐릭터 모델링에 들어갈 시간을 생각하면 이 쪽이 더 나은 것 같습니다.
게임 구상
초기 기획으로는 오버워치와 같이 N vs N 형식의 3인칭 액션 슈팅 게임을 만들려고 했는데, 문제가 생겼습니다.
https://keyzard.org/devlib/tt/119
제가 하고자 한 바를 이미 먼저 하고 계신 분이 있었습니다.
끄응.. 3인칭 액션 슈팅이라는 장르는 버리고 싶지 않은데,,
차별화를 둘 필요가 있었습니다.
그래서 생각해낸 점이 3인칭 슈팅 게임 장르는 유지하되, 오버워치 형식의 N vs N이 아닌, PVE 형식의 디펜스 느낌으로 생각해보았습니다.
이는 제가 예전에 즐겨하던 팀포트리스2 라는 게임의 MVM (Mann VS. Machine) 모드를 참고하였습니다.
->MVM 나무위키<-
MVM 모드는 플레이어 vs AI의 PVE 형식의 모드이고, AI 측에서는 폭탄, 또는 수레를 기지의 특정 지점까지 옮기면 우승하게 되고, 플레이어 측에서는 이를 시간 안에 막아야하는 모드입니다.
디펜스 형식으로 매 턴마다 적들이 강해지며, 플레이어는 적을 처치함으로써 골드를 얻습니다.
매 턴이 끝나면 잠시 정비 시간이 있는데, 이 시간에 얻은 골드를 통해서 능력치 강화 또는 스킬을 구매하여 강해지는 방식입니다.
.
.
.
우선은 여기까지 생각해놓고, 내일부터 마음을 다잡고 유니티를 공부해보도록 하겠습니다…
Game_project
· 2024-08-10
-
-
-
-
-
-
-
-
-
-
-
AVL 트리
AVL Tree
AVL Tree란 앞에서 살펴보았던 이진 탐색 트리의 한 종류로, Height-Balanced Tree입니다.
이진 탐색 트리는 데이터의 삽입과 삭제 연산이 이루어지면서 트리의 구조가 비효율적으로 바뀌게 되고, 그에 따라 연산의 속도가 느려질 수 있다는 단점이 있었습니다.
AVL 트리는 그러한 단점을 보완한 트리 구조입니다. 자체적으로 각 노드의 왼쪽 부분 트리와 오른쪽 부분 트리의 높이를 조절하여 전체적으로 트리가 균등해지도록 합니다.
AVL트리는 기본적으로 이진 탐색 트리와 같습니다.
삽입, 삭제, 탐색 연산 모두 이진 탐색 트리와 같습니다.
그러나 AVL 트리의 각 노드에는 Balance Factor, BF 라는 변수가 추가됩니다.
$BF = (왼쪽 부분 트리의 높이) - (오른쪽 부분 트리의 높이)$로, 이 값이 -1, 0, 1의 값을 가져야 하며, 그렇지 않을 경우, 회전이라는 연산을 통해 이 값들을 조정합니다.
루트 노드인 A 노드의 경우, 왼쪽 부분 트리의 높이는 2이고, 오른쪽 부분 트리의 높이는 1이므로, BF의 값은 2 - 1 = 1 입니다.
말단 노드인 D 노드의 경우, 왼쪽 부분 트리와 오른쪽 부분 트리 모두 높이가 0이므로 BF의 값은 0 - 0 = 0이 됩니다.
위 트리의 경우, A 노드의 왼쪽 부분 트리의 높이는 2이고, 오른쪽 부분 트리의 높이는 0으로, BF = 2 - 0 = 2의 값을 가집니다.
AVL 트리는 BF의 값이 0, -1, 1 이 아닌 경우, 트리 구조가 연산에 있어서 비효율적이라고 판단하고, 회전이라는 연산을 통해 모든 노드의 BF 값을 0, -1, 1의 값을 가지게끔 합니다.
회전 연산에는 4가지가 있습니다.
LL
LR
RR
RL
LL
LL 연산의 경우, A의 왼쪽 자식 B의 Bf 값이 1 이상인 경우에 사용됩니다.
간단하게 노드의 연결 방향이 차례대로 두번 왼쪽인 경우를 뜻합니다.
연산은 다음과 같습니다.
A 노드를 B 노드의 오른쪽 자식 노드로 설정
B 노드를 기존 A노드의 부모 노드와 연결
B 노드의 오른쪽 자식 노드가 존재하는 경우, 위와 동일하나, 추가적으로 B 노드의 오른쪽 자식 노드를 A 노드의 왼쪽 자식노드로 옮깁니다.
기술력 문제로.. 더 나은 예시를 만들어 보겠습니다..
LR
LR 연산의 경우, A의 왼쪽 자식 B의 Bf 값이 -1 이하인 경우에 사용됩니다.
간단하게 노드의 연결 방향이 차례대로 왼쪽, 오른쪽인 경우 입니다.
이 경우 연산은 다음과 같습니다.
A 노드의 왼쪽 자식 노드를 C로 설정
C 노드의 왼쪽 자식 노드를 B로 설정
이 과정에서 C 노드의 왼쪽 자식 노드는 B 노드의 자식 노드로 이동
해당 연산을 진행한 뒤에는 LL 연산의 경우와 같은 구조가 되는데, 이때 LL 연산을 진행합니다.
RR, RL 연산 모두 앞서 말씀드린 두 연산에서 방향만 바꾼 것입니다.
AVL 트리는 데이터의 추가, 삭제 후에 각 노드의 bf 값을 확인합니다.
만약 bf 값이 적절하지 않으면 각 상황에 맞는 회전 연산을 통해 전체 트리를 균일하게 유지합니다.
code
#include<iostream>
#include<ostream>
#define inorder 0
#define preorder 1
#define postorder 2
using namespace std;
class Underflow {};
template <typename T>
class Node {
public:
T data;
Node<T> *left, *right;
Node<T>() : left(nullptr), right(nullptr) {}
Node<T>(T value) : data(value), left(nullptr), right(nullptr) {}
};
template <typename T>
class AVLTree {
public:
int size;
Node<T> *root;
AVLTree<T>() : size(0), root(nullptr) {}
bool search(T value){
Node<T> *parent = nullptr;
Node<T> *ptr = returnNodePosition(value, root, parent);
if(ptr == nullptr)
return false;
return true;
}
void insert(T value){
Node<T> *parent = nullptr;
Node<T> *insertedPosition = returnNodePosition(value, root, parent);
if(parent == nullptr)
root = new Node<T>(value);
else if(parent->data == value){
cout << value << " already exist.\n";
return;
}
else{
Node<T> *newNode = new Node<T>(value);
if(value < parent->data)
parent->left = newNode;
else
parent->right = newNode;
}
size++;
cout << value << " inserted.\n";
sort();
}
void remove(T value){
try{
if(size <= 0) throw Underflow();
Node<T> *parent = nullptr;
Node<T> *removedPosition = returnNodePosition(value, root, parent);
if(removedPosition == nullptr){
cout << value << " does not exist.\n";
return;
}
//자식노드가 없는 경우 : 그냥 제거
if(removedPosition->left == nullptr && removedPosition->right == nullptr){
if(parent->data > value)
parent->left = nullptr;
else
parent->right = nullptr;
delete removedPosition;
}
//하나만 있는 경우 : 부모 노드와 자식 노드를 연결
else if(removedPosition->left != nullptr && removedPosition->right == nullptr){
if(parent->data > value)
parent->left = removedPosition->left;
else
parent->right = removedPosition->left;
delete removedPosition;
}
else if(removedPosition->left == nullptr && removedPosition->right != nullptr){
if(parent->data > value)
parent->left = removedPosition->right;
else
parent->right = removedPosition->right;
delete removedPosition;
}
//둘 다 있는 경우 : LeftMost 노드와 교체
else{
Node<T> *ptr = removedPosition->left, *parent = removedPosition;
while(ptr->right != nullptr){
parent = ptr;
ptr = ptr->right;
}
removedPosition->data = ptr->data;
if(parent == removedPosition)
parent->left = nullptr;
else
parent->right = nullptr;
delete ptr;
}
cout << value << " removed\n";
size--;
sort();
}
catch(Underflow e){
cout << "Underflow occurs.\n";
exit(0);
}
}
void print(int N){
if(N == inorder){
cout << "inorder : ";
inOrder(root);
}
else if(N == preorder){
cout << "preorder : ";
preOrder(root);
}
else if(N == postorder){
cout << "postorder : ";
postOrder(root);
}
cout << '\n';
}
private:
// value 값이 존재하지 않을 경우, 리턴 값 : nullptr, parent 변수 : 해당 위치의 부모 노드
// value 값이 존재하는 경우, 리턴 값 : 해당 노드, parent 변수 : 해당 노드의 부모 노드
Node<T> *returnNodePosition(T value, Node<T> *current, Node<T> *&parent){
Node<T> *child_ptr = current;
while(child_ptr != nullptr){
if(child_ptr->data == value){
return child_ptr;
}
parent = child_ptr;
if(child_ptr->data < value)
child_ptr = child_ptr->right;
else
child_ptr = child_ptr->left;
}
return child_ptr;
}
void RR(Node<T> *current, Node<T> *&parrent){
Node<T> *newCurrent = current->right;
if(parrent == nullptr)
root = newCurrent;
else{
if(parrent->data > current->data)
parrent->left = newCurrent;
else
parrent->right = newCurrent;
}
current->right = newCurrent->left;
newCurrent->left = current;
}
void LL(Node<T> *current, Node<T> *&parrent){
Node<T> *newCurrent = current->left;
if(parrent == nullptr)
root = newCurrent;
else{
if(parrent->data > current->data)
parrent->left = newCurrent;
else
parrent->right = newCurrent;
}
current->left = newCurrent->right;
newCurrent->right = current;
}
void RL(Node<T> *current, Node<T> *&parrent){
Node<T> *rightChild = current->right;
current->right = rightChild->left;
rightChild->left = current->right->right;
current->right->right = rightChild;
RR(current, parrent);
}
void LR(Node<T> *current, Node<T> *&parrent){
Node<T> *leftChild = current->left;
current->left = leftChild->right;
leftChild->right = current->left->left;
current->left->left = leftChild;
LL(current, parrent);
}
int findHieght(Node<T> *current){
if(current == nullptr)
return 0;
int temp1 = 0, temp2 = 0;
if(current->left != nullptr)
temp1 = findHieght(current->left);
if(current->right != nullptr)
temp2 = findHieght(current->right);
return 1 + (temp1 > temp2 ? temp1 : temp2);
}
int getBf(Node<T> *current){
int height_L = 0,height_R = 0;
if(current->left != nullptr)
height_L = findHieght(current->left);
if(current->right != nullptr)
height_R = findHieght(current->right);
return height_L - height_R;
}
void sort(){
Node<T> *parent = nullptr;
sortNode(root, parent);
}
void sortNode(Node<T> *¤t, Node<T> *&parent){
if(current == nullptr || (current->left == nullptr && current->right == nullptr))
return;
sortNode(current->left, current);
sortNode(current->right, current);
int bf = getBf(current);
if(bf == 0 || bf == 1 || bf == -1)
return;
if(bf > 1){
if(getBf(current->left) < 0)
LR(current,parent);
else
LL(current,parent);
}
else{
if(getBf(current->right) > 0)
RL(current, parent);
else
RR(current,parent);
}
}
void inOrder(Node<T>* current){
if(current != nullptr){
inOrder(current->left);
cout << "[ " << current->data << " ] ";
inOrder(current->right);
}
}
void preOrder(Node<T>* current){
if(current != nullptr){
cout << "[ " << current->data << " ] ";
preOrder(current->left);
preOrder(current->right);
}
}
void postOrder(Node<T>* current){
if(current != nullptr){
postOrder(current->left);
postOrder(current->right);
cout << "[ " << current->data << " ] ";
}
}
};
int main(){
AVLTree<int> test;
int a[] = {9,4,3,1,11,15,13,12,14,5,6};
for(int k : a){
test.insert(k);
test.print(preorder);
}
test.remove(9);
test.print(preorder);
test.remove(12);
test.print(preorder);
test.remove(5);
test.print(preorder);
return 0;
}
기본적으로 이진 탐색 트리의 코드에 bf값, 회전 연산의 코드만 추가하면 됩니다.
그래서 저번에 올린 이진 탐색 트리 코드를 그대로 가져오면 되는데, 약간의 변경사항이 있습니다.
그래서 변경사항과 회전 연산 코드를 중점으로 살펴보겠습니다.
returnNodePosition
// value 값이 존재하지 않을 경우, 리턴 값 : nullptr, parent 변수 : 해당 위치의 부모 노드
// value 값이 존재하는 경우, 리턴 값 : 해당 노드, parent 변수 : 해당 노드의 부모 노드
Node<T> *returnNodePosition(T value, Node<T> *current, Node<T> *&parent){
Node<T> *child_ptr = current;
while(child_ptr != nullptr){
if(child_ptr->data == value){
return child_ptr;
}
parent = child_ptr;
if(child_ptr->data < value)
child_ptr = child_ptr->right;
else
child_ptr = child_ptr->left;
}
return child_ptr;
}
먼저 삽입, 삭제, 탐색 연산에 공통적으로 사용되는 함수입니다.
이 함수는 특정 값을 가진 노드의 포인터를 반환하고, parent 변수는 해당 노드의 부모 노드가 됩니다.
특정 값이 존재하지 않으면, nullptr를 반환하고, parent 변수는 해당 위치의 부모 노드가 됩니다.
탐색
returnNodePosition 함수의 반환 값이 nullptr이 아닌 경우, true를 리턴합니다.
삽입
returnNodePosition 함수의 반환 값이 nullptr인 경우, parent 노드의 자식 노드로서 value값을 가진 새로운 노드를 추가합니다.
삭제
returnNodePosition 함수의 반환 값이 nullptr이 아닌 경우, 이진 탐색 트리의 삭제 연산과 마찬가지로,
자식 노드가 없는 경우
하나의 자식 노드를 가지는 경우
두 개의 자식 노드를 가지는 경우
각 상황에 따라 알맞은 연산을 진행합니다.
getBF
int findHieght(Node<T> *current){
if(current == nullptr)
return 0;
int temp1 = 0, temp2 = 0;
if(current->left != nullptr)
temp1 = findHieght(current->left);
if(current->right != nullptr)
temp2 = findHieght(current->right);
return 1 + (temp1 > temp2 ? temp1 : temp2);
}
int getBf(Node<T> *current){
int height_L = 0,height_R = 0;
if(current->left != nullptr)
height_L = findHieght(current->left);
if(current->right != nullptr)
height_R = findHieght(current->right);
return height_L - height_R;
}
해당 노드의 bf 값을 반환합니다.
sort
void sort(){
Node<T> *parent = nullptr;
sortNode(root, parent);
}
루트 노드를 시작으로 sortNode 함수를 실행하는 함수입니다.
적절한 회전 연산을 통해 각 노드의 bf 값을 조절합니다.
삽입, 삭제 연산 과정에서 항상 실행되도록 하였습니다.
sortNode
//각 노드의 bf 값을 확인하고, 적절하지 않은 경우, 회전 연산 진행
void sortNode(Node<T> *¤t, Node<T> *&parent){
if(current == nullptr || (current->left == nullptr && current->right == nullptr))
return;
sortNode(current->left, current);
sortNode(current->right, current);
int bf = getBf(current);
if(bf == 0 || bf == 1 || bf == -1)
return;
if(bf > 1){
if(getBf(current->left) < 0)
LR(current,parent);
else
LL(current,parent);
}
else{
if(getBf(current->right) > 0)
RL(current, parent);
else
RR(current,parent);
}
}
먼저 postorder 순회를 진행합니다.
getBF 함수를 통해서 방문한 노드의 bf 값을 확인합니다.
bf 값이 적절하지 않은 경우, 상황에 알맞게 회전 연산을 진행합니다.
예를 들어 LL 연산과 LR 연산의 구분은 현재 왼쪽 자식 노드의 bf 값을 기준으로 정했습니다.
회전 연산
void RR(Node<T> *current, Node<T> *&parrent){
Node<T> *newCurrent = current->right;
if(parrent == nullptr)
root = newCurrent;
else{
if(parrent->data > current->data)
parrent->left = newCurrent;
else
parrent->right = newCurrent;
}
current->right = newCurrent->left;
newCurrent->left = current;
}
void LL(Node<T> *current, Node<T> *&parrent){
Node<T> *newCurrent = current->left;
if(parrent == nullptr)
root = newCurrent;
else{
if(parrent->data > current->data)
parrent->left = newCurrent;
else
parrent->right = newCurrent;
}
current->left = newCurrent->right;
newCurrent->right = current;
}
void RL(Node<T> *current, Node<T> *&parrent){
Node<T> *rightChild = current->right;
current->right = rightChild->left;
rightChild->left = current->right->right;
current->right->right = rightChild;
RR(current, parrent);
}
void LR(Node<T> *current, Node<T> *&parrent){
Node<T> *leftChild = current->left;
current->left = leftChild->right;
leftChild->right = current->left->left;
current->left->left = leftChild;
LL(current, parrent);
}
각 회전 연산의 코드입니다.
result
int main(){
AVLTree<int> test;
int a[] = {9,4,3,1,11,15,13,12,14,5,6};
for(int k : a){
test.insert(k);
test.print(preorder);
}
test.remove(9);
test.print(preorder);
test.remove(12);
test.print(preorder);
test.remove(5);
test.print(preorder);
return 0;
}
9 inserted.
preorder : [ 9 ]
4 inserted.
preorder : [ 9 ] [ 4 ]
3 inserted.
preorder : [ 4 ] [ 3 ] [ 9 ]
1 inserted.
preorder : [ 4 ] [ 3 ] [ 1 ] [ 9 ]
11 inserted.
preorder : [ 4 ] [ 3 ] [ 1 ] [ 9 ] [ 11 ]
15 inserted.
preorder : [ 4 ] [ 3 ] [ 1 ] [ 11 ] [ 9 ] [ 15 ]
13 inserted.
preorder : [ 4 ] [ 3 ] [ 1 ] [ 11 ] [ 9 ] [ 15 ] [ 13 ]
12 inserted.
preorder : [ 4 ] [ 3 ] [ 1 ] [ 11 ] [ 9 ] [ 13 ] [ 12 ] [ 15 ]
14 inserted.
preorder : [ 4 ] [ 3 ] [ 1 ] [ 13 ] [ 11 ] [ 9 ] [ 12 ] [ 15 ] [ 14 ]
5 inserted.
preorder : [ 11 ] [ 4 ] [ 3 ] [ 1 ] [ 9 ] [ 5 ] [ 13 ] [ 12 ] [ 15 ] [ 14 ]
6 inserted.
preorder : [ 11 ] [ 4 ] [ 3 ] [ 1 ] [ 6 ] [ 5 ] [ 9 ] [ 13 ] [ 12 ] [ 15 ] [ 14 ]
9 removed
preorder : [ 11 ] [ 4 ] [ 3 ] [ 1 ] [ 6 ] [ 5 ] [ 13 ] [ 12 ] [ 15 ] [ 14 ]
12 removed
preorder : [ 11 ] [ 4 ] [ 3 ] [ 1 ] [ 6 ] [ 5 ] [ 14 ] [ 13 ] [ 15 ]
5 removed
preorder : [ 11 ] [ 4 ] [ 3 ] [ 1 ] [ 6 ] [ 14 ] [ 13 ] [ 15 ]
9,4,3,1,11,15,13,12,14,5,6 을 순서대로 삽입한 결과 입니다.
9, 12, 5를 순서대로 삭제한 결과입니다.
https://www.cs.usfca.edu/~galles/visualization/AVLtree.html
AVL 트리의 삽입, 삭제 연산 과정은 이 사이트에서 확인할 수 있습니다.
AVL 트리 뿐만 아니라 다양한 자료구조의 연산을 시각화하여 나타냈기에, 많은 도움이 될 것이라고 생각합니다.
-
-
-
이진 트리
Binary Tree
Tree란 노드의 집합에 의한 계층적 자료구조입니다. 각 노드들은 데이터 값과 자식 노드라고 칭하는 노드들의 포인터 값을 가집니다. 그리고 자신의 포인터 값을 가지고 있는 노드를 부모노드라고 합니다.
트리의 각 노드는 세 가지로 분류될 수 있습니다.
루트 노드 ( Root Node ) : 부모노드를 갖지 않는 경우
말단 노드 ( Leaf Node ) : 자녀노드를 갖지 않는 경우
내부 노드 ( Internal Node ) : 위의 두 경우를 제외한 경우
그리고 자신과 같은 부모 노드를 가지고 있는 노드들을 형제 ( Sibling ) 노드 라고 합니다.
차수 ( Degree, = d ) : 자식 노드의 개수
Level ( = Height ) : 루트 노드는 0 또는 1부터 시작하여, 자식노드는 부모노드보다 1을 더한 값을 얻는다.
이진 트리 ( Binary Tree )
이진 트리 ( Binary Tree )는 차수가 2 이하인 트리를 말합니다.
그 안에도 여러 종류가 있습니다.
편향 이진 트리 ( Skewed Binary Tree )
말단 노드를 제외한 모든 노드가 오직 한개의 자식 노드를 갖는 트리를 말합니다.
Degenerate Tree 라고도 합니다. 이 경우엔 연결리스트와 같은 기능을 가집니다.
정 이진 트리 ( Full Binary Tree )
말단 노드를 제외한 모든 노드의 차수가 0 또는 2인 트리를 말합니다.
완전 이진 트리 ( Complete Binary Tree )
말단 노드를 제외한 모든 노드의 차수가 2인 트리를 말합니다. 또한 마지막 레벨을 제외한 모든 레벨이 채워져 있어야 합니다. 즉, 말단 노드들의 레벨 차이는 최대 1 입니다.
말단 노드들은 트리에 채워질 때, 왼쪽부터 채워집니다.
포화 이진 트리 ( Perfect Binary Tree )
완전 이진 트리에서 마지막 레벨이 모두 채워진 경우를 포화 이진 트리라고 합니다. 즉, 모든 말단 노드의 레벨이 같습니다.
이진 탐색 트리 (Binary Search Tree, BST)
이진 탐색 트리는 이진 탐색 알고리즘을 트리에 접목시킨 것입니다.
각 노드의 데이터보다 작은 값은 왼쪽 부분 트리로, 큰 값은 오른쪽 부분 트리로 저장됩니다.
특정 값 n을 찾을 때, 현재 노드의 데이터보다 작다면 왼쪽 자식 노드, 크다면 오른쪽 자식 노드로 이동해서 재귀적으로 진행되기 때문에, 이진 탐색과 같이 삽입, 삭제, 탐색 연산이 모두 $O(log_2N)$이 됩니다.
탐색 연산 find “key”
루트 노드부터 탐색을 시작합니다.
노드의 값 == key 이면, 탐색 성공, 종료
노드의 값 < key 이면, 왼쪽 자식 노드로 이동
노드의 값 > key 이면, 오른쪽 자식 노드로 이동
이 과정을 반복하였을 때, 마지막에 key 값과 같은 값을 가진 노드가 존재하지 않다면 탐색 실패로 종료됩니다.
삽입 연산 insert “key”
삽입 연산이 이루어지기 위해서 탐색 연산을 시작합니다.
탐색이 종료되는 경우, 탐색이 종료된 위치에 키 값을 삽입합니다.
삭제 연산 delete “key”
탐색 연산을 시작합니다.
탐색이 실패하면 어떠한 행동도 취하지 않습니다.
탐색이 성공하면 해당 노드를 삭제합니다.
해당 노드가 말단 노드인 경우 : 해당 노드를 삭제합니다.
해당 노드가 하나의 자식 노드를 가지는 경우 : 해당 노드를 삭제하고, 자식 노드로 이를 대체합니다.
해당 노드가 두개의 자식 노드를 가지는 경우 : 해당 노드를 삭제하고, 다음 중 하나의 노드를 골라 이를 대체합니다.
왼쪽 부분 트리에서 가장 큰 값을 가지는 노드
오른쪽 부분 트리에서 가장 작은 값을 가지는 노드
이제 BST를 구현해보도록 하겠습니다.
code
#include<iostream>
#include<ostream>
#define inorder 0
#define preorder 1
#define postorder 2
using namespace std;
class Underflow {};
template <typename T>
class Node {
public:
T data;
Node<T> *left, *right;
Node<T>() : left(nullptr), right(nullptr) {}
Node<T>(T value) : data(value), left(nullptr), right(nullptr) {}
};
template <typename T>
class BinaryTree {
public:
int size;
Node<T> *root;
BinaryTree<T>() : size(0) , root(nullptr) {}
void insert(T value){
insertNode(value, root);
size++;
}
bool search(T value){
return searchNode(value, root);
}
void remove(T value){
try{
if(size <= 0) throw Underflow();
removeNode(value, root);
size--;
cout << "\nremoved " << value << '\n';
}
catch(Underflow e){
cout << "underflow occurs" << '\n';
exit(0);
}
}
void print(int N){
if(N == inorder){
cout << "inorder : ";
inOrder(root);
}
else if(N == preorder){
cout << "preorder : ";
preOrder(root);
}
else if(N == postorder){
cout << "postorder : ";
postOrder(root);
}
cout << '\n';
}
private:
void insertNode(T value, Node<T> *¤tNode){
if(currentNode == nullptr)
currentNode = new Node<T>(value);
else{
if(value <= currentNode->data)
insertNode(value,currentNode->left);
else
insertNode(value, currentNode->right);
}
}
bool searchNode(T value,Node<T> *current){
if(current->data == value)
return 1;
if(value < current->data)
searchNode(value, current->left);
else
searchNode(value,current->right);
return 0;
}
void getleftMost(Node<T> *¤t){
Node<T> *ptr = current->left, *prev = current;
while(ptr->right != nullptr){
prev = ptr;
ptr = ptr->right;
}
prev->right = nullptr;
current->data = ptr->data;
delete ptr;
}
void removeNode(T value, Node<T> *¤t){
if(current != nullptr){
if(value < current->data)
removeNode(value,current->left);
else if(value > current->data)
removeNode(value,current->right);
else if (value == current->data){
if(current->left == nullptr){
Node<T> *ptr = current;
current = current->right;
delete ptr;
}
else if(current->right == nullptr){
Node<T> *ptr = current;
current = current->left;
delete ptr;
}
else{
getleftMost(current);
}
}
}
}
void inOrder(Node<T>* current){
if(current != nullptr){
inOrder(current->left);
cout << "[ " << current->data << " ] ";
inOrder(current->right);
}
}
void preOrder(Node<T>* current){
if(current != nullptr){
cout << "[ " << current->data << " ] ";
preOrder(current->left);
preOrder(current->right);
}
}
void postOrder(Node<T>* current){
if(current != nullptr){
postOrder(current->left);
postOrder(current->right);
cout << "[ " << current->data << " ] ";
}
}
};
int main(){
BinaryTree<int> test;
int k[] = {3, 9, 4, 1, 10, 5, 9, 10, 7, 2};
for(int i = 0; i < 10; i++)
test.insert(k[i]);
test.print(inorder);
test.print(preorder);
test.print(postorder);
test.remove(3);
test.print(inorder);
test.print(preorder);
test.print(postorder);
return 0;
}
코드 내에서는 빈 트리에 3, 9, 4, 1, 10, 5, 9, 10, 7, 2를 순서대로 삽입을 진행합니다.
그 과정은 다음과 같습니다.
여기서 inorder, preorder, postorder가 있는데, 이는 이진 트리 순회 방법입니다.
특정한 순서로 각 노드를 방문하여 최종적으로 트리의 모든 노드를 방문하는 방법을 말합니다.
inorder traversal : 왼쪽 자식 노드, 자신, 오른쪽 자식 노드의 순서로 순회하는 방법입니다.
preorder traversal : 자신, 왼쪽 자식 노드, 오른쪽 자식 노드의 순서로 순회하는 방법입니다.
postorder traversal : 왼쪽 자식 노드, 오른쪽 자식 노드, 자신의 순서로 순회하는 방법입니다.
result
inorder : [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 7 ] [ 9 ] [ 9 ] [ 10 ] [ 10 ]
preorder : [ 3 ] [ 1 ] [ 2 ] [ 9 ] [ 4 ] [ 5 ] [ 9 ] [ 7 ] [ 10 ] [ 10 ]
postorder : [ 2 ] [ 1 ] [ 7 ] [ 9 ] [ 5 ] [ 4 ] [ 10 ] [ 10 ] [ 9 ] [ 3 ]
removed 3
inorder : [ 1 ] [ 2 ] [ 4 ] [ 5 ] [ 7 ] [ 9 ] [ 9 ] [ 10 ] [ 10 ]
preorder : [ 2 ] [ 1 ] [ 9 ] [ 4 ] [ 5 ] [ 9 ] [ 7 ] [ 10 ] [ 10 ]
postorder : [ 1 ] [ 7 ] [ 9 ] [ 5 ] [ 4 ] [ 10 ] [ 10 ] [ 9 ] [ 2 ]
예시로 보여드린 트리의 구조가 매우 비효율적입니다.
이러한 구조의 트리의 경우, 삽입, 삭제, 탐색 연산의 시간 복잡도가 증가하게 됩니다.
이러한 문제에 대한 해결 방안으로 Height Balanced Tree 중에서,
AVL Tree와 Red-Black Tree에 대해서 알아보도록 하겠습니다.
물론 내일..
-
-
스택, 큐
Stack
Stack은 FILO(First In Last Out) 형식의, 가장 먼저 추가된 데이터가 가장 나중에 삭제되는 자료구조입니다.
헬스를 하면서 바벨에 원판 끼우고 뺄 때, 가장 나중에 넣은 원판을 가장 먼저 빼는 것, 이것이 스택 자료구조라고 보면 됩니다.
스택은 프로세스 메모리 상에서 임시 로컬 데이터를 저장하는데 쓰이기도 합니다. 예를 들어 C++ 프로그램을 실행하면 코드 내 함수 파라미터, 지역 변수, 리턴 값 등이 이 스택 자료구조에 저장됩니다.
스택에는 push 연산과 pop 연산이 있는데, push 연산은 마지막에 노드를 추가하는 연산이고, pop은 가장 마지막 노드를 제거하는 연산입니다.
스택은 보통 배열 또는 연결리스트를 통해서 구현을 합니다.
by Linked List
code
#include<iostream>
#include<ostream>
#define MAX 10
class Underflow {};
using namespace std;
template <typename T>
class Node {
public:
T data;
Node<T> *next;
Node<T>() : next(nullptr) {}
Node<T>(T value, Node<T>* next1) : data(value), next(next1) {}
};
template <typename T>
class Stack {
public:
int length;
Node<T> *top;
Stack<T>() : length(0), top(nullptr) {}
bool empty(){ return (length ? false : true); }
void push(T value){
top = new Node<T>(value, top);
length++;
}
T pop(){
try{
if(length == 0) throw Underflow();
T returnValue = top->data;
Node<T> *ptr = top;
top = top->next;
delete ptr;
length--;
return returnValue;
}
catch(Underflow e){
cout << "Underflow occurs" << '\n';
exit(0);
}
}
~Stack<T>(){
Node<T> *ptr = top, *prev;
while(ptr != nullptr){
prev = ptr;
ptr = ptr->next;
delete prev;
}
}
};
template <typename T>
ostream& operator<< (ostream& scan, Stack<T> &inputArr){
Node<T> *ptr = inputArr.top;
while(ptr != nullptr){
scan << "[ " << ptr->data << " ]-";
ptr = ptr->next;
}
scan << "[ NULL ]" << '\n';
}
int main(){
Stack<int> test;
int k = 4;
for(int i = 0; i < MAX; i++)
test.push(k++);
cout << test;
test.pop();
cout << test;
return 0;
}
result
[ 13 ]-[ 12 ]-[ 11 ]-[ 10 ]-[ 9 ]-[ 8 ]-[ 7 ]-[ 6 ]-[ 5 ]-[ 4 ]-[ NULL ]
[ 12 ]-[ 11 ]-[ 10 ]-[ 9 ]-[ 8 ]-[ 7 ]-[ 6 ]-[ 5 ]-[ 4 ]-[ NULL ]
by Array
code
#include<iostream>
#include<ostream>
#define MAX 10
class Underflow {};
using namespace std;
template <typename T>
class Stack {
public:
int length;
int top;
T* arr;
Stack<T>() : length(0), top(-1) {}
Stack<T>(int size) : length(size), top(-1) {
arr = new T(size);
}
~Stack<T>(){
delete[] arr;
}
bool empty(){ return (length ? false : true); }
bool full(){ return (top == length - 1 ? true : false); }
void push(T value){
if(full()){
T* newArr = new T[length + MAX];
for(int i = 0; i < length; i++)
newArr[i] = arr[i];
delete[] arr;
arr = newArr;
}
arr[++top] = value;
}
T pop(){
try{
if(top < 0) throw Underflow();
return arr[top--];
}
catch(Underflow e){
cout << "underflow occurs" << '\n';
exit(0);
}
}
};
template <typename T>
ostream& operator<< (ostream& scan, Stack<T> &inputArr){
for(int i = inputArr.top; i >= 0; i--)
scan << "[ " << inputArr.arr[i] << " ]-";
scan << "[ NULL ]" << '\n';
}
int main(){
Stack<int> test;
int k = 4;
for(int i = 0; i < MAX; i++)
test.push(k++);
cout << test;
test.pop();
cout << test;
return 0;
}
result
[ 13 ]-[ 12 ]-[ 11 ]-[ 10 ]-[ 9 ]-[ 8 ]-[ 7 ]-[ 6 ]-[ 5 ]-[ 4 ]-[ NULL ]
[ 12 ]-[ 11 ]-[ 10 ]-[ 9 ]-[ 8 ]-[ 7 ]-[ 6 ]-[ 5 ]-[ 4 ]-[ NULL ]
Queue
Queue는 FIFO (First In First Out) 의 형태로, 가장 먼저 추가된 노드가 가장 먼저 삭제되는 자료구조이다.
도로 신호등에 걸린 차량들을 생각해보았을 때, 신호등이 초록불이 되면 먼저 도착해 정지했던 차량이 먼저 출발하는데, 큐가 이러한 구조로 되어있다.
큐는 enqueue와 dequeue 연산이 있는데, enqueue는 가장 마지막에 새로운 노드를 추가하는 연산이고, dequeue는 가장 앞에 있는 (가장 먼저 추가됐었던) 노드를 삭제하는 연산이다.
이러한 큐 자료구조는 한 예로 실행가능한 상태의 프로세스들이 CPU 자원을 할당받고자 대기 중일 때, 이러한 큐 자료구조 형태로 저장된다.
By Linked List
code
#include<iostream>
#include<ostream>
#define MAX 10
class Underflow {};
using namespace std;
template <typename T>
class Node {
public:
T data;
Node<T> *next;
Node<T>() : next(nullptr) {}
Node<T>(T value, Node<T> *next1) : data(value), next(next1) {}
};
template <typename T>
class Queue {
public:
int length;
Node<T> *front, *rear;
Queue<T>() : length(0), front(nullptr), rear(nullptr) {}
~Queue<T>(){
Node<T> *ptr = front,*prev;
while(ptr != nullptr){
prev = ptr;
ptr = ptr->next;
delete prev;
}
}
bool empty() {return (length? false : true);}
void enqueue(T value){
if(length == 0)
front = rear = new Node<T>(value, nullptr);
else{
rear->next = new Node<T>(value, nullptr);
rear = rear->next;
}
length++;
}
T dequeue(){
try{
if(empty()) throw Underflow();
Node<T> *ptr = front;
T returnValue = ptr->data;
front = front->next;
delete ptr;
length--;
return returnValue;
}
catch(Underflow e){
cout << "underflow occurs" << '\n';
exit(0);
}
}
};
template <typename T>
ostream& operator<< (ostream& scan, Queue<T>& inputQueue){
Node<T> *ptr = inputQueue.front;
scan << "front-";
while(ptr !=nullptr){
scan << "[ " << ptr->data << " ]-";
ptr = ptr->next;
}
scan << "rear" << '\n';
}
int main(){
Queue<int> test;
int k = 3;
for(int i = 0; i < MAX; i++)
test.enqueue(k++);
cout << test;
test.dequeue();
cout << test;
return 0;
}
result
front-[ 3 ]-[ 4 ]-[ 5 ]-[ 6 ]-[ 7 ]-[ 8 ]-[ 9 ]-[ 10 ]-[ 11 ]-[ 12 ]-rear
front-[ 4 ]-[ 5 ]-[ 6 ]-[ 7 ]-[ 8 ]-[ 9 ]-[ 10 ]-[ 11 ]-[ 12 ]-rear
By Array
큐의 한 형태로 원형 큐 (Circular Queue)가 있는데, 이는 배열을 통해 큐를 구현하였을 때, 배열의 크기는 고정된다는 특징으로 저장 공간이 부족하다는 단점을 해결한 형태의 큐입니다.
enqueue
rear 인덱스 값에 1을 더해 업데이트하고, rear 인덱스 값에 데이터를 삽입합니다. 만약 rear의 인덱스 값이 배열의 크기 이상이 되면 rear 값을 0으로 초기화합니다.
dequeue
배열의 front 인덱스에 해당하는 데이터을 리턴하고, front 인덱스 값에 1을 더해 업데이트 합니다. enqueue의 rear와 마찬가지로 front 값이 배열의 크기 이상이 되면 rear 값을 0으로 초기화합니다.
code
#include<iostream>
#include<ostream>
#define MAX 10
using namespace std;
class Underflow {};
class Overflow {};
template <typename T>
class Queue {
public:
int length;
int front,rear;
T *arr;
Queue<T>() : length(0), front(-1), rear(-1) {
arr = new T[MAX];
}
~Queue<T>(){
delete[] arr;
}
bool full(){ return (length == MAX ? 1 : 0); }
bool empty(){ return (length? 0 : 1); }
void enqueue(T value){
try{
if(full()) throw Overflow();
rear++;
if(rear >= MAX) rear %= MAX;
if(length == 0) front = rear;
arr[rear] = value;
length++;
}
catch(Overflow e){
cout << "overflow occurs" << '\n';
exit(0);
}
}
T dequeue(){
try{
if(empty()) throw Underflow();
T returnValue = arr[front];
if(front == rear) front = rear = -1;
else
front++;
if(front >= MAX) front %= MAX;
length--;
return returnValue;
}
catch(Underflow e){
cout << "underflow occurs" << '\n';
exit(0);
}
}
};
template <typename T>
ostream& operator<<(ostream& scan, Queue<T>& inputQueue){
scan << "front-";
int idx = inputQueue.front;
while(1){
scan << "[ " << inputQueue.arr[idx] << " ]-";
if(idx == inputQueue.rear) break;
idx++;
if(idx >= MAX) idx %= MAX;
}
scan << "rear" << '\n';
}
int main(){
Queue<int> test;
int k = 3;
for(int i = 0; i < MAX; i++)
test.enqueue(k++);
cout << test;
test.dequeue();
cout << test;
test.enqueue(k);
cout << test;
return 0;
}
result
front-[ 3 ]-[ 4 ]-[ 5 ]-[ 6 ]-[ 7 ]-[ 8 ]-[ 9 ]-[ 10 ]-[ 11 ]-[ 12 ]-rear
front-[ 4 ]-[ 5 ]-[ 6 ]-[ 7 ]-[ 8 ]-[ 9 ]-[ 10 ]-[ 11 ]-[ 12 ]-rear
front-[ 4 ]-[ 5 ]-[ 6 ]-[ 7 ]-[ 8 ]-[ 9 ]-[ 10 ]-[ 11 ]-[ 12 ]-[ 13 ]-rear
Queue By Two Stack
두개의 스택을 통해서 큐를 구현할 수 있습니다.
기본적으로 데이터가 저장되는 스택1과 dequeue 작업을 위해 데이터를 임시적으로 저장할 스택2가 필요한데, enqueue연산의 경우 스택1에 push 연산을 통해 스택의 경우와 똑같이 저장합니다. dequeue연산을 위해서는 가장 밑에 있는 데이터를 추출해야 하는데, 스택의 경우, FILO 구조로 가장 위의 있는 데이터가 먼저 추출될 수 밖에 없다. 여기서 임시 저장소 스택2가 사용되는데, 먼저 스택1에 저장된 데이터들을 가장 밑에 있는 데이터가 나올 때까지 pop 연산을 진행합니다. 그리고 각 연산마다 추출되는 데이터를 스택2에 그대로 push 연산을 진행합니다. 그러면 마지막엔 스택2에는 가장 밑에 있던 데이터를 제외한 나머지 노드들이 삽입된 순서의 반대로 저장되어있을텐데, 밑에 있던 데이터를 추출한 후, 스택2 안에 데이터가 모두 사라질 때까지 pop연산을 진행하고, 연산을 통해 추출된 데이터들을 다시 스택1에 push 연산을 진행합니다.
스택1에서 pop 연산 진행
추출된 데이터를 스택2에 push 연산 진행
1,2 단계를 스택1의 가장 밑에 있는 데이터가 추출될 때까지 진행
목표 데이터 추출
스택2에서 pop연산 진행
추출된 데이터를 스택1에 push연산 진행
5,6 단계를 스택2에 아무 데이터도 남지 않을 때까지 진행
마찬가지로 스택 또한 두개의 큐를 통해서 구현할 수 있습니다.
-
연결 리스트
블렌더 모델링 너무 힘들어서 머리 좀 식히고자 복습할 겸 작성합니다..
Linked List
연결리스트는 각 노드가 연속되어 저장되는 배열과 달리, 각 노드들의 위치가 연속되지 않지만, 각자 다음 노드의 위치 정보를 함께 저장하여 연결되는 자료구조입니다.
각 노드는 데이터와 다른 노드에 대한 포인터가 저장된다.
연결리스트는 노드의 추가, 삭제에 있어서 특정 노드들의 연결만 업데이트하면 되므로 배열보다 월등히 빠르다.
그러나 특정 노드에 접근하기 위해서는 첫 노드로부터 순차적으로 접근해야하기 때문에 리스트의 노드 수에 따라서 선형적이며, 특정 노드와의 연결이 끊어지게 되는 경우, 끊어진 노드와 연결된 다른 노드들의 정보도 잃어버린다는 단점이 있다.
Singly Linked List
Singly Linked List는 단순히 각 노드가 다음 노드의 포인터만을 가지고 있는 연결 리스트이다.
이는 운영체제의 파일 시스템에서 연속 할당 (Contiguous Allocation) 방식에서 사용되기도 한다.
code
#include<iostream>
#include<ostream>
#define MAX 10
using namespace std;
class InvalidIndex {};
class Underflow {};
template <typename T>
class Node{
public:
T data;
Node<T> *nextNode;
Node<T>() : nextNode(nullptr) {}
Node<T>(T value, Node<T> *next1) : data(value), nextNode(next1) {};
~Node<T>(){
nextNode = nullptr;
}
};
template <typename T>
class LinkedList{
public:
int length;
Node<T> *head;
LinkedList() : length(0), head(nullptr) {}
~LinkedList(){
Node<T> *ptr1 = head, *ptr2;
while(ptr1 != nullptr){
ptr2 = ptr1;
ptr1 = ptr1->nextNode;
delete ptr2;
}
}
int size(){
return length;
}
void insert(int idx, T value){
try
{
if(idx < 0 || idx > length)
throw InvalidIndex();
if(idx == 0)
head = new Node<T>(value, head);
else{
Node<T> *ptr = head;
for(int i = 0; i < idx - 1; i++)
ptr = ptr->nextNode;
ptr->nextNode = new Node<T>(value,ptr->nextNode);
}
length++;
}
catch(InvalidIndex e){
cout << "invalid index" << '\n';
exit(0);
}
}
void erase(int idx){
try{
if(length <= 0)
throw Underflow();
if(idx < 0 || idx >= length)
throw InvalidIndex();
Node<T> *ptr = head;
if(idx == 0){
head = head->nextNode;
delete ptr;
}
else{
for(int i=0; i < idx - 1;i++)
ptr = ptr->nextNode;
Node<T> *deletedNode = ptr->nextNode;
ptr->nextNode = deletedNode->nextNode;
delete deletedNode;
}
length--;
}
catch(InvalidIndex e){
cout << "invalid index" << '\n';
exit(0);
}
catch(Underflow e){
cout << "underflow" << '\n';
}
}
bool serach(T value){
Node<T> *ptr = head;
while(ptr != nullptr){
if(ptr->data == value)
return 1;
ptr = ptr->nextNode;
}
return 0;
}
T& operator[] (int idx){
Node<T> *ptr = head;
for(int i=0 ; i < idx; i++)
ptr = ptr->nextNode;
return ptr->data;
}
};
template <typename T>
ostream& operator <<(ostream &scan, LinkedList<T> &inputArr){
Node<T> *ptr = inputArr.head;
while(ptr != nullptr){
scan << "[ " << ptr->data << " ] - ";
ptr = ptr->nextNode;
}
scan << "[ NULL ]" << '\n';
}
int main(){
LinkedList<int> test;
int k = 4;
for(int i = 0; i < MAX; i ++)
test.insert(i,k);
cout << test;
return 0;
}
result
[ 4 ] - [ 5 ] - [ 6 ] - [ 7 ] - [ 8 ] - [ 9 ] - [ 10 ] - [ 11 ] - [ 12 ] - [ 13 ] - [ NULL ]
Doubly Linked List
Doubly Linked List는 각 노드가 다음 노드의 포인터와 이전 노드의 포인터를 저장하여, 이중으로 연결된 연결리스트를 말한다.
각 노드가 이중으로 연결되었기 때문에, 혹여나 특정 노드가 다음 노드와의 연결이 끊어지더라도, 끊어진 다음 노드에 저장된 이전 노드 포인터를 이용하여 복원할 수 있다는 장점이 있다.
code
#include<iostream>
#include<ostream>
#define MAX 10
using namespace std;
class InvalidIndex {};
class Underflow {};
template <typename T>
class Node {
public:
T data;
Node<T> *prev, *next;
Node<T>() : prev(nullptr), next(nullptr) {}
Node<T>(T value, Node<T> *prev1, Node<T> *next1) : data(value), prev(prev1), next(next1) {}
};
template <typename T>
class DoublyLinkedList {
public:
int length;
Node<T> *head, *tail;
DoublyLinkedList<T>() : length(0), head(nullptr), tail(nullptr) {}
int size() { return length; }
void insert(int idx, T value){
try
{
if(idx < 0 || idx > length) throw InvalidIndex();
if(idx == 0) {
head = new Node<T>(value, nullptr, head);
if(length == 0)
tail = head;
else
head->next->prev = head;
}
else{
tail = new Node<T>(value,tail,nullptr);
tail->prev->next = tail;
}
length++;
}
catch(InvalidIndex e)
{
cerr << "invalid index" << '\n';
exit(0);
}
}
void erase(int idx){
try{
if(!length) throw Underflow();
if(idx < 0 || idx >= length) throw InvalidIndex();
if(idx == 0){
Node<T> *ptr = head;
head = head->next;
head->prev = nullptr;
delete ptr;
}
else if(idx == length - 1){
Node<T> *ptr = tail;
tail = tail->prev;
tail->next = nullptr;
delete ptr;
}
else{
if(idx >= (length - 1) / 2.0){
Node<T> *ptr = tail;
for(int i = length - 1; i > idx + 1; i--)
ptr = ptr->prev;
Node<T> *erasedNode = ptr->prev;
ptr->prev = erasedNode->prev;
ptr->prev->next = ptr;
delete erasedNode;
}
else{
Node<T> *ptr = head;
for(int i = 0; i < idx - 1; i++)
ptr = ptr->next;
Node<T> *eraseNode = ptr->next;
ptr->next = eraseNode->next;
ptr->next->prev = ptr;
delete eraseNode;
}
}
length--;
}
catch(Underflow e){
cout << "underflow occur" << '\n';
exit(0);
}
catch(InvalidIndex e){
cout << "invalid index" << '\n';
exit(0);
}
}
};
template <typename T>
ostream& operator <<(ostream &scan, DoublyLinkedList<T> &inputArr){
Node<T> *ptr = inputArr.head;
scan << "[ NULL ] - ";
while(ptr != nullptr){
scan << "[ " << ptr->data << " ] - ";
ptr = ptr->next;
}
scan << "[ NULL ]" << '\n';
}
template <typename T>
ostream& operator >>(ostream &scan, DoublyLinkedList<T> &inputArr){
Node<T> *ptr = inputArr.tail;
scan << "[ NULL ] - ";
while(ptr != nullptr){
scan << "[ " << ptr->data << " ] - ";
ptr = ptr->prev;
}
scan << "[ NULL ]" << '\n';
}
int main(){
DoublyLinkedList<int> test;
int k = 4;
for(int i = 0; i < MAX; i ++)
test.insert(i,k++);
cout << test << '\n';
cout >> test << '\n';
test.erase(7);
cout << "delete indxe.7\n" << test << '\n';
test.erase(2);
cout << "delete index.2\n" << test << '\n';
return 0;
}
result
[ NULL ] - [ 4 ] - [ 5 ] - [ 6 ] - [ 7 ] - [ 8 ] - [ 9 ] - [ 10 ] - [ 11 ] - [ 12 ] - [ 13 ] - [ NULL ]
[ NULL ] - [ 13 ] - [ 12 ] - [ 11 ] - [ 10 ] - [ 9 ] - [ 8 ] - [ 7 ] - [ 6 ] - [ 5 ] - [ 4 ] - [ NULL ]
delete indxe.7
[ NULL ] - [ 4 ] - [ 5 ] - [ 6 ] - [ 7 ] - [ 8 ] - [ 9 ] - [ 10 ] - [ 12 ] - [ 13 ] - [ NULL ]
delete index.2
[ NULL ] - [ 4 ] - [ 5 ] - [ 7 ] - [ 8 ] - [ 9 ] - [ 10 ] - [ 12 ] - [ 13 ] - [ NULL ]
Circular Linked List
Circular Linked List는 tail, 마지막 노드가 head, 처음 노드와 연결된 구조를 말한다.
순차적으로 재생되는 음악 재생목록이라고 보면 된다.
code
##include<iostream>
##include<ostream>
##define MAX 10
using namespace std;
class InvalidIndex {};
class Underflow {};
template <typename T>
class Node {
public:
T data;
Node<T> *prev, *next;
Node<T>() : prev(nullptr), next(nullptr) {}
Node<T>(T value, Node<T> *prev1, Node<T> *next1) : data(value), prev(prev1), next(next1) {}
};
template <typename T>
class CircularLinkedList {
public:
int length;
Node<T> *head, *tail;
CircularLinkedList<T>() : length(0), head(nullptr), tail(nullptr) {}
int size(){ return length; }
void insert(int idx, T value){
try{
if(idx < 0 || idx > length) throw InvalidIndex();
if(idx == 0){
head = new Node<T>(value, tail, head);
if(length == 0)
tail = head;
else
head->next->prev = head;
}
else{
tail = new Node<T>(value,tail,head);
tail->prev->next = tail;
tail->next->prev = tail;
}
length++;
}
catch(InvalidIndex e){
cout << "invalid index" << '\n';
exit(0);
}
}
void erase(int idx){
try{
if(!length) throw Underflow();
if(idx < 0 || idx >= length) throw InvalidIndex();
if(idx == 0){
Node<T> *ptr = head;
head = head->next;
head->prev = tail;
tail->next = head;
delete ptr;
}
else if(idx == length - 1){
Node<T> *ptr = tail;
tail = tail->prev;
tail->next = head;
head->prev = tail;
delete ptr;
}
else{
if(idx >= (length - 1) / 2.0){
Node<T> *ptr = tail;
for(int i = length - 1; i > idx + 1; i--)
ptr = ptr->prev;
Node<T> *erasedNode = ptr->prev;
ptr->prev = erasedNode->prev;
ptr->prev->next = ptr;
delete erasedNode;
}
else{
Node<T> *ptr = head;
for(int i = 0; i < idx - 1; i++)
ptr = ptr->next;
Node<T> *erasedNode = ptr->next;
ptr->next = erasedNode->next;
ptr->next->prev = ptr;
delete erasedNode;
}
}
length--;
}
catch(Underflow e){
cout << "underflow occur" << '\n';
exit(0);
}
catch(InvalidIndex e){
cout << "invalid index" << '\n';
exit(0);
}
}
};
template <typename T>
ostream& operator <<(ostream &scan, CircularLinkedList<T> &inputArr){
Node<T> *ptr = inputArr.head;
for(int i = 0; i < inputArr.size(); i++){
scan << "[ " << ptr->data << " ] - ";
ptr = ptr->next;
}
scan << "[ " << ptr->data << " ]" << '\n';
}
template <typename T>
ostream& operator >>(ostream &scan, CircularLinkedList<T> &inputArr){
Node<T> *ptr = inputArr.tail;
for(int i = inputArr.size() - 1; i >= 0; i--){
scan << "[ " << ptr->data << " ] - ";
ptr = ptr->prev;
}
scan << "[ " << ptr->data << " ]" << '\n';
}
int main(){
CircularLinkedList<int> test;
int k = 4;
for(int i = 0; i < MAX; i ++)
test.insert(i,k++);
cout << test << '\n';
cout >> test << '\n';
test.erase(7);
cout << "delete indxe.7\n" << test << '\n';
test.erase(2);
cout << "delete index.2\n" << test << '\n';
return 0;
}
result
[ 4 ] - [ 5 ] - [ 6 ] - [ 7 ] - [ 8 ] - [ 9 ] - [ 10 ] - [ 11 ] - [ 12 ] - [ 13 ] - [ 4 ]
[ 13 ] - [ 12 ] - [ 11 ] - [ 10 ] - [ 9 ] - [ 8 ] - [ 7 ] - [ 6 ] - [ 5 ] - [ 4 ] - [ 13 ]
delete indxe.7
[ 4 ] - [ 5 ] - [ 6 ] - [ 7 ] - [ 8 ] - [ 9 ] - [ 10 ] - [ 12 ] - [ 13 ] - [ 4 ]
delete index.2
[ 4 ] - [ 5 ] - [ 7 ] - [ 8 ] - [ 9 ] - [ 10 ] - [ 12 ] - [ 13 ] - [ 4 ]
-
-
-
-
Kayoko AI with ChatGpt (2)
목표
카요코 보이스 기능 추가하기.
질문에 대한 답변의 텍스트를 딥러닝으로 학습한 카요코의 목소리가 출력될 것임.
구현 시작
준비
먼저 학습에 사용하기 위한 오디오 파일들을 준비할 것임.
데이터 처리하기 편하도록 이름을 voiceFile로 통합하여 저장하였다.
이제 학습에 사용할 데이터파일을 만들기 위해 ChatGpt한테 부탁하여 다음과 같은 코드를 만들었다.
이 코드를 실행하여
다음과 같은 텍스트 파일을 생성할 수 있었다.
모델 학습
엔비디아의 tacotron2 모델을 사용하여 학습을 진행하기로 했다.
tacotron2 링크
파일을 다운받고, tacotron2는 기본적으로 학습하는데 영어를 사용하기 때문에, japanese cleaner 따로 추가하여 코드를 수정하였다.
코드 수정 완료 후, 성공적으로 학습을 시작할 수 있게 되었다.
이 과정에서 수많은 오류를 직면하였다.
라이브러리의 버전이 바뀌면서 함수가 사라지거나 하는 등의 이유로 나는 6시간을 고군분투했다.
chatGpt의 도움이 없었다면 큰일날 뻔 했다.
샤워하고 오니 대략 이만큼 진행되었다.
보니까 컴퓨터 GPU 사용률이 90~100 % 사이를 왔다갔다하는데 글카의 비명소리가 들리는 것 같다.
체크포인트를 따로 설정하지 않아서 이게 잘 되고 있는지를 모르겠다…
학습된 모델을 가지고 검증을 시도했으나.. 결과는 처참했다. 그래서 학습할 데이터의 양을 더 늘리기로 했다.
카요코라는 캐릭터의 음성파일을 더 늘리기 위해 구글링 결과 카요코 asmr 1시간 짜리가 있었다.
이를 다운받고 음성 구간을 나누어 다수의 음성파일로 만들 것이다.
파이썬의 AudioSegment를 이용해서 음성 부분만 추출했는데, 결과가 만족스럽지 않아서 adobe media encoder를 통해서 asmr 음성 파일을 여러 구간으로 나눠준다. (손으로 직접)
추가한 wav 파일들을 학습에 사용할 txt 파일에 추가해준다..
총 486개의 5~10초 길이의 음성파일이 준비되었다.
다시 학습을 진행해보자..
.
.
.
.
.
2024-06-18
며칠간을 씨름하였으나 tacotron2 모델은 오래되기도 해서, 방법을 바꾸기로 했다.
https://github.com/coqui-ai/TTS
바로 coqui TTS의 기존에 학습된 모델에 파인 튜닝을 통해서 카요코의 목소리로 나타내기로 했다.
내일 다시 오도록 하겠다…
2024-06-20
다음 링크를 참고 해서, chatgpt의 도움을 받아 코드를 완성했다.
참고 링크
import os
from pydub import AudioSegment
from trainer import Trainer, TrainerArgs
import sys
OUT_PATH = os.path.join(os.path.dirname(os.path.abspath(__file__)), "run", "training")
# 현재 작업 디렉토리를 PYTHONPATH에 추가
current_dir = os.path.dirname(os.path.abspath(__file__))
tts_module_path = os.path.abspath(os.path.join(current_dir, '..', '..', '..'))
sys.path.append(tts_module_path)
from TTS.config.shared_configs import BaseDatasetConfig
from TTS.tts.datasets import load_tts_samples
from TTS.tts.layers.xtts.trainer.gpt_trainer import GPTArgs, GPTTrainer, GPTTrainerConfig, XttsAudioConfig
from TTS.utils.manage import ModelManager
RUN_NAME = "GPT_XTTS_v2.0_Japanese_FT"
PROJECT_NAME = "XTTS_trainer"
DASHBOARD_LOGGER = "tensorboard"
LOGGER_URI = None
OPTIMIZER_WD_ONLY_ON_WEIGHTS = True
START_WITH_EVAL = True
BATCH_SIZE = 3
GRAD_ACUMM_STEPS = 84
config_dataset = BaseDatasetConfig(
formatter="ljspeech",
dataset_name="custom_japanese_dataset",
path="C:/Users/aj200/Desktop/VS/Data/mine/MyTTSDataset/",
meta_file_train="C:/Users/aj200/Desktop/VS/Data/mine/MyTTSDataset/metadata.csv",
language="ja",
)
DATASETS_CONFIG_LIST = [config_dataset]
CHECKPOINTS_OUT_PATH = os.path.join(OUT_PATH, "XTTS_v2.0_original_model_files/")
os.makedirs(CHECKPOINTS_OUT_PATH, exist_ok=True)
DVAE_CHECKPOINT_LINK = "https://coqui.gateway.scarf.sh/hf-coqui/XTTS-v2/main/dvae.pth"
MEL_NORM_LINK = "https://coqui.gateway.scarf.sh/hf-coqui/XTTS-v2/main/mel_stats.pth"
DVAE_CHECKPOINT = os.path.join(CHECKPOINTS_OUT_PATH, os.path.basename(DVAE_CHECKPOINT_LINK))
MEL_NORM_FILE = os.path.join(CHECKPOINTS_OUT_PATH, os.path.basename(MEL_NORM_LINK))
if not os.path.isfile(DVAE_CHECKPOINT) or not os.path.isfile(MEL_NORM_FILE):
print(" > Downloading DVAE files!")
ModelManager._download_model_files([MEL_NORM_LINK, DVAE_CHECKPOINT_LINK], CHECKPOINTS_OUT_PATH, progress_bar=True)
TOKENIZER_FILE_LINK = "https://coqui.gateway.scarf.sh/hf-coqui/XTTS-v2/main/vocab.json"
XTTS_CHECKPOINT_LINK = "https://coqui.gateway.scarf.sh/hf-coqui/XTTS-v2/main/model.pth"
TOKENIZER_FILE = os.path.join(CHECKPOINTS_OUT_PATH, os.path.basename(TOKENIZER_FILE_LINK))
XTTS_CHECKPOINT = os.path.join(CHECKPOINTS_OUT_PATH, os.path.basename(XTTS_CHECKPOINT_LINK))
if not os.path.isfile(TOKENIZER_FILE) or not os.path.isfile(XTTS_CHECKPOINT):
print(" > Downloading XTTS v2.0 files!")
ModelManager._download_model_files(
[TOKENIZER_FILE_LINK, XTTS_CHECKPOINT_LINK], CHECKPOINTS_OUT_PATH, progress_bar=True
)
SPEAKER_REFERENCE = [
"C:/Users/aj200/Desktop/VS/Data/wavs/voiceFile0_0.wav",
"C:/Users/aj200/Desktop/VS/Data/wavs/voiceFile1_0.wav",
"C:/Users/aj200/Desktop/VS/Data/wavs/voiceFile22.wav",
"C:/Users/aj200/Desktop/VS/Data/wavs/voiceFile512_0.wav",
"C:/Users/aj200/Desktop/VS/Data/wavs/voiceFile82_0.wav",
"C:/Users/aj200/Desktop/VS/Data/wavs/voiceFile56_0.wav",
"C:/Users/aj200/Desktop/VS/Data/wavs/voiceFile97.wav"
]
LANGUAGE = config_dataset.language
# '。' 를 기준으로 텍스트를 나눠 문장의 길이를 줄임.
def split_text(text, delimiter='。'):
sentences = text.split(delimiter)
return [s + delimiter for s in sentences if s]
# 텍스트를 분할하는 기준에 맞춰 오디오도 같이 분할
def split_audio(audio_path, split_durations):
audio = AudioSegment.from_wav(audio_path)
segments = []
start = 0
for duration in split_durations:
end = start + duration
segments.append(audio[start:end])
start = end
return segments
# 텍스트와 오디오 파일을 분할하는 함수
def split_text_and_audio(sample, delimiter='。'):
text = sample['text']
audio_file = sample['audio_file']
speaker_name = sample['speaker_name']
language = sample['language']
split_texts = split_text(text, delimiter)
audio = AudioSegment.from_wav(audio_file)
total_duration = len(audio)
split_durations = [total_duration * len(t) / len(text) for t in split_texts]
split_audios = split_audio(audio_file, split_durations)
return [{'text': t, 'audio_file': audio_file.replace(".wav", f"_{i}.wav"), 'speaker_name': speaker_name, 'language': language}
for i, (t, a) in enumerate(zip(split_texts, split_audios))]
def main():
# 모델 파라미터 설정
model_args = GPTArgs(
max_conditioning_length=132300, # 6초
min_conditioning_length=66150, # 3초
debug_loading_failures=False,
max_wav_length=255995, # 약 11.6초
max_text_length=200,
mel_norm_file=MEL_NORM_FILE,
dvae_checkpoint=DVAE_CHECKPOINT,
xtts_checkpoint=XTTS_CHECKPOINT,
tokenizer_file=TOKENIZER_FILE,
gpt_num_audio_tokens=1026,
gpt_start_audio_token=1024,
gpt_stop_audio_token=1025,
gpt_use_masking_gt_prompt_approach=True,
gpt_use_perceiver_resampler=True,
)
# 오디오 설정 정의
audio_config = XttsAudioConfig(sample_rate=22050, dvae_sample_rate=22050, output_sample_rate=24000)
# 학습 파라미터 설정
config = GPTTrainerConfig(
output_path=OUT_PATH,
model_args=model_args,
run_name=RUN_NAME,
project_name=PROJECT_NAME,
run_description="GPT XTTS training",
dashboard_logger=DASHBOARD_LOGGER,
logger_uri=LOGGER_URI,
audio=audio_config,
batch_size=BATCH_SIZE,
batch_group_size=48,
eval_batch_size=BATCH_SIZE,
num_loader_workers=0, # 멀티프로세싱 비활성화
num_eval_loader_workers=0, # 멀티프로세싱 비활성화
eval_split_max_size=256,
print_step=100,
plot_step=100,
log_model_step=1000,
save_step=10000,
save_n_checkpoints=1,
save_checkpoints=True,
optimizer="AdamW",
optimizer_wd_only_on_weights=OPTIMIZER_WD_ONLY_ON_WEIGHTS,
optimizer_params={"betas": [0.9, 0.96], "eps": 1e-8, "weight_decay": 1e-2},
lr=5e-06,
lr_scheduler="MultiStepLR",
lr_scheduler_params={"milestones": [50000 * 18, 150000 * 18, 300000 * 18], "gamma": 0.5, "last_epoch": -1},
test_sentences=[
{
"text": "やあ、先生。今日はどうしたの？",
"speaker_wav": SPEAKER_REFERENCE,
"language": LANGUAGE,
},
{
"text": "うーん... 音楽のCDを集めるのが好きだよ。特にヘビーメタルとかね。先生も好きなものはあるの？",
"speaker_wav": SPEAKER_REFERENCE,
"language": LANGUAGE,
},
{
"text": "これくらいでいい？",
"speaker_wav": SPEAKER_REFERENCE,
"language": LANGUAGE,
},
{
"text": "なんか用？まあ、問題があったら解決してあげるけど。",
"speaker_wav": SPEAKER_REFERENCE,
"language": LANGUAGE,
},
{
"text": "耳かきって？そういう趣味はないけど、なんでそんなこと聞くの？",
"speaker_wav": SPEAKER_REFERENCE,
"language": LANGUAGE,
},
],
)
model = GPTTrainer.init_from_config(config)
try:
train_samples, eval_samples = load_tts_samples(config_dataset, eval_split = True, eval_split_max_size = config.eval_split_max_size, eval_split_size = config.eval_split_size,)
if len(train_samples) == 0:
raise ValueError("Training samples are empty.")
if len(eval_samples) == 0:
raise ValueError("Evaluation samples are empty.")
# 학습 시작
trainer = Trainer(
TrainerArgs(
restore_path = None,
skip_train_epoch = False,
start_with_eval = START_WITH_EVAL,
grad_accum_steps = GRAD_ACUMM_STEPS,
),
config,
output_path=OUT_PATH,
model=model,
train_samples=train_samples,
eval_samples=eval_samples,
)
trainer.fit()
except Exception as e:
print(f"Error during training: {e}")
if __name__ == "__main__":
main()
다음 오디오는 모델 평가 과정에서 생성된 음성이다.
Your browser does not support the audio element.
Your browser does not support the audio element.
이제 학습한 모델을 기존 코드에 합쳐준다..
import sys
import atexit
from PyQt5.QtWidgets import QMainWindow, QApplication, QTextEdit, QLineEdit, QVBoxLayout, QLabel, QPushButton
from PyQt5.QtGui import QPixmap, QFont, QFontDatabase
from PyQt5.QtCore import QTimer
from selenium import webdriver
from selenium.webdriver.common.by import By
from selenium.webdriver.support.ui import WebDriverWait
from selenium.webdriver.support import expected_conditions as EC
from bs4 import BeautifulSoup
import time
from selenium.webdriver.chrome.options import Options
import subprocess
from selenium.webdriver.chrome.service import Service
from webdriver_manager.chrome import ChromeDriverManager
import os
import torch
import torchaudio
from TTS.TTS.tts.configs.xtts_config import XttsConfig
from TTS.TTS.tts.models.xtts import Xtts
import sounddevice as sd
CONFIG_PATH = "TTS/voice/tts/custum_ja/config.json"
TOKENIZER_PATH = "TTS/voice/tts/XTTS_v2.0_original_model_files/vocab.json"
XTTS_CHECKPOINT = "TTS/voice/tts/custum_ja/checkpoint_9300.pth"
SPEAKER_REFERENCE = "TTS/voice/tts/custum_ja/voiceFile0.wav"
def play_kayoko_TTS(text):
out = model.inference(
text,
"ja",
gpt_cond_latent,
speaker_embedding,
temperature=0.7, # Add custom parameters here
)
audio_data = torch.tensor(out["wav"]).numpy()
volume_factor = 0.3 # For example, reduce volume to 50%
audio_data = audio_data * volume_factor
sd.play(audio_data, samplerate=24000)
# TTS
config = XttsConfig()
config.load_json(CONFIG_PATH)
model = Xtts.init_from_config(config)
model.load_checkpoint(config, checkpoint_path=XTTS_CHECKPOINT, vocab_path=TOKENIZER_PATH, use_deepspeed=False)
model.cuda()
gpt_cond_latent, speaker_embedding = model.get_conditioning_latents(audio_path=[SPEAKER_REFERENCE])
subprocess.Popen(r'C:\Program Files\Google\Chrome\Application\chrome.exe --remote-debugging-port=9222 --user-data-dir="C:\chromeCookie"')
option = Options()
option.add_experimental_option("debuggerAddress", "127.0.0.1:9222")
driver = webdriver.Chrome(service=Service(ChromeDriverManager().install()), options=option)
# 웹사이트 접속
driver.get('https://chatgpt.com/g/g-1aLqNB1zW-kayoko')
chat_button_xpath = '//button[@class="mb-1 me-1 flex h-8 w-8 items-center justify-center rounded-full bg-black text-white transition-colors hover:opacity-70 focus-visible:outline-none focus-visible:outline-black disabled:bg-[#D7D7D7] disabled:text-[#f4f4f4] disabled:hover:opacity-100 dark:bg-white dark:text-black dark:focus-visible:outline-white disabled:dark:bg-token-text-quaternary dark:disabled:text-token-main-surface-secondary"]'
def addOneLenDiv():
lendiv = lendiv + 1
def input_Text(text):
inputarea = driver.find_element(By.ID, "prompt-textarea")
inputarea.send_keys(text)
driver.find_element("xpath",chat_button_xpath).click()
def get_latest_answer():
selector = ".markdown.prose.w-full.break-words.dark\:prose-invert.dark"
current_count = len(driver.find_elements(By.CSS_SELECTOR, selector))
WebDriverWait(driver, 20).until(
lambda x: len(x.find_elements(By.CSS_SELECTOR, selector)) > current_count
)
#time.sleep(4)
button = driver.find_element("xpath",chat_button_xpath)
while(button.is_enabled()):
pass
latest_answer_div = driver.find_elements(By.CSS_SELECTOR, selector)[-1]
p_text = latest_answer_div.find_elements(By.TAG_NAME, "p")
return p_text
def resource_path(relative_path):
try:
# PyInstaller creates a temp folder and stores path in _MEIPASS
base_path = sys._MEIPASS
except Exception:
base_path = os.path.abspath(".")
return os.path.join(base_path, relative_path)
class ChatUI(QMainWindow):
def __init__(self):
super().__init__()
# Set the background image
self.initUI()
def initUI(self):
# Window settings
self.setGeometry(100, 100, 1280, 960)
self.setWindowTitle('Chat UI Example')
QFontDatabase.addApplicationFont('./GodoB.ttf')
# Set the background
self.backgorund_label = QLabel(self)
background_image_path = resource_path('img/kayoko.jpg')
self.backgorund_label.setPixmap(QPixmap(background_image_path))
self.backgorund_label.setScaledContents(True)
self.backgorund_label.setFixedSize(1280,960)
# Create the name area
self.nameArea = QLabel("카요코",self)
self.nameArea.setFixedSize(1000,70)
self.nameArea.setStyleSheet(
"background-color: rgba(255,255,255,0);"
"border-width: 0px 0px 3px 0px;"
"border-style: solid;"
"border-color: rgba(138,138,138,200);"
"color: white;"
)
self.nameArea.setFont(QFont('고도 B',40))
self.nameArea.move(140,575)
# Create the explaination area
self.explain = QTextEdit(self)
self.explain.setReadOnly(True)
self.explain.append("흥신소 68")
self.explain.setFixedSize(500,60)
self.explain.move(320,590)
self.explain.setStyleSheet(
"background-color: rgba(255,255,255,0);"
"border-style: solid;"
"border-color: rgba(255,255,255,0);"
"color: rgba(74,162,188,200);"
)
self.explain.setFont(QFont('고도 B',25))
# Create the answer area
self.answerArea = QTextEdit(self)
self.answerArea.setReadOnly(True)
self.answerArea.setLineWrapMode(1)
self.answerArea.setLineWrapColumnOrWidth(1)
self.answerArea.setStyleSheet(
"background-color: rgba(255,255,255,0);"
"border-color: rgba(255,255,255,0);"
"border-style: solid;"
"font-weight: bold;"
"color: white;"
)
self.answerArea.setFixedSize(1000,220)
self.answerArea.move(140,660)
self.answerArea.setFont(QFont('고도 B',25))
# Create the chat display area
self.chat_display = QTextEdit(self)
self.chat_display.setReadOnly(True)
self.chat_display.setStyleSheet(
"background-color: qLineargradient(y1: 0, y2: 1, stop: 0 rgba(20, 27, 59, 0), stop: 0.1 rgba(20, 27, 59, 160));"
"border-color: rgba(255,255,255,0);"
"border-style: solid;"
"font-weight: bold;"
"font-size: 20px;"
"color: rgba(255,255,255,200);"
)
self.chat_display.setFixedSize(1280,450)
self.chat_display.move(0,510)
# Create the input text box
self.text_input = QLineEdit(self)
self.text_input.setStyleSheet(
"background-color: rgba(255, 255, 255, 200);"
"border-color: rgba(255,255,255,0);"
"border-radius: 20px;"
)
self.text_input.returnPressed.connect(self.on_enter)
self.text_input.setFixedSize(1000,60)
self.text_input.move(140,880)
self.text_input.setFont(QFont('고도 B', 25))
self.text_input.setTextMargins(20,0,0,0)
layout = QVBoxLayout()
layout.addWidget(self.nameArea)
layout.addWidget(self.text_input)
layout.addWidget(self.chat_display)
layout.addWidget(self.answerArea)
layout.addWidget(self.explain)
self.chat_display.lower()
self.backgorund_label.lower()
self.setLayout(layout)
self.show()
def show_Answer(self):
answer_arr = get_latest_answer()
answer = answer_arr[0].text
ja_answer = answer_arr[1].text
play_kayoko_TTS(ja_answer)
#answer = get_latest_answer()
self.answerArea.setText('')
self.text = answer
self.idx = 0
self.timer = QTimer(self)
self.timer.timeout.connect(self.typeLetter)
self.timer.start(80)
self.text_input.clear()
def typeLetter(self):
if self.idx < len(self.text):
self.answerArea.insertPlainText(self.text[self.idx])
self.idx += 1
else:
self.timer.stop()
def on_enter(self):
# Get text from input box and display it in the chat display area
input_textAPP = self.text_input.text()
input_Text(input_textAPP)
self.show_Answer()
# 상태 확인 간격
def closeEvent(self, event):
# 윈도우가 닫힐 때 웹드라이버 종료
driver.quit()
event.accept()
if __name__ == '__main__':
app = QApplication(sys.argv)
ex = ChatUI()
sys.exit(app.exec_())
# Register the driver.quit function to be called on program exit
atexit.register(driver.quit)
생각보다 음성의 품질이 좋지 않아서 만족스럽지가 않다.
따로 방법을 찾아야겠다..
-
-
Touch background to close
이승준
