[일본 기본정보기술자] 자료구조(データ構造)

일본에서 많이들 따라고 권장하는 자격증 '기본정보기술자'

한국 정처기보다 내용이 어렵지 않아보이지만 (솔직히 일본인들 이 시험을 공부하고 보나 궁금하다.)

쓰는 용어들이 달라서 참고서 1회독해서 내용 파악을 해 둘 필요가 있어보인다.

 

1. 큐 (キュー)

- 먼저 들어간 게 먼저 나옴. (교수님이 멘토스라고 설명했던 기억이 아직도 난다.)

  일본어로 先入れ先出し, FIFO(First-In First-out) 두 용어 다 쓰는 것 같다.

- enqueue(エンキュー)

  큐에 격납(格納)하는 조작

- dequeue(デキュー)

  큐에서 빼내는(取り出す) 조작

- 포인터 (ポインター)

맨 앞 데이터를 가르키는 front pointer & 맨 뒤 데이터를 가르키는 rear pointer

 

2.  스택 (スタック)

- 먼저 들어간 게 나중에 나옴. 

  일본어로 後入れ先出し, LIFO(Last-In Last-Out)

- 계산 도중 결과를 넣거나, 일시적 데이터를 보관하는데에 사용된다.

- 격납할때는 push, 빼낼때는 pop 

- 격납하는 장소를 스택포인터로 관리한다 SP(スタックポインター)

- push할 때는 SP-1 → SP

- pop할 때는 SP+1→ SP

 

3. 리스트 (リスト)

한국에서 배울때는 리스트, 연결리스트 따로 배운 것 같은데 여기서는 그냥 연결리스트부터 가르친다.

- セル(셀)단위로 연결되어있고, 셀은 데이터부와 포인터부로 이루어져있다.

- 이점 : 리스트 요소를 더하거나 뺄 때 데이터를 한 칸씩 밀지 않고(ずらす操作を行わなく) 빠르게 처리할 수 있다.

- 단점 : 특정 요소로 접근할 때는 포인터를 거슬러 올라가야하기 때문에(たどる) 늦어진다.

- 単方向リスト(단방향 리스트) : 포인터가 한 방향. head의 데이터부와,  마지막 요소의 포인터부는 NULL값.

- 双方向リスト(양방향 리스트) : 양방향 포인터

- 環状リスト(순환 리스트) : 한국어랑 똑같이 循環リスト라고도 부르는 것 같은데. 環状(환상) 이라는 단어도 알아둬야 할 듯 하다. 선두와 마지막을 연결하는 리스트로 단뱡향, 양방향이 있음.

 

3-1 리스트 포인터의 조작

- 삭제할 때 : A→B→C→D에서 C를 삭제할 때 B의 포인터를 D를 가르키게 조작한다.

- 격납할 때 : A→B→C→D에서 C와 D의 사이에 E를 넣을때, C의 포인터를 E를 가르키게 하고, E의 포인터를 D를 가르키게 한다.

 

3-2 배열을 사용하여 리스트를 실현해보자

- 배열을 사용한 리스트는 리스트의 요소를 일차원 배열의 연속영역에 저장하고,

포인터를 저장하는 또 다른 배열을 준비한다.

(그니까 배열을 두개 준비해서, 하나는 데이터 넣고 하나는 포인터 넣으라는 뜻)

- 이점 : 특정 요소에 접근할 때 위치를 알고있으면 인덱스를 직접 지정해서 접근하기 때문에 빠르다. 

- 단점 : 리스트 요소를 추가하거나 삭제할 때, 요소를 차례차례 넘겨 빈곳을 만들거나 채워야 하기 때문에 느리다.

 

 

이 자료구조 내용들은 '다음중 알맞는 설명은?' 이런 식으로 나오는 것 같다.