Unreal 사전 개발 캠프 16일차

오늘 학습 진행 내용
C++ 강의
3-3 정렬
정렬이란?
사용자가 정의한 순서대로 데이터를 나열
사용자가 정의한 순서는 오름차순 또는 내림차순 혹은 임의로 정한 조건 가능

정렬을 하는 이유
1. 원하는 값을 빨리 찾을 수 있어서
중앙값이나 최대값이 필요한 경우 데이터 정렬된 상태면 횔씬 빠르게 구하는 것 가능

2. 정렬이 전제 조건인 알고리즘이 존재
   이진 탐색은 데이터가 정렬되어 있어야만 정상적으로 동작

기본적인 삽입 정렬

	#include <iostream>
	using namespace std;

	// 삽입 정렬을 이용하여 정수 배열을 오름차순으로 정렬하는 예제
	int main() {
		int arr[] = { 5,2,4,6,1,3 };      // 정렬할 정수 배열 선언 및 초기화
		int n = sizeof(arr) / sizeof(arr[0]);  
		// 배열 전체 크기를 한 요소의 크기로 나누어 배열의 길이(요소 개수)를 계산

		// 삽입 정렬 알고리즘 시작
		for (int i = 1; i < n; i++) {     // i는 두 번째 요소부터 마지막 요소까지 이동
			int key = arr[i];            // 현재 삽입할 값(key)을 저장
			int j = i - 1;               // key의 앞쪽 요소들을 비교하기 위한 인덱스

			// key보다 큰 요소들을 한 칸씩 뒤로 이동시키는 과정
			while (j >= 0 && arr[j] > key) {  
				// j가 배열 범위를 벗어나지 않고, arr[j]가 key보다 크면 실행
				arr[j + 1] = arr[j];     // arr[j]를 한 칸 뒤로 이동
				j--;                     // j를 하나 줄여 앞 요소를 계속 비교
			}

			arr[j + 1] = key;            // key를 자신이 들어갈 적절한 위치에 삽입
		}

		// 정렬된 배열을 출력
		for (int i = 0; i < n; i++) {     // 배열의 모든 요소를 순회하며 출력
			cout << arr[i] << " ";        // 요소 출력 후 공백 추가
		}
		cout << endl;                     // 마지막 줄바꿈 출력

		return 0;                         // 프로그램 종료
	}

삽입 정렬은 정렬되지 않은 데이터를 이미 정렬된 부분 배열의 적절한 위치예 차례로 삽입하여 전체 데이터를 정렬하는 알고리즘

시간 복잡도
삽입 정렬의 시간 복잡도는 O(N^2)
최악의 경우 처음 의도한 정렬과 반대로 데이터 저장될 가능 성 존재
이미 정렬된 상태라면 시간 복잡도는O(N)

병합 정렬

	#include <iostream>
	using namespace std;

	void merge(int arr[], int left, int mid, int right) {
		int size = right - left + 1; // 임시 배열의 크기
		int* temp = new int[size]; // C-style 동적 배열 할당

		int i = left; //첫 번째 부분 배열(arr[left..,mid)의 시작 인덱스
		int j = mid + 1; //두 번째 부분 배열(arr[mid+1..right])의 시작 인덱스
		int k = 0; //임시 배열(temo)의 인덱스

		//두 부분 배열을 비교하며 임시 배열에 정렬하여 저장
		while (i <= mid && j <= right) {
			if (arr[i] <= arr[j]) {
				temp[k++] = arr[i++];
			}
			else {
				temp[k++] = arr[j++];
			}
		}
		
		// 첫 ㅂ전째 부분 배열에 남은 요소가 있다면 임시 배열에 복사
		while (i <= mid) {
			temp[k++] = arr[i++];
		}
		while (j <= right) {
			temp[k++] = arr[j++];
		}

		for (int idx = 0; idx < size; ++idx) {
			arr[left + idx] = temp[idx];
		}

		delete[] temp;
	}

	//mergeSort 함수는 변경할 필요 없음
	void mergeSort(int arr[], int left, int right) {
		if (left < right) {
			// (left + right) / 2 는 큰 값에서 오버 플로우를 일으킬 수 있음
			int mid = left + (right - left) / 2;

			//왼쪽 부분 배열 정렬
			mergeSort(arr, left, mid);
			// 오른쪽 부분 배열 정렬
			mergeSort(arr, mid + 1, right);

			//정렬된 두 부분 배열 병합
			merge(arr, left, mid, right);
		}
	}

	int main() {
		int arr[] = { 9,3,1,5,13,12 };
		int n = sizeof(arr) / sizeof(arr[0]);

		cout << "원본 배열: ";
		for (int i = 0; i < n; i++) {
			cout << arr[i] << " ";
		}
		cout << endl;

		mergeSort(arr, 0, n - 1);

		cout << "정렬된 배열: ";
		for (int i = 0; i < n; i++) {
			cout << arr[i] << " ";
		}
		cout << endl;

		return 0;
	}

정렬되지 않은 데이터를 계속 반으로 나눈 뒤 작은 단위부터 정렬하며 병합해 나가는 방식의 정렬 알고리즘
세 단계로 위루어진 배열
1. 분할 : 정렬된 배열의 중간 지점을 기준으로 두 개의 하위 배여로 나눔
2. 정복 : 각 하위 배열은 재귀적으로 병합 정렬을 호출해서 정렬
3. 결합 : 정렬된 두 개의 하위 배열을 하나의 정렬된 배열로 병합 이 과정에서 두 배열의 원소를 순서대로 비교해 작은 값 먼저 로운 배열에 추가

