I.A.P

https://www.acmicpc.net/problem/14889

일단 사전 작업을 해준다.

1. 대각선에 있는 것끼리 더해서 한 쪽으로 몰아준다
어차피 대각선에 있는 것끼리 더하는 작업을 하게 되기 때문이다/

    //더하고 0으로 초기화
    for (int i = 0; i < N ; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (i < j){
                matrix[i][j] += matrix[j][i];
                matrix[j][i] = 0;
            }
        }
    }

2. (N/2)명씩 팀을 짜야한다.

이 부분을 반복문으로 하는 건 힘들다.
4명까지는 몰라도 20명은 정말 힘들다.

그러므로 재귀호출을 통해서 combine을 구현해야 한다.
정확히 기억이 나지 않아서 다시 알고리즘 문제풀이 책을 펼쳐 보았다

void pick(int n, vector<int> element , int toPick, int *min)
{
	//터미널 조건
	if (toPick == 0){
		return;
	}
	int smallest = element.empty() ? 1 : element.back() + 1;

	for (int i = smallest ; i <= n; i++)
	{
		element.push_back(i);
		pick(n, element, toPick - 1, min);
		element.pop_back();
	}
}

위 코드는 조합을 구현한 것을 나타낸다.

//선택된 요소을 제외한 나머지 요소들 공식 적용
		for (int i = 0; i < (n / 2) - 1; i++)
		{
			num1 = element2.at(i);
			for (int j = i + 1; j < n / 2; j++)
			{
				num2 = element2.at(j);

				cnt2 += matrix[num1 - 1][num2 - 1];
			}
		}

위 코드는 선택된 (N/2)명을 제외한 나머지 (N/2)를 팀으로 짠 것이다.

ex) (1,2,3,4)가 한팀이면 (5,6,7,8)이 한팀이다.

3. 팀을 나눈 후 그 팀들의 점수를 구한다.

//선택된 조합을 가지고 공식 적용
		for (int i = 0; i < (n/2) - 1; i++)
		{
			num1 = element.at(i);
			for (int j = i + 1; j < n/2; j++)
			{
				num2 = element.at(j);
				cnt1 += matrix[num1 - 1][num2 - 1];
			}
		}

선택된 element를 가지고 공식을 적용하는 공식이다.
이는 자주 쓰이므로 함수로 만들어 사용하는 것이 좋다.

//abs구현
		int res = cnt1 - cnt2;
		if (res < 0)
			res = -res;

		//min업데이트
		if (*min > res)
			*min = res;

합산된 점수를 비교한다.
절댓값과 최솟값 비교가 필요하다.

가장 긴 공통 부분 문자열 찾기 알고리즘

#include <iostream>
#include <string>

using namespace std;

int lcs[1001][1001];
int main()
{
    //int memoization[][];
    string str1;
    string str2;

    cin >> str1;
    cin >> str2;

    //앞에 0을 더해준다.
    str1 = '0' + str1;
    str2 = '0' + str2;

    int len1 = str1.size();
    int len2 = str2.size();

    for (int i = 0; i < len1; i++)
    {

        for (int j = 0; j < len2; j++)
        {
            if (i == 0 || j == 0)
            {
                lcs[i][j] = 0;
                continue;
            }
            if (str1.at(i) == str2.at(j)){
                lcs[i][j] = lcs[i - 1][j - 1] + 1;
                //str3 += str1.at(i);
            }
            else
            {
                if (lcs[i - 1][j] > lcs[i][j - 1])
                    lcs[i][j] = lcs[i - 1][j];
                else
                    lcs[i][j] = lcs[i][j - 1];
            }
        }
    }
    return 0;
}

1. 1행과 1열은 0으로 초기화한다.
2. 행렬이므로 2중 for문 사용
3. str1의 i번째 문자 == str2의 j번쨰 (왼쪽 위 대각선 + 1)을 대입
4. 같지 않은 경우 (왼쪽과 위쪽 중 큰 값)을 대입

	char result[1001];
	
	int i = len1 - 1, j = len2 - 1 , cnt = 0;
	//행렬 우하향 설정
	while (i != 0 && j != 0){
		if (lcs[i - 1][j] == lcs[i][j])//왼쪽 오른쪽 비교
			i--;
		else if (lcs[i][j - 1] == lcs[i][j])
			j--;
		else
		{
			result[cnt++] = str1[i];
			i--;
			j--;
		}
	}
	//result[cnt++] = str1.at(i);
	result[cnt] = NULL;
	int temp;
	for (int i = 0; i < (cnt / 2); i++)
	{
		temp = result[i];
		result[i] = result[cnt - 1 - i];
		result[cnt - 1 - i] = temp;
	}
	cout << result  << endl;

알고리즘 설명

1. 같으면 그 쪽으로 이동한다.
2. 둘 다 같지 않으면 대각선으로 이동한다.

백준 알고리즘 문제를 풀어보는 중이다.

덱의 경우 스택과 큐 2개의 기능을 다 할 수 있다.
앞 뒤로 넣었다 뺐다 가능하다.
LIFO와 FIFO 둘 다 가능한 형태이다.

배열로 구현중인데 배열보다는 연결리스트로 구현하는 것이 쉽다.
요소가 1개일 때와 0개일 때 구별하는데 있어서 연결리스트가 훨씬 용이하다.

* 배열로 구현

