C++

알고리즘 특강

포인터를 왜쓰는가??

입력받은 숫자를 저장하고 싶은 상황을 가정

int arr_size;
cin >> arr_size;
int arr[arr_size]; // 왜 안될까?

일반 배열은 스택 영역에 할당, 이 스택 영역은 컴파일 시점에 크기가 결정되어야 하는 메모리 영역, 실행 시간에 입력받은 크기로 스택에 메모리를 할당하는 것은 C++ 언어의 설계 철학과 맞지 않음

게다가 스택 영역은 제한적인 메모리 영역이라 arr_size가 굉장히 크면 오버플로우가 발생한다.
그래서 C++은 모든 변수의 크기와 위치가 결정되어야 한다는 원칙이 있다.

이것을 가능하게 하려면 벡터를 사용하거나 포인터로 동적할당을 써주면 된다 (힙영역)
벡터의 경우 내부적으로 동적 배열을 관리해서 데이터는 힙에 저장된다.

int arr_size;
cin >> arr_size;
int* arr = new int[arr_size];

포인터 타입으로 배열을 동적으로 만들 수 있다. 동적할당(new)을 통해 메모리를 관리할 수 있기 때문에 필요할 때만 생성하고 필요 없을 때는 명시적으로 메모리를 해제(delete)할 수 있다. -> 메모리를 효율적으로 사용하는데 포인터는 필수적이다.
필요할때 생성하고 delete로 메모리해제를 해주어야 한다.
메모리를 효율적으로 사용하는데 포인터는 필수적이다.
이를 우려해서 스마트 포인터라는 개념이 나왔다.

포인터 / 레퍼런스

알아야 하는 이유

• 성능

  • 게임에서 캐릭터 데이터가 있다고 했을때 체력, 마나, 인벤토리, 스킬 정보를 다 합치면 사이즈가 커진다.
  • 이것을 Call by value형식 즉 복사를 하게되면 시스템 부하가 엄청난다 -> 프레임 드랍, 렉
  • 레퍼런스로 넘긴다 (복사 없이 원본)

• 원본을 바꿔야 하는 경우

  • 값으로 넘기면 복사본만 수정되므로
  • 포인터나 레퍼런스를 넘겨서 진짜 수정

• 동적 메모리 할당(포인터)

  • 게임중 몬스터가 스폰 and 죽음 반복 이것을 미리 만들어 놓을수없다
  • 런타임에 new로 만들고 delete로 지우고 해야됨 이때 포인터가 필수, 스마트 포인터도 결국 포인터 기반

알고리즘 문제 풀어보기

알고리즘 풀어보면서 새로 알게된거 정리하기

1.

• N-Queen

• 백트래킹의 대표적인 문제

• C++로는 풀어본적이 없어서 ai의 도움과 함께 풀어봤다.

• 전역변수를 사용

• #define 처음 사용해봄

  • 전처리기 지시문, 컴파일 전에 단순히 텍스트를 치환하는 역할
  • const와 constexpr써도됨
  • 둘의 차이는 const는 컴파일 타임, 런타임 둘다 가능, 값이 프로그램 실행중에 결정되는 경우도 있다.
  • constexpr은 무조건 컴파일 타임에 값이 정해짐, 배열 크기처럼 컴파일 타임에 알아야 하는 곳에 사용 가능

• 내 풀이

2.

• 두 수의합

• 내 풀이

• 투포인터 문제인데 이상하게 풀었다.

• 기존 코드에 while문과 그 아래 if문에 논리적으로 오류부분도 있어서 다시 정석버전을 배워서 짜기로 했다.

• 개선

• 개선 전 후 시간비교
  

• 시간이 많이 개선되었다.

3.

• 체스판 다시 칠하기

• 쉬운문제라고 무시했다가 중간에 설계 잘못해서 생각보다 시간이 오래걸린문제

• 알고리즘 풀이 할때도 공책에 쓰면서 해야 될것같다.

• 내 풀이

• 다른 풀이

• 다른 풀이를 보면 체스판 패턴을 만들고 직접 비교하는데 이게 더 나은것 같다.

4.

• 나이순 정렬
• 내 풀이
• algorithm헤더에있는 sort로 처리하려니 골치아팠던 문제
• stable_sort라고 들어온 순서를 보장하는 sort를 사용하면 된다.

stable_sort(vec.begin(), vec.end()); // 이렇게만쓰면 나이와 이름까지 다 비교하게 된다.

5.

• 좌표 압축

• 내 풀이

• 처음에 set을 사용하고, find로 위치를 찾아서 distance라는것을 사용해서 인덱스를 반환해주었는데 distance가 O(N)의 시간복잡도를 가지고있어서 실패했다.

• distance(begin, it) : 시작부터 it까지 길이, it-begin() : 벡터에서 찾을때는 이렇게

• 개선 풀이

• Map을 조회하는데 사용해서 풀었다.

• 다른 풀이

• lower_bound를 이용한 풀이

• lower_bound란??

  • 이진탐색 기반으로 동작하는 STL알고리즘
  • 정렬된 배열에서 특정 값 이상인 첫 번째 원소의 위치를 찾아주는 함수

int index = lower_bound(sorted_vec.begin(), sorted_vec.end(), vec[i]) - sorted_vec.begin();

// 처음부터 끝까지 순회하면서 첫번째로 vec[i]이상인 원소를 찾아줌 그것을 begin()으로 빼줘서 인덱스 형태로 만든다.