시간 복잡도
데이터가 N개일 때 병합 정렬은 데이터를 1개가 될때 까지 계속 반으로 나눔
분할 트리의 높이 h는 logN
분할 단계마다 모든 데이터를 병합하므로 병합 연산은 총 N번
전체 시간 복잡도는 각 단계당 O(N) * 단계 수 log(N) = O(NlogN)

계수 정렬

	//목적 : 양의 정수만큼 이루어진 배열을 계수 정렬로 정렬
	//동작 : 배열에서 최댓값을 찾아 그 크기 만큼 카운트 배열을 만들고, 카운트 정보를 기반으로 정렬된 결과 생성

	#include <iostream>
	using namespace std;

	int main() {
		int arr[] = { 4,2,2,8,3,3,1 };
		int n = sizeof(arr) / sizeof(arr[0]);

		// 1. 최댓값 찾기
		int max = arr[0];
		for (int i = 1; i < n; ++i) {
			if (arr[i] > max) {
				max = arr[i];
			}
		}

		//2. 카운트 배열 생성 및 초기화
		int* count = new int[max + 1] {};

		//3. 각 요소 개수 세기
		for (int i = 0; i < n; ++i) {
			count[arr[i]]++;
		}

		//4. 정렬 결과 저장
		int idx = 0;
		for (int i = 0; i <= max; ++i) {
			while (count[i]--) {
				arr[idx++] = i;
			}
		}

		//5. 출력
		for (int i = 0; i < n; ++i) {
			cout << arr[i] << " ";
		}
		delete[] count;

		return 0;
	}

계수 정렬은 데이터값 자체를 인덱스로 사용하는, 데이터에 의존적인 정렬 방식
각 값의 빈도 수를 세어 그 정보를 기반으로 정렬을 수행

세부 동작
계수 정렬은 일반적으로 다음과 같은 단계 거침
1. 카운트 배열 생성 : 입력 배열의 최대값 k를 기준으로 크기가 (k+1)인 count 배열을 생성하고 모든 원소를 0으로 초기화
2. 빈도수 계산 : 입력 배열을 순회하면서, 각 원소의 값을 인덱스로 사용하여 배열의 해당 위치에 해당 값의 빈도수를 누적

시간 복잡도
N은 입력 배열의 크기이고 K는 입력 배열의 최대값이라고 한다면 아래와 같이 진행
count 배열 초기화 O(K)
빈도수를 세는데 O(N)
정렬된 배열 생성 O(N)
최종 시간 복잡도 O(N+K)

계수 정렬의 한계
1. 음수 값이 존재하는 경우
음수 값이 존재하면 해당 값을 배열의 인덱스로 사용할 수 없기 때문에 계수정렬 적용 부락
2. 원소 값의 범위가 넓거나 듬성듬성 있는 경우
데이터가 500, 10억 처럼 매우 큰 간격을 가진 값을 포함할 경우 10억 크기의 배열 생성해야해서 메모리 비효율적

힙정렬

	//최대 힙(Max Heap)을 이용하여 정수 배열을 오름차순 정렬하는 힙 정렬 예제
	#include <iostream>;
	using namespace std;

	void heapify(int arr[], int n, int i) {
		int largest = i; // 루트를 가장 큰 값으로 시작
		int left = 2 * i + 1; //왼쪽 자식
		int right = 2 * i + 2; //오른쪽 자식
		
		if(left<n && arr[left]> arr[largest]) {
			largest = left;
		}
		if (right < n&& arr[right] > arr[largest]){
			largest = right;
		}
		if (largest != i) {
			swap(arr[i], arr[largest]);
			heapify(arr, n, largest); // 재귀적으로 하위 트리 정리
		}
	}

	void heapSort(int arr[], int n) {
		//배열을 힙 구조로 만들기 (Build Heap)
		for (int i = n / 2 - i; i >= 0; i--) {
			heapify(arr, n, i);
		}
		//힙에서 하나씩 요소를 추출
		for (int i = n - 1; i >= 0; i--) {
			swap(arr[0], arr[i]);//루트(최대값)와 마지막 요소 교환
			heapify(arr, i, 0); //줄어든 힙에 대해 다시 heapify
		}
	}

	int main() {
		int arr[] = { 4,10,3,5,1 };
		int n = sizeof(arr) / sizeof(arr[0]);

		heapSort(arr, n);

		for (int i = 0; i < n; i++) {
			cout << arr[i] << " ";
		}
		cout << endl;

	}

힙은 조건을 만족하는 이진 트리
보통 최대힙과 최소힙으로 구분
최대힙은 모든 부모 노드의 값이 자식 노드의 값보다 크거나 같고
최소 힙은그 반대로 부모 노드의 값이 자식 노드보다 작거나 같음

