자료구조 레포트 - 사용자가 입력한 수를 계속 더하는 프로그램을 배열과 연결리스트로 각각 구현할 경우의 장단점을

I. 서론

자료구조 과제를 하다 보면 같은 기능도 저장 방식을 바꾸는 순간 성격이 달라진다는 점이 재미있다. 사용자가 수를 계속 입력하고 프로그램이 그 값을 더하는 상황은 겉으로 매우 간단하다. 합계만 필요하다면 사실 매 입력값을 전부 저장하지 않고 현재 합만 갱신해도 된다. 그런데 과제에서 배열과 연결리스트를 비교하라는 요구가 붙는 순간 질문이 달라진다. 입력 기록을 보존한다고 할 때 어떤 구조가 더 자연스러운가, 입력 개수를 미리 알 수 있는가, 중간 값 조회가 필요한가, 메모리 사용과 구현 난이도는 어떤 차이가 있는가를 봐야 한다. 자료구조 선택은 이름을 외우는 문제가 아니라 프로그램에서 자주 일어나는 연산을 먼저 파악하고 그 연산에 맞는 비용을 비교하는 일이다.

II. 본론

1) 누적 입력 프로그램에서 필요한 연산부터 따져 보기

사용자가 수를 계속 넣는 프로그램의 기본 동작을 생각하면 입력값을 새로 저장하는 append 성격의 연산과 누적합 갱신이 반복된다. 예를 들어 사용자가 8, 3, 11을 차례로 입력하면 자료구조에는 세 값이 들어가고 별도의 sum 변수에는 22가 저장될 수 있다. 사용자가 종료 명령을 넣기 전까지 입력 개수가 몇 개인지 알 수 없다는 조건도 중요하다. 배열을 고정 크기로 만들면 어느 시점에 공간이 부족할 수 있고, 연결리스트는 노드를 하나씩 추가하며 길이를 늘릴 수 있다.

합계 계산만 놓고 보면 배열과 연결리스트 사이의 차이는 거의 사라진다. 새 숫자 x를 받을 때 sum에 x를 더하면 누적합 갱신은 상수 시간에 끝난다. 데이터 구조 전체를 매번 처음부터 다시 순회해 합을 계산할 이유가 없다. 자료구조 수업에서는 여기서 한 걸음 더 나가야 한다. 모든 입력값을 나중에 다시 출력하거나 특정 입력을 수정하거나 통계를 낼 가능성이 있다면 저장 방식이 중요해진다. 자료구조의 장단점은 "더하기" 자체보다 입력 기록을 어떻게 보관하고 다시 다루느냐에서 나타난다.

연산 빈도를 먼저 정리하면 선택 기준이 선명해진다. 입력은 계속 뒤에 붙는다. 중간 삽입과 삭제가 거의 없다면 배열은 꽤 유리하다. 반대로 프로그램이 중간 원소를 자주 넣거나 지우고, 저장 개수가 매우 불규칙하며 재할당을 피하고 싶다면 연결리스트가 편할 수 있다. 특정 번째 입력을 바로 조회하는 기능이 중요하면 배열이 압도적으로 편하다. 배열은 인덱스로 원하는 위치를 곧바로 계산할 수 있지만 연결리스트는 머리 노드에서 링크를 따라가야 한다.

OpenDSA 자료구조 교재는 배열 기반 리스트에서 직접 접근을 상수 시간으로 보고, 연결리스트의 위치 접근은 선형 시간으로 설명한다. 연결리스트는 알맞은 노드를 이미 가리키고 있을 때 삽입과 삭제를 상수 시간에 처리할 수 있지만, 배열 기반 리스트에서 중간 삽입과 삭제는 뒤 원소들을 옮겨야 하므로 선형 시간이 걸릴 수 있다. 이 비교를 누적 입력 프로그램에 그대로 적용하면 "어느 구조가 무조건 빠르다"는 답은 나오지 않는다. 프로그램이 실제로 무엇을 자주 하는지에 따라 유리한 구조가 달라진다.