IT&컴퓨터공학/자료구조&알고리즘
-
[04]C언어 연결리스트 :: 단일리스트 초기화/삽입IT&컴퓨터공학/자료구조&알고리즘 2019. 2. 8. 21:35
연결리스트에는 ① 단일연결리스트② 이중연결리스트 등이 있는데, 이번에는 단일리스트에 대해 설명해보겠습니다. 단일리스트는 바로 이런 구조를 가지고 있습니다. 이 단일리스트를 뜯어보면 바로 이런 모양이 나오게 되는데요.이걸 우리는 "노드 ( Node )" 라고 부릅니다. 노드는 ① Data : 데이터를 저장하는 장소② 화살표 : 다른 변수를 가리키기 위한 장소이렇게 두가지로 이루어져 있어요. 우리가 데이터를 리스트에 저장할 때 마다, 이 노드라는 바구니에 데이터를 넣어두고 바구니끼리 연결하면 됩니다.바구니끼리 연결하는 건 화살표를 이용해서 연결하면 되겠죠 ? 그럼 여기서 일단 노드라는 구조체를 만들어 볼까요 ?노드 구조체 만들기123456#include typedef struct _Node { int dat..
-
[03]C언어 재귀- 하노이 타워(The tower of hanoi)IT&컴퓨터공학/자료구조&알고리즘 2019. 2. 1. 21:31
하노이 타워 문제의 이해 하노이 타워란 ? 하나의 막대에 쌓여있는 원반을 다른 하나의 원반에 그 모양 그대로 옮겨라! 이때, 원반은 한 번에 하나씩만 옮길 수 있고,'그 모양 그대로' ! 즉, 가장 아래에는 가장 큰 원반에서 시작해서 갈수록 크기가 작아져야 합니다. 하노이 타워 문제를 직접 그려보자! EX)원반이 3개있을 때 막대 B를 경유하여 막대 A → C 로 원반을 옮겨보자 1. 1번째 원반은 도착점 C로 옮긴다.2. 2번째 원반은 경유할 B로 옮긴다. 3. C에 있던 1번째 원반을 B로 옮긴다. 4. 출발점 A에 있던 3번째 원반을 도착점 C로 옮긴다. 5. 경유점 B에 있던 1번째 원반을 A로 옮긴다.6. 경유점 B에 있던 2번째 원반을 C로 옮긴다. 7. 마지막 원반을 도착점 C로 옮기면 완성..
-
[02]알고리즘의 성능분석IT&컴퓨터공학/자료구조&알고리즘 2019. 1. 31. 15:40
알고리즘의 공간복잡도 ( space complexity ) " 어떤 알고리즘이 메모리는 적게 쓰는가 ? " 그러나 메모리의 사용량은 알고리즘의 성능에 크게 영향을 미치지않는다.따라서 알고리즘을 평가할때는 아래에 나오는 시간복잡도가 더 중요하다. 알고리즘의 시간복잡도 ( time complexity ) " 어떤 알고리즘이 더 빠른가 ? " 시간복잡도를 평가하는 방법데이터수 n에 대한 연산횟수의 함수 T(n)을 구한다. 위 그래프에서는 데이터가 적을 때는 빨간색 알고리즘이 더 빠르다.그러나 데이터가 많아지면 초록색 알고리즘이 더 빠르다. 때문에 알고리즘은 상황에 맞게 판단해서 구현해야한다. T(n) 을 구하는 방법for(i=0; i
-
[01]자료구조&알고리즘에 대해서IT&컴퓨터공학/자료구조&알고리즘 2019. 1. 31. 13:59
"프로그램이란 데이터를 표현하고, 그렇게 표현된 데이터를 처리하는 것이다." 자료구조란 ? 데이터를 표현하고 저장하는 역할은 자료구조가 한다. ex) 정수를 저장하기 위해서 int 형 변수를 선언한다. / 배열을 선언해서 다양한 정보를 저장한다. 즉, 자료구조는 데이터를 저장하는 도구이다. 자료구조의 분류 선형구조 리스트, 스택, 큐 비선형구조 트리, 그래프 파일구조 순차파일, 색인파일, 직접파일 단순구조 정수, 실수, 문자, 문자열 ☞ 선형구조(linear) vs 비선형구조 선형구조 : 데이터를 일렬로 저장. 상대적으로 쉽다.비선형구조: 데이터를 나란히 저장하지 않음. 어렵다! 알고리즘이란 ? 데이터를 처리하는 역할은 알고리즘이 한다.ex) int arr[5] = {1,10,5,3,4} 에서 최솟값을 ..