Skip to content

Data structure

Jump to bottom
cozytk edited this page Feb 24, 2020 · 1 revision

들어가기 전에,

  • 주석 : 블록 주석 (/* */)은 곂치면 안됨. 블록 주석 안에 // 이거 있는건 됨
  • switch 구문 : 문법은 exam) switch(5){ case 1: //세미콜론(;)이 아니라 콜론(:)인게 특징임. (중괄호 쓰고 똑같이 하지 않나) break; 와 연계. 뭐 나중에 필요할 때 다시보면 될듯
  • goto 구문 : 굳이 안써도됨
  • static 변수 : 0으로 초기화 되고, 프로그램이 실행되면서부터 (해당 함수에 접근 하지 않아도 메모리가 할당됨) 끝날때 까지 메모리 공간에 남아있는 전역 변수의 특징을 가지고 있음. 허나 선언된 함수에서만 접근이 가능함. 함수 내부에 static으로 초기화 해놓은 것은 사실상 없다고 생각하면 됨. (딱 1회만 초기화 된다는 것이 이 뜻.)
  • register 변수 : register 영역에서 쓰라고 권유하는 변수. 연산을 빠르게 하도록 장려함. 하지만 전역변수는 register 변수로 선언할 수 없고 (프로그램이 끝날때 까지 메모리 공간을 차지할 수는 없음) 아니다 싶으면 register로 선언해도 마음처럼 안됨.

포인터와 배열은 날 잡아서 다시 공부해야 할듯.

자료구조와 알고리즘의 이해

*01 - 1 : 자료구조에 대한 기본적인 이해.

말 그대로 자료의 구조를 정리해 놓은 것 아닌가? 대표적으로 스텍, 큐, 연결리스트, 트리 등이 생각이 난다.
자료구조란 데이터를 저장하는 것을 말한다. 그리고 우리는 알고리즘을 이용하여 데이터를 처리하여 프로그램을 완성하는 것이다.
쌓아놓은 박스 안에 있는 물건을 찾기 위해서는 위에서붙어 찾아야 하듯이, 자료구조는 알고리즘을 결정 짓는 강력한 도구이다.

우리가 일반적으로 int를 선언하거나, 개인정보를 만들기 위해 구조체를 선언했다면 그것 역시 자료구조이다.
단순 자료 구조에는 문자열, int형, float형, char형 등 있다.
선형 자료 구조에는 큐, 스텍, 연결리스트 등이 있다.
비선형 자료 구조에는 트리, 그래프가 있다.********
하나 더 있었는데 까먹었다.
보통 선형 자료 구조까지는 열심히 하는데 비선형에서 포기하는 경우가 많다. 파이팅해서 끝까지 가보자.

*01 - 2 : 알고리즘의 성능분석 방법.

시간 복잡도 계산 내용이었으면 좋겠다. O(n), O(nlogn) 머시기 머시기 뭔지 잘 모르겠다.
알고리즘의 성능을 분석할때는 얼마나 빠른 코드인가 혹은 얼마나 메모리를 적게 사용하는 코드인가로 분석한다. 시간을 기준으로
평가하는 것은 시간복잡도 메모리를 기준으로 평가하는 것을 공간복잡도라고 한다.

시간복잡도를 계산할때 평균 경우와 최악의 경우를 기준으로 계산할 수 있는데 평균 경우는 계산하기가 무척 까다롭다. 그래서 우리는
보통 최악의 경우를 빅 O 표기법을 사용하여 고친다. 빅 O표기법에서는 지수가 가장 큰수이거나, n자체가 지수일때는 밑이 가장큰
것을 기준으로 하여 계산한다 ex) 10 * 2^n + 3n^3 = O (2^n) 대표적으로 단순 탐색은 O(n) 바이너리 서치는 O(log_2_n)이 된다.
다음과 같이 계수를 신경쓰지 않고 표현하는 이유는 빅 o 표기법 자체가 변화의 추이를 중요시하기 때문이다.

재귀

알고리즘 개념인 줄 알았는데 자료구조의 단원에 해당을 한다. DFS, BFS등이 재귀함수로 구현하는 알고리즘으로 알고있다. 대표적으로 N_QUEEN 문제를 풀때 재귀함수를 이용한 후 가지치기 작업 (백트래킹)으로 알고리즘을 구현했었다.

  • 02 - 1 : 함수의 재귀적 호출의 이해.

    C언어는 재귀함수를 지원하는 언어중의 하나이다. 재귀함수를 돌릴 때는 재귀가 탈출하는 지점을 설정하는 것이 중요하다. 바이너리 서치를 재귀로 만들어봤는데 사실 시간복잡도는 더 복잡하다. 하지만 이런식으로 재귀랑 친해지는 경험을 하라.

바이너리 서치는 동일한 패턴이 반복되는 특징을 보인다. 알고리즘이 재귀적인 성격을 지니고 있는 것이므로 재귀적인 정의가 가능하다.

재귀 함수는 자료 구조적으로 스택으로 활용이 된다고 생각한다. 재귀함수를 먼저 불러 놓고 밑에 코드를 쓴다면 재귀 함수가 먼저 실행이 된 후 그 뒤에 쌓일테니까. 아니 이건 스택이 아닌가? 스택은 니트를 접어서 차곡차곡 올리는 것처럼 1 2 3 4 5 로 input하면 5 4 3 2 1 로 아웃풋 하는 것 아닌가. 아 그러면 위에 설명하려고 한 건 큐인가?? 차이를 알아보도록 하자.

  • 02 - 2 : 재귀의 활용

    재귀 함수는 같은 내용을 n - 1이 되어 반복할때 유용하게 쓸 수있다.

ex)피보나치 수열