최대힙 구축하기 max_heapify()의 정의
정렬되지 않은 데이터가 저장된 배열에서 최대 힙을 구축하는 방법
특정 원소를 기준으로 최대 힙의 성질을 만족하도록 재구성하는 함수

	// 전역 변수: A (배열), heap_size (힙 크기)

	// 인덱스 i를 루트로 하는 트리를 최대 힙 속성을 만족하도록 수정 (Heapify)
	max_heapify(i)
	  l = LEFT(i)  // 왼쪽 자식 인덱스
	  r = RIGHT(i) // 오른쪽 자식 인덱스
	  largest = i  // 가장 큰 값의 인덱스 (일단 부모 자신으로 초기화)

	  // 왼쪽 자식과 비교
	  if l < heap_size and A[l] > A[largest] then
		largest = l
	  // 오른쪽 자식과 비교
	  if r < heap_size and A[r] > A[largest] then
		largest = r

	  // 만약 자식 노드가 부모 노드보다 크다면
	  if largest != i then
		swap A[i] and A[largest] // 두 노드의 값을 교환
		max_heapify(largest)    // 교환된 위치(자식 노드)에서 재귀적으로 Heapify 수행

최대힙 구축하기 build_heap() 동작
max_heapify()는 현재 노드를 기준으로 최대 힙을 구성하는 함수, 마지막 non-leaf노드부터 루트 노드까지 차례대로 max_heaify()를 수행하면 배열을 최대 힙 구조로 변환, 해당 과정을 build_max_heap()

	// A : 힙으로 만들 배열
	build_max_heap()
	  heap_size = A.length // 배열의 크기를 설정합니다

	  // 마지막 non-leaf 노드부터 루트(1번 인덱스)까지 역순으로 반복합니다
	  for idx = floor(A.length / 2) down to 1
		max_heapify(idx) // 각 내부 노드에 대해 MAX_HEAPIFY를 호출합니다

힙정렬의 최종 목적은 배열을 오름차순 또는 내림차순으로 정렬하는 것
최대힙 상태는 가장 큰 값이 루트에 위치해 있다는 것만을 보장, 배열 전체 정렬 상태 X

최대 힙을 구성한 후, 루트 노드를 배열의 마지막 요소와 교환하고 나머지 구간에 대해 다시 최대 힙을 구성하는 과정을 반복해서 전체 배열을 정렬

	// 전역 변수: A (배열), heap_size (힙 크기)
	HEAP_SORT()
	  // 1. 최대 힙 구성
	  BUILD_MAX_HEAP()
	  // 이 시점에서 heap_size는 A.length와 같음

	  // 2. 정렬 단계 (힙에서 최대값을 꺼내 정렬된 위치로 이동)
	  // 배열의 마지막 요소부터 두 번째 요소까지 반복
	  for i = A.length - 1 down to 1
		// 현재 루트(최대값)와 힙의 마지막 요소(A[i]) 교환
		swap A[0] and A[i]

		// 힙 크기 1 감소 (정렬된 요소 A[i]를 힙에서 제외)
		heap_size = heap_size - 1 

		// 루트(0번 인덱스)에 대해 MAX_HEAPIFY를 호출하여 힙 속성 복원
		MAX_HEAPIFY(0)

	  // 루프 종료 후 전역 변수 A는 오름차순으로 정렬됨

시간 복잡도
정렬되지 않은 N개의 값을 힙 구조로 표현하면 최대 log N인 이진 트리
힙 정렬은 먼저 전체 데이터를 최대 힙으로 구성한 뒤, 가장 큰 값을 하나씩 꺼내 배열 뒤쪽에 정렬하는 작업 N번 반복
각 단계에서 힙 속성을 재구성하는데 O(logN)걸리므로 전체 정렬 시간 복잡도 O(N log N)

추가적으로 힙 자료구조의 장점은 새로운 원소를 삽입할 때도 힙의 성질 유지 가능
트리 높이만큼만 연산 필요하므로, 삽입, 삭제 연산 시간 복잡도 O(log N)

문제 풀어보기
계수 정렬 구현하기
문제 설명

인수로 받은 문자열 s를 사전순으로 정렬된 문자열로 반환하는 solution( ) 함수를 구현하세요. 정렬은 계수 정렬을 활용해야 합니다.

제약 조건

• strings의 길이는 1 이상 10,000 이하입니다.

• s는 알파벳 소문자로 이루어져 있습니다.

  		#include <string>
  		#include <vector>
  
  		using namespace std;
  
  		string solution(string s) {
  		  // 알파벳 개수(26개)만큼 빈도수 배열 생성
  		  vector<int> counts(26, 0); 
  
  		  // 문자열의 각 문자에 대한 빈도수를 빈도수 배열에 저장
  		  for (char c : s) {
  			counts[c - 'a']++;
  		  }
  
  		  // 빈도수 배열을 순회하면서 정렬된 문자열을 생성
  		  string sorted_str = "";
  		  for (int i = 0; i < 26; i++) {
  			sorted_str += string(counts[i], i + 'a');
  		  }
  
  		  return sorted_str;
  		}
  
  		//아래 코드는 테스트 코드 입니다.
  		#include <iostream>
  
  		using namespace std;
  
  		int main()
  		{
  		  cout << solution("hello") << endl; // 출력값 : ehllo
  		  cout << solution("algorithm") << endl; // 출력값 : aghilmort
  	  
  		  return 0;
  		}
  	

문자열 내 마음대로 정렬하기
문제 설명

문자열로 구성된 배열 strings와, 정수 n이 주어졌을 때, 각 문자열의 인덱스 n 번째 글자를 기준으로 오름차순 정렬하려 합니다.
예를 들어, strings가 [“sun”, “bed”, “car”]이고 n이 1이면 각 단어의 인덱스 1의 문자 “u”, “e”, “a”로 strings를 정렬합니다.

제약 조건

• strings는 길이 1 이상, 50 이하인 벡터입니다.

• strings의 원소는 소문자 알파벳으로 이루어져 있습니다.

