[C++ 코딩테스트 연습] 4. 배열, 정렬

samooyang 2026. 5. 14. 11:47

2026. 5. 14. 11:47

[1. 배열]

1. 배열의 특징

1) 동질성

배열의 원소는 모두 동일한 타입을 갖는다.

2) 연속된 메모리 할당

단편화 문제가 발생할 확률이 적어 접근 속도가 빠르다.

3) 인덱스 기반 접근

배열의 첫 번째 원소는 인덱스 0을 가지고, 이후의 원소들은 순차적으로 1씩 증가하는 인덱스를 가진다.

2. 배열의 선언

타입에 더해 배열은 배열의 크기를 추가로 명시해야 한다.

1) 1차원 배열

데이터를 선형형태로 저장하는 가장 기본적인 배열이다.

int arr[5]; 처럼 선언한다.

int arr[5] = {1,2,3,4,5}; 처럼 선언 후 초기화도 가능하다. 만약 초기화하는 값의 개수가 size보다 적으면 나머지 원소는 0으로 자동 초기화된다. 반대로 선언하고 아예 초기화하지 않으면 값은 Garbage Value로 남는다.

2) 2차원 배열

데이터를 행과 열로 구성된 표 형태로 저장하는 배열이다. 가로줄은 행. 세로줄은 열로 읽는다.

int arr[2][3]; 처럼 선언한다. 이 경우 2행, 3열의 2차원 배열을 선언한다.

int arr[2][3]={{1,2,3},{4,5,6}}; 기본적으로 가로줄 먼저 쓴다고 생각하면 된다. 첫번째 행은 {1,2,3}, 두번째 행은 {4,5,6}의 2차원 배열로 초기화된다.

3) 3차원 배열

먼저 게임 개발에서 어떻게 3차원 배열을 사용하는지 알아봤다.

복셀(Voxel)기반 지형 : 대표적으로 마인크래프트. 월드의 특정 구역(Chunk) 데이터를 저장할 때 chunk[x][y][z] 형태의 3차원 배열을 사용해서 해당 위치에 어떤 블록이 있는지를 저장한다.

공간 분할 : FPS게임에서 총알이 적과 부딪혔는지 검사하기 위해 3D 공간을 거대한 3차원 배열로 쪼갠뒤, 총알이 위치한 해당 배열 칸과 그 주변 칸의 적들만 검사하게 해서 성능을 향상시킨다.

3D 길찾기 : 공중을 날아다니는 비행기 같은 AI가 장애물을 피해 목표 지점으로 이동하게 하려면 3차원 노드 배열을 기반으로 알고리즘을 수행해야 한다.

3차원 배열을 위해서는 1차원 배열을 3차원처럼 다루는 평탄화 기법을 사용한다.

예를 들어, int width, height, depth 를 이용해서 가로, 세로, 깊이가 각각 10인 3차원 그리드를 만든다고 하면,

1차원 배열 하나로 다음과 같이 전체 공간 10*10*10 을 한번에 할당할 수 있다.

vector<int> grid(width * height * depth, 0);

이렇게 전체 공간을 할당해 둔 뒤, [x][y][z] 위치의 데이터에 접근하기 위해서

int index = x + (y*width) + (z*width*height);

grid[index] =1;

이렇게 3차원 공간을 1차원 배열처럼 만들고 사용할 수 있다.

3. 배열의 메모리 구조

다차원 배열이라고 할지라도, 컴퓨터의 메모리 구조는 결국 1차원이므로 배열의 원소들은 메모리 상에 연속적인 메모리 할당 방식으로 저장, 즉 한 줄로 저장된다. C++에서는 2차원 이상의 배열도 내부적으로는 행 우선 순서로 배치된다.

4. 배열의 효율성

1) 맨 뒤에 삽입하는 경우

O(1) 연산. 다른 원소에 영향을 미치지 않고 그냥 추가된다.

2) 맨 앞에 삽입하는 경우

O(n) 연산. 현재 존재하는 배열의 원소들이 한 칸씩 밀리면서 추가된다.

문제 풀어보기

