시간 및 공간 복잡도 / 배열의 장단점

 

 

 

 

알고리즘

 

동적 프로그래밍과 분할정복의 차이

 

둘 다 문제를 작은 단위로 쪼개어 큰 단위로 접근하는데,
작은 단위 해결 단계에서 문제 해결을 위한 데이터가 더 필요하다면 동적 프로그래밍을 사용,
같은 단계에서 해결 방법이 비슷하게 반복된다면 분할 정복 사용.

 

시간 복잡도

 

●  O(1) : 상수 시간 복잡도 : 입력 크기에 상관없이 실행 시간이 일정
●  O(n) : 선형 시간 복잡도 : 입력 크기에 비례하여 실행 시간이 증가
●  O(log n) : 로그 시간 복잡도 : 입력 크기에 대해 로그 함수적으로 증가
●  O(n^2) : 이차 시간 복잡도 : 입력 크기의 제곱에 비례하여 실행 시간이 증가

 

공간 복잡도

 

● 고정 공간 (Fixed Space)

알고리즘 실행에 필요한 고정 메모리 요소.

일반적으로 변수, 상수, 함수 호출 스택 등이 포함 된다.

이러한 메모리 요소들은 입력 크기와 무관하게 항상 고정적인 공간을 필요로한다.

● 가변 공간 (Variable Space)

입력 크기 또는 알고리즘의 진행에 따라 동적으로 할당되는 메모리 요소.
데이터 구조, 배열, 리스트, 트리, 그래프 등과 관련이 있으며, 입력 크기에 따라 메모리 요구량이 달라질 수 있다.

 

 

알고리즘에서 배열의 장단점

 

배열의 장점
● 빠른 조회 : 인덱스를 통한 조회가 빠름
● 효율적인 메모리 관리 : 연속적인 메모리 공간에 요소를 저장하므로 메모리 관리가 효율적

 

배열의 단점

● 크기 고정 : 배열의 크기는 초기에 결정되며 변경하기 어려움
● 삽입 및 삭제 시 비효율성 : 배열 중간에 요소를 삽입하거나 삭제할 때 다른 요소를 이동시킴
● 메모리 낭비 : 크기가 고정되어 있기 때문에 실제로 사용하지 않는 메모리 공간이 낭비됨

 

 

팀 과제 - TextRPG 만들기 개요

 

주요 회의 내용

 

프로젝트 작성에 앞서 전반적인 게임 구성에 대한 회의를 했다.

1. 클래스, 필드, 컨벤션 정리

2. 역할 분담 (캐릭터 / 몬스터 / 아이템-인벤토리-상점 / 던전) 

3. 매일 짝수시간 정각을 진행상황에 대해 브리핑하고 질의응답하는 시간으로 설정

4. GitHub Desktop의 브랜치 생성, 클론 만들기, pull-push 과정에서 생긴 오류를 함께 해결함

 

보완할 점

 

1. 아이템 클래스를 상점-인벤토리-캐릭터 모두에게 문제 없이 할당하기

2. HP/MP 관련 아이템 정리 (소비 아이템으로 분류하지만 HP 자체는 캐릭터와 공유하기 때문에)

3. 상점 창 인터페이스를 보기 좋게 바꾸는 방법 (클래스 별로 장비가 생길 것을 대비해)

 

 

팀 프로젝트에 본격적으로 돌입했다.

우리 팀 팀원분들 실력이 워낙 좋아서, 아직 배울 게 많은 나는 그 속도에 맞추기 어려운 상황이다(ㅠㅠ)

아이템-인벤토리-상점 부분을 팀원 한 분과 함께 완성하기로 했다.

전체적인 그림은 알겠는데, 명확하게 그려지지 않아서 코드 작성하는 데 어려움이 있었다.

내일은 클래스에 대한 그림부터 직접 그려보고 코드 수정에 들어가야겠다.

펜타곤 파이팅