BFS(Breath First Search)는 말그대로 너비를 우선 탐색한다. DFS는 연결된 노드를 계속 들어가며 재귀호출하는 방식이었지만 BFS는 이와 달리 queue를 이용해서 루트노드에 연결되어있는 모든 노드를 다 탐색 후에 다음 깊이로 들어간다. 소스로 확인하면 다음과 같다. 1234567891011121314151617181920212223242526272829303132333435#include#includeusing namespace std;int map[10][10]={0};int visit[10]={0};queue q;int num; void bfs(int v){ cout
안녕하세요 오늘은 자료구조의 연결 리스트를알아보겠습니다. 리스트란 순서를 가진 항목들의 모임이라고 할 수 있습니다. 예를 들어 요일(월화수목금토일), 한글자음(ㄱㄴㄷ...) 등 순서가 있는 항목들로 이루어진 집합입니다. 기존의 배열과는 다르게 메모리를 동적으로 할당하여 메모리의 낭비없이 자유롭게 삽입 및 삭제가 가능하고, 그 크기가 제한되지 않습니다. 다만, 구현이 복잡한 단점이 있습니다. 위의 그림처럼 하나의 박스를 노드(Node)라고 하는데, 한 노드에는 데이터필드와 링크필드로 구성되어있습니다. 데이터필드는 해당 노드의 값이고 링크필드는 다음에 오는 노드를 가리키는 포인터값이 들어갑니다. 가장 첫 노드를 가리키는 포인터는 헤드포인터, 가장 마지막노드가 가리키는 link값은 NULL이 들어갑니다. 1 ..
안녕하세요, 이번엔 자료구조의 아주 기본인 큐를 배워보도록 하겠습니다. 큐(Queue)란 사전적 의미로 줄, 대기행렬, 꼬리 등의 의미가 있는데요, 놀이공원 같은 곳에서 먼저 줄을 서면 먼저 입장하게 되는데 큐는 이러한 방식입니다. 지난번에 배운 스택과 어떤 차이점이 있을까요? 리스트의 한쪽 끝에서만 삽입과 삭제가 일어나기 때문에 최근에 넣은 데이터가 먼저 나오는 스택(LIFO 방식)과 달리 큐는 먼저 넣은 데이터가 먼저 나오는 FIFO(First In First Out) 방식으로, 리스트의 한쪽에서는 삽입, 다른 한쪽에서는 삭제가 가능한 구조입니다. 스택과의 매우 큰 차이를 아시겠나요? 그림으로 보면 다음과 같습니다. 위 그림처럼 한쪽(front)에서는 삭제가 가능하고, 다른 한쪽(rear)에서는 삽입..
안녕하세요 이번엔 C언어로 Stack을 구현해보겠습니다. 자료구조의 매우 기초적인 개념인 Stack이란 영어로 쌓아놓은 더미란 뜻입니다. LIFO(Last In First Out) 방식으로 가장 최근에 들어온 데이터가 가장 먼저 나가게 됩니다. 스택의 구조는 위와 같이 더미처럼 구성되어 있고 push&pop을 통해 데이터를 입력 또는 출력 할 수 있습니다. 단, 출력시에는 더미의 가장 위에있는 데이터를 빼온 다는 것이 매우 중요합니다. 이제 C언어로 구현해보도록 하겠습니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 #..
안녕하세요 오늘은 C언어로 재귀함수를 구현해보겠습니다. 저번에 설치한 Dev C++ 컴파일러를 사용하였습니다. 재귀함수란 자기 자신을 호출하는 함수인데요, 팩토리얼(factorial)이라는 함수를 구현하면서 살펴보겠습니다. 12345678910111213141516#include int factorial(int n){ if(n==0) return 1; else return n*factorial(n-1);}int main(){ int n; printf("수를 입력하세요: "); scanf("%d",&n); printf("%d",factorial(n)); return 0; } cs 전체 소스코드입니다. factorial이라는 새로운 함수를 main함수 위에 정의해주었구요, 값을 알고싶은 변수 n이 1이면 1..
- Total
- Today
- Yesterday