[1. 배열 제어하기]

<문제> 정수 배열 lst가 주어질 때, 배열의 중복값을 제거하고 배열 데이터를 내림차순으로 정렬해서 반환하는 solution() 함수 구현하기.

<조건>

lst의 길이는 2 이상 1,000 이하

lst의 원소 값은 -100,000 이상 100,000이하

#include <vector>
#include <algorithm> // sort, unique를 위해 선언
using namespace std;
bool compare(int a, int b) { // 정렬 기준 정의
 return a > b;
}
vector<int> solution(vector<int> lst) {
 sort(lst.begin(), lst.end(), compare); // 내림차순으로 정렬
 lst.erase(unique(lst.begin(), lst.end()), lst.end()); // 중복값 제거
 return lst;
}

1) 먼저 배열 데이터를 내림차순으로 정렬한다. sort() 와 compare()를 결합한다.

2) 중복값을 제거한다. 중복값을 제거할 땐 unique() 와 erase()를 사용한다.

[2. 두 수를 뽑아서 더하기]

<문제> 정수 배열 numbers가 주어질 때, numbers에서 서로 다른 인덱스에 있는 2개의 수를 더해 만들 수 있는 모든 수를 배열에 오름차순으로 담아 반환하는 solution()함수를 구현하기.

<조건>

numbers의 길이는 2 이상 100 이하

numbers의 모든 수는 0 이상 100 이하

#include <vector>
#include <set>
using namespace std;
vector<int> solution(vector<int> numbers) {
 set<int> sum; // 두 수의 합을 저장할 저장공간 선언
 for(int i = 0;i<numbers.size();++i) // 반복문을 수행하면서 두 수의 합을 저장
 for(int j = i+1 ; j< numbers.size();++j)
 sum.insert(numbers[i] + numbers[j]);
 vector<int> answer(sum.begin(), sum.end()); // 반환타입을 맞추기 위헤 벡터 자료형
 return answer;
}

set라는 컨테이너를 사용해서 애초에 그냥 중복을 없애버리고 오름차순으로 담아버리자.

[3. 가장 많은 문제를 맞춘 사람 찾기]

<문제>

3명이 모의고사의 문제를 전부 찍으려 할 때, 1번 문제부터 마지막 문제까지의 정답이 순서대로 저장된 배열 answers가 주어졌을 때 가장 많은 문제를 맞춘 사람이 누구인지 배열에 담아 반환하도록 solution() 함수를 작성하기.

<조건>

1번 사람 : 1, 2, 3, 4, 5 를 반복해서 찍음.

2번 사람 : 2, 1, 2, 3, 2, 4, 2, 5를 반복해서 찍음

3번 사람 : 3, 3, 1, 1, 2, 2, 4, 4, 5, 5를 반복해서 찍음

시험은 최대 10,000문제로 구성.

문제의 정답은 1, 2, 3, 4, 5 중 하나임.

가장 높은 점수를 받은 사람이 여럿이면 반환하는 값을 오름차순으로 정렬.

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
// 각 수포자가 찍는 패턴을 정의
vector<int> firstPattern = {1,2,3,4,5};
vector<int> secondPattern = {2,1,2,3,2,4,2,5};
vector<int> thirdPattern = {3,3,1,1,2,2,4,4,5,5};
vector<int> solution(vector<int> answers) {
 // 최종적으로 가장 많이 문제를 맞힌 사람이 저장될 벡터
 vector<int> answer;

 // 각 수포자들의 패턴대로 답안을 작성할때 문제를 맞힌 갯수가 저장될 벡터
 vector<int> matchCnt(3);
 // 실제 정답과 각 수포자들의 패턴을 비교해서 맞춘 갯수
 for(int i=0; i<answers.size(); i++) {
 if(answers[i] == firstPattern[i % firstPattern.size()]) matchCnt[0]++;
 if(answers[i] == secondPattern[i % secondPattern.size()]) matchCnt[1]++;
 if(answers[i] == thirdPattern[i % thirdPattern.size()]) matchCnt[2]++;
 }
 // 가장 많이 맞춘 수포자가 얻은 점수
 int max_score = *max_element(matchCnt.begin(),matchCnt.end());
  // 가장 많이 맞춘 수포자의 번호를 저장
 	for(int i = 0; i< 3; i++) {
 	if(matchCnt[i] == max_score) answer.push_back(i+1);
 	}
	
	return answer;
}

