Game DevTip/STL7 7. STL : 더블링크드 리스트(Double Linked List)를 구현해보자. 더블 링크드 리스트 이중 연결 리스트는 하나의 노드에서 두 개의 링크를 갖게 되는데선행 노드와 후속 노드에 주소를 각각의 링크에 연결시켜 양뱡향 겁색이 가능하게끔 하는 리스트이다.단순 연결 리스트에서 삽입과 삭제를 위해서는 선행노드의 주소가 반드시 필요했던 것과 달리이중 연결 리스트는 양방향 검색이 가능하기 때문에 삽입,삭제를 더 용이하게 진행할 수 있다.실제로 이중 연결과 원형 연결을 같이 구현하여 이중 원형 리스트를 가장 많이 사용한다고 한다.node의 시작 pointer리스트에 저장된 데이터의 개수Prev라는 포인터가 들어갔기에 일반적인 링크드 리스트보다 앞뒤를 순서를 더 고려해서 처리를 해줘야 함.대략적인 구조#include struct Node { int data; Node* prev.. 2024. 12. 7. 6. STL : 링크드 리스트(Linked List)를 직접 구현해 보자. List(STL)목록 & 도표마냥 여러 데이터를 관리할 수 있는 추상자료형이다.데이터가 연속으로 이어져있는 시퀀스이다.배열을 이용하는 방법 & 포인터를 이용하는 방법 있음.스택 큐는 리스트의 특수한 형태이다. (즉, 스택 & 큐도 리스트로 구현 가능.)LIST ADT속성 : 연속으로 저장된 n개의 데이터(객체) 집합.기능빈 리스트 만들기리스트 없애기데이터를 리스트에 추가하기.리스트에서 데이터 삭제리스트에서 데이터 검색리스트에 저장된 데이터 개수 확인리스트가 비어있는지 검사리스트가 꽉 찼는지 검사.class IntList{private: int m_data[50]; int m_count; public: IntList(); ~IntList(); void insert(int pos, int it.. 2024. 12. 7. 5. STL : 재귀함수에 대해서 재귀함수재귀는 대표적인 ‘분할 정복’ 알고리즘 이다.K번쨰 블록이 반드시 쓰러진다는 사실을 증명하시오수학적 귀납법(Mathematical Induction) - 한 조건으로 확정된 상황을 바탕으로 진행.첫번째 블록은 반드시 쓰러진다.첫번쨰 블록이 쓰러지면 두번째 블록도 반드시 쓰러진다.(k-1)번째 블록이 쓰러지면 k번째 블록도 반드시 쓰러진다.재귀적 알고리즘(Recursive Algorithm) - 메모리 스택을 씀.수학적 귀납법의 순서를 역순으로 증명.분할 정복 :큰 문제를 작은 문제로 환원 / 작은 문제 역시 큰문제와 유사.아주 작은 문제는 반드시 해결됨( = base case)반드시 베이스 케이스에 도달해야 함.팩토리얼, 문자열 뒤집기, 카운트 다운, 피보나치수열, 하노이 탑, 이진 탐색, 게임 .. 2024. 12. 7. 4. STL : Call by value, Ref, Address & 배열과 포인터에 관련해서. 배열과 포인터포인터 : 메모리에 저장된 다른 값의 메모리 주소를 저장하는 변수배열 : 이름은 주소(사실은 주소임)포인터 변수 선언 : Type *var_name;(int *ptr; → 인티저 값을 가르키는 포인터 변수.)포인터 사용 : 다른 변수의 주소를 참조하여 사용가능. 동적 메모리 할당가능. → 함수도 주소이므로 사용가능.- 주소할당.int a = 100;int p = &a; - 동적메모리 할당.int *p = null;p = new int ; // 동적 메모리 할당. *p = 500; //p가 가르키는 해당 공간에 500이라는 값을 저장해라.delete p; // 메모리 해제(안하면 누수 ^^7)Call by value & Call by address & Call by Refvalue : 인수가 .. 2024. 12. 7. 3. STL : 클래스 상속에 관하여. 1. 클래스 상속(객체지향 방법론)객체와 메세지클래스 : 붕어빵 틀객체 : 붕어빵 실물 (메시지를 보내거나 받는 대리인(클래스에 의해서 만들어진 실물))메세지(함수) → 윈도우 프로그래밍에서는 주로 이벤트이다.즉, 객체가 처리해야할 일을 전달하는 것.(그냥 함수임)정보은닉 : 실제 처리되는 과정과 내용이 숨겨져 있다.정리)클래스 : 프로그래머가 정의한 자료형객체 : 클래스 타입으로 선언하여 메모리에 할당 된 것.인터페이스 파일(헤더)객체를 추상화한 파일외부 사용자를 위한 파일클래스, 메시지(가상함수)가 정의된 파일 - 참고로 변수는 없음.외부사용자는 세부구현 내용을 몰라도 이 파일만 읽고 불러서 사용 가능.구현 파일(소스 파일)인터페이스 파일에 정의된 메시지(함수)를 구현한 파일내부 구현자가 작성한 파일.. 2024. 12. 7. 2. STL : 추상화에 관해서. 1. 추상화세부적인 것들을 다 빼고서 일반화를 시키는 것(부품을 뺴고 큰것들만 남기기)장점 : 재사용이 쉬워짐.언리얼에서 AActor → Chracter클래스로 상속 받는 거처럼 생각하면 됨.객체 단위로 프로그램을 짜게 만드는 요인.1-1 추상자료형기능의 세부구현 내용은 나타내지 않음.기능이 어떤 형태인지만 나타냄.세부구현 내용은 몰라도 사용가능.단, 개발자는 세부 구현 내용은 알고 있어야 함.C++에서는 header 파일에 클래스나 함수등을 선언해서 추상 자료형을 나타냄.실제 세부기능은 cpp파일에서 구현됨.1-2 추상자료형과 C++사용과 구현을 분리.추상 자료형은 헤더세부기능은 cpp사용자에게는 구현방법이 숨겨져 있어서 보이지 않음.추상 자료형 선언 = 클래스 or 구조체 선언추상 자료형 작업 = 객.. 2024. 12. 7. 1. 자료구조 전 기초 상식(?) 객체지향 프로그래밍 OOP클래스는 Define하기 위해 만드는 객체이다.엔진들은 모두 모듈화(상속이 되어있다.)프로그래밍 동작 순서하드 → 메모리(용량 큼) 속도 조금 느림 → 레지스터(용량 작음) 속도 빠름 → CPU선언파일(h), 구현파일(cpp)차이점헤더파일은 이름같은거 정의 할때 선언(public, protected, private으로 공개 범위 적용)구현파일은 헤더파일을 가지고 오거나 해당 변수를 이용하여 기능을 구현.변수(*메모리에 공간을 할당하는 것은 운영체제가 해줌.) 빌트인 타입, 유저인 타입(*클래스도 마찬가지임)즉, 메모리 공간하면, 구조를 생각 후 → 객체를 생각해줘야 한다.유저 디파인 타입 : 구조체 타입을 사용하여 만들어야 함(예시 : 캐릭터가 가질 수 있는 속성들을 보관.)변수.. 2024. 12. 7. 이전 1 다음