///* 배열로 deque구현
#include <iostream>
#include <cstring>
#include <string>
using namespace std;
#define MAX 10000
template <class T>
class Deque
{
private:
    T element[MAX];
    int size;
    int head;
    int tail;
public:
    Deque()
        : size(0), head(0), tail(0)
    {}
    void push_front(T _element)
    {
        if (getSize() == MAX - 1){
            //cout << "size error" << endl;
            return;
        }
        if (size++ > 0){
            head = (head - 1 + MAX) % MAX;
        }
        element[head] = _element;
    }
    void push_back(T _element)
    {
        if (getSize() == MAX - 1){
            //cout << "size error" << endl;
            return;
        }
        if (size++ > 0)
            tail = (tail + 1) % MAX;
        element[tail] = _element;
    }
    T front()
    {
        //cout << element[head] << endl;
        return isEmpty() ? -1 : element[head];
    }
    T back()
    {
        //cout << element[tail] << endl;
        return isEmpty() ? -1 : element[tail];
    }
    T pop_front()
    {
        if (isEmpty()){
        //    cout << "size error" << endl;
            return -1;
        }
        size--;
        int temp = head;
        if (size > 0)
            head = (head + 1) % MAX;
        return element[temp];
    }
    T pop_back()
    {
        if (isEmpty()){
            //cout << "size error" << endl;
            return -1;
        }
        size--;
        int temp = tail;
        if (size > 0)
            tail = (MAX + tail - 1) % MAX;
        return element[temp];
    }
    int getSize()
    {
        return size;
    }
    bool isEmpty()
    {
        //return getSize() ? false : true;
        return getSize() ? 0 : 1;
    }
    ~Deque(){}
};

int main()
{
    int testcase;
    cin >> testcase;
    string cmnd;
    Deque<int> deque;
    int element;
    for (int i = 0; i < testcase; i++)
    {
        cin >> cmnd;
        if (!cmnd.compare("push_front")){
            cin >> element;
            deque.push_front(element);
        }
        else if (!cmnd.compare("push_back")){
            cin >> element;
            deque.push_back(element);
        }
        else if (!cmnd.compare("pop_front"))
            cout << deque.pop_front() << endl;
        else if (!cmnd.compare("pop_back"))
            cout << deque.pop_back() << endl;
        else if (!cmnd.compare("size"))
            cout << deque.getSize() << endl;
        else if (!cmnd.compare("empty"))
            cout << deque.isEmpty() << endl;
        else if(!cmnd.compare("front"))
            cout << deque.front() << endl;
        else if(!cmnd.compare("back"))
            cout << deque.back() << endl;
    }
    return 0;
}

* 이중 연결리스트

///*이중 연결리스트로 deck구현하기!
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
class DequeNode
{
private:
public:
	int data;
	DequeNode* rLink;
	DequeNode* lLink;
	DequeNode(int _data = 0)
		: data(_data), rLink(NULL), lLink(NULL)
	{}
	~DequeNode()
	{}
};


class Deque
{
private:
	DequeNode* head;
	DequeNode* tail;
public:
	Deque()
		: head(NULL), tail(NULL)
	{}
	~Deque()
	{}
	void push_front(int _element)
	{
		DequeNode* newNode = new DequeNode(_element);
		//if (head)//head != NULL
		if (isEmpty())
			head = tail = newNode;
		else
		{
			head->lLink = newNode;
			newNode->rLink = head;
			head = newNode;
		}
	}
	void push_back(int _element)
	{
		DequeNode* newNode = new DequeNode(_element);
		if (isEmpty())
			tail = head = newNode;
		else
		{
			tail->rLink = newNode;
			newNode->lLink = tail;
			tail = newNode;
		}
	}
	int pop_front()
	{
		if (isEmpty())
			return -1;
		int data = head->data;
		//요소가 2개 이상이면
		if (head != tail)
		{
			head = head->rLink;
			head->lLink = NULL;
			delete head->lLink;
		}
		//요소가 1개라면
		else{
			delete head;
			tail = head = NULL;
		}
		return data;
	}
	int pop_back()
	{
		if (isEmpty())
			return -1;
		int data = tail->data;
		
		//요소가 2개 이상이면
		if (head != tail){
			tail = tail->lLink;
			tail->rLink = NULL;
			delete tail->rLink;
		}
		//요소가 1개이면
		else
		{
			delete head;
			head = tail = NULL;
		}
		return data;
	}
	bool isEmpty()
	{
		//return (head == NULL) ? true : false;
		return (head == NULL) ? 1 : 0;
	}
	int front()
	{
		if (isEmpty())
			return -1;
		return head->data;
	}
	int back()
	{
		if (isEmpty())
			return -1;
		return tail->data;
	}
	int getSize()
	{
		if (isEmpty())
			return 0;
		int cnt = 1;
		DequeNode* node = head;
		while (node = node->rLink)
			cnt++; 
		return cnt;
	}
};
int main()
{
	int testcase;
	cin >> testcase;
	string cmnd;
	Deque deque;
	int element;
	for (int i = 0; i < testcase; i++)
	{
		cin >> cmnd;
		if (!cmnd.compare("push_front")){
			cin >> element;
			deque.push_front(element);
		}
		else if (!cmnd.compare("push_back")){
			cin >> element;
			deque.push_back(element);
		}
		else if (!cmnd.compare("pop_front"))
			cout << deque.pop_front() << endl;
		else if (!cmnd.compare("pop_back"))
			cout << deque.pop_back() << endl;
		else if (!cmnd.compare("size"))
			cout << deque.getSize() << endl;
		else if (!cmnd.compare("empty"))
			cout << deque.isEmpty() << endl;
		else if (!cmnd.compare("front"))
			cout << deque.front() << endl;
		else if (!cmnd.compare("back"))
			cout << deque.back() << endl;
	}
	return 0;
}
//*/