외부:활동 티스토리
알고리즘 스터디 - 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이다.
배열의 크기 (첨자 지정)
- Static
- 정적으로 범위가 고정
- 예 ) static int a[100];
- Fixed-Stack dynamic
- 범위는 정적으로 고정 , 할당은 Stack에 할당되어 효율성 증가
- 예 ) int a[100];//local variable
- Stack dynamic - 범위가 동적으로 결정/메모리 할당도 동적(실행시간에 됨)
- stack에 할당
- 예 ) int size = scanner.nextInt();
- int [] arr = new int [size];
- 단, 최신 C는 가능하나, VS에서는 지원을 아직 안 할 가능성..GCC에서는 가능할지도 ?
- Fixed heap dynamic - 동적 할당 후 크기가 고정
- 동적/할당 후 크기는 고정 stack이 아닌 Heap 메모리 사용
- C/C++ : malloc / free for arrays
- C++ : new & delete
- Java / C# : new
- C# : Class2[] c2 = new Class2[20];
- Heap-dynamic - Heap 영역 할당 크기가 동적으로 변화
- C# :
List<String> stringList = new List<String>();
- C# :
언어별 첨자 검사
- C/C++, Fortran, Perl : 첨자 범위 검사 명세 없음.
- Java, ML, C# : 첨자의 범위를 명시함.
- Ada : 기본은 첨자 범위 검사 그러나 하지 않을 가능성도 높다.
또한, 일반적인 언어는 첨자 하한이 0인데 반면, Ada, Perl의 경우 음수도 가능하다.
바꿔서 말하면, 보통의 언어는 Index -> 0 부터 시작, Ada, Perl의 언어는 지정한 index(음수가능)부터 가능하다
원소들의 실제 메모리 위치
정해진 사이즈만큼 연속적인 공간에 할당 된다.
1차원 배열의 경우
| A[0] | A[1] | A[2] |
|---|---|---|
| 204 | 208 | 212 |
1차원 배열 주소 공식
A[i] = base * (i - a) * size
base : 시작 주소 (A[0]가 시작주소)
a : 첫번 째 원소의 첨자 (음수가 아니면 0)
Size : 각 원소의 크기
A[n][m]의 첫 번째 원소의 행과 열의 첨자는 a
base : 시작 주소
size : 원소 크기
row-major
실제 메모리에 저장되는 위치가 행 중심으로 저장 된다.
A[1][1] , A[1][2] , A[1][3] … 식으로 저장 된다.
대부분의 언어에서 사용.
A[i][j] = base + (m * (i-a) + (j-a)) * size
column-major
실제 메모리에 저장되는 위치가 열 중심으로 저장 된다.
A[1][1] , A[2][1] , A[3][1] … 식으로 저장 된다.
주로 Fortran 계열에서 사용.
A[i][j] = base + (n * (j-a) + (i-a)) * size
선언,생성,초기화,원소접근방법
선언
int arr[100]; - C
int[] arr = new int[100]; - Java
검색
- index를 통해 직접 접근/처음 부터 끝까지 전체 순회
삭제
- 해당 index에 해당하는 공간 삭제 후 빈 공간을 데이터 이동하여 빈 공간이 없도록 함.
삽입
- index에 해당하는 공간에 값 대입, 주로 끝에 데이터를 삽입.
퀴즈
1.int main()
2.{
3. int arr[5] = {1,2,3,4,5};
4. printf("%d %d\n", arr[5] , 5[arr]);
5.}
위 코드에서 이상한 점을 발견 하셨나요?
왜 그렇게 되는지는 한 번 공부해보시기 바랍니다.
생각해볼 문제!
컴퓨터의 메모리 영역 관련 자료 : 메모리 영역 참고
- 메모리 할당( 정적 메모리 할당, 동적 메모리 할당 )의 비교
- 정적 할당
- 동적 메모리 할당
- 저장된 원소들의 자료형( 배열 vs 구조체 )에 따른 비교
- 추상자료형(ADT)와 자료구조(Data Structure)의 비교 및 구분
리스트의 개념?
쉽게 생각하면 정보의 나열이라고 생각 할 수 있는데, 순서가 있다.
- arrayList
- LinkedList
두 구현방법의 특징과 비교, 장단점, 사용되는 예
특징
- ArrayList의 경우 배열 구조를 사용하므로 직접 접근이 가능하다.
- LinkedList의 경우 확장이 용이하다.
비교
-
ArrayList의 경우
- 삽입은 빠르다. 단, 삭제연산에는 많은 비용이 발생한다.
- 추가적으로 확장에 불리한 구조를 가진다.
- 검색도 빠르다.
- LinkedList의 경우
- 삽입이 느리다.
- 순차검색!!
- 삭제는 편리하다.
왜 리스트를 구현함에 있어, 다양한 방법이 존재할까?
- 효율성에 따라 사용처가 다르기 때문이 아닐까 생각해본다. 어떤 곳은 검색이 중요하면, 배열이 더 편리할 것이다.
- 공간 효율성을 중요하게 생각하는 곳이라면 배열이 좋다.
리스트의 주요 연산 및 주의 사항
삽입의 3가지 경우( 공백리스트인 경우, 리스트의 맨처음에 삽입, 리스트의 중간에 삽입 )
삭제의 2가지 경우( 맨 앞의 노드 삭제, 중간의 노드 삭제 )
-
삭제 및 검색시 중복자료를 허용하는 경우와 그렇지 않는 경우
- 중복을 허용하는 경우와 그렇지 않은경우의 차이가 존재함.
다양한 리스트의 비교 및 존재 이유, 사용 경우
- 단순 연결 리스트
- 이중 연결 리스트
- 이중 말단 연결 리스트
- 원형 연결 리스트
스택이란?
- 쉽게 생각하자면, 그릇 쌓기로 생각할 수 있다. 자료구조 형태가 그릇 쌓기처럼 구성 되어 있는 것이다.
- 컴퓨터용어로 표현하면, LIFO(Last In First Out)의 특징을 갖는 구조이다.
스택의 연산
- 삽입
- 그릇은 위로만 쌓을 수 있다.
- 삭제
- 그릇은 위로만 뺄 수 있다. ( 중간 것을 빼면 그릇이 깨진다. - 주인한테 혼난다(컴퓨터로 치면 OS?))
스택의 실제 사용 예
- 계산기
스택의 구현
- Array
- List
큐란 ?
- 은행에서 순서표를 받고 기다리는 행위와 비슷하다.
- 컴퓨터용어로 표현하면, FIFO(First In First Out)의 특징을 갖는 구조이다.
큐의 연산
- 삽입
- 삭제
큐의 사용 예
- OS의 스케쥴링, BFS의 정보 저장, 그래프의 사이클 찾기, 네트워크 통신 ?
큐의 구현과 특징, 비교
- Array
- List
큐의 종류와 존재 이유 특징, 차이점 비교
-
선형큐
- 일렬로 대기표를 받는 공간이라고 생각하면 쉬우며, 선형큐는 완벽한 순서 절차를 위해 존재한다고 생각함.
- 배열로 구현시 데이터 이동이 빈번하다.
-
원형큐
- 흔히 배열로 구현할 수 있으며, % 연산자를 활용해 indexing이 가능하다.
- 장점
- Node형태 보다 간결하고, 쉬운 구현
- 단점
- 데이터 삭제시 데이터의 이동이 빈번하다.
- 포화상태와 공백상태를 구분하기 위해 1개의 공간이 유휴공간으로 지정되어야한다.
-
덱(Dequeue)
- 기존 큐와는 다르게 앞/뒤로 out이 가능한 형태의 큐로 기존 큐와는 다르다.
- 먼저 온 데이터가 먼저 Out될 수 있고, 제일 늦게 온 데이터가 Out될 수 있는 구조이므로 스택과 큐의 혼용 개념이라고 생각한다.
- 보통 일반적으로 이중 연결 링크드 리스트로 구현한다.
'프로그래밍 > Algorithm' 카테고리의 다른 글
| 무방향 그래프 - DFS/BFS (0) | 2016.05.14 |
|---|---|
| Algorithm Study 1 - 2주차 (0) | 2016.05.09 |
| 에라토스테네스의 체 (0) | 2015.11.04 |
| 알고리즘 - 정렬 (0) | 2015.10.21 |
| Heap sort (0) | 2015.04.19 |