제 1 강 : 자료 구조 개요 서울산업기술대학교 게임공학과김태환 C.P MSN/ Penguri Entertainment Co, Ltd. All rights reserved
우리는 어떤 것을 만드는 사람들인가 ? Penguri Entertainment Co, Ltd. All rights reserved
NC 소프트 2007 년 매출 2225 억, 당기순이익 450 억 액면가 : 500 원 주가 : 원 ( 액면가의 100 배 ) 시가총액 : 1 조 442 억원 Penguri Entertainment Co, Ltd. All rights reserved
결과물은 ? Penguri Entertainment Co, Ltd. All rights reserved 아이온 동영상 아이온 동영상
자료구조의 의미와 중요성을 알아본다. 자료구조에서 다루는 내용을 알아본다. 컴퓨터 내부의 2 진수 코드 체계를 알아본다. 자료의 형태에 따른 자료 표현 형식을 알아본다.
자료 구조를 왜 잘 알아야 하는가 ? 왜 프로그래밍을 배우는가 ? 비전은 ? 마스터 플랜은 ? Penguri Entertainment Co, Ltd. All rights reserved
프로그래머의 비전은 ? 주위의 인정 : ◦ 동네에서 인정받는 ◦ 서울시에서 수준급인 ◦ 한국에서 인정받는 ◦ 아시아에서 인정받는 ◦ 세계에서 인정받는 Penguri Entertainment Co, Ltd. All rights reserved
연봉은 1 억이상, 집은 ? Penguri Entertainment Co, Ltd. All rights reserved
자동차는 ? Penguri Entertainment Co, Ltd. All rights reserved
여자 친구는 ? Penguri Entertainment Co, Ltd. All rights reserved
여자 친구는 ? Penguri Entertainment Co, Ltd. All rights reserved
심지어 이런 것도 가능합니다. Penguri Entertainment Co, Ltd. All rights reserved
이런 것도 가능합니다. Penguri Entertainment Co, Ltd. All rights reserved
프로그래밍 속에는 이런 것이 있습니다 ! 돈이 있고 집이 있고 차가 있고 여자 친구가 있습니다. Penguri Entertainment Co, Ltd. All rights reserved
프로그래밍 속에는 이런 것이 있습니다 ! 돈이 있고 집이 있고 차가 있고 여자 친구가 있습니다. 오늘 죽어라 공부하면, 내일 아침에 타워팰리스 한채 가 들어오고, 외제차가 생기고, 귀여운 여자친구가 생깁니다. => 조금 힘들다고 밤에 잠이 올까요 ? Penguri Entertainment Co, Ltd. All rights reserved
자료구조 자료구조란 자료를 효율적으로 사용하기 위해서 자료의 특성에 따라서 분류하 여 구성하고 저장 및 처리하는 모든 작업 [ 그림 1-1] 자료구조의 예
자료구조의 필요성 컴퓨터가 효율적으로 문제를 처리하기 위해서는 문제를 정의하고 분석하여 그에 대한 최적의 프로그램을 작성해야 하기 때문에 자료구조에 대한 개념과 활용 능 력을 필요로 한다. [ 그림 1-2] 문제해결 과정
자료구조의 내용 [ 그림 1-3] 자료구조의 내용
자료의 형태에 따른 분류 [ 그림 1-4] 자료구조의 형태에 따른 분류
디지털 시스템에서의 자료의 표현 숫자, 문자, 그림, 소리, 기호 등 모든 형식의 자료를 2 진수 코드로 표현하여 저장 및 처리 2 진수 코드 1 과 0, ON 과 OFF, 참 (True) 과 거짓 (False) 의 조합 2 진수 코드의 단위 [ 그림 1-5] 비트와 니블과 바이트
n 개의 비트로 2n 개의 상태수 표현 예 ) n=2 인 경우 [ 그림 1-7] n 개의 비트로 2n 개의 상태 표현 _ n=4 인 경우 [ 그림 1-6] n 개의 비트로 2n 개의 상태 표현 _ n=2 인 경우 예 ) n=4 인 경우
컴퓨터 내부에서 표현할 수 있는 자료의 종류 [ 그림 1-8] 컴퓨터 내부에서 자료를 표현하는 방법
10 진수의 표현 10 진수의 존 (Zone) 형식의 표현 10 진수 한자리를 표현하기 위해서 1 바이트 (8 비트 ) 를 사용하는 형식 존 영역 상위 4 비트 1111 로 표시 수치 영역 하위 4 비트 표현하고자 하는 10 진수 한자리 값에 대한 2 진수 값을 표시 존 형식의 구조 [ 그림 1-9] 존 형식의 구조
수치 영역의 값 표현 [ 표 1-1] 4 비트의 2 진수에 대한 10 진수 표현
여러 자리의 10 진수를 표현하는 방법 10 진수의 자릿수 만큼 존 형식을 연결하여 사용 마지막 자리의 존 영역에 부호를 표시양수 (+) : 1100 음수 (-) : 1101 존 형식으로 10 진수를 표현하는 예 +213 -213 [ 그림 1-10] 존 형식의 10 진수 표현 형식 F2F1C(+) F2F1D(-)
팩 (Pack) 형식의 표현 10 진수 한자리를 표현하기 위해서 존 영역 없이 4 비트를 사용하는 형식 최하위 4 비트에 부호를 표시 양수 (+) : 1100 음수 (-) : 1101 팩 형식으로 10 진수를 표현하는 예 [ 그림 1-11] 팩 형식의 10 진수 표현 형식 C(+) D(-)
2 진수의 정수 표현 n 비트의 부호 절대값 형식 최상위 1 비트 - 부호 표시 양수 (+) : 0 음수 (-) : 1 나머지 n-1 비트 – 이진수 표시 1 바이트를 사용하는 부호 절대값 형식의 예 1 비트 ← 7 비트 → 부호 21 의 절대값 1 비트 ← 7 비트 → 부호 21 의 절대값
1 의 보수 (1’ Complement) 형식 음수의 표현에서 부호 비트를 사용하는 대신 1 의 보수를 사용하는 방법 n 비트의 2 진수를 1 의 보수로 만드는 방법 n 비트를 1 로 한 이진수에서 변환하고자 하는 이진수를 뺀다. 예 ) 10 진수 21 을 1 의 보수로 만들기 (1 바이트 사용 ) 1 바이트를 사용하는 1 의 보수 형식의 예 + 21 - 21 부호절대값형식의 양수 표현과 같음 ☜ 21 의 2 진수 값 ☜ 21 의 1 의 보수 ← 21 의 절대값 → ← 21 의 1 의 보수 →
2 의 보수 (2’ Complement) 형식 음수의 표현에서 부호 비트를 사용하는 대신 2 의 보수를 사용하는 방법 n 비트의 2 진수를 2 의 보수로 만드는 방법 1 의 보수에 1 을 더해준다. 예 ) 10 진수 21 을 2 의 보수로 만들기 (1 바이트 사용 ) 1 바이트를 사용하는 2 의 보수 형식의 예 + 21 - 21 부호절대값 형식의 양수 표현과 같음 2 진수 정수의 세 가지 표현 방법에서 양수의 표현은 같고, 음수의 표현만 다르다 ☜ 21 의 2 진수 값 ☜ 21 의 1 의 보수 ☜ 21 의 2 의 보수 ← 21 의 절대값 → ← 21 의 2 의 보수 →
2 진수의 실수 표현 고정 소수점 표현 소수점이 항상 최상위 비트의 왼쪽 밖에 고정되어있는 것으로 취급하는 방법 고정 소수점 표현의 은 의 실수 값을 의미 부동 소수점 형식의 표현 고정 소수점 형식에 비해서 표현 가능한 값의 범위가 넓다. 실수를 부호와 지수, 소수의 세 부분으로 구분하여 표현 4 바이트를 사용하는 부동 소수점 형식 [ 그림 1-12] 4 바이트 부동소수점 표현 형식
문자자료의 표현 문자에 대한 이진수 코드를 정의하여 사용 문자에 대한 이진수 코드표 BCD 코드 EBCDIC 코드 ASCII 코드 BCD 코드 6 비트를 사용하여 문자 표현 상위 2 비트 : 존 비트 하위 4 비트 : 2 진수 비트 존 비트와 2 진수 비트를 조합하여 10 진수 0~9 와 영어 대문자와 특수문자를 표현 BCD 코드의 구성 [ 그림 1-13] BCD 코드의 구성
[ 표 1-2] BCD 코드 표 예 ) 영문자 A 에 대한 BCD 코드 ☞ [ 표 1-2] BCD 코드 표
EBCDIC 코드 8 비트를 사용하여 문자 표현 상위 4 비트 : 존 비트 하위 4 비트 : 2 진수 비트 존 비트와 2 진수 비트를 조합하여 10 진수 0~9 와 영어 대문자 / 소문자와 특수문자 를 표현 EBCDIC 코드의 구성 [ 그림 1-14] EBCDIC 코드의 구성
[ 표 1-3] EBCDIC 코드 표 예 ) 영문자 A 에 대한 EBCDIC 코드 ☞ [ 표 1-3] EBCDIC 코드표
ASCII 코드 7 비트를 사용하여 문자 표현 상위 3 비트 : 존 비트 하위 4 비트 : 2 진수 비트 존 비트와 2 진수 비트를 조합하여 10 진수 0~9 와 영어 대문자 / 소문자와 특수문자 를 표현 ASCII 코드의 구성 [ 그림 1-15] ASCII 코드의 구성
[ 표 1-4] ASCII 코드 표 예 ) 영문자 A 에 대한 ASCII 코드 ☞ [ 표 1-4] ASCII 코드표
논리자료 논리값을 표현하기 위한 자료 형식 논리값 참 (true) 과 거짓 (false), 1 과 0 1 바이트를 사용하여 논리자료를 표현하는 방법 방법 1) 참 - 최하위 비트를 1 로 표시 거짓 – 전체 비트를 0 으로 표시 방법 2) 참 – 전체 비트를 1 로 표시 거짓 – 전체 비트를 0 으로 표시 방법 3) 참 – 하나 이상의 비트를 1 로 표시 거짓 – 전체 비트를 0 으로 표시
포인터 자료 메모리의 주소를 표현하기 위한 자료 형식 변수의 주소나 메모리의 특정 위치에 대한 주소를 저장하고 주소연산 하기 위해 사용 문자열 (string) 자료 여러 문자로 이루어진 문자의 그룹을 하나의 자료로 취급하여 메모리에 연속적 으로 저장하는 자료 형식 하나의 문자열 자료에 포함된 부분문자열을 표현하는 방법 방법 1) 부분문자열 사이에 구분자를 두고 연속 저장하는 방법 방법 2) 가장 긴 부분문자열의 길이에 맞추어 고정 길이로 연속 저장 하는 방법 ( 배열 ) 방법 3) 부분문자열을 연속 저장하고 각 부분문자열에 대한 포인터 를 사용하는 방법 ( 포인터 )
부분문자열의 표현 예 표현할 문자열 : {COMPUTER, DATA STRUCTURE, STRING} 방법 1) 구분자를 사용하는 표현 : 구분자로 세미콜론 (;) 사용 방법 2) 고정길이를 사용하는 표현 [ 그림 1-17] 고정 길이로 저장하는 방법 _ 방법 2 [ 그림 1-16] 구분자를 사용하여 저장하는 방법 _ 방법 1
부분문자열의 표현 예 방법 3) 포인터를 사용하는 표현 [ 그림 1-18] 포인터를 사용하여 저장하는 방법 _ 방법 3
부분 문자열 표현 방법의 비교 [ 표 1-5] 문자열 표현 방법 비교
궁금한 점 ? Penguri Entertainment Co, Ltd. All rights reserved 향후 수업에서 집중적으로 다루어줬 으면 하는 분야는 ?
수고하셨습니다 수고하셨습니다 Penguri Entertainment Co, Ltd. All rights reserved