[자료구조 기초 - 배열 리스트(ArrayList)]백준 제로(10773번) 풀이 (C++/Python)
데이터를 저장할 때 다양한 자료구조를 활용합니다.
이 중 저번에 정적 배열(Array)을 간단하게 확인해봤습니다.
로우 레벨에서 봐도 정적 배열은 메모리 내부에서 임의의 주소값에 정해진 크기대로 메모리 할당해서 그 안에 값 조회 및 수정을 할 수 있었습니다.
그런데 정적 배열의 단점은 추가 및 삭제가 안 됩니다.
그래서 이번엔 다른 자료 구조를 들고 왔습니다.
리스트(List)는 기존 정적 배열에서 메모리 재할당을 통해 추가 및 삭제할 수 있는 자료 구조입니다.
리스트는 ArrayList와 LinkedList가 있는데 여기서는 ArrayList만 설명하겠습니다.
왜냐면 LinkedList 이것도 결국 ArrayList 2개로 비슷하게 구현할 수 있거든요.
물론 로우 레벨로 보면 LinkedList와 ArrayList는 엄연히 다르며 상황에 따라 LinkedList로 구현해야 하나
요즘 메모리 자체가 워낙 용량이 커서 그냥 깡으로 ArrayList 2개만으로도 LinkedList를 비슷하게 구현할 수 있습니다.
표를 통해 ArrayList를 직접 확인해보시죠!
| 0xA0 | 0xA1 | 0xA2 | 0xA3 | 0xA4 | 0xA5 | 0xA6 | 0xA7 | 0xA8 | 0xA9 |
| 5 |
1번째 행은 주소값(address), 2번째 행은 원소값(value)입니다.
메모리 내부는 대충 이렇게 되어 있다고 가정합니다.(실제 메모리 구조와 다릅니다. 편의상 이렇게 만든 것입니다.)
여기서 제가 정적 배열 하나를 선언합니다, 그 배열명의 이름은 list라고 가정하겠습니다.
그리고 0xA4 부분은 "int a = 5;"로 되어 있는 부분입니다.
이미 할당된 부분이라서 여기에 배열 list를 할당하면 안 됩니다.
| 0xA0 | 0xA1 | 0xA2 | 0xA3 | 0xA4 | 0xA5 | 0xA6 | 0xA7 | 0xA8 | 0xA9 |
| 5 |
해당 배열의 초기 주소값은 0xA2이며 초기 배열의 크기는 2로 할당했습니다.
그리고 초기 포인터는 0xA2입니다.
포인터는 정말 쉽게 말하자면 "현재 주소값을 가리키는 마우스 커서"라고 생각하시면 그나마 이해하기 쉬울 것입니다.
여기에 값을 적어야겠죠?
처음에는 3을 넣어주세요.
| 0xA0 | 0xA1 | 0xA2 | 0xA3 | 0xA4 | 0xA5 | 0xA6 | 0xA7 | 0xA8 | 0xA9 |
| 3 | 5 |
짜잔! 주소값 0xA2에 원소값 3이 추가되었습니다.
추가되고 나면 다음 작업을 하기 전에 포인터를 오른쪽으로 옮겨야 합니다.
| 0xA0 | 0xA1 | 0xA2 | 0xA3 | 0xA4 | 0xA5 | 0xA6 | 0xA7 | 0xA8 | 0xA9 |
| 3 | 5 |
현재 포인터는 0xA3입니다.
이렇게 해서 현재 리스트의 크기는 1이 됩니다.
이제 해당 포인터가 가리키는 부분에 6을 대입해보겠습니다.
| 0xA0 | 0xA1 | 0xA2 | 0xA3 | 0xA4 | 0xA5 | 0xA6 | 0xA7 | 0xA8 | 0xA9 |
| 3 | 6 | 5 |
자, 주소값 0xA3의 value에 6을 대입하는데 성공했습니다.
추가 작업 완료할려면 포인터를 옮겨줘야 합니다.
| 0xA0 | 0xA1 | 0xA2 | 0xA3 | 0xA4 | 0xA5 | 0xA6 | 0xA7 | 0xA8 | 0xA9 |
| 3 | 6 | 5 |
이것을 코드로 표현하면 int list = {3, 6};입니다.
리스트의 크기가 2가 되었습니다.
그러면 현재 포인터(0xA4) 부분에 값을 대입할 수 있을까요?
저는 이 자리에 9를 대입하고 싶거든요.
로우 레벨에서 대입은 가능합니다.
하지만 만약 int a의 주소값이 0xA4이고 이미 a = 5인 상태로 되어 9로 바꾸면 나중에 printf("%d", a);에서 5가 아닌 9가 출력되는 문제가 발생합니다.
이것은 실제로 C/C++에서 껶고 있는 메모리 보안 문제와 연결됩니다.
이게 왜 메모리 보안 문제로 바뀌냐고요?
만약 0xA4 부분에 "int important_price = 100000000;"이 저장되어 있습니다.
"나중에 받아야 할 돈이 1억원이다"인데 어떤 악질적인 해커가 이 부분을 건들여서 "int important_price = 9;"으로 만든다면?
그러면 나중에 받아야 할 돈이 9원이 되는 진짜 큰일난 결과가 나옵니다.
그래서 C/C++ 말고 Java나 Python 등 자동으로 메모리 할당해주는 프로그래밍 언어에서는 index 범위를 체크해서 만약 범위를 넘어서면 컴파일 과정에서 Exception 혹은 Error를 발생시켜 메모리 보안 문제를 어느 정도 해결해줍니다.
그러면 로우 레벨에서는 이것을 어떻게 해결해야 할까요?
바로 메모리 재할당을 통해 이미 저장된 a의 주소값을 임의의 장소로 변경하고 그 자리에 list 배열의 메모리를 해제하고 크기 4의 list 배열로 재할당합니다.
그런데 재할당하는 과정을 보면 이미 0xA4 부분에 int a = 5;가 자리 잡고 있네요?
그러면 list의 주소값 자체를 바꿔서 다른 곳에 할당해야 합니다.
| 0xA0 | 0xA1 | 0xA2 | 0xA3 | 0xA4 | 0xA5 | 0xA6 | 0xA7 | 0xA8 | 0xA9 |
| 5 | 3 | 6 |
바로 이렇게 말이죠.
기존 list 주소값이 0xA2인데 이것을 통째로 메모리 해제하고 0xA5 자리에 새롭게 재할당합니다.
재할당 하기 전 리스트의 크기가 2이므로 현재 포인터는 0xA7입니다.
여기서 한 칸 움직이면 안전하게 배열 안에서 값을 넣을 수 있어요.
그 자리에 9를 넣어볼게요.
| 0xA0 | 0xA1 | 0xA2 | 0xA3 | 0xA4 | 0xA5 | 0xA6 | 0xA7 | 0xA8 | 0xA9 |
| 5 | 3 | 6 | 9 |
이제 리스트의 크기는 3이 되었습니다.
그러면 이번엔 원소 삭제를 어떻게 해야 할까요?
메모리 내부에는 0xA7 부분이 반드시 있어야 해서 0xA7 부분을 물리적으로 못 없애는데 말이죠.
여기서 "인간은 컴퓨터 내부를 볼 수 없다"를 활용하여 속임수(?)를 하나 부릴 것입니다.
그냥 포인터를 왼쪽으로 옮기면 그만입니다.
| 0xA0 | 0xA1 | 0xA2 | 0xA3 | 0xA4 | 0xA5 | 0xA6 | 0xA7 | 0xA8 | 0xA9 |
| 5 | 3 | 6 | 9 |
바로 이렇게 말이죠.
이렇게 해서 만약 나머지 원소들을 모두 제거하면 포인터는 어떻게 될까요?
그러면 포인터는 0xA5가 되겠죠.
이러면 리스트의 크기는 0xA5 - 0xA5 = 0이 되어서 리스트 크기를 측정하기도 편안합니다.
하지만 여기서는 9 원소만 삭제 작업(실제 컴퓨터 내부에서는 그저 포인터 하나만 옮김)을 진행하여
현재 리스트의 크기는 0xA7 - 0xA5 = 2가 됩니다.
이제 다음으로 {3, 6} 부분에 2를 추가해볼까요?
0xA7 부분에 9를 2로 수정해서 포인터를 한 칸 옮기면 마치 사람 입장에서 보면 "{3, 6}에서 {3, 6, 2}로 추가되었구나!"라고 느끼지만 실제 컴퓨터 내부에서는 그저 9에서 2로 수정하고 포인터 한 칸 옮겼을 뿐입니다.
| 0xA0 | 0xA1 | 0xA2 | 0xA3 | 0xA4 | 0xA5 | 0xA6 | 0xA7 | 0xA8 | 0xA9 |
| 5 | 3 | 6 | 2 |
그런데 어떻게 리스트의 크기를 구할 수 있을까요?
0xA0 부분에 list의 주소값, 0xA1 부분에 현재 포인터 주소값을 저장해서 *(0xA1) - *(0xA0) 연산하면 되거든요.
| 0xA0 | 0xA1 | 0xA2 | 0xA3 | 0xA4 | 0xA5 | 0xA6 | 0xA7 | 0xA8 | 0xA9 |
| 0xA5 | 0xA8 | 5 | 3 | 6 | 2 |
이렇게 말이죠. 그러면 (주소값 0xA1의 value) - (주소값 0xA0의 value) = 0xA8 - 0xA5 = 3으로 리스트의 크기가 나와요!
만약 현재 포인터가 0xA8 -> 0xA6로 바뀐다면 리스트의 크기는 1이 되겠죠?
아 맞다. 가장 중요한 것을 빼먹을 뻔했네요.
지금 value 부분에 비어있는 칸들 있잖아요?
사실 진짜 비어있는 것이 아닌 임의의 값(쓰레기 값)들이 들어있는 상태입니다.
그래서 printf("%d", 0xA8); 형식으로 하면 102937460 등으로 쓰레기 값이 출력됩니다.
이 부분은 이전에 정적 배열(Array)에서 이미 다루었으니 복습 개념에서 한 번 더 알려드립니다.
어쨋거나 {3, 6, 2}에 이번에는 4를 넣겠습니다.
| 0xA0 | 0xA1 | 0xA2 | 0xA3 | 0xA4 | 0xA5 | 0xA6 | 0xA7 | 0xA8 | 0xA9 |
| 0xA5 | 0xA9 | 5 | 3 | 6 | 2 | 4 |
이렇게 해서 리스트는 {3, 6, 2, 4}가 됩니다.
크기는 0xA9 - 0xA5 = 4가 되고요.
마지막으로 0xA7 부분(index 2)에 있는 값을 수정할려고 합니다.
이 때 다른 포인터가 등장하게 됩니다.
우선 다른 포인터 부분을 보라색으로 표시합니다.
이 때 포인터 계산 과정은 *(0xA0) + index = 0xA5 + 2 = 0xA7이 됩니다.
| 0xA0 | 0xA1 | 0xA2 | 0xA3 | 0xA4 | 0xA5 | 0xA6 | 0xA7 | 0xA8 | 0xA9 |
| 0xA5 | 0xA9 | 5 | 3 | 6 | 2 | 4 |
해당 포인터의 value를 1로 수정하겠습니다.
| 0xA0 | 0xA1 | 0xA2 | 0xA3 | 0xA4 | 0xA5 | 0xA6 | 0xA7 | 0xA8 | 0xA9 |
| 0xA5 | 0xA9 | 5 | 3 | 6 | 1 | 4 |
수정이 끝나고 하면 해당 포인터는 없어지고 *(0xA0)과 *(0xA1) 값은 변경되지 않았으므로 여전히 리스트의 크기는 4입니다.
이제 이것을 C언어로 구현해보겠습니다.
#include <stdio.h>
#include <stdlib.h>
// ArrayList 구조체 정의
typedef struct {
int* data;
int size; // 현재 저장된 데이터의 개수 (논리적 크기)
int capacity; // 할당된 전체 메모리 용량 (물리적 크기)
} ArrayList;
// 1. 초기화
void initList(ArrayList* list, int initCapacity) {
list->data = (int*)malloc(initCapacity * sizeof(int));
list->size = 0; // 데이터가 하나도 없으므로 0부터 시작합니다.
list->capacity = initCapacity;
}
// 2. 맨 뒤에 추가 (append)
void append(ArrayList* list, int value) {
// 현재 개수가 용량과 같아지면, 집을 2배로 넓힙니다.
if (list->size >= list->capacity) {
list->capacity *= 2;
list->data = (int*)realloc(list->data, list->capacity * sizeof(int));
}
// size는 현재 개수이자, 다음에 들어갈 'index' 번호와 같습니다.
list->data[list->size] = value;
list->size++; // 데이터를 넣었으니 개수를 하나 늘립니다.
}
// 3. 맨 뒤 데이터 삭제 (pop)
void pop(ArrayList* list) {
// 실제로 메모리를 지울 필요 없이, "여기까지만 데이터야"라고
// 경계선(size)만 한 칸 안으로 당기면 됩니다.
if (list->size > 0) list->size--;
}
// 4. 조회 (get)
int get(ArrayList* list, int index) {
// (보통 여기서 index < list->size 인지 체크하는 안전장치를 둡니다)
return list->data[index];
}
// 5. 수정 (set)
void set(ArrayList* list, int index, int value) {
list->data[index] = value;
}
// 전체 출력 함수
void printList(ArrayList* list) {
printf("현재 리스트: [");
for (int i = 0; i < list->size; i++) {
printf("%d", get(list, i));
if (i < list->size - 1) printf(", ");
}
printf("]\n");
}
int main() {
int a = 5; // 이미 자리 잡은 변수
ArrayList list;
initList(&list, 2);
printf("=== 1단계 : 3, 6, 9 삽입 ===\n");
append(&list, 3);
append(&list, 6);
append(&list, 9);
printList(&list);
printf("\n=== 2단계 : 맨 뒤(9) 제거 ===\n");
pop(&list);
printList(&list);
printf("\n=== 3단계 : 2, 4 삽입 ===\n");
append(&list, 2);
append(&list, 4);
printList(&list);
printf("\n=== 4단계 : 인덱스 2의 값을 1로 수정 ===\n");
set(&list, 2, 1);
printList(&list);
// 다 쓴 메모리는 반드시 반환!
free(list.data);
return 0;
}뭔가 좀 많이 어려워 보이죠?
하지만 이건 사실 지금까지 했던 과정을 C언어 소스 코드로 구현한 것입니다.
출력 결과를 확인해볼까요?
아주 잘 나옵니다.
이것이 바로 C언어로 ArrayList를 구현하는 방법입니다.
"그러면 ArrayList를 일일히 구현해야 하나요?"라고 물어볼 수 있는데 걱정 마십시오.
C++에서는 <vector> 혹은 <list>라는 STL(표준 탬플릿 라이브러리)가 있어서 굳이 일일히 구현할 필요 없이 바로 구할 수 있거든요.
여기서는 간단하게 <vector>로 위 C언어와 동일한 논리를 가진 C++ 소스 코드를 만들어 보겠습니다.
#include <iostream>
#include <vector>
using namespace std;
// 편의를 위한 전체 출력 함수 (get 메서드 대신 인덱스 [] 직접 사용)
void printList(const vector<int>& list) {
cout << "현재 리스트: [";
for (int i = 0; i < list.size(); i++) {
cout << list[i];
if (i < list.size() - 1) cout << ", ";
}
cout << "]\n";
}
int main() {
int a = 5; // 이미 자리 잡은 변수 (C++ vector는 알아서 안전하게 피해갑니다!)
// 1. 초기화
// C언어의 구조체 생성 및 malloc(initCapacity)이 단 한 줄로 끝납니다.
vector<int> list;
list.reserve(2); // 초기 용량(capacity)을 2로 설정 (생략해도 무방함)
// 2. 3, 6, 9 삽입 후 출력
cout << "=== 1단계 : 3, 6, 9 삽입 ===\n";
list.push_back(3); // C언어의 append() 역할 + 메모리가 꽉 차면 알아서 realloc!
list.push_back(6);
list.push_back(9);
printList(list);
// 3. 맨 뒤 9 제거 후 출력
cout << "\n=== 2단계 : 맨 뒤(9) 제거 ===\n";
list.pop_back(); // C언어의 pop() 역할 (알아서 size를 1 줄여줍니다)
printList(list);
// 4. 2, 4 삽입 후 출력
cout << "\n=== 3단계 : 2, 4 삽입 ===\n";
list.push_back(2);
list.push_back(4);
printList(list);
// 5. 인덱스 2의 값을 1로 수정 후 출력
cout << "\n=== 4단계 : 인덱스 2의 값을 1로 수정 ===\n";
list[2] = 1; // C언어의 set() 역할 (배열처럼 직관적으로 접근 가능)
printList(list);
// 메모리 해제(free)는 어디 갔냐고요?
// main 함수가 끝날 때 vector가 알아서 쓰레기통(Destructor)에 버려줍니다!
return 0;
}복잡한 포인터와 구조체가 사라졌습니다!
사실 list.reserve()는 생략해도 됩니다. 어차피 C++의 <vector> 라이브러리는 메모리 할당을 알아서 해주기 때문입니다.
C++에서 원소를 삽입할려면 push_back(), 원소를 제거할려면 pop_back()을 사용하면 됩니다.
그리고 C++에서는 조회 및 수정을 할려면 그냥 정적 배열처럼 list[index] 형식으로 간편하게 조회 및 수정할 수 있어요.
그리고 Python으로 넘어가면 훨씬 더 쉬워집니다.
# 파이썬은 배열 선언, 초기 용량 설정, 메모리 관리가 전혀 필요 없습니다.
# 심지어 전체 출력을 위한 별도의 함수(printList)를 만들 필요도 없습니다!
L:list = []
# 1. 3, 6, 9 삽입 후 출력
print("=== 1단계 : 3, 6, 9 삽입 ===")
L.append(3)
L.append(6)
L.append(9)
print(f"현재 리스트: {L}")
# 2. 맨 뒤 9 제거 후 출력
print("\n=== 2단계 : 맨 뒤(9) 제거 ===")
L.pop()
print(f"현재 리스트: {L}")
# 3. 2, 4 삽입 후 출력
print("\n=== 3단계 : 2, 4 삽입 ===")
L.append(2)
L.append(4)
print(f"현재 리스트: {L}")
# 4. 인덱스 2의 값을 1로 수정 후 출력
print("\n=== 4단계 : 인덱스 2의 값을 1로 수정 ===")
L[2] = 1
print(f"현재 리스트: {L}")
# 프로그램이 종료되면 파이썬의 가비지 컬렉터(Garbage Collector)가
# 알아서 메모리를 청소해주므로 free() 같은 작업도 필요 없습니다.ArrayList는 정말 자주 사용하는 자료 구조입니다.
수많은 자료들을 ArrayList에 다 저장해서 훗날 나올 수많은 알고리즘을 사용하는데 ArrayList가 무조건 들어갑니다.
특히 Python에서는 ArrayList가 기본 자료형으로 채택되어 있어 더더욱 중요합니다.
이제 ArrayList를 활용하여 백준 문제를 해결해보겠습니다.
문제 : 제로(10773번)(Silver IV)
문제 링크 : https://www.acmicpc.net/problem/10773
출처 : Baekjoon Online Judge
이 때까지 브론즈 문제들만 해결하다가 갑자기 실버 문제가 나와서 당황했죠?
하지만 겁 먹을 필요는 없습니다. 지금까지 게시글을 끝까지 읽었다면 이 문제는 별거 아니라는 것을 알 수 있습니다.
항상 크기가 0인 리스트(= 비어 있는 상태)로 시작해서 만약 입력한 숫자가 0이면 원소 제거, 0이 아니면 해당 숫자를 맨 끝에 추가하는 문제입니다.
그 뒤 모든 원소들을 조회해서 모든 원소들의 합을 구하면 됩니다. 참 쉽죠?
이제 C++와 Python으로 이 문제를 간단하게 해결하겠습니다.
[C++]
#include <bits/stdc++.h>
using namespace std;
vector<int> L;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
for(int i = 0; i < n; i++) {
int a;
cin >> a;
if(a != 0) L.push_back(a);
else L.pop_back();
}
int result = 0;
int size = L.size();
for(int i = 0; i < size; i++) result += L[i];
cout << result;
return 0;
}[Python]
import sys
input = sys.stdin.readline
N:int = int(input().rstrip())
L:list = []
for _ in range(N) :
K:int = int(input().rstrip())
if K != 0 :
L.append(K)
else :
L.pop()
print(sum(L))