오늘의 공부

programmers.co.kr/learn/courses/30/lessons/43105

앞서 풀었던 문제 중 땅따먹기와 개념이 비슷한 문제이다. 

int Find_max(int n1, int n2)
{
	return n1 > n2 ? n1 : n2;
}

int solution(vector<vector<int>> triangle) {
	int answer = 0;

	int triangle_size = triangle.size();

	for (int i = 0; i < triangle_size-1; ++i)
	{
		for (int j = 0; j < triangle[i+1].size(); ++j)
		{
			if (j < 1 || (j == triangle[i + 1].size() - 1))
			{
				// 왼쪽 끝// 오른쪽 끝 
				if (j < 1)
				{
					triangle[i + 1][j] += triangle[i][0];
				}
				else
				{
					triangle[i + 1][j] += triangle[i][j-1];
				}
				
			}
			else
			{
				triangle[i + 1][j] += Find_max(triangle[i][j - 1], triangle[i][j]);
			}
		}
	}
	
	answer = triangle[triangle_size - 1][0];
	for (int i = 1; i < triangle[triangle_size - 1].size(); ++i)
	{
		if (answer < triangle[triangle_size - 1][i])
		{
			answer = triangle[triangle_size - 1][i];
		}
	}

	return answer;
}

programmers.co.kr/learn/courses/30/lessons/12913

처음에는 단순히 뇌빼기를 하고 풀어도 되는 쉬운 문제인 줄 알고 이전값만 더했는데 테스트에서 실패가 뜨는 것을 보고 직감했다. 이게 아니구나.

그래서 다른 방식으로 풀었다. 

원래는 각 행에 가장 큰 값을 더하되 이전 행에서 더했던 인덱스(열)면 다른 최댓값을 찾았었다.

그런데 생각해보니 반례가 있었다.

이렇게 극한으로 치닫는 예제에서 4->8->12를 하고나면 마지막행에서 1000을 더할 수가 없게 된다.

그래서 각 행에 이전 행의 최댓값을 더한 후에 비교해줬다. 

int find_max(int n1, int n2, int n3)
{
	int temp = n1;

	if (temp < n2)
	{
		temp = n2;
	}
	if (temp < n3)
	{
		temp = n3;
	}
	return temp;
}


int solution(vector<vector<int> > land)
{
	int answer = 0;
	int m_size = land.size();

	for (int i = 0; i < m_size-1; ++i)
	{
		land[i+1][0]+= find_max(land[i][1], land[i][2], land[i][3]);
		land[i+1][1]+= find_max(land[i][0], land[i][2], land[i][3]);
		land[i+1][2]+= find_max(land[i][0], land[i][1], land[i][3]);
		land[i+1][3]+= find_max(land[i][1], land[i][2], land[i][0]);
	}

	answer = land[m_size - 1][0];
	for (int i = 1; i < 4; ++i)
	{
		if (answer < land[m_size - 1][i])
		{
			answer = land[m_size - 1][i];
		}
	}
	return answer;
}

programmers.co.kr/learn/courses/30/lessons/12973

효율성 테스트까지 통과하기 위해서는 Stack을 이용해서 풀어야 한다.

괄호 { } 맞추기 문제, 그리고 카카오 테스트 중에 크레인 인형 뽑기와 비슷했던 문제였다.

stack의 top과 s의 idx값을 비교했을 때 같으면 stack의 top을 pop하고 같지 않다면 s의 idx값을 현재 stack에 넣어준다. 

#include <iostream>
#include<string>
#include <stack>
using namespace std;
int solution(string s)
{
	int answer = 0;
	stack<char> Stack;

	int idx = 0;

	Stack.push(s[idx++]);

	while (idx < s.size())
	{
		if (Stack.empty())
		{
			Stack.push(s[idx++]);
		}
		char s_top = Stack.top();

		if (!Stack.empty() && s_top == s[idx])
		{
			Stack.pop();
		}
		else
		{
			Stack.push(s[idx]);
		}
		idx += 1;

	}

	if (Stack.empty())
		answer = 1;
	else
		answer = 0;

	return answer;
}

이분탐색

이진탐색

처음부터 하나하나 값을 비교하는 순차탐색과 달리 이분탐색은 데이터를 찾을 때 검색 대상의 데이터를 반 씩 줄여나가면서 자료를 찾는 방법을 말한다.