재귀함수의 실행흐름. 호출 순서를 파악하려고 너무 애쓰지 않아도 된다. 시간이 지나서 재귀함수에 익숙해지면 누구니 호출순서에 신경을 쓰지 않게 된다. 그러니 재귀함수 자체를 이해하려고 노력하자.

  • 02 -3 : 하노이 타워

    하노이 타워는 대표적인 재귀함수 문제이다. 이 문제는 재귀함수로 풀지 않으면 상당히 까다롭지만, 재귀함수를 사용한다면 10줄 남짓 한 코드로 작성을 할 수 있다. 문제를 이해하고 패턴을 찾아 재귀함수로 만들고 문제를 풀어보자.

  1. 연결 리스트1
연결 리스트로 표현되는게 3개의 챕터나 있다니 무섭다. 이렇게 방대한 내용의 자료구조였나. 일단 연결 리스트를 구현하기 위해서는 C에서 구조체 포인터를 사용해야 하는 것으로 알고있다. 구조체로 정의한 것의 변수로 next라는 변수가 있어야 하며 이 next를 구조체 포인터로 받아주면서 연결이 된다고 알고 있다. 사실 좀 이해하기 까다롭다. 하지만 구조체 포인터를 사용하는 것이 메모리 효율? 때문이라는 글을 얼핏 본 것 같다.
  • 03 - 1 : 추상 자료형
추상 자료형이 뭐지
ADT = 추상 자료형 이었다. 책만 봐서는 주석 같은 느낌이다. 리스트부터 본격적인 자료구조의 시작인데 우리가 자료구조를 학습함에
앞서 리스트라는 구조체를 공부할 때 구조체 내부의 변수에 대해 알 필요는 없고 그저 리스트 자료구조의 ADT만 알면 된다고 말해주는
것 같다. 리스트의 기능과 구현에 초점을 맞췄다.

_자료형의 정의에 기능 혹은 연산과 관련된 내용을 명시할 수 있다.

  • 03 - 2 : 배열을 이용한 리스트의 구현
뭐지 구조체 안쓰고 배열로만 이용한 리스트들인가

리스트 자료구조의 ADT 보고 자료구조 예측하기.

일단 구조상으로 일렬로 되어있는 선형 자료구조이고, 삭제는 마지막 반환 데이터에서만 일어난다. 참조가 말하는게 무슨 의미인지 잘 모르겠다. 반환값을 받았다는 것으로 이해하면 되는 것인가 싶다. 데이터의 참조에 왜 초기화가 필요할까?

데이터의 참조방식을 주의 깊게 보고 또 이해하여야 한다

LFirst 함수의 호출을 왜 요구했냐는 자문에 LNext 함수를 호출할때마다 다음에 저장된 데이터를 얻을 수 있다는 사실에서 찾을 수 있으> 며, 이것이 가능한 이유가 데이터의 참조위치를 기록하기 때문이라고 대답하고 있는데 사실 이해가 가지 않는다. 리스트에 저장 된 모든 데이터를 참조하려면 호출 순서가 First가 맨 처음이어야 하기 때문이다 단순히 모든 데이터를 참조하기 위해 다른 데이터 자료 구조와 다르다는 것을 보여주려고 한 것인가?

  1. 연결 리스트2

04 - 1 : 연결 리스트의 개념적인 이해

  • ?? 연결 리스트 에서 개념적인 이해를 시작한다 04 - 2 : 단순 연결 리스트의 ADT와 구현
  • ADT가 뭐지 다른 목차에도 있던데 04 - 3 : 연결 리스트의 정렬 삽입의 구현
  • 삽입 정렬을 들어봤는데 정렬 삽입은 뭐지
  1. 연결 리스트3 05 - 1 : 원형 연결 리스트 05 - 2 : 양방향 연결 리스트
  • 뭔가 양뱡향 연결 리스트는 원형 리스트일시 바로 옆인데 반대방향으로 돌면 찾는데 한참 나오니 구현을 한 것이 아닐까. 애초에 연결 리스트가 배열이 있는데 중간에 삽입을 하려면 뒤에 것들을 다 한칸씩 뒤로 미룰 순 없으니까. 해당 자료의 다음을 설정해 준 것으로 알고있다.
  1. 스택

06 - 1 스택의 이해와 ADT 정의 06 - 2 스택의 배열 기반 구현 06 - 3 스택의 연결리스트 기반 구현

  • 배열과 연결 리스트 두가지 방법으로 구현이 가능하구나. 06 - 4 계산기 프로그램 구현
  • do-op과제가 생각 난다. 함수 포인터를 받아서 풀었던 기억이 새록새록
  1. 큐
  • 위와 비슷한 구성

07 - 5 : 덱의 이해와 구현.

  • 덱은 뭐지
  1. 트리
  • 뭔가 어려워 보인다. 이진 트리가 b-tree맞나
  1. 우선순위 큐와 힙
  • 힙은 메모리 영역으로 알고 있는데 이것도 자료구조라고 하는건가.
  1. 정렬

  • 버블정렬 : 처음부터 끝까지 정렬해서 맨 마지막을 정해놓고, N - 1 만큼 반복하며 끝을 채워가면서 정렬하는 방식

  • 퀵정렬 : <stdlib.h> 헤더 파일에 qsort라는 함수를 본 적이 있다. 양쪽에서 비교하면서 정렬하는 방식으로 기억하는데 구현 해보겠다고 마음은 먹었는데 아직 하진 않았다

  • 삽입 정렬 : 이건 제일 작은 것 부터 정렬하는 것으로 알고 있다. while 문 안에 j = i + 1; 이런식으로 넣어서

  1. 탐색 1

  2. 탐색 2

  3. 테이블과 해쉬

  4. 그래프



  • 먼 훗날 이야기들

Day 00.

Clone this wiki locally