얌생

오늘의 목표

⏱️ 오늘의 일정

최종 프로젝트 전 [팀프로젝트 끝]

최종 프로젝트 시작

📜 최종 프로젝트 전 [팀프로젝트 끝]

TCP로 타워 디펜스 온라인게임을 만드는 팀프로젝트가 끝났다.

앞서 포스팅한대로 원래는 9조 였으나, 팀원 2분의 건강 이슈로 인해 팀이 결국 폭파되어

늦게 2조에 합류해서 팀프로젝트를 진행했다.

아무래도 늦게 합류하다보니... 이미 코드 구현 담당자가 모두 배분되어 맡아야 하는 부분이 없던 상황이라.. ㅠㅠ

팀원들을 보조하는 느낌으로 진행했다. 그래도 내 이름으로 맡은 부분은 있어야 했기 때문에,

이전 개인 프로젝트에서 만들었던 더미 클라이언트( 스트레스 테스트 )를 이번 프로젝트에도 적용해보겠다고 팀에 말해서,

더미 클라이언트는 내가 담당해 만들었다. 

우리가 만든 게임은 위 그림처럼 2명의 유저가 방에 들어가서 오른쪽에 있는 성이 먼저 파괴되는 유저가 패배하는 게임이다. 개인 프로젝트와는 다르게 500명을 접속해 패킷을 전송해도 지연되는 상황은 딱히 발견되지 않았다.

아무래도 방안에 들어있는 2명에 대한 패킷을 받아 전달하기 때문에 패킷을 빠르게 처리할 수 있어서 지연 상황에 대한 문제는 발생하지 않은 것으로 추론했다.

트러블 슈팅은 총 3가지로 다음과 같다.

📜 최종 프로젝트 시작

팀프로젝트 발표가 끝난후, 내일배움캠프의 마지막 팀프로젝트인 최종프로젝트 주차에 진입했다.

이번 기수는 유니티클라 기수와 협업해서 진행할 수 있는 기수였는데, 아쉽게도 유니티클라 팀과의 협업은 하지 못하게 됐다.

아쉽지만.. 그래도 이번에 배정된 동료분들과 같이 우리가 원하는 재밌는 게임과 서버를 멋지게 만들어 봐야겠다.

캠프에서 제공해주는 클라 사용법을 내일 알려준다고 하는데, 어떤 클라를 제공해주는지 면밀하게 분석해봐야겠다.

루트 노드 또는 임의 노드에서 인접한 노드부터 먼저 탐색하는 방법

큐를 통해 구현한다. ( 해당 노드의 주변부터 탐색해야하기 때문 )

• 최소 비용 ( 즉, 모든 곳을 탐색하는 것보다 최소 비용이 우선일 때 )에 적합

시간 복잡도

• 인접 행렬 : O ( V^2 )
• 인접 리스트 : O ( V+E )

코드

#include <stdio.h>

int map[1001][1001], bfs[1001];
int queue[1001];

void init(int *, int size);

void BFS(int v, int N) {
	int front = 0, rear = 0;
	int pop;

	printf("%d ", v);
	queue[rear++] = v;
	bfs[v] = 1;

	while (front < rear) {
		pop = queue[front++];

		for (int i = 1; i <= N; i++) {
			if (map[pop][i] == 1 && bfs[i] == 0) {
				printf("%d ", i);
				queue[rear++] = i;
				bfs[i] = 1;
			}
		}
	}

	return;
}

int main(void) {

	init(map, sizeof(map) / 4);
	init(bfs, sizeof(bfs) / 4);
	init(queue, sizeof(queue) / 4);

	int N, M, V;
	scanf("%d%d%d", &N, &M, &V);

	for (int i = 0; i < M; i++)
	{
		int start, end;
		scanf("%d%d", &start, &end);
		map[start][end] = 1;
		map[end][start] = 1;
	}

	BFS(V, N);

	return 0;
}

void init(int *arr, int size) {
	for (int i = 0; i < size; i++)
	{
		arr[i] = 0;
	}
}

DFS

 루트 노드 혹은 임의 노드에서 다음 브랜치로 넘어가기 전에, 해당 브랜치를 모두 탐색하는 방법

스택 or 재귀함수를 통해 구현한다.

• 모든 경로를 방문해야 할 경우 사용에 적합

시간 복잡도

• 인접 행렬 : O( V^2 )
• 인접 리스트 : O ( V+E )

V는 접점, E는 간선을 뜻한다.

#include <stdio.h>

int map[1001][1001], dfs[1001];

void init(int *, int size);