0) 채점을 한 다음에, 가장 높은 점수를 받은 사람의 번호를 배열 형태로 돌려주는 메인 함수를 작성한다.

1) vector<int> matchCnt(3); 수포자 3명의 점수가 담길 벡터를 만들어놓은 것. 크기가 3인 배열 matchCnt를 선언하고, 기본적으로 배열은 초기화 하지 않으면 0으로 채워지기 때문에 채점 준비를 마치게 된 것이다.

2) 채점 로직 : for문을 사용해서 i = 0 부터 정답표를 스캔하면서 3명을 동시에 채점하기 위한 반복문.

찍는 패턴이 반복되므로 나머지 연산자를 사용해서 배열의 크기 이내에서 패턴이 반복될 수 있도록 만든 것. 값이 일치하면 matchCnt를 1 증가 시킴. 첫번째 사람의 경우 인덱스 0번에 카운트가 저장됨.

3) matchCnt 배열을 확인한 뒤에 max_element 함수를 사용해 가장 높은 점수가 몇 점인지 확인하고, 그게 max_score로 된다. 담만 값이 있는 위치를 알려주어야 하기 때문에 *max_element를 사용하였다.

4) 인덱스 i에 1을 더한 값이 학생의 번호가 되므로 최고 점수를 받은 학생이 vector<int> answer 배열에 들어가게 된다. 이렇게 해야 공동 1등이 있어도 번호가 작은 순서대로 배열에 담기게 된다.

[2. 정렬]

정렬이란?: 사용자가 정의한 순서대로 데이터를 나열하는 것을 의미한다.

정렬을 하는 이유: 원하는 값을 빨리 찾을 수 있다. 또한 정렬이 전제 조건인 알고리즘이 존재하기도 한다.

1. 정렬의 종류

1) 삽입 정렬

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

[의사 코드]

for j = 2 to A.length
 key = A[j]
 // A[j]를 정렬된 부분 배열 A[1..j-1]에 삽입한다.
 	i = j - 1
 	while i > 0 and A[i] > key
	 	A[i + 1] = A[i]
 		i = i - 1
	A[i + 1] = key

[세부 동작]

기본적으로, 두 원소를 비교하고, 삽입 정렬 연산을 수행하면 앞의 원소가 뒤로 밀려나고, 그 빈칸을 뒤의 원소가 채워주는 방식. 최종적으로는 오름차순의 경우 작은 숫자가 맨 앞으로 오게 되고, 큰 숫자가 맨 뒤로 가게 된다.

(1) 첫 번째 원소는 이미 정렬된 것으로 간주하므로, 두 번째 원소부터 시작한다.

(2) 뒷자리의 원소와 비교해서 (오름차순인 경우) 뒷자리의 원소가 더 크면 연산을 수행하지 않고, 뒷자리의 원소가 더 작으면 연산을 수행한다. 이 연산은 뒷자리에 있던 원소가 정렬 상태를 만들 때까지 밀어내고 채워넣는 식으로 반복된다.

[시간 복잡도]

O(N^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++) {
 int key = arr[i];
 int j = i - 1;
 // key보다 큰 요소를 한 칸씩 뒤로 이동
 	while (j >= 0 && arr[j] > key) {
 	arr[j + 1] = arr[j];
 	j--;
 	}
 	arr[j + 1] = key;
 	}
 	for (int i = 0; i < n; i++)
 		cout << arr[i] << " ";
 		cout << endl;
// 출력결과
// 1 2 3 4 5 6
}

2) 병합 정렬

정렬되지 않은 데이터를 계속 반으로 나눈 뒤, 작은 단위부터 정렬하며 병합해 나가는 방식의 정렬 알고리즘.

[의사 코드]