• strings의 원소는 길이 1 이상, 100 이하인 문자열입니다.

• 모든 strings의 원소 길이는 n보다 큽니다.

• 인덱스 1의 문자가 같은 문자열이 여럿이면, 사전 순으로 앞선 문자열이 앞쪽에 위치합니다.

  		#include <string>
  		#include <vector>
  		#include <algorithm>
  
  		using namespace std;
  
  		int idx;
  
  		// 비교 함수
  		bool compare (string a, string b) {
  		  return a[idx] == b[idx] ? a < b : a[idx] < b[idx];
  		}
  
  		vector<string> solution(vector<string> strings, int n) {
  		  idx = n;
  		
  		  // 각 문자열의 idx번째 문자를 기준으로 정렬 
  		  sort (strings.begin(), strings.end(), compare);
  		  return strings;
  		}

	// 아래 코드는 테스트 코드 입니다.
	#include <iostream>
	#include <iterator>

	using namespace std;

	void print(vector<string> vec)
	{
	  copy(vec.begin(), vec.end(), std::ostream_iterator<string>(cout, " "));
	  cout << endl;
	}

	int main()
	{
	  print(solution({"sun", "bed", "car"}, 1)); // 출력값 : car bed sun
	  print(solution({"abce", "abcd", "cdx"}, 2)); // 출력값 : abcd abce cdx

	  return 0;
	}
	

가장 큰 수
문제 설명

0 또는 양의 정수가 주어졌을 때 정수를 이어붙여 만들 수 있는 가장 큰 수를 알아내세요.
예를 들어, [6, 10, 2]가 주어졌다면 [6102, 6210, 1062, 1026, 2610, 2106]을 만들 수 있으며 이 중 가 장 큰 수는 6210입니다.
0 또는 양의 정수가 담긴 배열 numbers가 주어질 때 순서를 재배치해 만들 수 있는 가장 큰 수를 문자열로 바꾸어 반환하는 solution( ) 함수를 작성하세요.

제약 조건

• numbers의 길이는 1 이상 100,000 이하입니다.

• numbers의 원소는 0 이상 1,000 이하입니다.

• 정답이 너무 클 수 있으니 문자열로 바꾸어 반환합니다.

  		#include <string>
  		#include <vector>
  		#include <algorithm>
  
  		using namespace std;
  
  		// 문자열로 바뀐 두 수를 조합해서 크기를 비교
  		bool compare(const string& lhs, const string& rhs) {
  		  return (lhs + rhs) > (rhs + lhs);
  		}
  
  		string solution(vector<int> numbers) {
  		  string answer = "";
  		  vector<string> strings;
  
  		  for (auto elem : numbers) {
  			// numbers의 원소를 문자열로 변형해서 푸시
  			strings.push_back(to_string(elem));
  		  }
  		  // 정렬함수를 기준으로 정렬 
  		  sort(strings.begin(), strings.end(), compare);
  
  		  // 정렬된 문자열을 앞에서 부터 추가
  		  for (auto elem : strings) {
  			answer += elem;
  		  }
  
  			// 최종 숫자가 0이면 0을 반환하고 그렇지 않으면 answer 반환
  			return answer[0] == '0' ? "0" : answer;
  		}

	//아래 코드는 테스트 코드 입니다.
	#include <iostream>

	using namespace std;

	int main()
	{
	  cout << solution({6, 10, 2}) << endl; // 출력값 : 6210
	  cout << solution({3, 30, 34, 5, 9}) << endl; // 출력값 : 9534330
	  return 0;
	}

---

3-4 시뮬레이션
시뮬레이션의 핵심 개념을 명확히 이해하고, 이를 실제 프로그래밍 코드에 적용
2차원 배열 형태의 행렬 구조와 특정 위치를 나타내는 좌표 정보를 활용하여 발생하는 다양한 시뮬레이션 문제 효과적으로 해결

좌표 연산
y,x좌표 표현하기
2차원 배열 좌표로 표현 시 y 좌표를 행의 인덱스로, x좌표를 열의 인덱스로 표현

dx,dy 배열로 현재 좌표에서 이동하기
현재 좌표에서 주변 좌표로 이동하는 경우
이동 방향에 대한 오프셋 배열을 활용해서 구현하면 효율적이고 깔끔하게 구현
dy,dx 배열을 만들고 각각의 오프셋을 현재 좌표에 더해주면 됨
dy와 dx는 같은 인덱스끼리 짝을 이루므로, 반복문 사용해 모든 좌표 깔끔하게 순회 가능

좌우 대칭
좌우 대칭은 x축의 원소들이 이동하는 대칭이므로 Y좌표는 변하지 않음
배열 크기가 N이면 특정 원소의 좌표는 (N-1)-X

상하 대칭
상하 대칭은 Y축의 원소들이 이동하는 대칭이므로 X좌표는 변하지 않음
배열의 크기가 N이면 특정 원소의 Y좌표는 (N-1)-Y

90도 회전
기존 좌표가 (Y,X)이고 배열의 크기가 N이면 회전 후에는 ((N-1)-X,Y)

대각선 행렬
기존 좌표가 (Y,X)일 때 (Y+1, X+1)을 하면 정방향 대각선 기준 다음 원소
특정 좌표 (A,B)가 (Y,X)와 같은 대각선 상에 있는지 확인하려면 Y-A와 X-B가 동일한지 비교하는 것으로 확인 가능