void DFS(int v, int N) {

	dfs[v] = 1;
	printf("%d ", v);

	for (int i = 1; i <= N; i++) {
		if (map[v][i] == 1 && dfs[i] == 0) {
			DFS(i, N);
		}
	}

}

int main(void) {

	init(map, sizeof(map) / 4);
	init(dfs, sizeof(dfs) / 4);

	int N, M, V;
	scanf("%d%d%d", &N, &M, &V);

	for (int i = 0; i < M; i++)
	{
		int start, end;
		scanf("%d%d", &start, &end);
		map[start][end] = 1;
		map[end][start] = 1;
	}

	DFS(V, N);

	return 0;
}

void init(int *arr, int size) {
	for (int i = 0; i < size; i++)
	{
		arr[i] = 0;
	}
}

일종의 설계 기법이며, 설계 방법이다.

목적

SW 재사용성, 호환성, 유지 보수성을 보장

특징

디자인 패턴은 아이디어고, 특정한 구현이 아니다.

프로젝트에 항상 적용해야 하는 것은 아니지만, 추후 재사용, 호환, 유지 보수시 발생하는

문제 해결을 예방하기 위해 패턴을 만들어 둔 것이라고 생각하면 된다.

분류

1. 생성 패턴 ( Creational ) : 객체의 생성 방식 결정

 Class-creational patterns, Object-creational patterns

2. 구조 패턴 ( Structural ) : 객체간의 관계를 조직

3. 행위 패턴 ( Behavioral ) : 객체의 행위를 조직, 관리, 연합

힙 정렬은 완전 이진 트리를 기본으로 하는 힙( Heap ) 자료구조를 기반으로 한 정렬 방식을 말한다.

완전 이진 트리

삽입할 때 왼쪽부터 차례대로 추가하는 이진 트리

힙 정렬은 불안정 정렬에 속한다.

시간복잡도

평균 : O(nlogn)

최선 : Ω(nlogn)

최악 : O(nlogn)

과정

1. 최대 힙을 구성한다.

2. 현재 힙 루트에 가장 큰 값이 존재. 루트의 값을 마지막 요소와 바꾼 후, 힙의 사이즈를 하나 줄인다.

3. 힙의 사이즈가 1보다 크면 위 과정을 반복한다.

루트를 마지막 노드로 대체 ( 11 -> 4 ), 다시 최대 힙을 구성

이와 같은 방식으로 최대 값을 하나씩 뽑아내면서 정렬하는 것을 힙 정렬이라 한다.

public void heapSort(int[] array) {
    int n = array.length;
    
    // max heap 초기화
    for (int i = n/2-1; i>=0; i--){
        heapify(array, n, i); // 1
    }
    
    // extract 연산
    for (int i = n-1; i>0; i--) {
        swap(array, 0, i); 
        heapify(array, i, 0); // 2
    }
}

1번째 heapify

 - 일반 배열을 힙으로 구성하는 역할

   자식노드로부터 부모노드 비교

 n / 2-1 부터 0 까지 인덱스가 도는 이유 

   - 부모 노드의 인덱스를 기준으로 왼쪽 자식노드 ( i2 + 1 ), 오른쪽 자식 노드 ( i2 + 2 )이기 때문

2번째 heapify

 요소가 하나 제거된 이후에 다시 최대 힙을 구성하기 위함

 루트를 기준으로 진행 ( extract 연산 처리를 하기 위함 )

public void heapify(int array[], int n, int i) {
    int p = i;
    int l = i*2 + 1;
    int r = i*2 + 2;
    
    //왼쪽 자식노드
    if (l < n && array[p] < array[l]) {
        p = l;
    }
    //오른쪽 자식노드
    if (r < n && array[p] < array[r]) {
        p = r;
    }
    
    //부모노드 < 자식노드
    if(i != p) {
        swap(array, p, i);
        heapify(array, n, p);
    }
}

다시 최대 힙을 구성할 때까지 부모 노드와 자식 노드를 swap하며 재귀로 진행한다.

퀵정렬과 합병정렬의 성능이 좋기 때문에 힙 정렬의 사용빈도가 높지는 않다.

하지만 힙 자료구조가 많이 활용되고 있고, 이때 합께 따라오는 개념이 힙 정렬이다.

힙 정렬이 유용할 때

- 가장 크거나 가장 작은 값을 구할 때

• 최소 힙  or 최대 힙의 루트 값이기 때문에 한번의 힙 구성을 통해 구하는 것이 가능하다.

- 최대 k 만큼 떨어진 요소들을 정렬할 때

• 삽입정렬보다 더욱 개선된 결과를 얻어낼 수 있다.

