EYEN
knockon rev 2week TIL 본문
1. 정렬 알고리즘
정렬 알고리즘은 자료구조를 기준에 따라 오름차순, 내림차순으로 정렬하는 기능
BIG-O 표기법은 알고리즘의 효율성을 상한선을 기준으로 표기한 방법입니다. O(1), O(N), O(log N) 과 같은 형태로 사용
각 정렬의 시간 복잡도 (Big-O)
| 정렬 알고리즘 | 최선 | 평균 | 최악 |
| 버블 정렬 | O(n) | O(n²) | O(n²) |
| 선택 정렬 | O(n²) | O(n²) | O(n²) |
| 삽입 정렬 | O(n) | O(n²) | O(n² |
1) 버블 정렬
#include <stdio.h>
#include <stdlib.h>
int main() {
// 정렬할 정수 배열 선언 및 초기화
int arr[10] = { 4, 6, 2, 7, 5, 1, 8, 9, 10, 3 };
int temp; // 두 값을 바꿀 때 사용할 임시 변수
// 초기 배열 출력
for (int i = 0; i < 10; i++) {
printf("%d ", arr[i]);
}
// 버블 정렬 시작
// 총 9번 반복 (배열 크기 - 1)
for (int i = 0; i < 9; i++) {
// 매 반복마다 뒤에서 i개는 이미 정렬되었으므로 제외
for (int j = 0; j < 9 - i; j++) {
// 현재 원소가 다음 원소보다 크면 위치 교환
if (arr[j] > arr[j + 1]) {
// 두 원소를 바꾸기 위한 temp 사용
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
printf("\n"); // 줄 바꿈
// 정렬된 배열 출력
for (int i = 0; i < 10; i++) {
printf("%d ", arr[i]);
}
return 0; // 프로그램 종료
}2) 선택 정렬
#include <stdio.h>
int main() {
int arr[10] = { 4, 6, 2, 7, 5, 1, 8, 9, 10, 3 };
int minIndex, temp;
// 초기 배열 출력
for (int i = 0; i < 10; i++) {
printf("%d ", arr[i]);
}
// 선택 정렬 시작
for (int i = 0; i < 9; i++) {
minIndex = i; // 현재 위치를 최소값 인덱스로 가정
for (int j = i + 1; j < 10; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j; // 더 작은 값 발견 시 인덱스 갱신
}
}
// 현재 위치(i)와 최소값 위치(minIndex) 교환
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
printf("\n");
// 정렬된 배열 출력
for (int i = 0; i < 10; i++) {
printf("%d ", arr[i]);
}
return 0;
}3) 삽입 정렬
#include <stdio.h>
int main() {
int arr[10] = { 4, 6, 2, 7, 5, 1, 8, 9, 10, 3 };
int key, j;
// 초기 배열 출력
for (int i = 0; i < 10; i++) {
printf("%d ", arr[i]);
}
// 삽입 정렬 시작
for (int i = 1; i < 10; i++) {
key = arr[i]; // 현재 정렬할 원소
j = i - 1;
// key보다 큰 원소들을 오른쪽으로 한 칸씩 이동
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
// 정렬된 위치에 key 삽입
arr[j + 1] = key;
}
printf("\n");
// 정렬된 배열 출력
for (int i = 0; i < 10; i++) {
printf("%d ", arr[i]);
}
return 0;
}
2. 탐색 알고리즘
정렬알고리즘 이후에 활용되는 탐색 알고리즘을 공부
많은 데이터 중에서 특정 데이터를 찾아내는 작업을 탐색이라고 함
전체 데이터의 양이 많아질 수록 탐색에 걸리는 시간이 길어지게 되므로 효율적인 알고리즘을 사용하는 것이 중요
1) 탐색 알고리즘이란
- 데이터를 검색하는 알고리즘으로, 원하는 데이터를 찾기 위해 사용하는 절차
- 대표적인 탐색 알고리즘에는 순차 탐색과 이진 탐색이 있음
- 정렬 여부에 따라 사용 가능한 탐색 알고리즘이 달라짐
| 알고리즘 | 전제 조건 | 시간 복잡도 |
| 순차 탐색 | 정렬 필요 없음 | O(n) |
| 이진 탐색 | 오름차순 정렬 | O(log n) |
2) 순차 탐색
- 배열의 처음부터 끝까지 하나씩 확인하며 원하는 데이터를 찾음
- 간단하지만 비효율적, 작은 데이터에 적합
#include <stdio.h>
// 순차 탐색 함수
int linear_search(int arr[], int size, int target) {
for (int i = 0; i < size; i++) {
// 원하는 값을 찾으면 인덱스를 반환
if (arr[i] == target)
return i;
}
return -1; // 찾지 못했을 경우
}
int main() {
int arr[] = {5, 3, 8, 4, 2, 7, 6, 1};
int size = sizeof(arr) / sizeof(arr[0]);
int target = 4;
int result = linear_search(arr, size, target);
if (result != -1)
printf("값 %d는 인덱스 %d에 있습니다.\n", target, result);
else
printf("값 %d를 찾을 수 없습니다.\n", target);
return 0;
}
3) 이진 탐색
- 정렬된 배열에서만 사용할 수 있는 효율적인 탐색 알고리즘
- 배열을 반씩 나누면서 탐색 범위를 줄여가는 방식
- 시간 복잡도는 O(log n)
#include <stdio.h>
// 이진 탐색 함수
int binary_search(int arr[], int size, int target) {
int left = 0;
int right = size - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] == target) return mid; // 중간 값이 타겟이면 반환
else if (arr[mid] < target) left = mid + 1; // 타겟이 더 크면 오른쪽 탐색
else right = mid - 1; // 타겟이 더 작으면 왼쪽 탐색
}
return -1; // 찾지 못했을 경우
}
int main() {
int arr[] = {1, 2, 3, 4, 5, 6, 7, 8}; // 정렬된 배열
int size = sizeof(arr) / sizeof(arr[0]);
int target = 4;
int result = binary_search(arr, size, target);
if (result != -1)
printf("값 %d는 인덱스 %d에 있습니다.\n", target, result);
else
printf("값 %d를 찾을 수 없습니다.\n", target);
return 0;
}
4) 도전 과제
(1) C언어로 순차 탐색 구현
#include <stdio.h>
// 순차 탐색 함수
int linear_search(int arr[], int size, int target) {
for (int i = 0; i < size; i++) {
// 각 요소를 하나씩 확인
if (arr[i] == target) {
return i; // 찾았으면 해당 인덱스를 반환
}
}
return -1; // 찾지 못했으면 -1 반환
}
int main() {
int arr[] = {7, 2, 9, 4, 6, 1, 3};
int size = sizeof(arr) / sizeof(arr[0]);
int target = 4;
int result = linear_search(arr, size, target);
if (result != -1)
printf("값 %d는 인덱스 %d에 있습니다.\n", target, result);
else
printf("값 %d를 찾을 수 없습니다.\n", target);
return 0;
}
(2) C언어로 이진 탐색 구현
#include <stdio.h>
// 이진 탐색 함수
int binary_search(int arr[], int size, int target) {
int left = 0;
int right = size - 1;
while (left <= right) {
int mid = (left + right) / 2; // 중간 인덱스 계산
if (arr[mid] == target) {
return mid; // 타겟을 찾았으면 해당 인덱스 반환
}
else if (arr[mid] < target) {
left = mid + 1; // 오른쪽 반으로 탐색 범위 축소
}
else {
right = mid - 1; // 왼쪽 반으로 탐색 범위 축소
}
}
return -1; // 찾지 못했으면 -1 반환
}
int main() {
int arr[] = {1, 2, 3, 4, 5, 6, 7}; // 오름차순으로 정렬된 배열
int size = sizeof(arr) / sizeof(arr[0]);
int target = 4;
int result = binary_search(arr, size, target);
if (result != -1)
printf("값 %d는 인덱스 %d에 있습니다.\n", target, result);
else
printf("값 %d를 찾을 수 없습니다.\n", target);
return 0;
}
3. 프로젝트 만들기
포켓몬스터 대작전!
- 프로그램이 시작되면, pokemon.txt 파일에서 모든 포켓몬 정보를 읽어와 구조체 연결리스트로 저장한다.
- 모든 포켓몬은 적절한 구조체로 만들어져야 한다.
- 포켓몬은 최소 10종류 이상 존재하여야 한다. ( 타입은 불, 물, 풀 3종류 )
- pokemon.txt 는 이름, 속성, 최소 공격력, 최소 HP로 이루어져 있다.
- pokemon.txt의 제일 첫 행에는 읽어야 할 라인 수가 적혀 있다.
- 게임이 시작되면 다음 화면을 출력한다
===============================
KnockOn Pokemon Game
press enter to start
===============================3. 엔터키를 입력하면 게임이 시작되며, 세이브 파일이 존재한다면 다음과 같은 화면을 출력한다.
===============================
1. 새로하기 2. 이어하기
>>1) 새로하기를 입력하였을 경우(or 세이브 파일이 없을 경우)
a. 다음과 같이 출력한다. (첫 시작 포켓몬 종류는 자유롭게 선택하여도 된다.)
===============================
어느 포켓몬을 선택하시겠습니까?
1. 파이리 2. 이상해씨 3. 꼬부기
>>b. 번호를 입력하면 선택한 포켓몬을 사용자의 포켓몬 정보에 대입한다.
i. 사용자의 포켓몬 정보에는 이름, 별명, 속성, 공격력, 체력이 존재한다.
가. 공격력은 포켓몬의 최소 공격력에 0 ~ 100 사이의 값이 랜덤으로 더해져서 결정된다.
나. 체력은 포켓몬의 최소 체력에 0~150 사이의 값이 랜덤으로 더해져서 결정된다.
ii. 트레이너의 지갑에는 10000원이 추가된다.
2) 이어하기를 입력하였을 경우
a. savefile이 존재하면 해당 정보를 불러온다.
4.메인 게임 화면
a. 다음과 같이 출력한다.
===============================
모험을 진행하시겠습니까?
1. 네 2. 저장 3. 상점 4. 포켓몬센터 5. 포켓몬 도감
b. 입력한 번호에 따라 해당 내용을 수행한다.
c. 입력한 내용을 마쳤을 경우 해당 화면으로 다시 복귀하여야 한다.
5. 모험 (1을 선택하였을 경우)
a. 다음과 같이 출력한다.
===============================
포켓몬을 탐색하는중 ...b. 1~5초의 시간을 대기한 뒤 포켓몬 리스트에 있는 포켓몬 중 하나가 랜덤으로 등장한다.
c. 야생포켓몬은 트레이너 포켓몬과 같이
i. 공격력은 포켓몬의 최소 공격력에 0 ~ 100 사이의 값이 랜덤으로 더해져서 결정된다.
ii. 체력은 포켓몬의 최소 체력에 0~150 사이의 값이 랜덤으로 더해져서 결정된다.
d. 다음과 같이 출력한다.
===============================
야생 포켓몬 이름
현재hp/maxhp
내 포켓몬 이름
현재hp/maxhp
===============================
앗! 야생의 포켓몬이 나타났다!
무엇을 해야할까?
1. 공격 2. 가방열기 3. 도망치기
>>
- 공격 메뉴
- 공격
- 서로 공격을 한번씩 주고받는다. 먼저 공격하는 쪽은 50%확률 랜덤으로 정한다.
- 약점 : 풀 < 불 < 물 < 풀
- 자신의 약점 타입으로 공격당했을 경우 상대의 공격력 * 1.5 의 데미지를 입는다. (ex 물 → 불 공격) 이후 효과가 굉장했다! 를 출력한다.
- 자신이 강한 타입에게 공격당했을 경우 상대의 공격력 * 0.5 의 데미지를 입는다. (ex 불 → 물 공격) 이후 효과가 별로인 듯 하다. 를 출력한다.
- 20% 확률로 크리티컬이 적용된다. 크리티컬은 최종 계산 데미지에 1.5배를 입힌다. 이후 급소에 맞았다! 를 출력한다.
- 내 포켓몬의 hp가 0이 되었을 경우
- 내 포켓몬 리스트 중 체력이 0보다 큰 포켓몬이 있을 때
- 체력이 0보다 큰 포켓몬 리스트를 출력한 뒤 어느 포켓몬을 내보낼지 선택한다.
- 0보다 작거나 같은 수를 입력했을 경우 전투를 포기하고 도망친다.
- else
- 눈앞이 깜깜해졌다… 문구를 출력하고 1000원을 잃고 전투를 종료한다.
- 내 포켓몬 리스트 중 체력이 0보다 큰 포켓몬이 있을 때
- 상대 포켓몬 hp가 0이 되었을 경우
- 300~500원 사이의 돈을 랜덤하게 지급받고 전투를 종료한다
- 공격
- 가방열기
- 보유한 가방 물건 리스트를 출력한 뒤 무엇을 할지 선택한다.
- 포켓몬 볼
- 100 - (상대 몬스터의 체력%) 의 확률로 포획을 진행한다.
- 포획에 성공하였을 경우
- {포켓몬이름}을 잡았다! 를 출력 한 뒤 별명 입력 여부를 묻는다.
- 별명 입력을 체크하였을 경우, 별명을 입력받은 뒤 별명을 설정한다.
- 별명입력을 체크하지 않았을 경우, 기본 포켓몬 이름으로 별명을 설정한다.
- 이후 해당 포켓몬의 상태를 포함하여 사용자 포켓몬 리스트에 추가한다.
- 포켓몬이 총 6마리가 모였을 경우, 포켓몬 마스터가 되었다! 문구 출력 후 마지막 상태를 출력 (포켓몬 리스트, 돈, 가방 등)후 게임을 재시작 하겠습니까? 문구 출력.
- Y를 선택할 경우 포켓몬 리스트를 초기화 후 처음부터 시작
- N을 선택할 경우 저장 없이 게임 종료
- 포획에 실패하였을 경우
- 포켓몬이 몬스터볼에서 빠져나왔다! 문구를 출력한 뒤 상대 턴 공격을 진행한다.
- 회복 물약
- 최대 HP의 30%를 회복한다.
- 도망치기
- 상대 포켓몬의 체력에 따라 확률적으로 도망칠 수 있다.
- 100% : 10%
- 60~100% : 40%
- 60~40% : 60%
- 40% ~ : 90%
- 도망치기에 성공하였을 경우, 성공적으로 도망쳤다! 문구를 출력한 뒤 메인화면으로 복귀한다.
- 상대 포켓몬의 체력에 따라 확률적으로 도망칠 수 있다.