알고리즘 스터디 - 1일차

4/30(토) 알고리즘 스터디1

자료구조란 무엇일까?

A) 일련의 자료를 집합형태로 쌓을 수 있는 구조를 말한다고 생각한다. 실생활에서 장에 그릇을 놓는 다면 찬장, 책을 모아 두면 책장이 되는 것 처럼 ‘틀’이라고 생각 할 수 있다. 그런 의미로 볼 수 있다고 생각한다. 컴퓨터로 치면 데이터 집합인 배열, 리스트 등등도 그러한 경우 결국 어떤 용도로 쓸 것인지가 중요하다. 결국 자료구조의 용도는 무엇을 담을지에 대한 초점이다.

팀원) 사용하기 편하게 & 빠르게 만드는게 자료구조. - 효율성 위주 ( 목적성 위주로 생각해도 될 것 같다.)

자료구조를 왜 사용할까?

A) 나는 프로그래머의 편의성인 것 같다. 우선 컴퓨터 프로그래밍에서 자료구조가 생긴 이유는 각 자료형의 진화 역사를 보면 알 수 있다고 생각한다. 초기에는 int, char, float,double등 primitive type만 존재했으나, 동등한(equivalent) type을 여러 개 생성 하는 방법이 필요해 진 것이다. 그게 바로 Array이고, 그 이후에 다른 Type도 같이 사용하고 싶어서 나온 개념은 Struct이다. 이는 다양한 Type을 한데 모아 사용하고자 함이다. 그러다가 순간 순간에만 메모리 효율성을 위해 사용하고자 해서 나온 구조가 Union이고, Method(행위)까지 추가하게 된 개념이 class라고 생각한다. 결국 프로그래머의 편의성에 대한 점도 일부 맞지 않을까 ?

팀원 ) 자료들에 사용하는데 초점을 맞춰서 생각!

  • 사용할 때, 어떤 부분을 초점을 맞추는지에 대해 목적이 다르기에 각기 필요한 자료구조(시간/메모리)

왜 다양한 자료구조가 있으며, 자료구조의 선택 기준은 무엇일까?

A) 자료구조의 선택 기준은 상황에 따른 목적이 중요할 것으로 생각 된다. 어떤 자료가 특정 집합으로 구성되어 있을 때 이것을 원하는 바(목적)의 형태로 가공하기 쉽고, 자료 처리를 쉽게 할 수 있는 구조가 상황마다 다르기 때문이다.

팀원 )

  • 목적을 실현하는데 중요한 효율성(시간/공간)
  • 얼마나 빠른 시간/제한 된 시간에서 답을 도출하는지

알고리즘이란 무엇일까??

A)알고리즘은 일련의 처리 절차이다. 단, 여기서 중요한점은 간략함이 될 것 같다. 부수적인 것들이 많아지면 알고리즘이라 부르기 어렵고 Logic이라 부르는 것이 더 알맞는 표현일 것 같다. 부수적인 것이 없는 처리 절차를 표현한 것이 알고리즘이며, 알고리즘은 시간 복잡도, 공간 복잡도를 따져야 할 만큼 중요한 처리 절차의 목적을 포함하고 있다.

즉, 알고리즘과 자료구조의 차이점은 자료구조는 ‘데이터를 저장하는 틀’이고, 알고리즘은 처리 절차이다. 알고리즘에서 자료구조를 사용한다고 표현 할 수 있겠다.

왜 다양한 알고리즘이 존재할까??

A)상황마다 매번 같은 알고리즘을 쓸 수 없을 것이 첫 번째 이유라 생각한다. 정렬 기법도 다양한 이유가 목적이 다르기때문에 달라진다. 흔하게 사용하는 Quick Sort라던지, Insertion Sort등 속도가 다르고, 정렬시 사용하는 공간(Space)이 다르다. 즉, 정보를 처리하는 목적에 따라 시간에 High-Cost를 투자 할 것인지? 공간에 High-Cost를 투자 할 것인지가 모든 개발 상황마다 다르게 적용이 될 수 있으므로, 알고리즘은 다양해진다. 상황이 다양하고, 목적도 다양하기에 다양한 알고리즘을 만들고 사용 한다.