전체 코드

private void solve() {
    int[] array = { 230, 10, 60, 550, 40, 220, 20 };
 
    heapSort(array);
 
    for (int v : array) {
        System.out.println(v);
    }
}
 
public static void heapify(int array[], int n, int i) {
    int p = i;
    int l = i * 2 + 1;
    int r = i * 2 + 2;
 
    if (l < n && array[p] < array[l]) {
        p = l;
    }
 
    if (r < n && array[p] < array[r]) {
        p = r;
    }
 
    if (i != p) {
        swap(array, p, i);
        heapify(array, n, p);
    }
}
 
public static void heapSort(int[] array) {
    int n = array.length;
 
    // init, max heap
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(array, n, i);
    }
 
    // for extract max element from heap
    for (int i = n - 1; i > 0; i--) {
        swap(array, 0, i);
        heapify(array, i, 0);
    }
}
 
public static void swap(int[] array, int a, int b) {
    int temp = array[a];
    array[a] = array[b];
    array[b] = temp;
}

오늘의 목표

⏱️ 오늘의 일정

프로그래머스 코테 문제 풀이

📜 프로그래머스 코테 문제 풀이

H-Index

https://github.com/YamSaeng/AlgorithmCodingTest/tree/main/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/2/42747.%E2%80%85H%EF%BC%8DIndex

📜 팀 프로젝트 진행

팀 프로젝트에서 맡은 파트인 게임 오버를 하려면 프로젝트가 어느정도 진행이 되야하는 상황이라서

팀원 분중 한분이 맡고 계셨던 걸 도와주는 식으로 우선 프로젝트를 진행했다.

추가로 맡은 부분은 위 그림처럼 회원가입 부분인데, 

export const registHandler = async ({ socket, payload }) => { 

  let registerResponsePayloadData = {};

  // 비밀번호 해시화
  let hashPassword = await bcrypt.hash(payload.password, 10);

  // 유저 검색
  let user = await DatabaseManager.GetInstance().findUser(payload.id, payload.email);

  if (user === undefined) {
    // 유저가 없다면 회원가입 진행
    DatabaseManager.GetInstance().createUser(payload.id, payload.email, hashPassword);

    registerResponsePayloadData.success = true;
    registerResponsePayloadData.message = '회원가입 성공';
    registerResponsePayloadData.failCode = 0;
  } else {
    // 이미 id값을 가진 유저가 DB에 저장되어 있음 ( 회원가입 실패 )
    registerResponsePayloadData.success = false;
    registerResponsePayloadData.message = '이미 존재하는 사용자입니다';
    registerResponsePayloadData.failCode = 1;
  }

  const registerResponsePacket = createResponse(
    PACKET_TYPE.REGISTER_RESPONSE,
    registerResponsePayloadData,
    socket.sequence,
  );
  
  socket.write(registerResponsePacket);
};

기본적으로 클라에서 보낸 아이디와 이메일이 DB에 있는지 확인하고, 회원 정보를 DB에 기록한다.

그 후 클라에게 적절한 응답 메세지 패킷을 보내주는걸로 구현을 완료했다.

오늘의 목표

⏱️ 오늘의 일정

프로그래머스 코테 문제 풀이

팀 프로젝트 진행

📜 프로그래머스 코테 문제 풀이

연속 부분 수열 합의 개수

https://github.com/YamSaeng/AlgorithmCodingTest/tree/main/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/2/131701.%E2%80%85%EC%97%B0%EC%86%8D%E2%80%85%EB%B6%80%EB%B6%84%E2%80%85%EC%88%98%EC%97%B4%E2%80%85%ED%95%A9%EC%9D%98%E2%80%85%EA%B0%9C%EC%88%98

function sumFunc(array) {
    let sum = 0;
    for (let i = 0; i < array.length; i++) {
        sum += array[i];
    }

    return sum;
}

function solution(elements) {
    const answer = new Set();
    
    for (let i = 1; i <= elements.length; i++) {
        for (let j = 0; j < elements.length; j++) {            
            if (j + i > elements.length) {
                let sliceEndArr = elements.slice(j, elements.length);
                let sliceEndNextArr = elements.slice(0, j + i - elements.length);

                answer.add(sumFunc(sliceEndArr) + sumFunc(sliceEndNextArr));
            }
            else {
                let commonSliceArr = elements.slice(j, j + i);

                answer.add(sumFunc(commonSliceArr));
            }
        }
    }

    return answer.size;
}

slice를 이용해 풀긴했는데, 시간이 간당간당 한거 같아 마음을 졸였지만 다행히도 통과했다.

