C로 학습한 배열은 사실상 C++와 큰 차이가 없다.
아니, 정확하게 이야기하면 입출력 방식을 제외하면 아예 차이가 없다.
이번 포스팅에서는 배열을 왜 사용해야 하는가? 배열의 한계점은 무엇인가?에 대해서 살펴보고, 각각 1차원, 2차원 배열을 활용한 간단한 문제들을
백준 온라인 저지에서 가져와 해결해본다.
배열을 사용하는 이유
배열은 데이터를 순차적으로 저장하는 자료구조에 해당한다.
지금까지는 임의로 데이터를 하나씩 받아와서 처리하는 행위들을 해왔는데 사용자로부터 여러 개의 데이터를 입력 받는 경우를 생각해보면 필요성에 대해서는 납득이 될 듯 하다.
배열을 사용하는 이유는 다음과 같다
1. 데이터 저장
배열은 연속된 메모리 공간에 데이터를 저장한다. 이로 인해 데이터에 접근하기 위해 메모리 주소만으로도 빠르게 데이터에 접근할 수 있다.
알다시피, 우리가 학습할 문자열 역시 C에서 char 형의 문자로 구성된 배열이고, 아래의 그림과 함께 학습했던 내용을 상기해보면 어떤 의미인지 쉽게 이해할 수 있다.
2. 색인 접근의 효율성
배열은 Index라는 색인을 활용하여 원하는 곳에 있는 원소에 효율적으로 접근할 수 있다는 장점이 있다. 1번과 사실 연장선에 있는 이야기인데, 데이터들이 메모리 기준으로 떨어져서 배치되는 것이 아니라 연속적으로 배치되어 있기에 단순하게 원하는 인덱스(용어에 익숙해지자!)에 쉽게 접근할 수 있다.
3. 자료구조의 BASE
공부에는 흐름이 있다.
배열을 가장 먼저 학습을 했고, 아직 학습하지 않은 수많은 자료구조들이 존재한다. (스택, 큐 , 링크드 리스트, 벡터, 그래프, 트리 등)
그래프는 나중에 학습하지만 2차원 배열의 구조를 매우 적극적으로 활용해야하고, 링크드 리스트는 대놓고 배열을 변형한 구조에 해당한다. 스택과 큐 역시 배열과 큰 차이가 없을 뿐더러 벡터 역시 인덱스로 참조가 가능한 배열과 많은 부분에서 유사하다. (당연히 이해가 안될거고 그냥 그런가보다 하고 넘어가면 된다.)
혹시 벡터 자료구조에 대해서 살펴보기를 원한다면 다음 Reference를 참고하길 바란다. https://velog.io/@jameschoi15/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-Vector
배열의 아쉬운 점
위에서 언급했듯이, 자료구조의 베이스가 된다는 것은 다른 자료구조들이 필요하다는 것이고 그 말은 즉슨, 배열이 언제나 유리하지는 않다는 것이다.
가장 아쉬운 점 2개는 다음과 같다.
1. 배열의 크기를 먼저 선언해야 한다.
우선, 일반적으로 배열을 선언하는 과정을 살펴보자.
#include <iostream>
using namespace std;
int main()
{
int arr[10];
return 0;
}위와 같이 arr이라는 배열을 선언함과 동시에 10이라는 사이즈를 미리 설정해둔 상태로 선언을 해야한다.
그런데 생각해보면 때로는, 내가 어느 정도 크기의 배열이 필요한지는 모를 때가 있을 수 있다. (아니, 알고리즘 문제를 풀다보면 대부분이 그렇다)
간단한 예시로, 사용자에게 정수 n을 입력받고, n사이즈의 배열을 만드는 코드를 작성해보자.
#include <iostream>
using namespace std;
int main()
{
int n;
cin >> n;
int arr[n];
return 0;
}위의 코드는 아무 문제가 없어 보인다. 사용자로부터 정수를 입력받아서 그만큼의 변수를 arr이라는 배열의 사이즈로 설정을 해줬다.
하지만 아래와 같은 오류가 발생한다.
식에 상수값이 있어야한다. 즉, arr[n]이 불가능하다는 것이다.
(조금 어려운 이야기인데, 컴파일러에 따라서 이게 되는 것도 있고, 안되는 것도 있다. 그냥 안된다고 생각하면 편하다.)
그럼 다음과 같은 문제를 어떻게 해결해야할까?
1> 배열의 사이즈를 최대한으로 설정한다.
강력하게 추천한다.
무슨 이야기인지 2차원 배열의 선언과 활용 Part에서 설명한다.
2> 배열을 동적으로 할당한다.
1학기에 C프로그래밍 수업에서 진도가 밀려서 덜 나간 부분에 해당하는데 상당히 까다롭다. 필자는 잘 사용하지 않지만, 필요한 사람은 다음 Reference를 참고하길 바란다. (포인터 개념 익숙하지 않으면 정신 건강을 위해 보지 않기를 강력하게 추천한다.)
https://coding-factory.tistory.com/672
3> 배열을 사용하지 않는다.
강력하게 추천한다.
반드시 배열을 사용할 필요는 없다. 필자는 위에서 언급한 벡터를 자주 사용한다.
Vector의 특징상 사이즈를 미리 선언할 필요가 없고 필요할 때마다 자료들을 처리하는 구조라 이 난점을 극복한다.
2. 배열의 삽입과 삭제가 매우 복잡하다.
다음 상황을 가정해보자.
12345의 5개의 정수가 담긴 배열에서 2와 3사이에 6이라는 데이터를 넣고자 하면, 3부터 5까지의 자료는 모두 뒤로 한칸씩 밀어야하므로 이를 코드로 직접 구현하고자 한다면 상당히 복잡하다.
마찬가지로, 12345에서 3을 지운다고 하면 45는 앞으로 한칸씩 당겨야하므로 꽤나 귀찮은 코드를 작성해야한다.
위의 그림을 참고하면 되고, 이는 그럼 어떻게 해결하는가?
다른 자료구조들을 사용하면 된다..!!!
(사실 자료구조 공부를 깊이 하면서 느끼는 건데, 각각의 자료구조들은 크게 어렵지 않다는 생각이 들다가도, 언제 어떤 자료구조를 사용해야할까가 가장 큰 고민거리인 듯하다.)
1차원 배열의 선언과 활용
다음 문제를 해결해보자.
(너무 쉬운 문제는 재미가 없으니 조금 고민할만한 문제로 가져왔다.)
시간이 된다면 먼저 풀어보고 코드를 살펴봐도 좋다.
https://www.acmicpc.net/problem/3052
#include <iostream>
using namespace std;
void test()
{
int num[42];
//배열 초기화해줌.
for (int i = 0; i < 42; i++)
{
num[i] = 0;
}
int input = 10;
while (input--)
{
int x;
cin >> x;
num[x % 42] = num[x % 42] + 1;
}
int result = 0;
for (int i = 0; i < 42; i++)
{
if (num[i] != 0)
result += 1;
}
cout << result << endl;
}
int main()
{
test();
return 0;
}나머지라고 해봐야 0부터 41까지 42개이므로 각각의 나머지를 인덱스로 갖는 배열을 하나 선언했다.
위에서 언급한것처럼 배열 선언 시 사이즈는 상수로!!!
10개의 정수들을 입력받을 때마다 각각의 인덱스에 나머지로 참조하여 값을 키워주는 생각이 필요했다.
PS ) 여기서 하나 중요한 포인트가 있어서 체크하고 넘어간다.
int input = 10;
while (input--)
{
int x;
cin >> x;
num[x % 42] = num[x % 42] + 1;
}백준을 풀다보면 사용자로부터 특정한 수 만큼의 입력을 받아서 데이터를 처리해야 할 때가 있는데 위에서 필자가 작성한 방법이 매우 편리하다.
while(input--)만 작성해주면 input이 10이었으므로 10번만큼 반복문 안에 있는 명령이 실행된다.
적극적으로 사용하길 바란다!!!
2차원 배열의 선언과 활용
2차원 배열에서는 행과 열이라는 개념이 등장한다.
(행렬에 대해서는 선형대수에서 집중적으로 다룸)
위 그림을 살펴보면 1행/1열이 시작으로 주어지지만 실제로는 인덱스 기준으로 코딩을 진행하기에 a[0][0]으로 참조하면 3이 나오게 된다.
a[1][2]에서 순서대로 2행 3열(그림 기준)을 의미한다는 점 역시 반드시 알고 있어야한다. (행렬을 입에 붙이면 당연히 행이 먼저)
다음 문제를 해결해보자.
시간이 된다면 먼저 풀어보고 코드를 살펴봐도 좋다.
https://www.acmicpc.net/problem/2738
#include <iostream>
#include <algorithm>
#include <stack>
#include <queue>
#include <string>
#include <cmath>
using namespace std;
void test2()
{
int n, m;
cin >> n >> m;
int first[101][101];
int second[101][101];
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
cin >> first[i][j];
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
cin >> second[i][j];
}
//cout << n << m << endl;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
cout << first[i][j]+second[i][j] << " ";
cout << endl;
}
}
int main() {
test2();
return 0;
}배열의 사이즈 설정 관련 문제에 직면하게 된다.
사용자로부터 행과 열을 입력을 받기는 하지만, 이를 직접적으로 배열을 선언하는데 활용할 수는 없기에 위에서 언급한 솔루션 중 첫번째를 사용해야 한다.
입력 문구를 읽어보면 사용자로부터 입력받는 수가 커봐야 100이라는 사실을 알 수 있다.
이를 통해서 위에서처럼 넉넉하게 101개 101개의 배열을 만들어준 것이다.
물론, 우리가 예시에 나온 것처럼 3과 3을 입력받게 되면 남은 97개의 행과 열에는 쓰레기값이 들어있게 되어 메모리 낭비가 발생하지만, 이는 문제의 조건 상 어쩔 수 없는 셈이다.
