二重接続リスト

**//do-while문 사용하는 이유에 대해 생각해보기**
void print_node() {
	if (Head == NULL) {
		cout << "empty node" << endl;
	}
	else {
		Node* list = Head;
		do {
			cout << list->link->data << endl;
			list = list->link;
		} while (list != Head);
	}
}

**//원형연결리스트 복습**
#include<iostream>
using namespace std;

class Node {
public:
	int data;
	Node* link;
};

Node* Head;//리스트의 마지막노드를 가리킴

**/*선행노드를 아는 경우*/**
void insert_node_A(Node*pre,Node*new_node) {
	if (Head == NULL) {
		new_node->link = new_node;
		Head = new_node;
	}
	else {
		new_node->link = pre->link;
		pre->link = new_node;
		if (pre == Head) {
			Head = new_node;
		}
	}
}
**/*선행노드를 모르는 경우(마지막)*/**
void insert_node_B(Node* new_node) {
	if (Head == NULL) {
		new_node->link = new_node;
		Head = new_node;
	}
	else {
		new_node->link = Head->link;
		Head->link = new_node;
		Head = new_node;
	}
}
**/*선행노드를 모르는 경우(처음)*/**
void insert_node_C(Node* new_node) {
	if (Head == NULL) {
		new_node->link = new_node;
		Head = new_node;
	}
	else {
		new_node->link = Head->link;
		Head->link = new_node;
	}
}
**/*특정 값의 노드 삭제*/**
void delete_node(int key) {
	if (Head == NULL)return;
	else if (Head->link==Head&&Head->data==key) {
		Head = NULL;
	}
	else {
		Node* list = Head;
		do {
			if (list->link->data == key) {
				Node* removed = list->link;
				list->link = removed->link;
				if (Head==removed) {
					Head = list;
				}
				return;
			}
			list = list->link;//논리적오류 이유: 반복 조건을 if문 안에 넣어버림.^^;
		} while (list != Head);
	}
}
**/*원형연결리스트의 출력*/**
void print_node() {
	if (Head == NULL) {
		cout << "empty node" << endl;
	}
	else {
		Node* list = Head;
		do {
			cout << list->link->data << endl;
			list = list->link;
		} while (list != Head);
	}
}

**void main() {**
	Head = NULL;
	int answer;
	int del;
	for (int i = 0; i < 3; i++) {
		cout << "노드의 데이터를 입력하세요: ";
		cin >> answer;
		Node* new_node = new Node;
		new_node->data = answer;
		new_node->link = NULL;
		insert_node_B(new_node);
	}
	print_node();
	cout << "삭제할 데이터를 입력하세요: ";
	cin >> del;
	delete_node(del);
	print_node();
}

class Node{
public:
	int data;
	Node*llink;
	Node*rlink;
	**//생성자**
	Node() {
		llink = rlink = NULL;
	}
	Node(int value) {
		data = value;
		llink = rlink = NULL;
	}
};

**/*특정 데이터를 가진 노드 삭제*/**
void delete_node(int key) {
	for (Node* list = Head->rlink; list != Head; list = list->rlink) {
		if (list->data == key) {
			list->llink->rlink = list->rlink;
			list->rlink->llink = list->llink;
			break;
		}
	}
}

void print_node() {
	cout << "[리스트의 내용 출력]" << endl;
	for (Node* list = Head->rlink; list !=Head; list = list->rlink){
		cout << list->data << endl;
	}
}

**//이중연결리스트 구현
#include<iostream>
using namespace std;

//이중연결리스트(원형리스트+헤드노드)
class Node {
public:
	int data;
	Node* llink;
	Node* rlink;
};

Node* Head=NULL;

/*선행노드를 아는 경우 노드삽입*/
void insert_node_A(Node*pre,Node*new_node) {
	new_node->rlink = pre->llink;
	new_node->llink = pre;
	pre->rlink->llink = new_node;
	pre->rlink = new_node;
}
/*선행노드 모르는 경우 첫 노드(헤드노드 제외) 삽입*/
void insert_node_B(Node* new_node) {
	new_node->llink = Head;
	new_node->rlink = Head->rlink;
	Head->rlink->llink = new_node;
	Head->rlink = new_node;
}
/*선행노드 모르는 경우 리스트 마지막에 노드에 삽입*/
void insert_node_C(Node* new_node) {
	new_node->rlink = Head;
	new_node->llink = Head->llink;
	Head->llink->rlink = new_node;
	Head->llink = new_node;
}