◎ 이진탐색?

이분탐색에는 중요한 조건이 있는데, 바로 데이터가 정렬된 상태여야 한다는 것이다.

왜일까?

이분탐색은 데이터를 반씩 줄여 나가는 방식은 다음과 같다.

총 n개의 데이터가 있다고 했을 때

1. 중심 값(mid = (n+1)/2)을 잡는다

2. 중심 값(mid)과 찾으려는 값(value)을 비교.

3-1. mid == value => 탐색 종료. value의 값은 mid

3-2. mid > value => 중심값을 기준으로 왼쪽 값을 기준으로 다음 탐색을 진행한다. 즉 오른 쪽의 데이터는 더 이상 확인하지 않는다.

3-3. mid < value => 중심값을 기준으로 오른쪽 값을 기준으로 다음 탐색을 진행한다. 즉 왼쪽의 데이터는 더 이상 확인하지 않는다. 

4. 데이터가 1개 남을 때까지 반복한다. 

이렇게 7개의 데이터를 가진 배열이 있을 때 5를 찾고 싶으면 우선 배열의 가장 가운데 값을 기준으로 잡는다.

그 다음 찾으려는 값이 가장 가운데 값과 같으면 탐색이 끝나는 것이고 크면 오른쪽, 작으면 왼쪽을 확인한다.

5를 찾고 싶으니 중심인 4를 기준으로 오른쪽 값을 비교할 것이다. 그러면 1,2,3은 더 이상 비교하지 않아도 되므로 다음 탐색에서는 대상이 3개로 줄어들게 된다.

이런식으로 비교할 데이터가 1개가 남을 때까지 반복한다. 

계속 탐색 대상의 데이터를 반으로 줄여나가므로 이분탐색의 시간 복잡도는 O(logn)이 된다. 

◎ 라이브러리

#include <algorithm> 헤더를 추가하면 이미 구현된 이분 탐색을 사용할 수 있다.

iterator의 begin값과 end값, 찾을 value값을 순서대로 넣어주면 사용이 가능하다. 

www.acmicpc.net/problem/13904

우선 입력받은 데이터를 점수를 기반으로 정렬했다. 

vector의 second에 점수가 first에 과제 제출 기한이 담겨있다. 

탐욕법을 이용해서 푸는 문제로 점수를 기준으로 가장 큰 수부터 마감일에 가깝게 넣는다. 

오름차순으로 정렬된 벡터의 값에서 0번은 (한 번 돌릴 때마다 erase를 해주므로) 제일 점수가 큰 값이다.

따라서 0번을 뽑아서 해당 마감일에 이미 다른 점수가 있으면 전 날, 전전날을 계속 찾아본다.

비어있는 날이 있다면 해당 날짜에 넣고 없다면 버린다. 

왜 계속 틀렸을까 고민했던 문제이다. 그래서 이것저것 잘못 생각한 게 있었나 고민해봤지만 답이 나오지 않았다. 

그럴 수 밖에.. 틀린 이유는 따로 있었다.

밑에 answer에 더해주는 for문에서 n의 범위값을 틀려서 계속 채점 오류가 발생했다.

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
bool cmp(const pair<int, int> &a, const pair<int, int> &b) 
{
	if (a.second == b.second)
	{
		return a.first < b.first;
	}
	return a.second > b.second;
}

int max_score(vector<pair<int, int>>& v, int &n)
{
	vector<int> tempv;
	tempv.resize(1001);
	int idx = 0;
	int answer = 0;
	while (idx < n) {

		for (int i = v[0].first; i > 0; --i)
		{
			if (tempv[i] != 0)
			{
				continue;
			}
			else
			{
				tempv[i] = v[0].second;
				break;
			}
		}

		idx += 1;
		v.erase(v.begin());
	}

	for (int i = 0; i <=1000; ++i)
	{
		answer += tempv[i];
	}
	return answer;
}


int main()
{
	vector<pair<int, int>>  v;
	int n;
	cin >> n;

	for (int i = 0; i < n; i++)
	{
		int n1, n2;
		cin >> n1 >> n2;
		v.push_back(make_pair(n1, n2));
	}
	sort(v.begin(), v.end(), cmp);
	int answer = max_score(v, n);
	cout << answer;
    
    return 0;
}