역방향
현재 좌표에서 역방향 대각선 방향으로 이동
기존 좌표가 (Y,X)일 때 (Y+1 , X-1)을 하면 역방향 대각선 기준 다음 원소가 됨
특정 좌표 (A,B)가 (Y,X)와 같은 대각선 상에 있는지 확인 하려면 Y-A와 B-X가 동일한지 비교

문제 64. 달팽이 수열 만들기

문제 설명

n을 입력받아 n × n 크기의 2차원 배열을 생 성하여 달팽이 수열을 채우는 solution() 함수를 구현하세요. 달팽이 수열은 다음과 같이 숫 자 1부터 시작하여 시계 방향 나선형으로 채우는 수열을 말합니다.

제약 조건

• n은 2 이상 10미만의 자연수입니다.

• 숫자는 배열의 첫 번째 행, 첫 번째 열에서 시작합니다.

  		#include <vector>
  
  		using namespace std;
  
  		vector<vector<int>> solution(int n) {
  
  			// N*N 2차원 벡터를 선언하고 초깃값을 0으로 함
  			vector<vector<int>> snail_array(n, vector<int>(n, 0));
  			int num = 1;
  			// 행과 열의 시작과 끝 인덱스를 설정
  			int start_row = 0, end_row = n - 1;
  			int start_col = 0, end_col = n - 1;
  
  			// 제일 외각부터 달팽이 수열 규칙대로 채움
  			while (start_row <= end_row && start_col <= end_col) {
  				// 가장 왼쪽 윗부분 에서 가장 아래 바로 직전 까지  채우기
  				for (int i = start_col; i <= end_col; ++i) {
  					snail_array[start_row][i] = num++;
  				}
  				++start_row;
  
  				// 가장 왼쪽  아래부분 에서 가장 오른쪽 바로 직전 까지 채우기
  				for (int i = start_row; i <= end_row; ++i) {
  					snail_array[i][end_col] = num++;
  				}
  				--end_col;
  
  				// 가장 오른쪽 아래부분 에서 가장 위 바로 직전 까지 채우기
  				if (start_row <= end_row) {
  					for (int i = end_col; i >= start_col; --i) {
  						snail_array[end_row][i] = num++;
  					}
  					--end_row;
  				}
  
  				// 가장 윗부분 에서 가장 왼쪽 바로 직전 까지 채우기
  				if (start_col <= end_col) {
  					for (int i = end_row; i >= start_row; --i) {
  						snail_array[i][start_col] = num++;
  					}
  					++start_col;
  				}
  			}
  
  			return snail_array;
  		}
  	

문제 65. 이진 변환

문제 설명

0과 1로 이루어진 어떤 문자열 x에 대한 이진 변환을 다음과 같이 정의합니다.

1️⃣

x의 모든 0을 제거합니다.

1️⃣

x의 길이를 c라고 하면 x를 ‘c를 2진법으로 표현한 문자열’로 바꿉니다.

예를 들어, x = “0111010”이면 이진 변환 과정은 “0111010” → “1111” → “100”입니다. 0과 1로 이루어진 문자열 s가 주어지고 s가 “1”이 될 때까지 계속해서 이진 변환을 할 때 이진 변환의 횟수와 변환 과정에서 제거된 모든 0의 개수를 배열에 담아 반환하는 solution() 함수를 완성해 주세요.

제약 조건

• s의 길이는 1 이상 150,000 이하입니다.
• s에는 ‘1’이 하나 이상 포함되어 있습니다.

#include
#include
#include
#include

using namespace std;

vector solution(string s) {
int transforms = 0;
int removedZeros = 0;
// s가 “1”이 될때까지 계속 반복
while (s != "1") {
transforms++;

// '0' 개수를 세어 removedZeros에 누적
removedZeros += count(s.begin(), s.end(), '0');

// '1' 개수를 세고, 이를 이진수로 변환
int onesCount = count(s.begin(), s.end(), '1');
s = bitset<32>(onesCount).to_string();
s = s.substr(s.find('1'));

}

return {transforms, removedZeros};
}

문제 69. 캐릭터의 좌표

문제 설명

머쓱이는 RPG 게임을 하고 있습니다. 게임에는 [up], [down], [left], [right] 방향 키가 있으며 각 키를 누르면 위, 아래, 왼쪽, 오른쪽으로 1칸씩 이동합니다.
예를 들어, [0, 0]에서 [up]을 누르면 캐 릭터는 [0, 1]로, [down]을 누르면 [0, -1]로, [left]를 누르면 [-1, 0]로, [right]를 누르면 [1, 0]로 이동합니다.

머쓱이가 입력한 방향 키의 배열 keyinput과 맵의 크기 board가 주어지고, 캐릭터는 항상 [0, 0]에서 시작합니다. 키 입력이 모두 끝난 뒤에 캐릭터의 좌표 [x, y]를 반환하는 solution() 함수를 완성해 주세요. [0, 0]은 board의 정중앙에 위치합니다.

예를 들어, board의 가로 크기가 9면 캐릭터는 왼쪽으로 최대 [-4, 0],
오른쪽으로 최대 [4, 0]까지 이동할 수 있습니다.

제약 조건

• board는 [가로 크기, 세로 크기] 형태로 주어집니다.

• board의 가로 크기와 세로 크기는 홀수입니다.

• board의 크기를 벗어난 방향 키 입력은 무시합니다.

• 0 ≤ keyinput의 길이 ≤ 50

• 1 ≤ board[0] ≤ 99