MERGE_SORT(A, p, r)
if p < r
 q = (p + r) / 2
 MERGE_SORT(A, p, q)
 MERGE_SORT(A, q + 1, r)
 MERGE(A, p, q, r) // 이미 정렬된 A[p...q]와 A[q+1....r]을 병합해서 하나의 배열로 만듬

[세부 동작]

(1) 분할

정렬할 배열의 중간 지점을 기준으로 두 개의 하위 배열로 나눈다.

(2) 정복

각 하위 배열은 재귀적으로 병합 정렬을 호출해서 정렬한다.
(3) 결합

정렬된 두 개의 하위 배열을 하나의 정렬된 배열로 병합한다. 이 과정에서 두 배열의 원소를 순서대로 비교해서 작은 값을 먼저 새로운 배열에 추가한다.

[시간 복잡도]

데이터가 N 개일 때 데이터가 1개가 될 때까지 계속 반으로 나누면 분할트리의 높이 h는 logN이다.

각각의 분할 단계마다 모든 데이터를 병합하므로, 병합 연산은 단계마다 총 N번 발생한다. 따라서 전체 시간 복잡도는

O(N) * logN = O(NlogN)이 된다.

#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; // 임시 배열(temp)의 시작 인덱스
  
   // 두 부분 배열을 비교하며 임시 배열에 정렬하여 저장
     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++];
     }
     // 임시 배열(temp)에 정렬된 요소들을 원래 배열(arr)의 해당 위치에 복사
     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;
 // 출력 결과
 // 원본 배열: 9 3 1 5 13 12
 // 정렬된 배열: 1 3 5 9 12 13
 return 0;
}

(1) mergesort() 함수로 배열을 더 이상 쪼갤 수 없을 때까지 계속 반으로 나눈다. 최종적으로는 요소가 1개씩 남는다. 이 과정에서 재귀함수가 사용된다.

(2) merge() 함수로 정렬하면서 다시 합친다. 임시 배열(temp)을 만들어서 정렬된 결과를 이곳에 쌓아놓으면서 왼쪽 배열의 첫번째가 i부터 시작하고, 오른쪽 배열의 첫번째가 j부터 시작하게 해서 i와 j를 비교하면서 더 작은 숫자를 임시 배열(k번째 인덱스)에 채워 넣는다. 이후, 다 수행하고 나서 보니 한쪽 배열의 숫자가 남아있는 경우, 남아있는 숫자들을 차례대로 temp에 그대로 옮겨 담는다.

(3) 원본 배열로 되돌린다. temp배열의 내용물을 원본 배열인 arr의 원래 위치에 덮어씌운다. temp는 delete[] temp를 통해 메모리에서 지운다.

3) 계수 정렬

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

[의사 코드]

//A는 입력 배열이고, k는 입력 배열의 최대값
COUNTING-SORT(A, k)
 count ← 크기가 k + 1인 0으로 채워진 배열
 output ← 입력 배열과 같은 크기의 배열
 for i = 0 to A.length - 1
 count[A[i]] ← count[A[i]] + 1
 idx ← 0
 for i = 0 to k-1
  while (count[i]--) {
 	arr[idx++] = i;
 }

[세부 동작]

(1) 카운트 배열을 생성한다. 입력 배열의 최대값 k를 기준으로 크기가 (k+1)인 count 배열을 생성하고 모든 원소를 0으로 초기화.

(2) 빈도수를 계산한다. 입력 배열을 순회하면서 각 원소의 값을 인덱스로 사용해서 배열의 해당 위치에 빈도수를 누적한다.

(3) 결국 값을 인덱스로 사용해서 그대로 끼워넣으며 정렬하는 방식이다. 굉장히 직관적인듯.

다만, 계수 정렬은 음수 값이 존재하여 해당 값을 배열의 인덱스로 사용할 수 없는 경우 계수 정렬을 사용할 수 없고, 원소 값의 범위가 넓거나 듬성듬성 있는 경우 메모리 사용 면에서 비효율적이라는 한계점이 있다.

[시간 복잡도]

count 배열을 초기화 할 때 O(K)