배열의 주요 특징은 무엇?

구조적 데이터 타입(Structured data type) : 여러 데이터를 묶어서 하나의 단위로 처리하는 데이터 타입 배열 - 같은 자료형의 모임(homogeneous)이며, 저장하는 자료형태는 Equivalent Type이다.

배열의 크기 (첨자 지정)

  1. Static
    • 정적으로 범위가 고정
    • 예 ) static int a[100];
  2. Fixed-Stack dynamic
    • 범위는 정적으로 고정 할당은 선언문에서 되어 효율성 증가
    • 예 ) int a[100];//local variable
  3. Stack dynamic - 범위가 동적으로 결정/메모리 할당도 동적(실행시간에 됨)
    • stack에 할당
  4. Fixed heap dynamic - 동적 할당 후 크기가 고정
    • 동적/할당 후 크기는 고정 stack이 아닌 Heap 메모리 사용
    • C/C++ : malloc / free for arrays
    • C++ : new & delete
    • Java / C# : new
    • C# : Class2[] c2 = new Class2[20];
  5. Heap-dynamic - 할당 크기 모두 동적으로 변화
    • C# : List stringList = new List();
  • C/C++, Fortran, Perl : 첨자 범위 검사 명세 없음.
  • Java, ML, C# : 첨자의 범위를 명시함.
  • Ada : 기본은 첨자 범위 검사 그러나 하지 않을 가능성도 높다.

또한, 일반적인 언어는 첨자 하한이 0인데 반면, Ada, Perl의 경우 음수도 가능하다.

원소들의 실제 메모리 위치

정해진 사이즈만큼 연속적인 공간에 할당 된다.

1차원 배열의 경우

A[0] A[1] A[2]
204 208 212

1차원 배열 주소 공식

A[i] = base * (i - a) * size base : 시작 주소 (A[0]가 시작주소) a : 첫번 째 원소의 첨자 (음수가 아니면 0) Size : 각 원소의 크기

row-major

실제 메모리에 저장되는 위치가 행 중심으로 저장 된다. A[1][1] , A[1][2] , A[1][3] … 식으로 저장 된다. 대부분의 언어에서 사용.

column-major

실제 메모리에 저장되는 위치가 열 중심으로 저장 된다. A[1][1] , A[2][1] , A[3][1] … 식으로 저장 된다. 주로 Fortran 계열에서 사용.

선언,생성,초기화,원소접근방법

선언

int arr[100]; - C int[] arr = new int[100]; - Java

검색

  • index를 통해 직접 접근/처음 부터 끝까지 전체 순회

삭제

  • 해당 index에 해당하는 공간 삭제 후 빈 공간을 데이터 이동하여 빈 공간이 없도록 함.

삽입

  • index에 해당하는 공간에 값 대입, 주로 끝에 데이터를 삽입.

######퀴즈

int main()
{
  int arr[5] = {1,2,3,4,5};
  printf("%d %d\n", arr[5] , 5[arr]);
}

위 코드에서 이상한 점을 발견 하셨나요? 왜 그렇게 되는지는 한 번 공부해보시기 바랍니다.

생각해볼 문제!

컴퓨터의 메모리 영역 관련 자료 : 메모리 영역 참고

  • 메모리 할당( 정적 메모리 할당, 동적 메모리 할당 )의 비교
    • 정적 할당
    • 동적 메모리 할당
  • 저장된 원소들의 자료형( 배열 vs 구조체 )에 따른 비교
  • 추상자료형(ADT)와 자료구조(Data Structure)의 비교 및 구분
리스트의 개념?

쉽게 생각하면 정보의 나열이라고 생각 할 수 있는데, 순서가 있다.

  • arrayList
  • LinkedList
두 구현방법의 특징과 비교, 장단점, 사용되는 예

