자료구조란?
Data structure , 자료들을 저장하는 방법
여러가지 자료를 저장하는 방법을 배우고
만들 프로그램에 적절한 곳에 적절하게 적합한 자료구조를
선택해서 사용 하면된다.
그 선택에 따라서 프로그램이 동작하는 속도와 메모리 효율이 천지차이로 작동할수도 있다.
대표적인 자료구조 : 배열, 링크드리스트, 큐, 스택, 그래프, 트리
노드
데이터를 저장하는 최소 단위
배열에서 노드는 각각의 변수 1개(1칸)을 뜻한다.
링크드 리스트
링크드리스트란 한 노드가 노드를 가르키고 있는 자료구조
여러개의 노드로 이루어져 있다.
링크드리스트 한 노드가 노드를 가르키는데
그 한개를 노드라고한다.
구조체 (클래스) 포인터를 이용해서 구현한다.
배열 vs 링크드리스트
배열의 단점
10칸 짜리 배열을 만들었는데 내가 데이터를 12칸을 쓰고싶다.
쉽지않다. 12칸짜리 배열을 만들어서 복사해주면된다.
그 과정이 연산이 너무 많아지기 떄문에 비효율적이다.
링크드리스트는 실행도중에 추가적으로 데이터를 추가해줘도
큰 부담이 없다.
노드만 생성해주고 주소만 연결해주면 되니까
중간에 데이터를 삽입하건 삭제하여도 큰 부담이 없다.
링크드 리스트를 써야 할떄는 실행도중에
데이터가 자주 삽입되거나 삭제될떄 사용하면 좋다.
메모리의 동적 할당(dynamic allocation)
데이터 영역과 스택 영역에 할당되는 메모리의 크기는 컴파일 타임(compile time)에 미리 결정됩니다.
하지만 힙 영역의 크기는 프로그램이 실행되는 도중인 런 타임(run time)에 사용자가 직접 결정하게 됩니다.
이렇게 런 타임에 메모리를 할당받는 것을 메모리의 동적 할당(dynamic allocation)이라고 합니다.
포인터의 가장 큰 목적은 런 타임에 이름 없는 메모리를 할당받아 포인터에 할당하여, 할당받은 메모리에 접근하는 것입니다.
C언어에서는 malloc() 함수 등의 라이브러리 함수를 제공하여 이러한 작업을 수행할 수 있게 해줍니다.
C++에서도 C언어의 라이브러리 함수를 사용하여 메모리의 동적 할당 및 해제를 할 수 있습니다.
하지만 C++에서는 메모리의 동적 할당 및 해제를 위한 더욱 효과적인 방법을 new 연산자와 delete 연산자를 통해 제공합니다.
new 연산자
C언어에서는 malloc()이나 calloc() 함수 등을 이용하여 메모리의 동적 할당을 수행합니다.
C++에서도 위의 함수를 사용할 수 있지만, 더 나은 방법인 new 연산자를 이용한 방법을 제공하고 있습니다.
C++에서 new 연산자는 다음과 같은 문법으로 사용합니다.
문법
타입* 포인터이름 = new 타입;
첫 번째 타입은 데이터에 맞는 포인터를 선언하기 위해, 두 번째 타입은 메모리의 종류를 지정하기 위해 사용됩니다.
만약 사용할 수 있는 메모리가 부족하여 새로운 메모리를 만들지 못했다면, new 연산자는 널 포인터를 반환합니다.
new 연산자는 자유 기억 공간(free store)이라고 불리는 메모리 공간(memory pool)에 객체를 위한 메모리를 할당받습니다.
또한, new 연산자를 통해 할당받은 메모리는 따로 이름이 없으므로 해당 포인터로만 접근할 수 있게 됩니다.
delete 연산자
C언어에서는 free() 함수를 이용하여 동적으로 할당받은 메모리를 다시 운영체제로 반환합니다.
이와 마찬가지로 C++에서는 delete 연산자를 사용하여, 더는 사용하지 않는 메모리를 다시 메모리 공간에 돌려줄 수 있습니다.
C++에서 delete 연산자는 다음과 같은 문법으로 사용합니다.
문법
delete 포인터이름;
다음 예제는 런 타임에 int형과 double형 데이터를 위한 메모리를 할당받고, delete 연산자를 사용하여 더 이상 사용하지 않는 메모리를 반환하는 예제입니다.
예제
int* ptr_int = new int;
*ptr_int = 100;
double* ptr_double = new double;
*ptr_double = 100.123;
cout << "int형 숫자의 값은 " << *ptr_int << "입니다." << endl;
cout << "int형 숫자의 메모리 주소는 " << ptr_int << "입니다." << endl;
cout << "double형 숫자의 값은 " << *ptr_double << "입니다." << endl;
cout << "double형 숫자의 메모리 주소는 " << ptr_double << "입니다." << endl;
delete ptr_int;
delete ptr_double;
C++
복사
Node의 동적 할당
struct Node
{
int data;
Node* next;
};
Node node;
Node* pp = new Node;
pp->data = 3;
delete pp;
C++
복사
그럼 이제 앞서 만들어본 Node를 활용하여 링크드리스트를 구현해보자.
#include <iostream>
#include <list>
struct Node
{
int data;
Node* next;
};
Node* head = nullptr;
Node* tail = nullptr;
void AddNode(int data)
{
if (head == nullptr)
{
//헤드에 추가를 해준다.
head = new Node;
head->data = data;
head->next = nullptr;
tail = head;
}
else
{
// 제일 마지막 노드 뒤에 추가를 해준다.
tail->next = new Node;
tail->next->data = data;
tail->next->next = nullptr;
tail = tail->next;
}
}
int main()
{
AddNode(3);
AddNode(4);
AddNode(5);
//while, for 문을 활용한 linked list 순회
//Node* p = head;
//while (true)
//{
// if (p == nullptr)
// break;
// std::cout << p->data;
// p = p->next;
//}
for (Node* p = head
; p != nullptr
; p = p->next)
{
std::cout << p->data;
}
return 0;
}
C++
복사
연습문제
링크드리스트의 두 번째 시간입니다.
메모리 Heap 공간에 Node를 만드는 방식으로 링크드리스트를 만듭니다.
그리고 For문과 While로 탐색하여, 링크드리스트에 익숙 해 집니다.
힙에 구조체 변수 만들기
문제 1번
BBQ구조체를 만들어주세요.
그리고 new연산자 또는 malloc 함수를 이용하여 힙에 변수를 만들어 주세요.
그리고 숫자 2개를 이곳에 입력 받고 5를 더한 값을 출력 해주세요.
입력 예제
1 4
출력 결과
6 9
new(malloc)으로 변수 만들기
문제 2번
new (or malloc)을 이용하여 char 변수 3개를 만들어주세요.
그리고 문자 3개를 이 변수에 입력 받고,
모두 대문자 인지 아닌지 구분하는 프로그램을 작성해주세요.
모두 대문자이면 "모두대문자"
소문자가 하나라도 있으면 "소문자있음" 이라고 출력하세요.
입력 예제
A K T
출력 결과
모두대문자
트리식으로 링크드리스트 구현하기
문제 3번
new 또는 malloc 을 이용해서 아래의 그림처럼 연결 해주세요
(입력 및 출력 값은 없습니다)
HINT
① head 포인터가 필요합니다.
② head -> left = new or malloc ()
head -> right = new or malloc ()
head -> right -> left = new or malloc ()
흔적을 쫓아가자
문제 4번
다음 그림과 같이 노드를 만들어주세요.
이제 한 문장을 입력받아주세요.
H는 Head가 가르키는 값을 출력하라는 의미이고,
HR은 Head->Right 값을 출력하라는 의미입니다.
또 만약
HLL을 입력받는다면 Head->Left->Left의 값을 출력하고
HRR을 입력받는다면 Head->Right->Right 값을 출력하라는 의미입니다.
H / HR / HL / HLL / HLR에 대해 적합한 값을 출력하는 프로그램을 작성 해 주세요.
입력 예제
HLR
출력 결과
E
동굴 탐험하기
문제 5번
new / malloc을 이용해서 위와같은 노드를 구성해주세요.
이제 while문을 이용해서 처음부터 끝까지 출력 해주세요.
(입력은 없습니다)
출력 결과
3 5 4 2
마지막 노드를 찾아라
문제 6번
총 5개의 문자를 입력받습니다.
new 또는 malloc을 활용해, 입력받은 문자들을 링크드리스트에 저장 해 주세요.
만약 Q T P K Q 를 입력받았다면 아래와 같이 링크드리스트가 만들어집니다.
그리고 head pointer를 이용하여 가장 마지막 노드의 값을 출력하세요.
입력 예제
Q T P K Q
출력 결과
Q
아침드라마 : 삼각관계
문제 7번
아침드라마의 재미는 연인들의 관계입니다.
화살표는 사랑하는 사람을 나타낸 표식입니다.
아래와 같은 구성으로 관계가 되어 있을때 링크드리스트로 구현해주세요.
이제 head를 이용해서 son의 Love1과 Love2가 누구인지 출력 해주세요
조합한 숫자에 5 더하기
문제 8번
숫자 하나만 입력 받으세요. (int 변수에다가 숫자 하나 입력받으세요)
6자리 숫자만 입력할 수 있습니다.
두 번째 자리 숫자와 네 번째 자리 숫자를 추출하고 조합하세요
그리고 만들어진 두 자리 숫자에 5를 더한 값을 출력 해주세요.
입력 예제
354129
출력 결과
47
내려오는 물방을 갯수 세기
문제 9번
4 x 4 배열을 입력받아주세요. #은 빈칸을 의미합니다.
각 세로줄마다 몇개의 문자가 있는지 출력 하세요.
만약 아래와 같이 입력받았다면,
#AFG
B##E
###D
#E##
입력 예제
#AFG
B##E
###D
#E##
출력 결과
1 2 1 3
짝궁
문제 10번
B와 F로 된 문장을 입력 받고 짝이 맞는지 알려주는 프로그램을 작성해주세요.
(최대 글자수는 10글자)
B는 Begin을 뜻하고(시작) F는 Finish를 뜻합니다.(종료)
그리고 B와 F는 서로 짝이 맞아야 합니다.
아래 내용을 참고하세요.
BBFF인 경우는 짝이 맞습니다
시작이 2번 되었으니 끝 신호가
2번 와야 하기 때문입니다
짝이 맞으면 "짝이맞음" 출력
안맞으면 "짝이안맞음" 출력
입력 예제
BFBFBF
출력 결과
짝이맞음
블럭 굴리기
문제 11번
아래 그림과 같이 3 x 3의 네모블럭이 있습니다. 하드코딩 하세요.
그리고 숫자 하나를 입력 받으세요.
이 입력 숫자는 블럭을 오른쪽으로 굴릴 횟수 입니다.
입력한 숫자만큼 오른쪽으로 굴려 숫자 위치가 변경된 상태를 출력 해주세요.
•
빈칸은 언더바('_')로 바꾸어서 출력 해 주세요
[HINT]
오른쪽으로 한번 굴리면 좌표가 어떻게 바뀌는지 써 보세요
숫자가 들어있는 cube[3][3] 배열이 있고
돌린 결과를 저장할 result[3][3] 배열을 한개 더 만든다.
이동할 좌표 (y, x) ( result[3][3] <-- cube[3][3] )
0,2 <-- 0,0
1,2 <-- 0,1
2,2 <-- 0,2
0,1 <-- 1,0
1,1 <-- 1,1
2,1 <-- 1,2
0,0 <-- 2,0
1,0 <-- 2,1
2,0 <-- 2,2
위 이동 좌대로 for문을 돌리면
for (y=0; y<3; y++) {
for (x=0; x<3; x++) {
result[_][_] = input[y][x];
}
}
입력 예제
3
출력 결과
4_1
5__
_3_
배열 만들어 값 넣기
문제 12번
2진수형태의 한 문장을 입력 받으세요.(15글자)
그리고 5자리씩 끊어서
배열 3개에 넣고 출력 해주세요.
입력: 011011010101101 (문자열로 입력)
출력: 01101
10101
01101
입력 예제
011011010101101
출력 결과
01101
10101
01101
min과 max 찾기
문제 13번
6개의 숫자와 m과 x로 된 한 문장을 입력 받아주세요.
m은 min값을 의미하고, x는 max값을 의마합니다.
Command[0]부터~[5]까지 순서대로 탐색하면서
m이면 min값을, x면 max값을 Number배열에서 찾아 출력 하세요.
•
Number에 같은 숫자는 입력되지 않습니다.
•
한번 출력한 숫자는 다시 출력하지 않습니다.
입력 예제
3 7 4 0 9 6
mxmmxx
출력 결과
093476
주사위 던지기
문제 14번
주사위 n개로 나올 수 있는 눈금을 모두 출력 해주세요.
ex) 주사위 개수 3 입력 받으면
111
112
113
114
115
116
121
122
123
124
...
666
입력 예제
2
출력 결과
11
12
13
14
15
16
21
22
23
24
25
26
31
32
33
34
35
36
41
42
43
44
45
46
51
52
53
54
55
56
61
62
63
64
65
66
문제 14
문제 15
int main()
{
srand(time(NULL));
Array arr1(3);
Array arr2(5);
arr1.PrintArray();
arr2.PrintArray();
return 0;
}
JavaScript
복사