슬라이딩 윈도우 기법을 사용하면 시간을 줄일 수 있다고 하는데, 코드를 찾아봐야겠다.

📜 팀 프로젝트 진행

원래는 9조 였는데, 팀원 분들 중 2명이 몸이 아파서 빠지게 되어, 결국 조를 옮기게 되었다.. ㅠㅠ

안타깝게도.. 코드를 구현할 방법도 회의를 마치고, 컨펌을 받으려고 했는데..

새로 옮긴 조에서 열심히 참여해봐야겠다.. 아무래도 늦게 참여하다보니 간단한 부분을 맡게 되었다.

아무래도 굴러들어온 돌이니.. 전반적으로 코딩하는걸 도와주는 느낌으로 진행 해야겠다.

기본적으로 맡은건 게임 오버인데, 이전 개인과제에서 더미를 생성하는 부분을 만들어 본 경험이 있어서

더미 클라도 한번 만들어보겠다고 팀장님한테 얘기를 해서 추가했다.

이번 팀 프로젝트는 타워 디펜스를 온라인으로 진행하는 것인데

게임 진행 단계는 위 그림과 같다.

한 방에 2명이 접속을해 각자 게임을 진행하고, 2명 중 한명이 먼저 게임을 클리어 하면 승리하는 게임이다.

오늘의 목표

⏱️ 오늘의 일정

개인 프로젝트 완성

📜 개인프로젝트 완성

개인 프로젝트를 완성해서 캠프에 제출했다.

2024.10.30 - [분류 전체보기] - [내일배움캠프][TIL] 48일차 - 개인프로젝트 진행

이전 글 아래에 있는 이해가 안되는 부분인 OnEnd() 함수가 작동하지 않는 부분에 대한 튜터님의 피드백을

남기려고 한다.

내가 사용하는 OS 환경이 windows인데, 정말 당황스럽게도 MacOS에서 같은 코드를 실행하면,

OnEnd() 함수가 매우 작동이 잘된다..

정말 OS때문에 이런건가.. 싶어서 튜터님에게 찾아가 물어보니, 자바스크립트에서는 OS마다 코드를 따로 작성하지 않고,

하나의 코드로 실행을 하는데, 문제점이 어디인지는 직접 아랫단으로 내려가서 확인을 해봐야 한다는 피드백을 받았다.

https://www.korecmblog.com/blog/node-js-event-loop

이 블로그에서 소개하는 이벤트 루프를 분석해야한다는 말인데... 말은 쉽다.. ㅠㅠ

여튼 OnEnd와 같은 이벤트를 너무 믿지 않고, 직접 위 글에서 소개한 특정 프로토콜을 생성해

서버에서 직접 탐지할 수 있도록 하는 것이 좋겠다라는 점도 피드백을 받았다.

git 주소

https://github.com/YamSaeng/TCPMultiple

다음주 부터 최종 프로젝트 전 마지막 팀 프로젝트인데, 잘 준비해서 제 시간 안에 완성 할 수 있도록 노력해야겠다.

오늘의 목표

⏱️ 오늘의 일정

프로그래머스 코테 문제 풀기개인프로젝트 진행

📜 프로그래머스 코테 문제 풀기

의상

https://github.com/YamSaeng/AlgorithmCodingTest/tree/main/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/2/42578.%E2%80%85%EC%9D%98%EC%83%81

객체( map 구조 )를 이용해 푸니 쉽게 풀 수 있었다.

function solution(clothes) {
    const clothesMap = {};
    let answer = 1;
    clothes.forEach(cloth => {  
        const [type, name] = cloth;
        if(clothesMap.hasOwnProperty(name)) {
            clothesMap[name]++; 
        }
        else {
            clothesMap[name] = 1;
        }
    })

    for(const key in clothesMap) {
        answer *= (clothesMap[key] + 1);
    }    
    return answer - 1;
}

📜 개인프로젝트 진행

더미의 개수를 늘려 서버 과부하 테스트를 진행해봤다.

100, 200, 300, 400 명까지는 서버에서 감당을 하는데, 500명 정도 되니 렉이 걸려 버벅이는것이 느껴질 정도였다.

아래 함수 DummyclientCreate는 매개변수로 수를 받아 해당 수만큼 더미를 생성하고 접속하는 역할을 담당한다.

async function DummyClientCreate(count: number) {
    for (let i = 0; i < count; i++) {
        const dummyClient = new Client();
        DummyClients.push(dummyClient);

        dummyClient.Connect();
        await delay(100);        
    }
}