빈도수를 셀 때 O(N)

정렬된 배열을 생성하는 데 O(N)

최종적으로는 O(N+K)이다.

// 목적: 양의 정수만으로 이루어진 배열을 계수 정렬로 정렬한다.
// 동작: 배열에서 최댓값을 찾아 그 크기만큼 카운트 배열을 만들고, 카운트 정보를 기반으로
#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 2 2 3 3 4 8
//

4) 힙 정렬

힙이란 조건을 만족하는 이진 트리이다. 보통 최대힙과 최소힙으로 구분된다.

최대 힙은 모든 부모 노드의 값이 자식 노드의 값보다 크거나 같다.

최소 힙은 반대로 부모 노드의 값이 자식 노드보다 작거나 같다.

최대힙을 구축하는 과정을 통해 알아보자.

(1) 최대힙을 구축하기 위해선 먼저 max_heapify(int idx)를 정의한다. 이 함수는 특정 원소를 기준으로 최대 힙의 성질을 만족하도록 재구성하는 함수이다.

// 전역 변수: 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 수행

(2) 마지막 non-leaf 노드부터 루트 노드까지 차례대로 max_heapify()를 수행하면 배열을 최대 힙 구조로 변환할 수 있다. 이 과정을 bulid_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를 호출합니다

여기서, 반복문을 A.length / 2 부터 시작한 것에 주목해보자면, 힙을 구축할 때 자식 노드가 없으면 아무런 동작을 하지 않는다는 점을 이용한 것이다. 현재 노드 인덱스가 N/2 을 넘으면 자식 노드의 인덱스가 N을 넘게된다. 힙의 크기는 N이므로 이러한 일이 발생하지 않으니까 굳이 현재 노드 인덱스가 N/2을 넘는 일은 고려하지 않아도 된다는 것이다.

(3) max_heapift()를 수행하고 나서는 힙 정렬을 수행한다.

힙 정렬의 최종 목적은 배열을 오름차순 또는 내림차순으로 정렬하는 것이다. 최대 힙은 가장 큰 값이 루트에 위치하게만 할 뿐, 배열 전체가 정렬된 상태는 아니기 때문에 힙 정렬이 필요한 것이다.

최대 힙을 구성한 후, 루트 노드를 배열의 마지막 요소와 교환하고, 나머지 구간에 대해 다시 최대힙을 구성하는 과정을 반복해서 계속 뒤에서부터 끼워넣는 방식으로 전체 배열을 정렬한다.

[의사 코드]

// 전역 변수: 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는 오름차순으로 정렬됨

정렬된 요소 A[i]를 힙에서 제외하는 heap_size = heap_size - 1 (힙 크기 1 감소) 과정을 잘 숙지해놓자.

[시간 복잡도]

힙은 높이가 최대 log N인 이진트리가 되고, 각 단계에서 힙 속성을 재구성하는데 O(log N)의 시간이 걸리므로, 전체 정렬의 시간 복잡도는 O(N logN)이 된다.

힙 자료구조를 이용하게 되면 새로운 원소를 삽입 또는 삭제할 때 힙의 성질을 유지할 수가 있어 트리의 높이만큼만 연산이 필요하게 되어 O(log N)이 된다.

문제 풀어보기

[1. 계수 정렬 구현하기]

<문제>

인수로 받은 문자열 s를 사전순으로 정렬된 문자열로 반환하는 solution() 함수를 구현하기. 정렬은 계수 정렬을 활용할 것.

#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;
}

알파벳 개수만큼 빈도수 배열을 생성하면, 그 배열의 인덱스 0 은 'a'문자의 개수를 저장하는 공간이 된다.

counts[c - 'a']++. 아스키 코드 값을 이용할 때, 현재 글자(s[i])에서 'a'를 빼면 알파벳의 순서대로 인덱스 값을 얻을 수 있다. 예를 들어 s[i]가 b면 'b'의 아스키 코드값은 98이고, 'a'의 아스키 코드값은 97이다. 따라서 값이 1이 되어서 인덱스 1에 개수를 더할 수 있게 되는 것이다. 아스키코드를 외우는게 문제가 아니고, 그냥 보통 이런 식으로 사용해서 함수를 작성하는 경우가 많아서(성능이 좋음) 잘 숙지해두자.

