자료구조당

자료구조와 알고리즘

이히당 2023. 11. 14. 15:50

자료구조?

컴퓨터에서 자료들을 정리하고 조직화하는 여러가지 구조들을 말한답니다

 

위의 표에서 보는 것과 같이 자료구조는 ‘단순 자료구조’와 ‘복합 자료구조’로 나뉘는데

특히 복합 자료구조에 대해 깊이 알아봐야한다.

왜냐면 알고공부를 하려면 필수니까요..;;

 

무튼 이 중요한 복합 자료구조는 크게 두가지로 나뉜다.

1. 선형 자료구조

자료들이 순서적으로 나열되는 것을 선형 자료구조라 한다.

  • 순서 접근 - 시작 노드에서부터 하나씩 다음 노드로 이동해 접근
  • 직접 접근 - 인덱스를 이용해서 접근

이 두가지 방식으로 자료에 접근할 수 있다.

2. 비선형 자료구조

자료들 간에 선형적 순서가 있는 것이 아니라 복잡한 연결을 갖는 형태의 자료구조다.

트리, 그래프가 여기에 속한다.

 

알고리즘?

간단히 말해 ‘$문제 해결 절차$’라고 생각하면 된다.

이런 알고리즘은 몇 조건이 있다.

알고리즘의 조건

  • 입력 : 0개 이상의 입력이 필요하다.
  • 출력 : 1개 이상의 출력이 존재해야한다.
  • 명백성 : 각 명령어의 의미는 모호하지 않고 명백해야한다.
  • 유한성 : 한정된 수의 단계 후에는 반드시 종료되어야 한다.
  • 유효성 : 각 명령어들은 실행 가능한 연산이어야 한다.

알고리즘 기술 방법

  • 영어나 한국어같은 자연어
  • 흐름도
  • 유사 코드
  • 특정 프로그래밍 언어 (c언어 c++ java..)

이렇게 자료구조와 알고리즘에 대해 알아봤다!

그럼 이 두가지를 합치면 무엇이될까?

바로 컴퓨터 프로그램이다.

 

굳이 수식으로 표현하자면, 프로그램 = 자료구조 + 알고리즘 이다.

 

추상 자료형

추상화?

소프트웨어 개발과 유지보수에서 가장 중요한 문제가

어떻게 소프트웨어 시스템의 복잡성을 관리할 것인가이다.

 

이 “복잡성”을 대처하기 위한 방법론이나 언어의 핵심이 바로 “추상화”다!

다시말해, 복잡한 자료, 모듈, 시스템 등으로부터 핵심적인 개념이나 기능을 간추려 내는 것을 말한다.

추상자료형(ADT)?

음.. 추상화한 자료형이다.

자료의 집합과 자료에 가해지는 연산들의 집합에 대한 수학적인 명세다.

이걸 표현할 때는

  • 객체정의
  • 연산정의

가 우선된다.

 

위의 설명이 개떡같으니 예를 들어보자

‘자연수’에 대한 추상자료형이라 하면

  • 객체 : 1에서 시작해 INT_MAX까지의 순서화된 정수의 부분 범위
  • 연산 : add(x,y) - x+y가 INT_MAX보다 크면 INT_MAX를 반환하고 아니면 x+y를 반환

이렇게 정의할 수 있겠다.

 

이런 추상 자료형을 컴퓨터 프로그램으로 구현할 때

보통은 구현에 관한 세부사항들은 모르게하고 외부에서 간단한 ‘인터페이스’만을 공개한다.

이것이 ‘정보은닉’의 개념이고

이로써, ‘구현으로부터 명세의 분리’가 추상 자료형의 중심 아이디어가 되겠다!!!

 

추상자료형과 C++

추상 자료형은 객체지향 프로그램 언어에 큰 영향을 주었다.

그냥 특징만 알아보기도 그냥 저냥 의미없다. 그냥 그렇구나~하고 넘어가자

 

 

728x90