블로그 이미지
황상두

카테고리

기타 (101)
알고리즘(백준) (3)
임베디드 보안 (7)
windows internal (22)
공부 (16)
전공 스터디 (27)
과제 (8)
영어 (6)
기록물 (6)
Total
Today
Yesterday

달력

« » 2024.11
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30

공지사항

태그목록

최근에 올라온 글

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;

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

'알고리즘(백준)' 카테고리의 다른 글

LCS2(longest common subsequence) 알고리즘  (0) 2017.12.27
Deque 구현  (0) 2017.12.17
Posted by 황상두
, |

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

#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. 둘 다 같지 않으면 대각선으로 이동한다.

'알고리즘(백준)' 카테고리의 다른 글

스타트와 링크 14889번 (삼성전자 채용 시험)  (0) 2017.12.29
Deque 구현  (0) 2017.12.17
Posted by 황상두
, |

Deque 구현

알고리즘(백준) / 2017. 12. 17. 16:11

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

덱의 경우 스택과 큐 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;
}
//*/
Posted by 황상두
, |

1. 카멜 표기법

우리가 평소 쓰는 변수명과 같다고 보면 된다.

ex) int sayHello;

2.파스칼 표기법

클래스명에서 쓰는 표기법이다.
ex) class SayHello{};

 

enum 네이밍 규칙

class 처럼 대문자로 시작하는 파스칼 표기법을 사용한다.

안에 있는 element 경우도 파스칼 표기법을 따른다

 

'공부 > 프로그래밍' 카테고리의 다른 글

논리형 프로그래밍(?)  (0) 2017.01.14
함수형 프로그래밍(?)  (0) 2017.01.14
식과 제어문  (0) 2017.01.14
l-value 와 r-value 차이  (0) 2017.01.13
동적영역과 정적영역의 차이  (0) 2017.01.12
Posted by 황상두
, |

윈도우 커널

windows internal / 2017. 12. 16. 16:19

 

윈도우가 가장 많이 취약점이 발견 되었다.

 

윈도우 CVE 발생 순서

1. 코드실행
2. 서비스 거부
3. 버퍼오버플로우
4. 메모리 부패
5. 권한 상승

 

윈도우 커널만 두고 본다면 권한 상승이 가장 많다.
win32k.sys가 대부분인 것을 볼 수 있다.

동적분석은 코드 커버리지를 높이기 위한 목적으로 많이 사용된다.

동적 심볼릭 수행과 심볼릭 수행의 차이점(?)

심볼릭 수행은 x,y로 기호로 대체해서 실행하는 방식으로 조건문마다 경로가 전부 갈 수 있다고 가정하고 시작한다.

동적 심볼릭 수행은 심볼릭 수행 + 콘크리트 수행의 결합이라고 보면 된다.
실제값과 심볼릭 기호를 적절히 섞음으로서 코드 커버리지와 속도를 둘 다 잡으려는 시도라고 보면 된다.

taint 분석은 오염분석으로 입력값이 어느 메모리 영역까지 영향을 미치는지 연구하는 것이라고 보면된다.
특권 계층의 메모리까지 영향을 미친다면 이는 취약성 가능성이 있다고 볼 수 있는 것이다.

 

Posted by 황상두
, |

최근에 달린 댓글

글 보관함