sorted_str += string(counts[i], i + 'a'). 아까 아스키 코드 값을 이용해서 인덱스 i에 개수를 더했으니까, 이제는 다시 인덱스 숫자 i에 다시 문자 'a'를 더해서 string() 함수를 이용해서 문자로 변환하는 식이다. 그렇게해서 복원된 문자를 sorted_str에 저장하고 반환받는다.

<조건>

string의 길이는 1 이상 10,000이하

s는 알파벳 소문자로 이루어져 있음.

[2. 문자열 정렬하기]

<문제>

문자열로 구성된 배열 strings와 정수 n이 주어졌을 때, 각 문자열의 인덱스 n번째 문자를 기준으로 오름차순 정렬하기.

<조건>

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

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

strings의 원소는 길이 1 이상, 100 이한인 문자열이다.

모든 strings의 원소 길이는 n보다 크다.

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

#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;
}

sort()와 comp()를 이용해서 구현해보자.

비교함수는 삼항연산자를 이용해서 작성해본다. a[idx] == b[idx]면 문자열 전체를 사전순으로 비교(a<b) 하고, 그렇지 않으면 idx번째 문자 자체를 비교해서 오름차순으로 배치하라는 것이다.

[3. 가장 큰 수 구하기]

<문제>

0 또는 양의 정수 두 숫자가 주어졌을 때 정수를 이어붙여 만들 수 있는 가장 큰 수를 알아내기. 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;
}

(1) 입력된 정수를 문자열로 변환한 뒤, comp() 함수를 통해서 이어 붙였을 때 더 큰 경우를 찾아내서 결과를 완성하는 것이다.

(2) lhs, rhs를 문자열(const string& )로 받아와서 비교한 뒤 만약 왼쪽 + 오른쪽 순서로 문자열을 이어붙인 결과가 크면 true를 반환하고 그렇지 않으면 false를 반환하는 식이다.

(3) string solution(vector<int> numbers) -> 정수형 배열 numbers를 입력받아서 가장 큰 수를 문자열 형태로 반환하는 메인함수

(4) string answer = ""; -> 정답을 문자열로 바꾸어 반환한다. 누락하지 않도록 유의!

(5) sort + comp 이용해서 정렬함수를 기준으로 vector안에 담겨있는 문자열 형태의 원소를 정렬한다. 이렇게 되면 앞에 두었을 때 더 큰 숫자를 만들어내는 녀석으로 배열의 맨 앞으로 밀어내게 된다.

(6) 이렇게 정렬된 문자열 형태의 숫자를 결국 앞에서부터 추가한다. 예를 들어 sort(comp())를 거치고 나서 정렬된 배열이 {6, 10} 이면, 정렬된 순서대로 앞에서부터 문자열을 추가해서 answer = ""; 에 붙이는 것이다. 결과적으로 "610"의 문자열로 정답이 반환되게 된다.

오늘의 코드카타(05.13)

자연수 n을 뒤집어 각 자리 숫자를 원소로 가지는 배열 형태로 리턴해주세요. 예를 들어 n이 12345이면 [5,4,3,2,1]을 리턴합니다.

(1) malloc(C언어)

#include <stdio.h>
#include <stdlib.h>

int* solution(long long n) {
	long long temp = n;
    int len = 0;
    if (n == 0) {
    	len = 1;
	} else {
    	while (temp > 0) {
        	len++;
            temp /= 10;
		}
    }

	int* answer = (int*)malloc(sizeof(int)*len);
	int i = 0;
	
    if (n == 0) {
		answer[0] = 0;
	} else {
    	while (n>0) {
        	answer[i++] = n % 10;
            n /= 10;
        }
    }
    return answer;
}

동적 메모리 할당 함수인 malloc을 사용하기 위해서 먼저 n의 자릿수를 구한뒤에 필요한 메모리 공간의 크기를 계산한다.

