자료구조 문제 정리 (1) 배열, 리스트

1. 자료구조

• 선형구조 (배열, 리스트, 스택, 큐)
  
  • 데이터의 항목 사이의 관계가 1:1이며, 선후 관계가 명확한 1개의 선의 형태를 갖는 리스트 구조를 말한다.
  • 각 자료 항목 사이의 관계의 표현 방법과 항목의 입출력 방법에 따라 배열, 연결리스트, 스택, 큐, 데크로 나뉘어진다.
• 비선형 구조 (트리, 그래프)
  • 데이터의 항목 사이에 1:n 또는 n:m 관계를 갖는 그래프적 특성을 갖는 형태
  • 트리, 그래프가 속한다.
  • 그래프는 사이클을 허용하며 트리는 사이클을 허용하지 않는다

 

2. 알고리즘

 

컴퓨팅 사고에서 주어진 문제의 중요한 특징만으로

문제를 간결하게 재정의함으로써 문제 해결을 쉽게 하는 과정을 말한다.

알고리즘의 특성은 다음과 같다.

• 입력 : 외부에서 제공되는 자료가 있을 수 있다(0개 이상의 입력이 존재)
• 출력 : 반드시 한 개 이상의 결과를 생성한다
• 명확성 : 각 명령들은 명확하고, 모호하지 않아야 한다
• 유한성 : 어느 한정된 수의 단계 뒤에는 반드시 종료한다
• 실제성 : 알고리즘의 모든 명령은 실행 가능하다
• 유효성 : 원칙적으로 모든 명령들은 종이와 연필만으로 수행될 수 있게 기본적이어야 한다.

알고리즘은 어떤 특정 프로그래밍 언어의 특성에 관계없이 본래의 기능을 잘 수행할 수 있도록 기술할 수 있어야 한다.

 

 

3. 시간 복잡도
위에서부터 좋음 -> 나쁨 순서

Best	O(1)
	O(logN)
	O(N)
	O(nlogn)
	O(N^2)
	O(N^3)
	O(2^N)
	O(N!)
Worst	O(N^n)

 

4. 배열 

배열은 공통 성질을 갖는 순서화 된 데이터 항목들의 집합으로

한 배열 내의 각 데이터 항목은 배열 첨자(인덱스)에 의해 구분되어진다. 

배열의 접근 방법은 직접 접근(임의 접근) 이다.

정렬된 데이터를 배열에 저장하여 이진탐색을 하면 탐색의 시간 복잡도는 O(logn)을 보장한다.

 

 

[행우선, 열우선 문제]

(1)

배열 A(2:4, 3:7, 2:5)의 원소 개수로 옳은 것은? (단, 배열의 첫번째 원소는 A(2,3,2)이며, 마지막 원소는 A(4,7,5)이다)

 

배열의 시작 첨자와 끝 첨자를 지정할 수 있다.

3차원 배열 A(2:4, 3:7, 2:5)이므로 면 수는 2면에서 4면이므로 전체 3면, 행 수는 3행에서 7행이므로 전체 5행,

열 수는 2열에서 5열까지이므로 전체 4열이다. 

3 X 5 X 4 = 60

배열의 전체 크기는 5행 4열인 면이 총 세 개이므로 저장할 수 있는 원소의 개수는 전체 60개이다.

배열의 가장 큰 장점은 주소에 의해 직접 접근이 가능하며 저장과 탐색이 효율적이다.

 

(2)

int a[5][6]으로 선언되는 2차원 배열이 열우선 순서로 저장되고 a[0][0]의 주소가 1000이며 정수의 크기가 4byte일때

a[2][3]의 주소는?

 

주소 구하는 법

배열 위치 (i,j)

배열 크기 (K,L)

• 행 우선 : i*L+j
• 열 우선 : j*K+i

열 우선 순위일때 a[2][3]의 주소는 3*5+2=17 X 4byte(정수 크기) = 68

a[0][0]은 1000이므로 1000+68=1068이다

 

(3)

char A[20][30]의 원소 A[8][7]의 주소를 행 우선 순서(row-major)와 열 우선 순서(column-major)로 계산한다면?

