선형 구조Permalink
데이터를 순차적으로 한 줄로 표기한 자료구조로 선형리스트, 연결리스트, 스택, 큐가 있다.
순회를 하는 방법
반복문(for, while)
선형리스트 (Linear List)
데이터를 논리적인 순서대로 메모리에 연속하여 저장하는 구현 방식을 의미하며,
주로 고정된 크기를 가진 배열을 통해 구현한다.
그렇기 때문에 각 원소의 순서가 정해져 있으며, 각 원소의 인덱스를 사용할 수 있다.
이로인해 데이터 검색에 효율적이지만, 삽입과 삭제 시 크기를 더 할당하거나, 모든 데이터를 이동해줘야하기 때문에 비효율적이다.
연결리스트 (Linked List)
연결리스트는 노드를 통해 연결하는 리스트를 말한다.
선형리스트와 달리 고정이 아닌, 가변적인 크기의 리스트를 가진다.
따라서 데이터를 삽입, 제거 시 크기 할당이나, 데이터를 이동할 필요 없이 다음 노드를 추가하거나, 제거할 수 있다.
다만, 검색에 대해서는 선형리스트와 다르게 원하는 데이터를 한번에 찾아낼 수 없고, 리스트를 전부 탐색해야 한다.
주로 데이터 삽입, 제거가 많이 발생하는 프로그램이라면 연결리스트가 유리하고, 탐색이 주가 되는 프로그램이라면 선형리스트를 사용하는 것이 유리하다.
스택, 큐
트리 (Tree)
트리는 노드가 나무 가지처럼 연결되어 있는 비선형 자료구조이다.
마치 나무를 뒤집어 놓은 모습과 유사하다.
트리 내 또 다른 하위 트리가 있고, 그 안에 또 다른 하위 트리가 있는 재귀적인 구조를 가진다.
컴퓨터의 디렉토리 구조가 트리 구조이다.
그래프 (Graph)
그래프는 노드와 노드를 연결하는 간선을 모아놓은 자료구조이다.
트리와 많이 비교가 되는데 트리 역시 그래프의 형태이나, 그래프는 방향이 있거나, 없을 수 있으며,
루트 노드라는 개념이 없다. 또한 사이클이 가능한 형태로 구성되어 있다.
순회를 하는 방법
DFS, BFS 알고리즘 사용
그래프를 표현할 때는 인접행렬과 링크드리스트를 사용하는 방식이 있다.
보통 알고리즘 문제를 푸는데 있어서는 인접행렬을 활용한 방식을 많이 사용한다.
다음은 인접행렬을 이용해 그래프를 표현하고 1번 노드가 연결되어있는 다른노드의 종류를 표현하는 예제 코드이다.
int main()
{
int map[4][4] =
{
0,0,1,1,
1,0,1,1,
0,1,0,0,
0,0,0,0,
};
int target = 1;
for (size_t i = 0; i < 4; i++)
{
if (map[target][i] != 0)
{
std::cout << i << "번";
}
}
return 0;
}
C++
복사
가중치가 있는 그래프
연습문제 : 각 노드가 갈수 있는 노드번호와 비용을 출력을 전부 해보자!
문제 1번
4칸짜리 큐를 링크드리스트로 만들어주세요.
그리고 아래와 같이 입력 받았을때 최종 큐의 결과를 출력 하세요.
입력 예제
3
E 5
E 6
E 9
출력 결과
5 6 9
struct Node
{
int data;
Node* next;
};
Node* head = NULL;
Node* tail = NULL;
void push(int data)
{
Node* newNode = new Node();
newNode->data = data;
newNode->next = NULL;
if (head == NULL)
{
head = newNode;
tail = newNode;
}
else
{
tail->next = newNode;
tail = newNode;
}
}
void pop()
{
if (head == NULL)
{
std::cout << "Queue is empty" << std::endl;
}
else
{
Node* temp = head;
head = head->next;
delete temp;
}
}
Python
복사
문제 2번
ABC 타입 구조체는 다음과 같습니다.
ABC 타입 구조체 변수 a, b를 만들고, 다음과 같이 값을 초기화 해주세요.
구조체 포인터 p, g를 만들고,
p는 a를 가르키도록 하고
g는 b를 가르키도록 해주세요.
이제 p와 g를 이용해서 p와 g가 가르키고 있는 곳의 값들을 출력 해주세요.
출력 결과
1 2 3 4
10
7 8 9 10
15
문제 3번
짜리 동전이 있습니다.
동전교환할 금액을 입력 받아주세요.
가장 큰 금액의 동전부터 교환해주려고 합니다.
각 동전마다 몇개의 동전으로 교환 할 수 있는지 출력 하세요.
ex)
입력: 170
35:4개
17:1개
7:1개
1:6개
입력 예제
170
출력 결과
35:4개
17:1개
7:1개
1:6개
문제 4번
한문장을 입력 받으세요.(최대 10글자)
몇가지 종류의 알파벳이 존재하는지 출력 하세요.
알파벳은 A ~ Z 까지 나올 수 있습니다
1.
ex)
입력: AGGABC
출력: 4종류
(A, G, B, C 이렇게 네 종류의 알파벳이 있으므로 4 입니다)
입력 예제
AGGABC
출력 결과
4종류
문제 5번
4x4 배열에 병정개미 4마리를 입력하여 배치 합니다.
숫자 1이 병정개미라고 했을 때
만약, 아래와 같이 입력하면 붙어있는 개미가 있어 위험한 상태 입니다.
1 0 0 0
0 1 1 0
0 0 0 1
0 0 0 0
4x4 배열에 병정개미 4마리를 배치한 값을 입력받고,
개미의 상태가 안전하면 "안전한 상태",
안전하지 않으면 "위험한 상태"라고 판단하여 출력 해주는 프로그램을 만들어 주세요.
입력 예제
1 0 0 0
0 1 1 0
0 0 0 1
0 0 0 0
출력 결과
위험한 상태
문제 6번
4x10 char 배열에 4문장을 대문자로 입력 받으세요.(최대 10글자)
가장 긴 문장과 가장 짧은 문장을 찾아내고 모두 소문자로 바꾸어주세요.
(가장 긴문장과 짧은 문장은 한개씩 존재합니다)
ex)
[입력]
ABC
BBBQ
BT
JOW
[출력]
ABC
bbbq
bt
JOW
입력 예제
ABC
BBBQ
BT
JOW
출력 결과
ABC
bbbq
bt
JOW
문제 7번
입력 예제
1 1 1 1
출력 결과
1 1 1 1
1 2 3 4
1 3 6 10
문제 8번
9개의 숫자를 입력 받으세요.
그리고 가장 큰 숫자와 두번째로 큰 숫자를 찾아 값과 좌표를 출력 하세요.
ex)
[입력]
3 5 1
9 2 7
6 11 3
[출력]
첫번째:11(2,1)
두번째:9(1,0)
입력 예제
3 5 1
9 2 7
6 11 3
출력 결과
첫번째:11(2,1)
두번째:9(1,0)
문제 9번
4x4 배열의 땅이 있습니다.
#으로 표시되는 아기돼지 집 세곳을 입력 받으세요.
그리고 늑대에게 잡아먹히지 않도록 벽을 감싸주세요(8방향)
벽을 짓느라 아기돼지집을 부수면 안됩니다.
(빈공간은 언더바_로 출력 해주세요)
Hint: Direct를 이용해주세요.
입력 예제
0 0
2 2
0 3
출력 결과
#@@#
@@@@
_@#@
_@@@
문제 10번
A, B, C, D의 관계도가 그려져 있고 이것을 배열로 표현 하면
아래와 같이 표현 할 수 있습니다.
위 배열에서 가장 많이 연결된 알파벳은 A 입니다.
위와 같이 4x4 배열에 연결상태를 입력받고, 가장 많이 연결된 알파벳을 출력 하세요.
입력 예제
0 1 1 1
1 0 1 0
1 1 0 0
1 0 0 0
출력 결과
A
문제 11번
숫자 1의 위치를 입력 받으세요. (y, x)
그리고 1의 위치를 찾아내서 위, 아래, 왼쪽, 오른쪽칸의 빈칸에 숫자 2를 채워주세요.
그리고 숫자 2를 찾아서 모든 숫자 2에서 위, 아래, 오른쪽, 아래칸의 빈칸에 숫자 3을 채워주세요.
이 과정을 반복해서 배열을 아래와 같이 배열을 꽉 채운 후 결과를 출력 해주세요.
입력 예제
2 2
출력 결과
5 4 3 4
4 3 2 3
3 2 1 2
4 3 2 3
문제 12번
드라마의 삼각관계를 나타낸 그래프입니다.
그래프를 인접행렬로 작성 해 주세요.
인접행렬을 이용해서
다섯명의 사람 중 가장 인기가 좋은 사람을 찾아서 출력 해주세요.
(A -----> B는 A가 B를 좋아한다는 뜻입니다.)
출력 결과
Bob
문제 13번
아래와 같이 5개 노드를 가진 그래프를 인접행렬로 하드코딩 해 주세요
그리고 어떤 간선들이 존재하는지 아래와 같이 출력 해주세요.
(입력값은 없습니다)
출력 결과
A B 1
A C 7
A D 2
B C 8
B E 5
C D 3
C E 6
D A 0
D C 7
E B 1
E C 7
문제 14번
링크드리스트로 라인을 구현하고자 합니다.
입력받은 문자들을 모두 링크드리스트에 등록을 하고
등록이 끝난 후
다시 처음부터 출력을 해 주세요
•
add 함수를 만들어서 작성 해 주세요
ex)
[입력]
입력 예제
4
A B C D
출력 결과
A B C D
문제 15번
테트리스게임에서는 한줄이 꽉 찰때 그 줄은 사라지게 됩니다.
블럭 상태를 입력 받고, 꽉찬줄이 터트려지고 난 후의 결과를 출력 해주세요.
예시)
•
터진 줄만 제거하면 됩니다. 위에있는 블럭이 완전히 바닥으로 떨어지는 것이 아닙니다.
입력 예제
0 0 0 0
0 0 1 0
1 1 1 1
1 1 1 1
0 1 0 0
출력 결과
0 0 0 0
0 0 0 0
0 0 0 0
0 0 1 0
0 1 0 0