이후 n을 10으로 나눈 나머지를 인덱스 0번부터 배열에 채워나가는 식으로 작성한다.

(2) vector

#include <vector>

using namespace std;

vector<int> solution(long long n) {
	vector<int> answer;
    
    if (n==0) {
    	answer.push_back(0);
        return answer;
    }
    
    while (n>0) {
    	answer.push_back(n%10);
        n /= 10;
    }
    return answer;
}

C++에서 vector라는 컨테이너를 사용하면, 자릿수를 미리 구하지 않아도 알아서 메모리를 확보하고 push_back을 사용해서 쉽게 vector배열의 끝에 원소를 추가할 수 있다.

(3) to_string

다른 문제풀이에 많이 응용되기도 하는 방법. 숫자를 문자열로 변환하여 처리하는 방법이다. n을 문자열로 바꾼 뒤에, 문자열의 뒤에서 앞으로 순회하며 문자를 다시 숫자로 변환해 배열에 담는 방법이다.

#include <vector>
#include <string>

using namespace std;

vector<int> solution(long long n) {
    vector<int> answer;
    string s = to_string(n);
    
    for (int i = s.length() - 1; i >= 0; i--) {
        string temp = s.substr(i, 1);
        answer.push_back(stoi(temp));
    }
    
    return answer;
}

첫번째로, to_string과 stoi 함수를 결합 + 반복문을 사용해서 풀이하는 방법. 이 경우에 substr() 함수를 이용해서 현재 위치에서 1글자를 잘라내어 temp에 추가하고, 그 temp를 stoi함수로 숫자로 변환한 뒤 배열에 밀어넣는 과정이 필요하다.

#include <vector>
#include <string>

using namespace std;

vector<int> solution(long long n) {
    vector<int> answer;
    string s = to_string(n);
    
    for (int i = s.length() - 1; i >= 0; i--) {
        answer.push_back(s[i] - '0');
    }
    
    return answer;
}

두번째, 문자열의 특정 문자를 숫자 타입으로 변환할 때, '0'을 빼주면 아스키코드 값을 기준으로 실제 정수값을 얻을 수 있다. 즉 굳이 stoi를 쓰지 않아도 그냥 문자열에서 -'0' 을 해주는 것 만으로도 알아서 실제 정수값으로 바꿔준다. 이게 무슨말이냐.

아스키코드를 보면 기본적으로 숫자 형태의 문자들을 실제 정수값으로 저장해 놓은 것을 확인할 수 있다.

문자 '0'은 정수 48로 저장되어있고, 문자 '2'는 50으로 저장되어있는 식이다. 이렇게 해서 9까지 정수 1 단위로 저장해놓았다.

그래서 예를 들어, '2' - '0' 을 해주는 것 만으로도 컴퓨터 내부에서는 50 - 48 처럼 정수끼리의 연산을 통해 2라는 숫자값을 하는 것과 같다는 것이다. 결국 우리가 원하는 0에서 9 사이의 정수값만 남기게 할 수 있다. 잘 알아두자.

*그 외에 오늘 한 것*

[Text RPG 만들기]

1. 던전 탐험 시스템(eventRoll을 사용한 확률 분기, 기존의 몬스터를 활용한 강적 시스템)

2. 직업별 스킬(virtual 함수를 이용해서 player->useSkill()로 각 직업별 스킬 오버라이딩)

3. 연금술 공방(레시피 검색 및 재료 확인, 포션 제작, 포션 저장소 기능을 map을 사용해서 아이템을 관리하는 자료 구조 작성)

'게임 프로그래밍 공부 > C++ 코딩테스트' 카테고리의 다른 글

[C++ 코딩테스트 연습] 5. 시뮬레이션 (0)	2026.05.15
[C++ 코딩테스트 연습] 3. 재귀함수 (0)	2026.05.12
[C++ 코딩테스트 연습] 2. 입출력 데이터 다루기, STL 사용하기, 효율적인 코드 구현하기 (0)	2026.05.11
[C++ 코딩테스트 연습] 1. 필수 문법 (0)	2026.05.07

SMY TIL