[코드카타] 부족한 금액 계산하기

문제 링크

• https://school.programmers.co.kr/learn/courses/30/lessons/82612

문제 요약

• 놀이기구를 count번 탈 때 필요한 총 금액을 구한다.
• 이용 금액은 탈 때마다 price, 2 * price, 3 * price처럼 증가한다.
• 현재 가진 돈 money를 기준으로 부족한 금액을 반환하고, 부족하지 않다면 0을 반환한다.

내가 제출한 코드

using namespace std;

long long solution(int price, int money, int count)
{
    long long totalPrice = 1LL * price * count * (count + 1) / 2;
    return max(0LL, totalPrice - money);
}

배운 점

• 1LL을 곱해서 계산 전체를 long long으로 처리
• 반복해서 더해야 하는 문제는 먼저 수열 공식으로 줄일 수 있는지 생각해 볼 수 있음
• 삼항 연산자 대신 max(0LL, totalPrice - money)를 써서 반환부도 간단하게 정리

알고리즘 기초 라이브 세션 - Sorting

• 두 개를 비교해서 자리를 바꾼다 -> 이 단순한 동작의 반복이 정렬
  • 양자컴퓨터는 다중 비교가 가능하긴 함.

원리 탐구 - 비교하고 교환하기

• 데이터를 특정 순서로 나열하기 위해 하는 것.
• 정렬은 두 가지의 반복
  • 두 값 중 어느 쪽이 큰가?
  • 순서가 틀렸으면 둘을 교환

정렬	전략	비교 횟수	교환 횟수	최선의 경우
버블	인접 비교	O(n²)	O(n²)	O(n²)
선택	최소값 찾기	O(n²)	O(n)	O(n²)
삽입	끼워넣기	O(n²)	O(n²)	O(n)

버블 정렬 - 옆 사람과 비교

• 인접한 두 원소를 비교해서 순서가 잘못되었으면 교환
• 한 바퀴 돌면 가장 큰 값이 맨 뒤로 "떠오른다" -> 거품이 수면 위로 떠오르듯, 버블 정렬
• 즉 n개의 원소가 있는 배열의 경우, n번 비교, n-1번 비교...이런 식으로 n*(n-1)/2 번 비교
  • 시간복잡도 O(n^2)

선택 정렬 - 가장 작은 걸 찾아서 앞에

• 이것도 O(n^2)긴 한데, 훑고 가장 작은 걸 "찾아서" 맨 앞에 두기 때문에 교환은 라운드당 1번.

삽입 정렬

• 두 번째 원소부터 시작, 앞에 정렬된 원소들 중에 적절한 위치에 현재 보고 있는 원소를 삽입
• 역순으로 꺼내면 모든 원소가 밀리므로 잘못하면 한번 할때마다 O(1)씩 다 움직여야 할 수도 있다.
• 최선의 경우는 O(n), 최악의 경우 O(n^2)
• C++ sort() 도 16개 이하의 데이터 정렬에는 삽입정렬을 쓴다.
• '거의 정렬된' 데이터에 강하다
  1초에 1억번 계산 기준, 10만 개의 데이터 정리하는 데 O(n^2)는 3시간, O(n log n)은 0.2초

분할 정복 - Divide and Conquer

-나눠서 정렬하고 합치면 지수함수 원칙을 따르지 않으므로 훨씬 빨라진다

• 깊이(분할) 은 log2(n) , 병합과정은 n -> O(n long n)

퀵 정렬 - "기준값으로 나누기"

• 기준값(pivot)을 정해서, 작은것/큰 것으로 나누기 반복
• 병합은 O(nlogn) 보장. 반으로 균등 분할
• 퀵은 평균 nlogn, 최악 n^2

C++ sort 는 퀵 정렬을 기반으로 하되, 최악의 경우를 보정해 주기 위한 안전장치가 달린 Introsort 하이브리드 알고리즘

데이터 크기	사용 알고리즘	이유
~16개 이하	삽입 정렬	작은 데이터에서 빠름
일반적인 경우	퀵 정렬	평균 O(n log n), 캐시 친화
최악 감지 시	힙 정렬로 전환	O(n²) 방지

분할 정복의 3단계 - "혼자 다 하지 마라"

• 큰 문제를 반을 ㅗ나누기
• 각 부분을 독립적으로 해결하기
• 결과를 합쳐 전체 해답을 내기
• 병합 정렬, 이진 탐색, 쿼리 옵티마이저, MapReduce, FFT/Strassen 행렬 곱셈...
• 비교 기반 정렬은 O(n log n)이 이론적으로 하한이다. 비교 만으론 이보다 빠를 수 없다.
• "비교하지 않는 정렬" 은 O(n) 가능.