• 1 ≤ board[1] ≤ 99

• keyinput은 항상 up, down, left, right만 주어집니다.

  		#include <string>
  		#include <vector>
  
  		using namespace std;
  
  		vector<int> solution(vector<string> keyinput, vector<int> board)
  		{
  			// 현재 위치를 나타 내는 크기가 2이고 값이 모두 0인 벡터 선언
  			vector<int> v(2,0);
  		
  			// 키 입력순으로 캐릭터 이동
  			for(string s : keyinput)
  			{
  				if     (s=="up"    && v[1]<+board[1]/2) v[1]++;
  				else if(s=="down"  && v[1]>-board[1]/2) v[1]--;
  				else if(s=="left"  && v[0]>-board[0]/2) v[0]--;
  				else if(s=="right" && v[0]<+board[0]/2) v[0]++;
  			}
  
  			return v;
  		}		

---

3-5 스택
스택은 가장 최근에 넣은 원소가 가장 먼저 나오는 LIFO(Last In First Out) 구조

스택의 ADT
ADT(Abstract Data Type)이란
자료형의 구조와 동작을 인터페이스 스준에서 정의한 추상적인 개념

구분	정의	설명
연산	boolean isFull()	스택에 들어 있는 데이터 개수가 maxsize인지 확인하여 boolean 값을 반환합니다. 가득 차 있으면 true, 아니면 false입니다.
연산	boolean isEmpty()	스택에 들어 있는 데이터가 하나도 없는지 확인하여 boolean 값을 반환합니다. 데이터가 하나라도 있으면 false, 없으면 true입니다.
연산	void push(ItemType item)	스택에 데이터를 추가합니다.
연산	ItemType pop()	스택에서 최근에 추가된 데이터를 제거하고 그 데이터를 반환합니다.
상태	int top	스택에서 최근에 추가된 데이터의 위치를 기록합니다.
상태	ItemType data[maxsize]	스택의 데이터를 관리하는 배열입니다. 최대 maxsize개의 데이터를 저장할 수 있습니다.

STL의 스택 활용하기
C++에서는 STL의 헤더를 통해 스택 자료구조 제공하므로 따로 구현 X
C++의 stack에서는 pop() 메서드가 값을 반환X, top() 메서드를 통해 가장 최근 푸시된 원소 확인 가능

함수 이름	동작	간단한 예시 (인자가 있으면 설명)	시간 복잡도 (변수 설명 포함)
stack::top()	top 요소 접근	해당 없음	O(1)
stack::empty()	스택이 비어 있는지 확인	해당 없음	O(1)
stack::size()	스택 내 요소 개수 반환	해당 없음	O(1)
stack::push()	top에 요소 삽입	s.push(value);	O(1)
stack::pop()	top 요소 제거	해당 없음	O(1)
stack::push_range()	top에 범위 내 요소 삽입	s.push_range(first, last); (반복자 first와 last로 정의된 범위)	O(N) — N은 삽입되는 요소 수

문제 9. 10진수를 2진수로 변환하기

문제 설명

10진수 decimal을 입력받아 2진수로 변환해서 문자열 형태로 반환하는 solution() 함수를 구현하세요.

제약 조건

• 제약 조건 없음.

  		#include <stack>
  		#include <string>
  		using namespace std;
  
  		string solution(int decimal) {
  		   // 입력 값이  0인 경우 바로 처리
  			if (decimal == 0) return "0"; 
  
  			stack<int> stack;
  			while (decimal > 0) {
  				// 2로 나눈 나머지를 스택에 삽입
  				stack.push(decimal % 2);  
  				decimal /= 2;
  			}
  
  			string binary = "";
  			while (!stack.empty()) {
  			   // 스택에서 차례대로 top()에 해당되는 값을 binary에 추가
  				binary += to_string(stack.top());  
  				stack.pop();
  			}
  			return binary;
  		}
  	

문제 12. 주식 가격

문제 설명

초 단위로 기록된 주식 가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 반환하도록 solution() 함수를 완성하세요.

제약 조건

• prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.

• prices의 길이는 2 이상 100,000 이하입니다.

  		#include <string>
  		#include <vector>
  		#include <stack>
  
  		using namespace std;
  
  		vector<int> solution(vector<int> prices) {
  		   // 가격이 떨어지지 않은 기간을 저장한 벡터    
  			vector<int> answer(prices.size());
  		  // 스택에는 prices의 인덱스가 들어감, 이전 가격과 현재 가격을 비교하기 위한 용도로 사용됨  
  		   stack<int> s;
  		
  			int priceNum = prices.size();
  		
  			for(int i=0;i<priceNum;i++){
  				while(!s.empty()&&prices[s.top()]>prices[i]){
  				   // 가격이 떨어졌으므로 이전 가격의 기간 계산 
  					answer[s.top()] = i-s.top();
  					s.pop();
  				}
  				s.push(i);
  			}
  			// 스택에 남아있는 가격들은 가격이 떨어지지 않은 경우
  			while(!s.empty()){
  				answer[s.top()] = priceNum-s.top()-1;
  				s.pop();
  			}
  			return answer;
  		}

문제 13. 크레인 인형 뽑기 게임

☝

문제 설명

게임 개발자인 죠르디는 크레인 인형 뽑기 기계를 모바일 게임으로 만들려고 합니다. 죠르디는 게 임의 재미를 높이기 위해 화면 구성과 규칙을 다음과 같이 게임 로직에 반영하려고 합니다.

