본문 바로가기

Game DevTip/Algorithm5

5. 삽입정렬에 대해서 삽입 정렬(Insertion Sort)핵심 개념삽입 정렬은 이미 정렬되니 부분에 새로운 원소를 올바른 위치에 삽입하는 방식으로 동작하는 정렬 알고리즘이다. 마치 카드 게임에서 손패를 정렬하는 방식과 동일하다. 문제 정의 - 입력 : 양의 정수 n개의 키를 가진 배열 S[0...n-1]- 출력 : 오름차순으로 정렬된 배열 S[0...n-1]- 방법 : 각 원소를 이미 정렬된 부분의 적절한 위치에 삽입 핵심 아이디어1. 첫 번쨰 원소는 이미 정렬이 된 것으로 간주(미정렬부분과 정렬부분은 별개로 분리하여 따로 빼둔다.)2. 두 번째 원소부터 시작해서 하나씩 처리. 3. 현재 원소를 정렬된 부분의 올바른 위치에 삽입4. 모든 원소가 처리될 때까지 반복한다. 단계별 동작 과정초기 배열: [10, 7, 9, 1.. 2025. 7. 27.
4. 선택정렬과 이중 선택정렬에 대해서 알아보자. 정렬 알고리즘의 기초 개념정렬의 대상: 레코드(Record)struct Student { int id; // 학번 string name; // 이름 int score; // 점수}; 정렬의 대상: 레코드(Record) - 정렬키 : 정렬의 기준이 되는 필드 - 위 예시에서 id, name, score 중 어느 것이든 정렬키가 될 수 있다. 정렬 방향 - 오름차순 (Ascending) : 작은 값 -> 큰 값 - 내림차순 (Descending) : 큰 값 -> 작은 값 정렬 분류 : 메모리 사용에 따른 분류1. 내부 정렬 (internal Sorting) - 정렬 대상을 한꺼번에 메인 메모리에 로딩 가능 할 때, - 대부분의 기본 정렬 알고리즘이.. 2025. 7. 26.
3. 버블정렬 알고리즘에 대해서 버블 정렬이란?*버블 정렬(Bubble Sort)**은 가장 기본적인 정렬 알고리즘 중 하나로, 인접한 두 원소를 비교하여 순서가 잘못되어 있으면 교환하는 과정을 반복하는 방식이다.기본 정보입력: 양의 정수 n개의 키를 가진 배열 data[0..n-1]출력: 오름차순으로 정렬된 배열 data[0..n-1]정렬 방식: In-place sort (추가 메모리 공간을 거의 사용하지 않음)안정성: 안정 정렬 (Stable Sort) 버블 정렬이라 불리는 이유는 큰 원소가 배열의 끝으로 이동하는 모습이 마치 물속에서 기포(bubble)가 수면으로 떠오르는 것과 같다고 생각해서 그렇다고 한다....(.....진짜로..?) 동작 원리 1. 인접한 두 원소를 비교한다.2. 순서가 잘못되어 있으면 교환한다.3. 배열 .. 2025. 7. 25.
2. Algorithm : 알고리즘에 대해서 알고리즘이란 무엇인가?알고리즘은 하나의 문제를 해결하기 위한 단계적 절차나 방법을 의미한다. 같은 문제라도 여러가지 다른 방법으로 해결 할 수 있으며, 이때 효율성이 가장 중요한 선택 기준이 됨. 알고리즘의 핵심 특징- 명확성 : 각단계가 명확하고 모호하지 않아야 함.- 유한성: 유한한 단계 내에서 종료되어야 함.- 입력 : 0개 이상의 입력이 있어야 함- 출력 : 1개 이상의 출력이 있어야 함. - 효율성 : 문제 해결에 걸리는 시간과 공간이 합리적이어야 함. 실생활 예시: 전화번호부에서 이름 찾기문제: 전화번호부에서 "홍길동"의 전화번호 찾기방법 1: 순차검색1. 전화번호부의 첫 페이지부터 시작2. 한 명씩 차례대로 이름을 확인3. "홍길동"을 찾을 때까지 반복4. 찾으면 전화번호 반환 방법 2:.. 2025. 6. 9.
1. Algorithm : 피보나치 수열 & 다이나믹 프로그래밍 피보나치 수열이란? - 피보나치 수열은 이탈리아 수학자 레오나르도 피보나치가 발견한 수열이다. 앞의 두수를 더해서 다음 수를 만들어가는 규칙을 가지고 있음. 참고로 알고리즘을 할 때 해당 수학적 걔념이 많이 쓰인다 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...규칙을 자세히 보면:0번째: 01번째: 12번째: 0 + 1 = 13번째: 1 + 1 = 24번째: 1 + 2 = 35번째: 2 + 3 = 5수학적으로 표현하면: F(n) = F(n-1) + F(n-2)이다. 피보나치 수열을 구현하는 3가지 방법1. 반복문 방식(for문) - 가장 직관적이다. 2. 재귀 방식 - 수학적 정의와 가장 유사하다. 3. 다이나믹 프로그래밍 방식 - 가장 효율적이다. 1. 반복문(for문) .. 2025. 6. 9.

티스토리툴바