언리얼 C++ 녹화강의 - GameMode와 Character Class

각 클래스 역할

• GameMode: 게임의 전반적인 규칙과 흐름을 총괄 관리하는 컨트롤 타워
  • 게임 규칙 관리 - 로직(함수)
• Player Character
  • Pawn 아니면 Character.
  • PlayerController - 캐릭터에 빙의해서 조종할 수 있게 해주는 클래스
• GameState 클래스
  • 게임 전역 데이터 관리. 실제데이터들 여기에
• PlayerState 클래스
  • 개별 캐릭터마다 데이터. 멀티플레이어 게임의 경우 상당히 중요해 짐.

GameMode

• GameModeBase가 일반적인 싱글플레이어에서 필요한 Base 클래스
• GameMode의 경우 GameModeBase의 자손. 멀티플레이어 기능 제공. PlayerState 등등 연동도 되어 있는 무거운 클래스.

GameMode 적용법

• 대다수의 경우 C++ 클래스로 작성 후 블루프린트 자손을 생성해서 적용하는 게 낫다. 에디터 쓰기 더 편해짐.
• 전역 게임 모드: Edit - Project Settings - Maps&Modes - Default GameMode 에서 설정.
  • 이 프로젝트에서 만든 모든 레벨에 해당 GameMode를 기본으로 설정
  • 이 아래서 Selected GameMode에서 디폴트 폰 클래스, 플레이어 컨트롤러 클래스, HUD 클래스 등등 다 설정 가능하다.
  • Spectator Class 는 FPS 같은 데서 관전 같은 거 담당
• 레벨 하나에 적용하고 싶다면? Window - World Settings 에서 게임모드 적용.
  • 이게 우선순위 더 높다는 점 유의.

Character

Character와 Pawn의 차이

• Pawn: 어떠한 플레이어든 AI든 소유할 수 있는 가장 상위 클래스
  • 이동 로직, 충돌 처리, 중력, 네트워크 이동 기능 등등이 기본적으로 포함 X.
  • 일반적인 인간같은 캐릭터 클래스의 이동방식을 벗어난 특수한 로직이 필요한 클래스들을 Pawn으로 보통 구현
• Character: Movement 관련 로직들이 이미 구현이 되어 있는 클래스. 몇 줄 코드만 추가해서 캐릭터 움직임 구현 가능.
  • 이족보행하는 인간형 캐릭터만 거의 만들 수 있음.

Character Class

• Capsule Component(루트): 충돌판정관리
• Arrow Component: 방향 표시. 로직과 관계X
• Mesh - 보통 Skeletal Mesh
• Character Movement: 엔진 자체에서 제공하는 이동 로직 구현.

카메라 C++로 구현

• Spring Arm + Camera 콤보

public:
	ASpartaCharacter();

	USpringArmComponent* SpringArmComp;
	UCameraComponent* CameraComp;

• 이런 식으로 넣었을 경우 관련 파일을 헤더에 #include 할 수 있지만 낭비다. UCLASS 위에 class USpringArmComponent 이렇게 미리 선언만 해두는 게 나음.
  • 실제 구현은 실제로 쓸 때.
    cpp 파일에 #include "Camera/CameraComponent.h", #include "GameFramework/SpringArmComponent.h" 하면 된다.

SpringArmComp = CreateDefaultSubobject<USpringArmComponent>(TEXT("SpringArm"));
CameraComp->SetupAttachment(SpringArmComp, USpringArmComponent::SocketName);

• 이런 식으로 붙이기. CameraComp 의 경우 SpringArm에 붙이는데 이 때 "어디에 붙이냐" 를 결정해 주기 위해 USpringArmComponent::SocketName 하면 끝에 붙는다

DefaultPawnClass

• BP_MyGameMode 에서 Default Pawn Class에 내가 만든 캐릭터 클래스 넣어줘도 되고
• C++ 코드에서 GameMode 생성자 만든 후 거기에

#include "SpartaCharacter.h"
ASpartaGameMode::ASpartaGameMode()
{
	DefaultPawnClass = ASpartaCharacter::StaticClass();
}

• 이렇게 해 줘도 된다. StaticClass() 의 경우 UCLASS를 반환하는 함수. 객체를 실제로 생성하지 않고도 이렇게 대입할 수 있게 해 준다.
• 둘 중 하나만 해도 되지만, 안전빵은 둘 다.