[요약] 자료 구조 - 1 [정의, 분류, 표현, 알고리즘, 배열, 포인터, 구조체, 재귀]

※ 주의 ※
이 블로그는 어디까지나 CS관련 지식을 정리하는 것이 목적입니다. 제가 이해한 내용이 잘못 된 것 같다면 댓글로 남겨주세요. 여러분의 관심이 저의 지식 함양에 도움이 됩니다.

>> 자료구조의 개요와 정의 

• 다양한 자료를 "표현", "저장", "처리", "사용" 할 수 있도록 하는 것

>> 자료구조의 분류 

• 데이터 타입 : 정수, 실수, 문자, 문자열 등 => 단순구조
• 자료와 자료간의 관계
  • 1:1 = 선형구조
  • 1:다, 다:다 = 비선형구조
  • 파일구조

>> 수치로 자료 표현하기 

• 10진수를 표현하는 방법
  • 존(Zone): 각 자릿수를 나타내기 위해 각 숫자 앞에 4비트의 존 필드를 추가하여 숫자와 문자를 구별
  • 팩(Packed): 두 자리의 10진수를 하나의 바이트로 압축하여 표현하며, 마지막 바이트의 하위 4비트는 사인 비트를 포함
• 2진수 정수를 표현하는 방법
  • 부호와 절대값(Sign-Magnitude): 가장 왼쪽 비트를 부호 비트로 사용하여 양수(0) 또는 음수(1)를 나타내고, 나머지 비트는 숫자의 절대값을 나타냄
  • 1의 보수형식(Ones' Complement): 음수를 나타낼 때, 해당 숫자의 모든 비트를 반전(0을 1로, 1을 0으로)하여 표현
  • 2의 보수 형식(Two's Complement): 음수를 나타낼 때, 해당 숫자의 모든 비트를 반전하고 1을 더하여 표현하며, 이 형식은 덧셈 연산이 간편함
• 2진수 정수에서 음수를 표현하는 방법에는 부호와 절대값, 1의 보수, 2의 보수가 있지만, 현재 컴퓨터에서는 연산이 간편하고 일관성 있는 2의 보수 방식을 사용

>> 문자 자료 표현하기 

• 2진수 조합 => 2진수 코드 => BCD 코드, EBCDIC 코드, ASCII 코드, 유니코드

>> 논리 자료 표현하기 

• 참과 거짓, True and False, 1 && 0
• 1비트로 표현 가능
• 일반적으로 1바이트 또는 1워드를 사용
  • 1워드 : 8비트, 16비트, 32비트 등

>> 포인터 자료 표현하기 

• 메모리 주소
• 자료를 저장하고 있는 변수의 주소 또는 메모리 주소를 저장함
• 복잡한 자료구조 연산에 좋음

>> 문자열 자료 표현하기 

• 문자 자료는 한 글자, 문자열 자료는 문자 그룹이 하나의 자료
• 부분 문자열을 표현하는 세 가지 방법
  1. 구분자 사용: 부분 문자열 사이에 구분자를 넣어 저장
  2. 고정 길이: 가장 긴 문자열의 길이에 맞춰 고정된 길이로 저장
  3. 포인터 사용: 부분 문자열을 연속적으로 저장하고 각 부분 문자열에 대한 포인터를 사용

>> 추상 자료형 

• 자료와 연산자의 특성을 추상화
• 추상화 = 무엇인지를 정의
• 구체화 = 어떻게할 것인지를 표현

>> 알고리즘 

• 문제를 해결하는 방법을 기술해 놓은 명세서
• 조건
  • 입력(Input) : 문재해결에 필요한 자료가 외부에서 입력받아 제공될 수 있어야 한다.
  • 출력(Output) : 하나 이상의 결과를 출력해야 한다.
  • 명확성(Definiteness) : 내용과 순서를 나타내는 명령어들이 명확하게 명세되어야 한다.
  • 유한성(Finiteness) : 알고리즘이 끝나면 종료가 되어야 한다.
  • 효과성(Effectiveness) : 알고리즘의 모든 명령어들이 명확하고 이해 가능하며 실제로 실행할 수 있어야 한다.

>> 알고리즘 성능분석하기 

• 시간 복잡도 : 종료되기까지의 총 시간 = 컴파일 시간 + 실행 시간
• 컴파일 시간은 거의 고정적임
• 컴퓨터 성능에 따라 실행 시간은 달라질 수 있음
  • 그래서 명령문의 실행 빈도수를 계산
• 빅-오 표기 => O(n) 등
• 빅오 표기법은 알고리즘의 최악의 경우 수행 시간을 나타내어 최대 시간을 평가하는 데 사용됨

>> 1차원 배열 

• 같은 자료형의 자료들을 연속으로 메모리에 저장한 그룹
• 인덱스는 요소를 구별하기 위해 사용되며 일반적으 0부터 시작
• 선언 : 자료형 배열이름[개수];

>> 문자로된 배열 

• 문자를 나열한 것으로, " " 안에 문자열 값을 넣는다.
• 문자열은 연속적으로 저장되므로 char형 배열을 사용
• 초기화는 문자열 그대로 지정하거나 문자 리스트를 사용

>> 다차원 배열 

• 2차원 이상의 배열
• 선언
  • 자료형 배열이름[행][열];
  • int arr[10][10]
    • 행 생략 불가 => int arr[][3] (X)

>> 포인터 

• 포인터는 변수의 메모리 주소를 나타내는 변수
• 포인터 변수는 다른 변수를 가리키고 있다는 의미
• 간단히 포인터라고 한다.

>> 문자 배열과 포인터 배열 차이 

• 2차원 문자 배열은 1차원 포인터 배열로 표현
• 2차원 배열의 행 개수는 포인터 배열의 크기
• 포인터 배열의 각 요소는 문자열의 시작 주소를 가진 포인터
• 포인터 배열은 문자열 길이에 따라 메모리를 효율적으로 사용 가능하다.

>> 포인터의 포인터(이중 포인터) 

• 일반 변수의 주소가 아니라 포인터의 주소를 저장하는 포인터

>> 구조체 

• 구조체는 배열처럼 여러 데이터를 하나의 자료형으로 묶어 정의하는 자료형이다.
• 배열은 같은 자료형만 그룹화할 수 있지만, 구조체는 서로 다른 자료형을 하나의 자료형으로 선언해 사용한다.
• 구성 요소
  • 구조체 이름
  • 자료형
  • 데이터 항목

>> 구조체 연산 

• 구조체에서는 데이터 항목 참조 연산, 구조체 변수 복사, 구조체 변수의 주소 구하기 연산 등을 사용한다.
• 점 연산자(.)와 화살표 연산자(->)를 이용해 구조체의 개별 데이터 항목을 참조한다.
• 같은 구조체의 변수들끼리 내용을 한 번에 복사할 수 있으며, 포인터 연산자를 사용해 구조체 변수의 주소를 구할 수 있다.

>> 재귀 호출 

• 함수가 자기 자신을 호출하여 순환 수행되는 것
• 재귀 호출을 사용하면 프로그램의 크기를 줄이고 간단하게 작성할 수 있다.
• 전체 문제를 하위 작업으로 분할해 작은 문제부터 해결하는 방법이 효율적일 때 사용