스택  C언어로 구현하기 (연결리스트)

Stack!

먼저 들어온 데이터가 나중에 나가는 구조를 가지고 있는 스택은 배열과 연결리스트로 구현할 수 있다.

그 중 연결리스트의 구현 방법은 다음과 같다. 

◎ 연결리스트

배열을 이용한 것과 달리 연결 리스트로 구현한 스택에서는 요소들을 한꺼번에 할당하는 것이 아니다.

동적 할당을 이용해서 필요할 때마다 하나씩 할당하는 방식을 이용한다. 

연결리스트로 구현하기 위한 스택은 아래와 같은 노드 구조체를 추가로 정의해야 한다.

이 때 스택에 저장할 정보(데이터 필드)와 함께 다음 노드를 가리키기 위한 포인터(링크 필드)를 멤버로 가진다.

typedef struct LinkedNode
{
	int data; // 데이터 필드
	struct LinkedNode* link // 링크 필드(포인터) -> 다음 노드를 가리킴
 } Node; 

배열에서는 top(제일 위의 값)을 index값으로 저장했지만 연결리스트에서는 포인터로 저장해야 한다.

즉 헤드포인터를 저장하는 것이다.

헤드 포인터가 이해가 안된다면 ?

○삽입

만약 C->B->A 순으로 연결되어 있다면 헤드 포인터 top은 C를 가리키고 있고 C의 링크 필드가 B를 B의 링크 필드가 A를 가리키고 있을 것이다. 

여기에 새로운 노드 D를 삽입하려고 하면 성공했을 경우 top은 D의 노드를 가리키고 D는 C를 가리켜야 한다.

(왜? 스택의 특성상 먼저 들어온 값이 앞, 또는 위에 있기 때문에) 

1. 노드 D의 링크 필드가 노드 C를 가리키도록 함 p->link = top;

2. 헤더 포인터 top이 노드 D를 가리키도록 함 top = p;

이 두 가지의 과정을 거치면 push를 구현할 수 있다. 

void push(int e)
{
	Node* p = (Node*)malloc(sizeof(Node));
 	p->data = e;   // 데이터를 초기화
    
	p->link = top; // 1번
	top = p;   // 2번
 } 

○삭제

삭제 연산은 가장 최근에 삽입된 요소를 꺼내서 반환하는 연산이다.

스택은 FIFO, 즉 First in First Out인 큐와 달리 FILO(First in Last Out)이므로 삭제 시에 가장 최근에 삽입된 요소를 꺼내게 된다. 

1. 포인터 변수 p가 노드 C를 가리키도록 함 p = top

2. 헤더 포인터 top이 다음 노드를 가리키도록 함 top = p->next 

이 연산을 구현할 때 신경써야 할 부분은 메모리를 동적으로 해제하는 것이다.

항목을 반환하기 위해서 해제 하기 전에는 데이터 필드를 저장해두고 노드를 해제한 후에 저장된 항목을 반환해야 한다. 

int pop()
{
	Node* p;
	int e;
	if(is_empty())   // 스택이 비었는지 확인 -> 비었으면 pop할 데이터 X
    	error("스택 공백 에러");

	p = top;
	top = p->link;
	e = p->data;
	free(p); // 노드 동적 해제하기
	return e; // 반환
} 

참고 자료;

두근두근 자료구조 (출판사; 생능출판, 저;최영규, 천인국, 공용해)

연결리스트

Linked-List

연결리스트는 말 그대로 연결된 리스트이다. 물리적으로 흩어져 있는 자료들을 서로 연결해 하나로 묶는 방법인 것이다.

배열을 이용한 자료구조는 구현이 간단하지만 용량이 고정된다는 단점이 있다. 배열은 동적으로 크기를 늘리거나 줄일 수 없어서 처음 할당한 공간이 가득 차면 더 이상 데이터를 추가할 수 없기 때문이다.

그렇다면 연결리스트는? 데이터와 링크로 구성돼 있고 링크가 노드들을 연결하는 역할을 한다. 따라서 노드들의 연결만 바꿔주면 되니까 용량이 자동으로 변할 수 있는 것이다. 