/*특정 데이터를 가진 노드 삭제*/
void delete_node(int key) {
	for (Node* list = Head->rlink; list != Head; list = list->rlink) {
		if (list->data == key) {
			list->llink->rlink = list->rlink;
			list->rlink->llink = list->llink;
			break;
		}
	}
}

/*노드 출력*/
void print_node() {
	cout << "[리스트의 내용 출력]" << endl;
	for (Node* list = Head->rlink; list !=Head; list = list->rlink){
		cout << list->data << endl;
	}
}

void main() {
	//헤드노드 생성
	Head = new Node;
	Head->data = NULL;
	Head->llink = Head;
	Head->rlink = Head;
	int ans;
	int data;
	for (int i = 0; i < 3; i++) {
		cout << "데이터의 값을 입력해주세요: ";
		cin >> ans;
		Node* new_node = new Node;
		new_node->data = ans;
		new_node->rlink = NULL;
		new_node->llink = NULL;
		insert_node_C(new_node);
	}
	print_node();

	cout << "삭제할 값: ";
	cin >> data;
	delete_node(data);
	print_node();
}**

#include <string>
#include <vector>
#include <cmath>
/*
1. moves가 갖고있는 값을 선택함(열)
2. 같은 열 내에서 행의 값이 0이 아닌 가장 큰 인덱스를 찾음.
3. 해당 인덱스의 값을 can에 넣고 해당 인덱스의 값은 0으로 바꿈. 
4. 반복을 수행하는 과정에서 연속적으로 중복인 원소가 존재하면 해당 인덱스 두개를 삭제해야 함. 
5. 삭제할 때 답에 2씩 더함.
*/
using namespace std;

int solution(vector<vector<int>> board, vector<int> moves) {
    int answer = 0;
    vector<int> can;
    
    //board의 제곱근 구하여 N의 값을 찾는다
    int idx=sqrt(board.size());

    //int j: 열(moves가 갖고있는 값)
    //int i: 상하로 행 탐색(4-3-2-1-0 원소값 중 0이 아닌 값을 발견하면 리턴 종료)
    for(int j=0;j<moves.size();j++){        
        for(int i=idx-1;i==0;i--){            
            if((board[i][moves[j]-1])!=0){
                can.push_back(board[i][moves[j]-1]);
                //한번 크레인에 선택된 원소는 0으로 처리
                board[i][moves[j]-1]=0; 
            }
        }
    }
    if(can.size()>=2){
        for(int k=can.size()-1;k==0;k--){
            if(can[k]==can[k-1]){
                answer+=2;
                can.erase(can.begin()+k , can.begin()+k-1);
            }
        }
    }
    
    return answer;
    }

#include <string>
#include <vector>
/*
1. moves가 갖고있는 값을 선택함(열)
2. 같은 열 내에서 행의 값이 0이 아닌 가장 큰 인덱스를 찾음.
3. 해당 인덱스의 값을 can에 넣고 해당 인덱스의 값은 0으로 바꿈. 
4. 반복을 수행하는 과정에서 연속적으로 중복인 원소가 존재하면 해당 인덱스 두개를 삭제해야 함. 
5. 삭제할 때 답에 2씩 더함.
*/
using namespace std;

int solution(vector<vector<int>> board, vector<int> moves) {
    int answer = 0;
    vector<int> can;

    //int j: 열(moves가 갖고있는 값)
    //int i: 상하로 행 탐색(4-3-2-1-0 원소값 중 0이 아닌 값을 발견하면 리턴 종료)
    for(int j=0;j<moves.size();j++){        
        for(int i=0;i<board[0].size();i++){            
            if((board[i][moves[j]-1])!=0){
                can.push_back(board[i][moves[j]-1]);
                //한번 크레인에 선택된 원소는 0으로 처리
                board[i][moves[j]-1]=0; 
                if(can.size()>=2 && can[can.size()-1]==can[can.size()-2]){
                    can.pop_back();
                    can.pop_back();
                    answer+=2;
                }
						break;
            }
        }
    }
    
    return answer;
   }

Vectorバー

Vectorの宣言方法

vector<int> v;

v.push_back(10);
v.push_back(20);
v.push_back(30);
v.push_back(40);

for (auto iter : v) {
	cout << iter << endl;
}

for (auto iter = v.begin(); iter < v.end() ; iter++ ) {
	cout << *iter << endl;
}

10
20
30
40
10
20
30
40

vector<int> v;
v.push_back(10);
v.push_back(20);
v.push_back(30);
v.push_back(40);
while (!v.empty()) {
	cout << v.back() << endl;
	v.pop_back();
}

40
30
20
10

スタックとは

スタックの宣言方法