게임 화면은 1 × 1 크기의 격자로 구성된 N × N 크기의 격자이며 위쪽에는 크레인이 있고 오른쪽에는 바구니가 있습니다.
여러분이 보고 있는 화면은 5 × 5 크기의 격자 예입니다. 각 격자 칸에는 다양한 인형이 들어 있으며 인형이 없는 칸은 빈칸입니다.
인형은 격자 한 칸을 차지하며 격자의 가장 아래 칸부터 차곡차곡 쌓입니다.
플레이어는 크레인을 좌우로 움직일 수 있고 크레인을 멈춘 위치에서 가장 위에 있는 인형을 집어 올릴 수 있습니다. 집어 올린 인형은 바구니에 쌓입니다.
이떼 바구니의 가장 아래 칸부터 인형이 순서대로 쌓입니다. 그림은 ❶, ❷, ❸ [1번, 5번, 3번] 위치에서 순서대로 인형을 집어올려 바구니에 담은 모습입니다.

이 상태에서 ❹ 네모 인형이 1개 더 들어가면 어떻게 될까요?
같은 모양의 인형 2개가 바구니에 연속해 쌓이면 두 인형은 펑하고 터지며 사라집니다. 만약 인형이 없는 곳에서 크레인을 작동시키면 아무 일도 일어나지 않습니다. 또 바구니는 모든 인형이 들어갈 수 있을 만큼 충분히 큽니다. 2차원 배열 board와 인형을 집는 크레인을 작동시킨 위치가 담긴 배열 moves가 주어질 때, 크레인을 모두 작동시킨 후 사라진 인형 개수를 반환하는 solution() 함수를 완성하세요

제약 조건

• board는 2차원 배열, 크기는 5×5 이상 30×30 이하입니다.

• board의 각 칸에는 0 이상 100 이하인 정수가 담겨있습니다.

  • 0은 빈칸을 나타냅니다.
  • 1~100의 각 숫자는 각기 다른 인형의 모양을 의미하며 같은 숫자는 같은 모양의 인형을나타냅니다.

• moves 배열 크기는 1 이상 1,000 이하입니다.

• moves 배열 각원소들의 값은 1 이상이며 board 배열의 가로 크기 이하인 자연수입니다.

  		#include <stack>
  		#include <vector>
  
  		using namespace std;
  
  		int solution(vector<vector<int>> board, vector<int> moves) {
  		  // 보드판의 열의 크기만큼 스택을 생성 
  		  stack<int> lanes[board[0].size()];
  		  // 보드의 가장 밑의 행부터 위로 올라가먼서 순회 
  		  for(int i = board.size()-1 ; i >= 0; --i) {
  			for(int j = 0; j<board[0].size(); ++j) {
  			 // 블럭이 있는 경우 해당 열에 해당되는 스택에 푸시 
  			  if(board[i][j]) {
  				lanes[j].push(board[i][j]);
  			  }
  			}
  		  }
  
  		 // 보드판에서 꺼낸 인형을 담을 bucket과 사라진 인형의 개수를 저장할 answer 선언
  		  stack<int> bucket;
  		  int answer = 0;
  
  		  for(int m : moves) {
  		   // 해당 lane에 블럭이 있으면
  			if(lanes[m-1].size()){
  			  int doll = lanes[m-1].top();
  			  lanes[m-1].pop();
  			 // 버킷에 블럭이 있고, 가장 최근에 들어간 블럭과 현재 블럭이 같은지 확인
  			  if (bucket.size() && bucket.top() == doll) {
  				bucket.pop();
  				answer += 2;
  			  } else {
  				bucket.push(doll);
  			  }
  			}
  		  }
  
  		  return answer;
  		}

---

3-6 큐
큐는 대기열을 의미하며 먼저 들어간 데이터가 먼저 나오는 선입선출(First-In First-Out)방식의 자료구조
큐는 push() 연산으로 데이터를 삽입하고 pop() 연산으로 데이터를 꺼냄
이 연산은 스택과 동일하지만 큐는 선입선출 방식이라는 점에서 차이

큐 ADT
ADT(Abstaract Data Type)이란
인터페이스만 있고 실제로 구현하지 않은 자료형

구분	정의	설명
연산	boolean isFull()	큐에 들어 있는 데이터 개수가 maxsize인지 확인해 boolean 값을 반환합니다.
연산	boolean isEmpty()	큐에 들어 있는 데이터가 하나도 없는지 확인해 boolean 값을 반환합니다.
연산	void push(ItemType item)	큐에 데이터를 푸시합니다.
연산	ItemType pop()	큐에서 처음에 푸시한 데이터를 삭제하고 그 데이터를 반환합니다. (삭제하기 전 백업 필요)
상태	int front	큐에서 가장 마지막에 pop한 위치를 기록합니다.
상태	int rear	큐에서 최근에 push한 데이터의 위치를 기록합니다.
상태	ItemType data[maxsize]	큐의 데이터를 관리하는 배열입니다. 최대 maxsize개의 데이터를 저장할 수 있습니다.

STL의 큐 활용하기
C++에서는 STL을 통해 큐 자료구조를 사용할 수 있으므로, 기본적인 용도라면 직접적인 구현 X
STL의 queue는 front() 메서드를 통해 큐의 맨 앞 요소를 참조 반환, 이 값을 읽거나 수정 가능