그래서 배열에 비해 중간에 자료를 삽입하는 것이 용이하고 크기가 고정되지 않는다. 

배열에서 어떤 자료를 추가하고자 할 때는 그 위치 이후의 자료를 한 칸씩 뒤로 복사해 넣어주고 그 자리에 자료를 넣어줘야 한다.

하지만 연결 리스트에는 이럴 필요가 없다.

왜? 

◎ 삽입과 삭제 

위와 같이 노드들이 연결되어 있다고 할 때 (A->B->C->D->E) 데이터를 삽입하고자 한다. 

B와 C사이에 N을 삽입하려고 한다면? 

이렇게 B와 C를 연결해 주던 것을 없애고 B를 N과 N과 C를 연결한다. 그러면 A->B->N->C->D->E 순으로 연결되며 B와 C사이에 N이 위치하게 된다. 

삭제도 마찬가지이다. 

C를 없애고 싶다면 C로 연결되던 B와 D의 선을 지우고 B와 D를 연결시켜 주면 된다. 

◎ 연결리스트의 구조

연결리스트의 구조에는 크게 두 가지 노드와 헤드포인터가 있다.

○ 노드 (node)

위의 그림에서 A,B,C,D,E에 해당하는 것들이 노드이다. 연결리스트는 노드들의 집합이고 이들은 데이터를 저장하고 있으며 서로 연결되어 있다.

이 노드는 데이터를 담는 데이터 필드와 링크를 담는 링크 필드로 구성되어 있다.

데이터 필드에는 말 그대로 데이터가 들어간다. 담고 싶은 정보를 담는 곳이다. 정수가 될 수 있고 구조체가 될 수도 있다. 

링크 필드에는 다른 노드를 가리키는 정보가 들어있다. 위 사진에서는 화살표에 해당하며 다른 노드의 주소를 저장하는 포인터 변수가 존재한다. 이 포인터를 이용해서 현재 노드에 연결되어 있는 다음 노드가 어떤 노드인지 알 수 있는 것이다. 

○헤드 포인터(head pointer)

헤드 포인터는 연결 리스트의 첫 번째 노드의 주소를 저장하는 포인터이다. 

연결 리스트는 첫 번째 노드를 알면 그 뒤에 매달려 있는 모든 노드들에 순차적으로 접근할 수 있다.

그래서 헤드 포인터 주소를 반드시 알아야 한다. 

(마지막 노드 같은 경우에는 더 이상 연결할 노드가 없는데 링크 필드의 값을 NULL로 설정해서 이 노드가 마지막 노드임을 표현한다.)

◎ 연결리스트의 특징 

- 노드들은 메모리의 어느 곳에나 위치할 수 있다.

즉, 노드들의 주소가 연결 리스트 상의 순서와 동일하지 않다. 인접한 노드라고 해서 인접한 메모리에 있는 것이 아니다.

- 연속적인 기억공간이 없어도 데이터를 저장하는 것이 가능하고 미리 공간을 확보할 필요도 없다. 필요할 때마다 동적으로 노드를 생성해서 연결하기 때문이다.

- 링크 필드를 위한 추가 공간이 필요하다.

- 연산의 구현이나 사용 방법이 배열에 비해 복잡하다.

- 오류가 없더라도 동적 할당과 해제가 너무 빈번하게 일어나면 메모리 관리를 위한 처리시간이 길어져 프로그램이 느려질 수도 있다. 

◎ 연결리스트의 종류

연결리스트는 연결의 종류에 따라 세 가지로 나뉜다.

1. 단순 연결 리스트

하나의 방향으로만 연결되어 있으며, 맨 마지막 녿의 링크 필드는 NULL 값을 가진다.

2. 원형 연결 리스트

단순 연결 리스트와 같지만 맨 마지막 노드의 링크 값이 다시 첫 번째 노드를 가리킨다. 그래서 원형으로 연결 되었다고 표현하는 것이다.

3. 이중 연결 리스트

각 노드마다 링크 필드, 즉 포인터가 2개씩 존재한다. 따라서 각각의 노드는 선행 노드와 후속 노드를 모두 가리킬 수 있다. 

참고 자료;

두근두근 자료구조 (출판사; 생능 출판 / 저 ;최영국, 천인국, 공용해 )

