Data Structure [C]/문돌이도 할 수 있는 [C언어 자료구조] (30) 썸네일형 리스트형 #22 [C 자료구조] 스택으로 회문 검사하기 힐링 타임이다!!!! 미로의 지옥에 벗어나서 오늘은 간단간단하게 회문 검사하는 법을 배워보자. 회문 검사는 말그대로 한 문장 혹은 데이터가 앞뒤로 대칭해도 똑같은 지를 검사하는 과정이다. 예를 들어, 다 간다 이 일요일 일요일이 다 간다 (현실 반영형) 아들딸이 다 컸다 이 딸들아 (불효형) 소주 주소 (오늘 집에 안갈거야형) A man, a plan, a canal - Panama! (파나마 건설형) 이와 같은 문장들은 앞뒤가 바뀌어도 똑같다. 이렇게 스택에서 push와 pop을 하면서 같은지 검사해본다면 알 수 있다. 알고리즘을 짜보자면 1) 전반부 문자들을 스택에 push 2) 후반부 각 문자룰 pop한 문자와 차례로 비교 3) 짝수면 1,2를 따르되 홀 수면 중간 글자를 버리고 비교 수행함 코드는.. #21 [C 자료구조] 스택으로 미로 문제 풀기 오늘은 스택으로 풀 수 있는 문제 버전 2를 준비했다. 미로 되시겠다. 머리를 부여잡고 다시 한 번 스택으로 코딩을 시작해보자ㅎ 미로(Maze) 문제 미로를 배열 혹은 수열, 아니 애초에 코딩으로 구현할 수 있을까? 당연히 되기 때문에 제목으로 적었을 것이다 ㅎㅅㅎ 지나갈 수 있는 뚫린 길은 0, 벽은 1으로 표시한다. 자 그래프는 일단 그려봤다. 그렇다면 어떻게 스택을 구현하는 것일까? 위와 같이 경우의 수를 모두 스택에 쌓음으로써 가능하다. 경우의 수를 진행할 때는 스택 안에 쌓고, 벽에 막히면 Pop을 이용해 이전 단계까지 돌아온다. 미로 문제의 몇 가지 특성은 기억해줘야한다. 1) a*b 미로는 (a+2) * (b+2) 배열이 필요하다. 2) 입구는 [1][1], 출구는 [a][b] 3) 원칙상 .. #20 [C 자료구조] 스택으로 풀 수 있는 문제들 스택을 사용하는 것은 당연히 스택이 쓸모 있는 분야가 있어서다!! 진짜 이 파트에서는 스택이 어떻게 활용되는지, 어떤 방식을 통해 활용할 수 있는지 알아보자. 수식 괄호 검사 수식 괄호 검사는 쉽게 말해서 수학 공식에서 소중대 괄호를 사용할 시에 순서대로 맞게 사용했는지 검사하는 알고리즘이다. 위와 같은 수식에서 우리는 오른쪽 수식들이 잘못되었다는 것을 바로 알 수 있지만 컴퓨터는 몽총해서 에러를 출력한다. 이러한 에러를 출력하기 전에 먼저 올바른 수식인지 여부를 결정하는 함수를 써보자. 크게 논리가 되는 개요는 다음과 같다. {(){()}} 와 같은 수식이 있다고 해보자. 논리는 다음과 같다. - 직전에 읽은 괄호(왼쪽)와 다음 괄호(오른쪽)가 다른 종류면 에러 처리, 같은 종류(왼쪽 괄호)면 다음 괄.. #19 [C 자료구조] 스택: 자료 더미 스택(Stack)은 자료 저장 형태의 한 방식으로 큐와 정 반대되는 성질을 지닌다. 스택은 LIFO(Last In First Out) 방식으로 도시락 통에 차례로 도시락을 담고 다시 맨 위에서부터 꺼내는 경우를 생각해보면 된다. 큐(Queue)는 스택과는 반대로 FIFO(First In First Out), 즉 먼저 온사람이 먼저 빠지는 경우의 수이다. 일반적으로 놀이공원 줄을 기다리는 것이 FIFO 방식이라 볼 수 있다. 스택의 개념 스택은 선형 자료구조의 하나로써, 저장된 자료들 사이의 선후관계가 모두 1:1인 경우를 말한다. #3 자료구조의 분류 강의에서 썼던 자료구조 분류표이다. 자료구조 단순구조 (Simple) 정수(int) 실수(float, double) 문자열(char) 선형구조 (Linea.. #18 [C 자료구조] 자기 참조 구조체: 나야나 자기 참조 구조체 (Self-Referential Structure)는 구조체의 멤버가 자신의 구조체를 가리키는 포인터를 가질 때를 말한다. 구조체 멤버가 다른 구조체 다른 인자를 함수로써 써야할 때 필요하다. 자 코드로는 어떻게 구현하는지 살펴보자. typedef struct node { char data; struct node *link; } node; 위는 node 구조체의 안에서 *link를 통해 다시 자기 자신을 호출하는 방법이다. 이를 연결 시켜가면 이렇게 다른 node구조체를 호출할 수 있게 된다. 다른 구조체를 부르는 코딩을 짜보자!! node item1, item2, item3; item1.data = 'a'; item2.data = 'b'; item3.data = 'c'; item1.l.. #17 [C 자료구조] 동적/정적 메모리 할당할당 자료구조를 배우다가 동적 메모리, 정적 메모리, 동적 프로그래밍, 정적 프로그래밍 등등의 동/정적 단어를 많이 접할 수 있다. 영어로 풀어 쓰면 좀 더 이해하기 쉽다. 진짜 정적 메모리 할당 (Static Memory Allocation) 동적 메모리 할당 (Dynamic Memory Allocation) 정적은 정해진 크기, 동적은 알고리즘에 따라서 다른 메모리를 할당하는 것이다ㅎㅎ 조금 더 세부적으로 배워보자. 정적 메모리 할당 - 프로그램 시작 전에 미리 정해진 크기의 메모리를 할당하는 것 - 처음에 결정된 크기보다 더 큰 입력이 들어오면 처리 못함 - 더 작은 입력이 들어온다면 남은 메모리 낭비 딱봐도 쉽지만 비효율적이라는 것이 느껴지지 않는가? 우리가 처리했던 대부분의 메모리는 이렇게 할당 되었.. #16 [C 자료구조] 열거형(enum)과 공용체(union) 열거형에 대하여 변수가 가질 수 있는 값들을 미리 열거 해놓은 자료형이 있다. 예를 들어 일주일은 월화수목금토일 만 있으면 되고, 1년은 1월부터 12월까지만 있으면 된다. 이러한 자료형을 enumeration 줄여서 enum(열거형) 이라고 한다. 예시는 다음과 같다. 이를 활용해 숫자를 입력하면 TV가 선택되는 코드를 짜보자. #include enum type { tube, lcd, plasma, projection }; int main(void) { enum type num; while (1) { printf("TV 종류(코드) : "); scanf("%d",&num ); switch( num ) { case tube: printf("브라운관 TV 선택!\n\n"); break; case lcd: .. #15 [C 자료구조] 포인터와 구조체 배열을 가리키는 포인터가 있었다면 구조체를 포인터도 당연히 있을 것! 오늘은 구조체를 어떻게 가리키는지 살펴보자. 우선 포인터는 이렇게 생성한다. struct student *ps 구조체에서 포인터가 사용되는 경우는 두 가지이다. 1) 포인터가 구조체를 가리킴 2) 포인터가 구조체의 멤버가 됨 1) 포인터가 구조체를 가리킴 struct student s = { 123123, 12341, 1234} struct student *p p = &s 이렇게 p는 구조체 s를 가리키는 포인터가 된다. 포인터로 구조체 내 인자들을 가리키는 방법은 다음과 같다. (1) (*p).name // 멤버 참조 연산자인 . 보다 참조연산자 *의 우선순위가 더 높다 (2) p->name 2) 포인터가 구조체의 멤버가 됨 stru.. 이전 1 2 3 4 다음