특징

  1. ArrayList의 경우 배열 구조를 사용하므로 직접 접근이 가능하다.
  2. LinkedList의 경우 확장이 용이하다.

비교

  • ArrayList의 경우

    • 삽입은 빠르다. 단, 삭제연산에는 많은 비용이 발생한다.
    • 추가적으로 확장에 불리한 구조를 가진다.
    • 검색도 빠르다.

  • LinkedList의 경우

    • 삽입이 느리다.
    • 순차검색!!
    • 삭제는 편리하다.
왜 리스트를 구현함에 있어, 다양한 방법이 존재할까?
  • 효율성에 따라 사용처가 다르기 때문이 아닐까 생각해본다. 어떤 곳은 검색이 중요하면, 배열이 더 편리할 것이다.
  • 공간 효율성을 중요하게 생각하는 곳이라면 배열이 좋다.
리스트의 주요 연산 및 주의 사항

  • 삽입의 3가지 경우( 공백리스트인 경우, 리스트의 맨처음에 삽입, 리스트의 중간에 삽입 )

  • 삭제의 2가지 경우( 맨 앞의 노드 삭제, 중간의 노드 삭제 )

  • 삭제 및 검색시 중복자료를 허용하는 경우와 그렇지 않는 경우

    • 중복을 허용하는 경우와 그렇지 않은경우의 차이가 존재함.
다양한 리스트의 비교 및 존재 이유, 사용 경우
  • 단순 연결 리스트
  • 이중 연결 리스트
  • 이중 말단 연결 리스트
  • 원형 연결 리스트

스택이란?

  • 쉽게 생각하자면, 그릇 쌓기로 생각할 수 있다. 자료구조 형태가 그릇 쌓기처럼 구성 되어 있는 것이다.
  • 컴퓨터용어로 표현하면, LIFO(Last In First Out)의 특징을 갖는 구조이다.

스택의 연산

  • 삽입
    • 그릇은 위로만 쌓을 수 있다.
  • 삭제
    • 그릇은 위로만 뺄 수 있다. ( 중간 것을 빼면 그릇이 깨진다. - 주인한테 혼난다(컴퓨터로 치면 OS?))

스택의 실제 사용 예

  • 계산기 스택의 구현
    • Array
    • List

큐란 ?

  • 은행에서 순서표를 받고 기다리는 행위와 비슷하다.
  • 컴퓨터용어로 표현하면, FIFO(First In First Out)의 특징을 갖는 구조이다.

큐의 연산

  • 삽입
  • 삭제

큐의 사용 예

  • OS의 스케쥴링, BFS의 정보 저장, 그래프의 사이클 찾기, 네트워크 통신 ?

큐의 구현과 특징, 비교

  • Array
  • List

큐의 종류와 존재 이유 특징, 차이점 비교

큐 - 관련 colomy.tistory.com

  • 선형큐
    • 일렬로 대기표를 받는 공간이라고 생각하면 쉬우며, 선형큐는 완벽한 순서 절차를 위해 존재한다고 생각함.
    • 배열로 구현시 데이터 이동이 빈번하다.
  • 원형큐
    • 흔히 배열로 구현할 수 있으며, % 연산자를 활용해 indexing이 가능하다.
    • 장점
      • Node형태 보다 간결하고, 쉬운 구현
    • 단점
      • 데이터 삭제시 데이터의 이동이 빈번하다.
      • 포화상태와 공백상태를 구분하기 위해 1개의 공간이 유휴공간으로 지정되어야한다.
  • 덱(Dequeue)
    • 기존 큐와는 다르게 앞/뒤로 out이 가능한 형태의 큐로 기존 큐와는 다르다.
    • 먼저 온 데이터가 먼저 Out될 수 있고, 제일 늦게 온 데이터가 Out될 수 있는 구조이므로 스택과 큐의 혼용 개념이라고 생각한다.
    • 보통 일반적으로 이중 연결 링크드 리스트로 구현한다.