연결리스트(Linked List)
배열과는 다르게 각 노드가 차례대로 연결된 List이다.
그 종류는.
1. 단방향 링크드 리스트
요소를 단방향으로만 탐색이 가능하며, 지나간 원소를 다시 탐색하기 위해서는 다시 Head부터 탐색을 해야 한다.
2. 양방향 링크드 리스트
요소를 양방향으로 탐색이 가능하며, 지나간 원소를 다시 탐색이 가능하다. 단방향 링크드 리스트에 비해 연산과정과 메모리가 많이 든다.
3. 순환 링크드 리스트
마지막 노드의 next가 head를 가르키는 링크드 리스트 계속해서 탐색이 가능하며, 끝점을 표시하는 변수가 필요하다.
특징
- 특정 인덱스를 상수 시간에 접근 할 수 없다.
- 배열과 달리 리스트 맨 앞 또는 맨 뒤에 상수 시간에 삽입/삭제가 가능하다.
- 노드를 이용하기 때문에 삽입/삭제 시에 메모리 할당, 해제가 필요하다.
다만 가비지 콜렉터가 작동하는 언어라면 해당 과정은 굳이 필요없다.
구현
노드 선언
struct Node {
int value;
Node* next;
};
Linked List 선언
class LinkedList {
private:
Node* head = nullptr;
int listSize = 0;
};
Push함수 구현
void Push(int value) {
listSize++; //리스트의 원소가 증가한다는 표시.
Node* newNode = new Node; //노드를 선언한다.
newNode->value = value; //노드에 값을 넣는다.
newNode->next = nullptr; //마지막에 추가할 것이기 때문에 널 포인터를 넣어준다.
Node* cursor = head; //
if (cursor == nullptr) { //만약 리스트가 비어있다면,
head = newNode; //첫 노드를 head로 만들어준다.
}
else { //비어있지 않다면,
//마지막 노드까지 탐색.
while (cursor->next != nullptr) {
cursor = cursor->next;
}
cursor->next = newNode; //마지막 노드의 next에 새로운 노드를 추가한다.
}
return;
}
Pop 구현
bool Pop(int value) {
if (head == nullptr) return false; //리스트가 비었다면, 리턴.
if (head->value == value) {
Node* t = head; //메모리 해제를 위해 변수로 head의 포인터를 담고.
head = head->next; //head는 다음 노드를 가르킨다.
delete(t); //메모리 해제 후
listSize--;
return true; //리턴
}
Node* cursor = head; //처음 노드를 가르키고,
Node* next = cursor->next; //다음 노드를 가르킨다.
while (next!=nullptr && next->value != value) { //제거하고자 하는 값을 찾음
next = next->next;
cursor = cursor->next;
}
if (next == nullptr) return false; //리스트를 전부 탐색 했다면, 값이 없는 경우.
cursor->next = next->next; //값을 찾았다면 연결을 해제 시켜주고
delete(next); //메모리 해제 후
listSize--;
return true; //리턴
}
원소 출력
void printNode(void) {
Node* t = head;
while (t != nullptr) {
cout << t->value << " ";
t = t->next;
}
cout << "\n";
return;
}
전체 코드
struct Node {
int value;
Node* next;
};
class LinkedList {
private:
Node* head = nullptr;
int listSize = 0;
public:
void Push(int value) {
listSize++; //리스트의 원소가 증가한다는 표시.
Node* newNode = new Node; //노드를 선언한다.
newNode->value = value; //노드에 값을 넣는다.
newNode->next = nullptr; //마지막에 추가할 것이기 때문에 널 포인터를 넣어준다.
Node* cursor = head; //
if (cursor == nullptr) { //만약 리스트가 비어있다면,
head = newNode; //첫 노드를 head로 만들어준다.
}
else { //비어있지 않다면,
//마지막 노드까지 탐색.
while (cursor->next != nullptr) {
cursor = cursor->next;
}
cursor->next = newNode; //마지막 노드의 next에 새로운 노드를 추가한다.
}
return;
}
bool Pop(int value) {
if (head == nullptr) return false; //리스트가 비었다면, 리턴.
if (head->value == value) {
Node* t = head; //메모리 해제를 위해 변수로 head의 포인터를 담고.
head = head->next; //head는 다음 노드를 가르킨다.
delete(t); //메모리 해제 후
listSize--;
return true; //리턴
}
Node* cursor = head; //처음 노드를 가르키고,
Node* next = cursor->next; //다음 노드를 가르킨다.
while (next!=nullptr && next->value != value) { //제거하고자 하는 값을 찾음
next = next->next;
cursor = cursor->next;
}
if (next == nullptr) return false; //리스트를 전부 탐색 했다면, 값이 없는 경우.
cursor->next = next->next; //값을 찾았다면 연결을 해제 시켜주고
delete(next); //메모리 해제 후
listSize--;
return true; //리턴
}
int getSize(void) {
return listSize;
}
void printNode(void) {
Node* t = head;
while (t != nullptr) {
cout << t->value << " ";
t = t->next;
}
cout << "\n";
return;
}
};
응용문제
에디터
https://www.acmicpc.net/problem/1406
1406번: 에디터
첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수
www.acmicpc.net
솔루션
마우스 커서 기준으로 왼쪽 오른쪽 부분으로 두개의 영역으로 나뉜다.
따라서 2개의 스택을 이용하여 문제를 해결했다.
한개는 마우스 커서 왼쪽에 있는 문자열
다른 한개는 마우스 커서 오른쪽에 있는 문자열
마우스 커서는 왼쪽, 오른쪽으로 한칸씩 움직일 수 있으므로, 스택을 이용하면 쉽게 해결 할 수 있다.
마우스 커서는 맨 오른쪽에서 시작하기 때문에 왼쪽 영역 스택에 문자열을 차례대로 삽입한다.
그리고 명령에 맞춰 스택을 옮겨 담거나, 추가하거나, 제거한다.
코드
#include <iostream>
#include <stack>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int N;
string str;
cin >> str;
cin >> N;
stack<char> S; //기본 문자열을 담는다.
//스택 S는 마우스 커서 오른쪽에 있는 값.
stack<char> Cursor; //현재 마우스 커서의 위치 기준 왼쪽에 있는 값.
for (int i = 0; i < str.size(); i++) {
Cursor.push(str[i]);
}
while (N--) {
char c;
cin >> c;
if (c == 'L') { //커서를 왼쪽으로 옮김.
if (Cursor.empty()) continue; //왼쪽이 비었다면 무시.
else {
S.push(Cursor.top());
Cursor.pop();
}
}
else if (c == 'D') { //커서를 오른쪽으로 한 칸 옮김.
if (S.empty()) continue; //오른쪽이 비었다면 무시.
else {
Cursor.push(S.top());
S.pop();
}
}
else if (c == 'B') { //왼쪽에 존재하는 문자 한개를 제거
if (Cursor.empty()) continue; //왼쪽에 없다면 무시.
else {
Cursor.pop();
}
}
else if (c == 'P') {
char val;
cin >> val;
Cursor.push(val);
}
}
while (!Cursor.empty()) { //커서를 맨 왼쪽으로 옮김.
S.push(Cursor.top());
Cursor.pop();
}
while (!S.empty()) {
cout << S.top();
S.pop();
}
}
심화문제
히스토그램
https://www.acmicpc.net/problem/1725
1725번: 히스토그램
첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은
www.acmicpc.net
솔루션
스택을 이용하여 직사각형 넓이의 최대 값을 찾는다.
스택을 이용한 심화 문제라 접근이 쉽사리 떠올리지 않는다.
먼저 i번째 배열의 값이 들어올 때, 스택에 담겨있는 값이 배열의 값보다 크다면 배열의 값보다 큰 높이의 직사각형으로 만들 수 있는 직사각형은 스택에 담겨있는 수로 만들 수 있을 것이다.
그리고, 스택에는 스택에 쌓여있는 순은 비 내림차순으로 쌓이도록 한다.
이렇게 규칙을 정하면,
다음과 같은 규칙을 갖는다.
1. 스택의 Top에는 Top이전에 쌓인 높이보다 크다.
2. 현재 배열의 인덱스보다 높이가 높다.
3. Top이전에 쌓은 높이와 현재 배열의 인덱스 값 사이의 높이는 Top의 높이가 같거나 높다.
이 규칙을 통해, 스택의 Top의 높이를 저장하고, 스택에서 제거한다.
그러면 이전에 쌓인 스택의 x좌표값을 알 수 있는데, 현재 배열의 i값 까지의 길이가 너비가 된다.
따라서 높이 * 너비를 통해 답을 구할 수 있다.
그림을 통해 알아보자
와 같은 입력이 들어왔을 때,
처음에 높이가 2, x좌표가 1이 스택에 쌓인다.
높이가 1이 들어오면서, 기존에 존재하던 높이 2의 값이 뽑히면서 넓이가 계산된다.
높이가 8이 들어오면, 그냥 스택에 쌓는다.
비내림 차순이므로 쌓는다.
5번째 높이가 1이므로, 8이 다 뽑히면서 2와 5사이의 너비 2, 높이는 8을 곱해주어 16의 넓이를 도출 한다.
모든 과정을 다 걸치고 난 뒤 스택에 있는 값을 뽑으면서 가능한 넓이를 도출한다.
따라서 답은 16으로 구할 수 있다.
나는 알고리즘 수행을 할 때, 기저 상황을 없애기 위해서
높이0, x좌표 0을 넣어주고 시작하고,
마지막은 높이0, 좌표를 N까지 돌려주었다.
코드
#define ll long long int
#include <iostream>
#include <stack>
using namespace std;
int N;
ll arr[100003];
stack<pair<int,ll>> S;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> N;
for (int i = 0; i < N; i++) {
cin >> arr[i];
}
S.push({0,0});
ll ans = 0;
for (int i = 0; i <= N; i++) {
while (S.top().second > arr[i]) { //직사각형 구간의 합을 구해야 함.
ll height = S.top().second; //높이는 해당 스택에 담긴 값.
S.pop();
ll width = (i - S.top().first);
ans = max(ans, height * width);
//S.pop();
}
S.push({ i + 1,arr[i] });
}
cout << ans << "\n";
return 0;
}
'스터디' 카테고리의 다른 글
| 알고리즘 스터디 - 큐 (0) | 2023.07.20 |
|---|---|
| 우선순위 큐 (0) | 2023.07.04 |
| Deque 활용 문제 풀이 (0) | 2023.06.01 |
| 1-1 중복이 없는가? (0) | 2023.05.11 |