(단, 첫번째 원소 A[0][0]의 주소는 1000이고 하나의 원소는 1byte를 차지한다.

 

위치는 A[8][7]

크기는 A[20][30]

행 우선 : 8*30+7 = 247 + 1000 = 1247

열 우선 : 7*20+8 = 148 + 1000 = 1148

 

(4)

행 우선으로 저장되는 3차원 배열 a[4][5][3]이 있을 때, 이 배열의 첫번째 원소 a[0][0][0]의 주소를 a라고 하면,

a[2][3][1]의 주소를 a+i로 표현했을 때 i의 값은?

 

행 우선 순서이므로 배열 a[4][5][3]내의 a[2][3][1]의 주소는 다음과 같다.

a[2][3][1]의 주소 = a+(2-0) (한 면의 요소의 개수) + (3-0)(열의 개수) + (1-0) = a + 2(5*3) + 3(3) + 1 = a+40

즉 i는 40이다.

 

5. 연결리스트

 

#자기참조 구조체 #동적 메모리 할당 #포인터 #삽입 삭제가 쉬움

구현 : 연결리스트를 구현할 경우 자기참조 구조체에 의해 데이터와 포인터를 저장하는 노드를 구성해야 한다.

연결리스트는 배열과 달리 동적 메모리 할당되므로 공간이 부족하여 저장되지 않는 경우는 거의 없다.

또한 배열은 다음 데이터를 인덱스를 증가시켜 접근하지만 연결리스트는 포인터로 접근하므로 연속된 기억 공간이 아닌 아무 곳에나 저장할 수 있다(포인터로 연결시켜주면 됨)

• 삽입이나 삭제 시 선행노드(삽입, 삭제 직전 노드)를 찾기 위해 또 다른 검색이 수행되므로 O(N)의 시간을 소요하지만 선행노드를 알 경우에는 O(1)의 시간복잡도를 갖는다.
• 임의의 노드를 검색하는데 걸리는 시간은 O(N)이다.
• 검색에는 시간이 오래 걸리지만 삽입과 삭제는 빠르다
• 다음 원소의 장소나 주소를 저장하기 위한 기억 공간이 추가로 필요하다

(1)

배열와 연결리스트에 대한 차이

• 연결리스트는 배열에 비하여 희소행렬을 표현하는데 효율적이다 (희소행렬 : 행렬 값 중 0이 많은 행렬)
• 연결리스트에 비하여 배열은 원소를 임의의 위치에 삽입하는 비용이 크다
• 연결리스트에 비하여 배열은 임의의 위치에 있는 원소에 접근할 때 효율적이다
• n개의 원소를 관리할 때, 연결리스트가 n 크기의 배열보다 메모리 사용량이 더 크다

[리스트 삽입, 삭제 문제]

(2)

자료들이 단순 연결리스트에 다음과 같이 구성되어 있을 때, 자료 B를 삭제한 후 변경된 내용으로 옳은 것은?

메모리 주소	data	link
2000	A	2020
2010	B	2030
2020	C	2010
2030	D	0

 

C의 link - 2030

 

그림과 같은 단순 연결리스트에서 B를 삭제한 경우에는 

2010을 가리키고 있던 C의 link가 2030으로 변경된다.

 

(3)

연결리스트의 preNode 노드와 그 다음 노드 사이에 새로운 newNode 노드를 삽입하려고 할 때

사용하는 명령문은?

 

새로운 노드 newNode를 삽입하기 위해 첫번째로 preNode의 Link 값을 newNode의 Link에 삽입한다.

newNode -> link = preNode -> link;

두번째로 proNode의 Link에 새로운 노드의 주소인 newNode를 삽입한다.

preNode -> link = newNode;

 

(4)

두 개의 노드 first, second가 연결되었다고 가정하고, 위의 코드를 참조하여 노드 tmp를 노드 first와 second 사이에

삽입하고자 할때, 프로그램의 코드는?

 

노드 tmp를 first 뒤로 삽입하고자 한다면 first -> tmp -> second가 된다.

tmp.link = first.link; //tmp의 link에 first의 link 내용을 저장한다. second 노드의 주소이다

first.link = &tmp; //선행 노드인 first의 link에는 새로 삽입되는 tmp 노드의 주소를 저장한다.

 

(5)

단순 연결 리스트에서 특정 노드 p 바로 뒤에 새로운 노드 new를 삽입하기 위한 연산의 의사코드는?

 

특정 노드 p 바로 뒤에 새로운 노드 new를 삽입하기 위한 알고리즘은 다음과 같다.

new가 가리키는 노드의 링크에 p가 가리키는 노드의 링크를 복사한다.

new.next <- p.next;

이후 p가 가리키는 노드의 링크에 new의 값을 주어 새롭게 삽입되는 노드의 주소를 저장한다.

p.next <- new;

 

(6)

원형 연결 리스트에 x값을 갖는 노드 new를 pre가 가리키는 노드의 다음 노드로 삽입하고자 할 때 의사코드는?

new.link <- pre.link; //pre의 link를 new의 link에 복사한다

pre.link <- new; //pre의 link에 새로 삽입되는 노드의 주소인 new를 복사한다

 

(7) 이중연결리스트 삭제