기수 정렬과 계수 정렬

최악의 경우에도 비교 정렬들보다 빠른 정렬 알고리즘

최악의 경우 정렬 시간이 O(nlogn)보다 빠를 수는 없을까? 원소 두 개를 비교함에 의해 정렬하는 비교정렬은 최악의경우 수행 시간이 O(nlogn)보다 빨라질 수는 없다.

그런데 입력 원소들이 특수한 성질을 만족하는 경우 O(nlogn)의 한계를 극복할 수 있는 정렬 알고리즘들이 존재한다.

기수 정렬과 계수 정렬이다.

◎ 기수 정렬

기수 정렬은 문자열의 정렬에도 사용되는 방법이다.

입력이 모두 k 이하의 자리수를 가진 자연수인 특수한 경우에(자연수가 아닌 제한된 종류를 가진 알파벳 등도 해당 된다) 사용할 수 있는 방법으로 O(n) 시간이 소요되는 정렬 알고리즘이다.

작동의 순서는 다음과 같다.

1. 우선 가장 낮은 자리수만 가지고 모든 수를 재배열(정렬)한다.

2. 그런 다음 가장 낮은 자리수는 잊어버린다. 

3. 그 다음은 앞과 같은 방법으로 더이상 자리수가 안 남을 때까지 반복한다.

구현 방법은 우선 0부터 9까지의 버킷을 만든다.

그 후에 1의 자리를 비교한다. 0123같은 경우에는 3번 버킷에, 2154는 4번 버킷에 들어간다.

이 때 버킷의 각 번호는 FIFO의 구조를 가진 queue이다. 

그 후 0번 버킷부터 9번버킷까지 각 버킷에 저장된 숫자들을 뺀다.

다음으로는 10의 자리를 비교해서 위와 같은 과정을 거친다.

이 과정을 거치게 되면 마지막에는 정렬된 배열을 갖게 된다.

만약 첫 문자에서 정렬을 시작하게 된다면 MSD 기수 정렬, 마지막 문자에서부터 정렬을 시작하게 되면 LSD 기수 정렬이라고 한다. 

이 알고리즘은 "안정성을 유지하면서 정렬된다" 

이 말은 같은 값을 가진 아이템들은 정렬 후에도 원래의 순서가 유지되는 성질을 가진 정렬을 일컫는 말이다.

즉, 값이 같은 원소끼리는 정렬 후에 원래의 순서가 바뀌지 않는 성질을 말한다. 

◎ 계수 정렬

계수 정렬은 정렬하고자 하는 원소들의 값이 O(n)을 넘지 않는 경우에 사용할 수 있다. 

기본적인 특성은 버켓 정렬과 유사하지만 중복되는 키 값의 누적된 횟수를 구해서 그것을 인덱스로 삼는다.

작동의 순서는 다음과 같다.

ex) 0,3,2,1,0,0,2,3,1,1,1 을 정렬한다고 할 때 

1. 우선 각 배열의 원소를 훑어보고 각 키의 값이 몇 번씩 있는지 빈도수를 구한다.

2. 각 키의 등장 횟수를 누적 합으로 바꿔준다.

3. 위의 누적합은 새로 할당할 공간의 최댓값이 된다. 

즉 숫자 0의 인덱스는 1과 3의 사이이다. 

0이 3번 반복뒤니까 0을 3번째 인덱스에 넣은 후에 0의 누적 합을 2로 줄인다. 그 후 3의 누적 합은 11이므로 3을 11번 인덱스에 집어 넣고 3의 누적 합을 10으로 줄여준다. 

4. 2의 경우에도 마찬가지로 빈도 수는 2, 누적합은 9이므로 9에 넣고 누적합을 8로 줄여준다. 

이런 식으로 반복하며 정렬해야 하는 모든 값의 인덱스를 정해줄 수 있다.

계수정렬도 마찬가지로 안정 정렬이며 다른 정렬들 보다 시간 복잡도에서 좋은 효율을 보이는 이유는 키 값의 비교를 하지 않고 (비교정렬) 바로 자기 자리를 찾기 때문이다. 

참고 자료;

쉽게 배우는 알고리즘 - 관계 중심의 사고법 (출판사; 한빛 아카데미 / 저; 문병로)