■ 퀵 정렬(Quick Sort)퀵 정렬은 기준값(Pivot)을 하나 선택한 뒤, 그보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 보내며 배열을 분할하고, 각 부분을 재귀적으로 다시 정렬하는 알고리즘이다.퀵 정렬의 핵심 원리는 다음과 같다.Pivot(기준값)을 하나 정한다.배열을 pivot보다 작은 부분과 큰 부분으로 나눈다.이 두 부분을 재귀적으로 다시 퀵 정렬한다.이처럼 퀵 정렬은 분할(Divide) → 정복(Conquer) → 결합(Combine)의 순서를 따르는 전형적인 분할 정복(Divide and Conquer) 알고리즘이다.조금 복잡해 보일 수 있지만, pivot을 기준으로 어떻게 분할되고, 재귀가 어디까지 이어지는지만 이해하면 직접 구현하는 데에도 큰 어려움이 없다. ■ 퀵 정렬 구현 - Ho..

■ 삽입 정렬(Insertion Sort)삽입 정렬은 사람이 수를 정렬할 때 사용하는 방식과 매우 유사하게 동작한다.예를 들어, 손에 1부터 9까지 무작위로 섞인 카드를 들고 있다고 생각해 보자. 그럼 우리는 가장 왼쪽부터 카드를 꺼내, 앞쪽에 이미 정렬된 카드 들 중에서 자신이 들어갈 위치를 찾아 끼워 넣는 방식으로 정렬한다.삽입 정렬도 이와 같은 방식으로 동작한다.삽입 정렬은 현재 선택된 값을 정렬된 앞쪽 부분과 비교하면서, 자신이 들어갈 적절한 위치를 찾아 삽입한다.오름차순 정렬 기준으로, 현재 값보다 앞들에 있는 값이 큰지 확인한다.값이 크다면, 그 값들을 한 칸씩 뒤로 밀어내면서 빈 자리를 만든다.만들어진 빈 자리에 현재 값을 삽입하여 정렬한다. ■ 삽입 정렬 구현(C#)public static..

■ 선택 정렬(Selection Sort)선택 정렬은 배열에서 값을 하나 선택한 뒤, 뒤쪽 값들과 비교해 최솟값(오름차순 기준)을 찾아 교환하는 방식으로 앞쪽부터 순차적으로 정렬해 나가는 알고리즘이다.선택 정렬의 동작 방식은 아래와 같다.배열의 첫 번째 값을 선택한다.나머지 값들과 비교하면서 가장 작은 값을 찾는다.찾은 최소값을 현재 위치와 교환한다.다음 위치로 이동해 배열의 끝까지 이를 반복하며 정렬한다.즉, 버블 정렬(Bubble Sort)과 달리, 선택 정렬은 각 사이클마다 배열의 길이에 비례한 비교 연산을 수행하지만, 실제로 값의 교환은 한 번만 발생한다.버블 정렬은 인접한 두 값을 비교하며 여러 변 교환을 수행하지만, 선택 정렬은 가장 작은 값을 찾고 한 번만 교환하기 때문. ■ 선택 정렬 구현..

■ 버블 정렬(Bubble Sort)버블 정렬이란 이름은 큰 값이 뒤로 떠오르는 모습이 마치 물속에서 거품(버블)이 위로 올라가는 것처럼 보인다는 데서 유래된 이름이다.버블 정렬은 인접한 두 개의 원소를 비교하는 방식으로 정렬을 수행한다. 현재 탐색 중인 요소의 인덱스 번호를 $n$이라 한다면,arr[n] > arr[n+1] 이라면, 두 원소의 값을 서로 교환한다. (오름차순 정렬 기준)위 비교는 “$n + 1 만족하는 동안 반복된다.즉, 첫 번째 반복이 끝나면 배열에서 가장 큰 값이 맨 뒤에 위치하게 된다. 두 번째 반복이 끝나면 두 번째로 큰 값이 그 앞자리에 위치하게 된다.이렇게 반복이 진행될수록 가장 큰 값이 점차 뒤쪽으로 이동하게 되는 알고리즘이다. ■ 버블 정렬 구현(C#)버블 정렬의 구현 ..

■ 자료구조(Data structure)자료(data)를 효율적으로 저장하고, 효율적으로 접근하고, 관리하기 위한 구조(structure)이다.프로그래밍에서 “데이터”는 언제나 핵심이다. 이 데이터를 어떻게 저장할지, 꺼낼지, 정렬할지, 검색할지가 프로그램의 성능을 좌우한다.자료구조는 이러한 것을 잘할 수 있도록 도와주는 “틀”이다.넓은 의미에서 int 변수처럼 단순한 데이터 저장도 자료구조에 포함되며, 구조체(struct), 배열(array) 그리고 파일이 데이터를 저장하는 방식까지 모두 자료구조의 한 형태로 볼 수 있다.이름특징선형(Linear) 구조 각 요소가 일렬로 나열되며, 한 요소 다음에 오직 하나의 요소만 존재할 수 있는 구조. (예 : 리스트, 배열, 스택, 큐 등..)비선형(Non-Lin..

■ 동기(Synchronous)와 비동기(Asynchronous)동기와 비동기는 작업을 처리하는 방식의 차이를 나타내는 개념이다. 프로그래밍에서는 아래와 같은 의미로 사용된다.동기(Synchronous) : 작업이 순차적으로, 동일한 흐름 내에서 처리된다. 앞선 작업이 끝나야 다음이 실행된다.(일반적인 코드 실행 흐름.)OrderFood();Pay(); // => OrderFood()가 끝나야 실행.PrintReceipt(); // => Pay()가 끝나야 실행.비동기(Asynchronous) : 작업이 병렬적으로, 또는 다른 흐름에서 실행될 수 있다. 하나의 작업이 완료되기를 기다리지 않고, 그 사이 다른 작업이 함께 진행될 수 있다. public class Asynchronous ..

■ 벽 생성 이제 BSP 알고리즘으로 생성한 던전에 벽을 배치하여 마무리한다.벽은 Mesh를 사용해서 통으로 생성하는 것이 아니라, 벽 오브젝트를 1 유닛 단위로 배치하여 맵 전체를 감싸는 방식으로 구현한다. ■ 상세 구현벽 생성 로직 자체는 비교적 단순하다.각 방의 좌하단→우하단(수평), 좌하단 → 좌상단(수직) 방향으로 1씩 좌표를 증가시키며, 벽을 배치할 좌표를 저장한다.동일하게 반대 방향(좌상단→ 우상단(수평), 우하단 → 우상단(수직)) 방향도 기록한다.좌표 기록은 바닥 Mesh를 생성할 때 같이 진행한다.단, 복도와 겹치는 구간에는 벽을 생성하면 안 된다.따라서 벽을 배치할 좌표를 저장할 때, 이미 기록된 좌표가 넘어온다면 복도와 겹치는 공간이므로 저장된 좌표를 삭제한다.public class..

■ 복도 생성 BSP로 완성된 이진트리를 역방향으로 순회하며, 자식 노드에 생성된 방 사이를 복도로 연결한다. 복도 생성은 다음과 같은 흐름으로 진행된다. 복도 생성 절차트리의 가장 깊은 곳부터 시작하여, 자식 노드를 가진 부모 노드를 찾는다.두 자식 노드의 상대적인 위치(상,하,좌,우)를 파악한다.두 방이 연결 가능한 위치에 있는지 확인한다.연결이 가능하다면 복도를 생성한다. 연결이 불가능하다면, 다른 노드를 대상으로 연결 가능 여부를 다시 체크한다. ■ 상세 구현 내용1. 연결 대상 찾기using System.Collections.Generic;using System.Linq;public class CorridorGenerator{ private List _roomNodes; private..

2025/05/15- 조건부 분할 위치를 계산하는 부분에서 offset * 2를 기준으로 방 최소 사이즈를 만족하는지 확인하는 코드 수정.- 코드 변경에 따른 최종 결과 갱신.■ BSP 알고리즘 개선 현재 구현된 BSP 알고리즘은 분할 조건이 단순하기 때문에, 분할 방향이 한쪽(가로 또는 세로)으로만 생성되어 지나치게 긴 복도가 생성되는 경우가 존재한다.따라서 추가 조건을 생성하여 균등하게 공간이 분할될 수 있도록 수정한다. 1. 분할 방향 조건 추가var widthStatus = node.Width >= _data.RoomMinWidth * 2;var heightStatus = node.Height >= _data.RoomMinHeight * 2;var splitDir = (widthStatus, he..