함수 이름	동작	간단한 예시 (인자가 있으면 설명)	시간 복잡도 (변수 설명 포함)
queue::front()	front 요소 접근	해당 없음	O(1)
queue::empty()	큐가 비어 있는지 확인	해당 없음	O(1)
queue::size()	큐 내 요소 개수 반환	해당 없음	O(1)
queue::push()	rear에 요소 삽입	q.push(value);	O(1)
queue::pop()	front 요소 제거	해당 없음	O(1)
queue::push_range()	큐에 범위 내 요소 삽입	q.push_range(first, last); (반복자 first~last 범위)	O(N) — N은 삽입되는 요소 수

문제 15. 요세푸스 문제

문제 설명

N 명의 사람이 원 형태로 서 있습니다. 각 사람은 1부터 N까지 번호표를 갖고 있습니다. 그리고임 의의 숫자 K가 주어졌을 때 다음과 같이 사람을 없앱니다.

• 1번 번호표를 가진 사람 기준 시계방향으로 K 번째 사람을 없앱니다.
• 없앤 사람 다음 사람을 기준으로 하고 다시 K 번째 사람을 없앱니다.

N과 K가 주어질 때 마지막에 살아 있는 사람의 번호를 반환하는 solution() 함수를 구현해 주세요.

제약 조건

• N과 K는 1 이상 1,000 이하의 자연수입니다.

  		#include <queue>
  
  		using namespace std;
  
  		int solution(int N, int K) {
  			queue<int> q;
  
  			// 1부터 N까지의 번호를 큐에 추가
  			for (int i = 1; i <= N; i++) {
  				q.push(i);
  			}
  
  		  // 큐에 하나의 요소가 남을 때까지 순회
  			while (q.size() > 1) { 
  				for (int i = 0; i < K - 1; i++) {
  					// K번째 사람을 찾기 위해 앞에서부터 제거하고 뒤에 추가
  					q.push(q.front());
  					q.pop();
  				}
  				// K번째 사람 제거
  				q.pop();
  			}
  
  			// 마지막으로 남은 요소 반환
  			return q.front();
  		}

문제 17. 카드 뭉치

문제 설명

코니는 영어 단어가 적힌 카드 뭉치 2개를 선물로 받았습니다. 코니는 다음과 같은 규칙으로 카드에 적힌 단어들을 사용해 원하는 순서의 단어 배열을 만들 수 있는지 알고 싶습니다.

• 원하는 카드 뭉치에서 카드를 순서대로 한 장씩 사용합니다.
• 한번 사용한 카드는 다시 사용할 수 없습니다.
• 카드를 사용하지 않고 다음 카드로 넘어갈 수 없습니다.
• 기존에 주어진 카드 뭉치의 단어 순서는 바꿀 수 없습니다.

예를 들어, 첫 번째 카드 뭉치에 [“i”, “drink”, “water”], 두 번째 카드 뭉치에 [“want”, “to”]가 적 혀 있을 때 [“i”, “want”, “to”, “drink”, “water”] 순서의 단어 배열을 만들려고 합니다. 첫 번째 카드 뭉치에서 “i”를 사용한 후 두 번째 카드 뭉치에서 “want”와 “to”를 사용하고 첫 번째 카드 뭉 치에 “drink”와 “water”를 차례대로 사용하면 원하는 순서의 단어 배열을 만들 수 있습니다.

문자열로 이루어진 배열 cards1, cards2와 원하는 단어 배열 goal이 매개변수로 주어질 때 cards1 과 cards2에 적힌 단어들로 goal를 만들 수 있다면 “Yes”를, 만들 수 없다면 “No”를 반환하는 solution() 함수를 완성하세요.

제약 조건

• 1 ≤ cards1의 길이, cards2의 길이 ≤ 10

  • 1 ≤ cards1[i]의 길이, cards2[i]의 길이 ≤ 10
  • cards1과 cards2에는 서로 다른 단어만 있음.

• 2 ≤ goal의 길이≤ cards1의 길이 + cards2의 길이

  • 1 ≤ goal[i]의 길이 ≤ 10
  • goal의 원소는 cards1과 cards2의 원소들로만 이루어져 있음.

• cards1, cards2, goal의 문자열들은 모두 알파벳 소문자로만 이루어져 있음.

  		#include <iostream>
  		#include <queue>
  		#include <string>
  		#include <vector>
  
  		using namespace std;
  
  		string solution(vector<string> cards1, vector<string> cards2, vector<string> goal) {
  			queue<string> c1, c2, g;
  		
  		   // ❶cards와 goal을 queue로 나타냄 
  			for (const string& s : cards1) c1.push(s);    
  			for (const string& s : cards2) c2.push(s);
  			for (const string& s : goal) g.push(s);
  			
  			//❷ 단어 배열을 앞에서 부터 순회 
  			while (!g.empty()) {
  			   //❸ c1의 현재 문자열과 g의 현재 문자열이 일치하는 경우
  				if (!c1.empty() && c1.front() == g.front()) {
  					c1.pop();
  					g.pop();
  				}
  			   //❹ c2의 현재문자열과  g의 현재 문자열이 일치하는 경우 
  			   else if (!c2.empty() && c2.front() == g.front()) {
  					c2.pop();
  					g.pop(); 
  				}
  			   //❺ 일치하는 카드뭉치가 없는 경우 반복문을 빠져나감 
  			   else {
  					break;
  				}
  			}
  		   //❻ 원하는 문자열을 카드뭉치에서 만들었으면 Yes 아니면 No 반환
  			return g.empty() ? "Yes" : "No";
  		}