delay는 말그대로 서버 접속 할때 일정 시간 텀을 두고 connect를 할 수 있도록 만든 함수다.

이해가 안되는 부분이 하나가 있는데, 우회하는 방식으로 해결을 했다.

내용은 다음과 같다.

클라의 수가 200명이 넘어가면, 유니티로 접속하고 유니티 클라를 종료해도 

서버의 OnEnd가 작동하지 않는 문제가 생겼다.

신기하게도 100명 정도에서는 문제 없이 OnEnd가 작동을 하는데, 200이 넘어가면 OnEnd가 작동을 하지 않으니

당최 이해를 할 수가 없었다.. ㅠㅠ

구글링을 찾아봐도 도저히 답이 안나와서 PingPacket을 이용해 접속끊긴 대상을 탐지하는 방식으로 우회해 해결했다.

User는 pongCount라는 변수를 가진다.

pongCount는 서버에서 pingPacket을 User에게 보낼때마다 1씩 증가한다. ( 1초에 1씩 늘어남 )

클라가 pingPacket을 받아서 서버로 pongPacket을 보내면 해당 User의 pongCount를 0으로 초기화한다.

위와 같이 로직을 구성했을 때, 만약 해당 유저가 접속이 끊긴 것이라면, pongCount는 0으로 초기화 되지 않고,

누적해서 계속 쌓이게 된다. 이 점을 이용해서 일정 숫자 이상이 되면 해당 유저는 접속이 끊긴 것이라고 판단하고,

접속을 끊는다.

 if (user.pongCount >= config.gameserver.pongCount) {
      user.GetSocket().end();

      OnEnd(user.GetSocket());                
}

이처럼 구성을 하니 OnEnd가 작동하지 않더라도 접속 끊긴 대상을 탐지 할 수 있게 되었다.

위 코드처럼 서버에서 대상을 끊게되니,

이미 끊은 대상에 대해 패킷을 전송하는 경우가 생기게 되었다.

  if(locationUpdateUser.pongCount < config.gameserver.pongCount)
        {
            socket.write(usersLocationPacket);            
        }

따라서 위 코드처럼 패킷을 클라에게 전송하기 전에 해당 유저의 pongCount가 최대 pongCount를 넘겼는지 확인하고,

데이터를 보내주는 방식으로 해결했다.

Javscript에서 제공하는 스케줄링 함수는 다음과 같다.

setTimeout

let id = setTimeout(()=>{
	내용
}, 밀리초);

일정시간 ( = 내가 설정한 밀리초 ) 후에 콜백 함수를 실행해준다.

setTimeout 함수를 실행하면 타이머 식별자를 반환해줘서,

해당 타이머 식별자를 통해 예약되어 있는 setTieout 함수 실행을 취소 해 줄 수 있다.

clearTimout

clearTimeout(식별자 id);

위처럼 clearTimeout을 통해 취소해 줄 수 있다. 단, 취소가 되더라도 해당 식별자의 값은 null이 되지는 않는다.

setInterval

let id = setInterval(()=>{
	내용
}, 밀리초);

일정시간 ( = 내가 설정한 밀리초 ) 마다 콜백 함수를 실행해준다.

setTimeout과 마찬가지로 함수를 실행하면 식별자를 반환해줘서 취소해 줄 수 있다.

clearInterval

clearInterval(식별자 아이디);

위처럼 clearInterval을 통해 취소해 줄 수 있다.

setInterval, 중첩 setTimeout 비교

setInerval 사용

let i=0;
serInterval(function(){
	func(i++);
}, 100);

• setInterval을 사용하면 func 호출 사이의 지연 간격이 실제 명시한 간격(여기서는 100ms)보다 짧아진다.
• func을 실행하는 데 소모되는 시간도 지연 간격에 포함시키기 때문
• func 실행 시간이 명시한 간격보다 길어지면 함수 실행이 종료될 때까지 기다리고 종료되면 바로 다음 호출을 시작한다.
• 따라서 함수 호출에 걸리는 시간이 매번 delay 밀리 초보다 길면, 모든 함수가 한번에 쉼 없이 연속으로 호출된다.

중첩 setTimeout 사용

setTimeout을 재귀적으로 호출하면 setInterval을 쓰는 것처럼 사용할 수 있다.

let i = 1;
setTimeout(function run() {
  func(i++);
  setTimeout(run, 100);
}, 100);

• 중첩 setTimeout을 사용하면 명시한 지연( 여기서는 100ms )이 보장된다.
• 지연 간격이 보장되는 이유는 이전 함수의 실행이 종료(=완료)된 이후에 다음 함수 호출에 대한 계획이 세워지기 때문