프로그래머, 보안 관련 지식 썸네일형 리스트형 자료구조 : Stack & Queue(1) 이번 포스팅에서는 Stack과 Queue라는 자료구조에 대해 알아보자. Stack Insert/Delete만 제공 Push/Pop이라고 부름 Last in, First out(나중에 들어오는게, 먼저 나가는 것) 성능: Push: O(1), Pop: O(1)(넣는것을 push, 빼는것을 pop) Queue Insert/Delete만 제공 First in, First out( 먼저 들어오는게, 먼저 나가는 것) 성능: Insert O(1) , Delete O(1) Stack 구현 Stack Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 int Stack[N]; int SP; int init() {SP = 0} int isEmpty() {return SP == 0;} int .. 더보기 자료구조: String Matching(2) 지난번에 이어서 패턴 문제를 KMP 알고리즘에서 어떻게 처리하는지에 대해 알아보겠다. KMP 알고리즘은 DFA와 비슷하면서도 조금 더 메모리를 적게 먹는 알고리즘이다. 전반적인 과정은 비슷하지만 텍스트와 패턴을 비교했을때 다른 글자가 나올경우 다른 방법으로 처리하게 된다. 위에가 text 밑에를 pattern이라고 하자. 그리고 위의 숫자가 써있는 표가 있다. 이것의 용도를 차차 설명하겠다. 일단 상황을 하나 가정하자 텍스트에 값들이 써져있다고 생각한다. 아래의 사진을 보자 일단 맨위의 숫자는 생각하지 말고 글자 위에 다음과 같은 숫자들이 있고 빨간색은 패턴과 텍스트가 서로 지금까지 일치함을 뜻한다. 그리고 이제 다음으로 볼글자가 다음과 같이 c로 같다고 생각해보자. c 위에는 어떤 숫자를 써야할까? D.. 더보기 자료구조 : String Matching(1) 이번 포스팅에서는 String Matching이 뭔지에 대해 알아보자. Problem Defintion Text : Simple String of Characters Pattern: Simple String of Characters To Do : find where in the Text Pattern Occurs String Matching 문제는 Text 에서 패턴을 발생하는 곳을 찾는 문제이다. abababcabcabcdabccbaabdabcabcdabcd 다음과 같은 text에서 abcabcd 를 찾는 문제라고 생각해보자. 일반적으로 사람이 이 일을 할때 어떻게 할수 있을까? 대보면서 한글자씩 옆으로 밀어가며 찾을 것이다. 이 방법은 상당히 느린 작업이고 이것보다 더 빠르게 찾는 방법이 존재한다. .. 더보기 자료구조 : 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 2 3 다음
