프로그래머, 보안 관련 지식/자료구조 썸네일형 리스트형 자료구조 : Array for Search, Insert, Delete 이번 포스트에는 자료구조에서 자주 쓰이는 배열에서의 Search, Insert, Delete 에 대해 알아보겠다. Search, Insert, Delete 자료구조의 가장 중요한 연산들 책상 위를 보시오! (우리가 평소에도 많이 하는 작업들 공책에 쓰고 지우고...) 그렇다고 모든 자료 구조에 해당하는 것은 아니다. 예) 그래프 Item: 저장되는 대상을 부를 이름 정수만 가능한 것으로 생각을 하자. 임의의 배열을 통해서 알아보자. Array 임의의 배열의 형태를 생각해보자 배열은 index와 value로 구성되어있다. 그렇다면 위 배열을 토대로 배열 안에서 삽입, 삭제, 검색이 어떻게 이루어지는지 알아보자 How to Store Items in an Array? Packed vs Unpacked (빈자.. 더보기 자료 구조 : Selection Sort, Merge Sort(2) 이번 포스팅에서는 Merge Sort (합병정렬) 에 대해 알아보자. 지난 번에 Selection Sort 보다 좀 더 생각하기 쉬운 정렬 방법으로 생각한다. 우선 Merge Sort에 대해 알아 보기 전에 Merge에 대해 알아보자. Merge 와 Merge Sort 는 서로 같은 뜻 같지만 실제로는 둘이 조금 다르다. 그럼 Merge Algorithm에 대해 그림으로 설명하겠다. 위와 같은 흐름을 반복하는것이 Merge Algorithm의 흐름이다. 이러한 Merge Algorithm을 이용한것이 Merge Sort 이다. Merge Sort에 대한 그림을 보면서 설명 해보겠다. 어떤 배열을 하나씩 하나씩 따로 따로 나눈다음에 서로 2그룹씩 합치면서 점점 올라오면서 정렬하는 것이 Merge Sort의.. 더보기 자료 구조 : Selection Sort , Merge Sort (1) 오늘은 selection sort 와 merge sort 에 대해 알아보는 시간을 가지겠다. Selection Sort의 알고리즘 흐름은 다음과 같다. 어떤 배열이 있으면, 전체에서 제일 작은 값을 앞으로 옮긴다. 그 다음 나머지 부분에서 제일 작은 값을 앞으로 옮긴다. 그렇게 반복해서 결과적으로 정렬된 배열을 만들어 내는 것이다. 간단하게 코드로 작성하면 다음과 같다. Recursive Selection Sort 1 2 3 4 5 6 7 8 9 10 11 12 int sort (int a[], int n) // n 은 배열의 크기 { int i, j, m, t; for (i = 0; i k-1 a[k], .... , a[n-1] 중 최소값을 a[k]로 옮겼음! Invariant : k 번째 루프가 끝난.. 더보기 자료구조 시작 전 알기 (5) Arrays, Algorithms, Complexity, and Recursion 본격적으로 자료구조를 살펴보자. 첫번째로 살펴볼 자료구조는 프로그램 언어를 하나라도 배운 사람이면 이숙한 그 이름 배열이다. 배열에 대해 정리하면 다음과 같다. # Array ( 배열 ) 정의 : 연속된 주소, 동일한 Type 장점 : n개 중 k번째 access(Read&Write)가 상수 시간에 가능, Search(어떤 x가 배열안에 있느냐?)가 빠름 단점 : 크기 변화 비용이 크다. Insert, Delete가 느릴수 있따. 사용 : 변화가 없거나 드문 자료 5 3 7 6 4 8 12 이런식으로 연속된 주소에 동일한 타입을 주르륵 붙여 놓은 자료구조이다. 이제 이 배열을 통해서 Binary Search 의 정확성과 속도를 알아보자. 보통 Binary Search의 코드는 다음과 같이 작성될 것이다... 더보기 자료구조 시작 전 알기 (4) Arrays, Algorithms, Complexity, and Recursion 일단 들어가기 앞서서 앞으로 증명에 자주 사용할 수학적 귀납법에 대해 알아보자. 수학적 귀납법 ( 명제 : P(n)이 있을때 ) 기본형 : p(1)이 참이고, p(n-1) -> p(n) 이 참이면 p(n)은 모든 자연수 n에 대하여 참이다. 강한 형태 : p(1)이 참이고, p(1)^p(2) ^ ....^p(n-1) -> p(n) 이 참이면 p(n)은 모든 자연수 n에 대하여 참이다. 수학적 귀납법은 크게 Base 와 Step 부분으로 나뉜다. 먼저, 기본형에 대해 보자면 base: p(1) 인 것이 참이라는 것을 보이고 step : p(n-1) -> p(n) 가 참이라고 보이면, p (n) 은 모든 자연수 n에 대해 참이라고 증명이 가능하다. base 와 step은 서로 독립적이고, 보통 base는 참.. 더보기 자료구조 시작전 알기 (3) CPU-Memory Architeture, Variables ,Addresses, Pointers 지난 포스터에서는 변수와 포인터에 대해 알아보았다. 이번 포스터에서 포인터 관련해서 좀 더 다루어보자. 아래 코드를 보자 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 #include int main() { int a, x; char b; int *p, *r; int **q; p = &a; *p = 30; q= &p; **q = 30; x = a + *p; return 0; } 14 번째에서 x = a + *p가 허용이 될까? 한번 생각해보자 a 는 int 값을 가진 변수이다. 그리고 *P는 무슨 뜻이였는가? p주소로 가라는 뜻이다. 거기에 가면 뭐가 있는가? 9번째에 우리는 int *p라고 선언했다. p번지로 가면 int 값이 있다는 것이다. 그러면 a+*p 는 두개의 in.. 더보기 자료구조 시작전 알기 (2) CPU-Memory Architeture, Variables ,Addresses, Pointers 지난번에는 CPU Memory에 대해 알아 보았다. 이번 포스팅에서는 변수에 대해 이야기 해보자. 먼저 예시로 다음과 같은 간단한 C 코드를 돌려본다고 생각해보자. 1 2 3 4 5 6 7 8 9 10 11 12 #include int main() { int a; char b; a = 10; // 이진수로 나타내면 0000 0000 0000 0000 0000 0000 0000 1010 b = 'k'; // 이진수로 나타내면 0110 1011 printf("%d %c\n" , a, b); return 0; } 실행 결과 : 10 k 코드의 흐름을 간단하게 보면 a라는 변수를 만들고 int(정수형)를 담은 것 b라는 변수를 만들고 char(문자형)를 담은 것 a 는 숫자 10을 넣고, b 는 글자 k 를 넣.. 더보기 자료구조 시작전 알기 (1) CPU-Memory Architeture, Variables ,Addresses, Pointers # 주의사향 * 자료구조 포스팅은 학교 강의를 토대로 정리해 놓은 글입니다. (추후 공부하면서 내용이 수정될 수 있음) * 자료구조의 코드는 C++를 바탕으로 쓰이며 C++의 아주 기본적인 것을 알고 있다는 전제하고 진행됩니다.(그렇다고 복잡한 문법이 쓰이지 않습니다. (약간의 시간 투자만 하면 이해가능할수 있음) 코드 자체는 돌아가는 것에 중점에 두는 것이 아닌 전반적인 흐름을 나타내므로 코드를 그대로 쓴다고 해서 실행이 되지않을 수 있습니다. 본격적으로 자료구조를 배우기 전에 먼저 컴퓨터의 구조와 컴퓨터가 어떠한 방법으로 실행되는지 알아보자! 우리가 흔히 컴퓨터 관련해서 메모리 용량이 몇 기가니 몇 메가니 이런 말들을 자주 한다. 그런데 과연 이 메모리가 정확히 무엇인가? 메모리 안에 무엇이 들어 있.. 더보기 이전 1 2 다음
