오늘의 공부

https://programmers.co.kr/learn/courses/30/lessons/1829#

재귀를 이용한 DFS 방식으로 풀었다.

방문한 픽셀은 color값을 0으로 바꿔주고 방문 시에 해당 픽셀의 color값을 비교해 같은 부분인지 체크하는 방식으로 풀었다. 

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> v;
int sizeN, sizeM;
int maxSize = 0;

bool dfs(int x, int y, int color)
{
	if (x <= -1 || x >= sizeN || y <= -1 || y >= sizeM)
	{
		return false;
	}

	if (v[y][x] != 0 && v[y][x] == color)
	{
		v[y][x] = 0;
		maxSize += 1;
		dfs(x - 1, y, color);
		dfs(x, y - 1, color);
		dfs(x + 1, y, color);
		dfs(x, y + 1, color);
		return true;
	}
	return false;
}


vector<int> solution(int m, int n, vector<vector<int>> picture) {
	vector<int> answer(2, 0);
	int number_of_area = 0;
	sizeN = n;
	sizeM = m;
	v = picture;

	for (int i = 0; i < m; ++i)
	{
		for (int j = 0; j < n; ++j)
		{
			if (dfs(j, i, picture[i][j]))
			{
				number_of_area += 1;
				answer[1] = maxSize > answer[1] ? maxSize : answer[1];
				maxSize = 0;
			}
		}
	}
	answer[0] = number_of_area;
	return answer;
}

 프로그래머스 홈페이지에서 그냥 풀다가 dfs 함수를 if문으로 체크하는 부분에 i와 j를 반대로 줘서 분명 맞는데 왜 값이 다르게 나오지? 하고 디버깅까지 찍어봤다ㅠ

[y][x] 방식으로 이용하는데 함수에 인자로 넘겨줄 때 x,y 순서로 넘겨주고 있어서 문제가 생겼던 것이다... 

트리

Tree

트리는 객체간의 관계를 표현하는 자료구조인 그래프의 일종이다.

◎ 트리란

트리는 노드들이 가지처럼 연결된 비선형 계층적 자료구조이다.

노드 : 트리의 구성요소에 해당하는 A,B, C, D, E, F와 같은 요소
간선 : 노드와 노드를 연결하는 연결선
루트 노드 : 트리 구조에서 최상위에 존재하는 A와 같은 노드
단말 노드 : 아래로 또 다른 노드가 연결되어 있지 않은 가장 마지막 (E,F,C,D와 같은) 노드
내부 노드 : 단말 노드를 제외한 모든 노드
레벨 : 각 층 별로 숫자를 매긴 것
높이 : 트리의 최고 레벨

◎ 이진트리

이진트리란 루트 노드를 중심으로 두 개의 서브 트리로 나누어지며 나누어진 두 서브 트리도 모두 이진 트리여야 한다.
즉, A를 기준으로 B,D,E가 왼쪽 서브 트리 C,F,G가 오른쪽 서브트리이며 각각의 서브 트리들도 이진 트리여야 한다.

여기서 왼쪽과 같은 트리도 이진트리가 된다.
노드가 위치할 수 있는 곳에 노드가 존재하지 않으면 공집합 노드가 존재하는 것으로 간주해 공집합 노드도 '노드로 인정'하기 때문이다.

이진 트리는 여러 분류로 나뉠 수 있는데 그 중 완전 이진트리와 포화 이진트리가 존재한다.

포화 이진 트리는 위의 그림과 같이 모든 레벨이 꽉 차 있으며 노드를 더 추가하려면 레벨을 늘려야 하는 트리이다.

이 포화 이진 트리에서 레벨을 하나 더 늘려 H와 I를 추가한 다음 이진 트리를 보면 포화 이진 트리처럼 모든 레벨이 꽉 찬 상태는 아니지만 차곡차곡 빈 틈 없이 노드가 채워진 이진 트리가 된다.
여기서의 '차곡차곡 빈 틈 없이'는 노드가 위에서 아래로, 그리고 왼쪽에서 오른쪽의 순서대로 채워졌다는 의미가 된다.
이 트리가 바로 완전 이진 트리이다.

완전 이진트리는 임의의 두 단말 노드의 레벨 차이가 1이하인 경우이며 위의 그림과 같이 왼쪽에서 오른쪽으로 채워진 이진트리를 뜻한다.
레벨 n까지의 모든 노드수는 2^n -1개이다.

◎ 트리의 순회

트리의 순회란 트리에 속하는 모든 노드를 한 번씩 방문하는 것이다. 트리의 순회 방식에는 전위, 중위, 후위 방식이 있다.
루트를 방문하는 작업을 V, 왼쪽과 오른쪽 서브 트리를 방문하는 작업을 각각 L과 R이라고 하면
전위는 VLR, 중위는 LVR, 후위는 LRV 이다.

트리의 순회는 쉬워보이지만 복잡한 노드의 트리인 경우 생각보다 헷갈리게 된다.

다음과 같은 사진이 있을 때 전위, 중위, 후위 순회의 결과는 다음과 같다.
전위 순회 : F,B,A,D,C,E,G,I,H
중위 순회 : A,B,C,D,E,F,G,H,I
후위 순회 : A,C,E,D,B,H,I,G,F

전위 순회

Void preorder(TNode *n) 
{ 
	If( n!= NULL ) 
    { 
    	Printf(“[%c]”, n->data); 
        Preorder(n->left); 
        Preorder(n->right); 
     }
}

중위 순회

Void inorder(TNode *n) 
{ 
	If( n!= NULL ) 
	{ 
    	inorder(n->left); 
        Printf(“[%c]”, n->data); 
        inorder (n->right); 
    } 
}

후위 순회

Void postorder(TNode *n) 
{ 
	If( n!= NULL ) 
	{ 
    	postorder(n->left); 
        postorder (n->right); 
        Printf(“[%c]”, n->data); 
    } 
}

참고로 이 트리의 전위순회 방식을 일반화시킨 그래프의 정점 순회 방법이 깊이 우선탐색 (DFS)이다.
탐색 도중에 인접된 모든 정점이 이미 방문된 정점을 만났을 때 바로 이전에 방문한 정점으로 돌아가기 위해 스택을 사용한다.



참고 자료;
윤성우의 열혈 자료구조 (저; 윤성우, 출판; 오렌지 미디어)

https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%A6%AC_%EC%88%9C%ED%9A%8C

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

#include <cstdio>
#include <queue>

using namespace std;

// 라우터

int main()
{
	queue<int> q;

	int n;
	scanf("%d", &n);

	int packet = 0;
	int packet_size = 0;

	while (packet != -1)
	{
		scanf("%d", &packet);

		if (packet == 0)
		{
			q.pop();
			packet_size = q.size();
		}
		else if (packet == -1)
		{
			break;
		}
		else
		{
			if (q.size() < n)
			{
				q.push(packet);
				packet_size += 1;
			}
		}
	}

	if (packet_size == 0)
	{
		printf("empty");
		return;
	}

	for (int i = 0; i < packet_size; ++i)
	{
		printf("%d\n", q.front());
		q.pop();
	}
}

..원래 C++로 풀었는데 똑같은 코드임에도 C++로 제출할 때는 시간초과가 뜨는데 C로 제출하니 100점이라고 떴다.

이전에 개행이나 print같은 부분에서 C가 훨씬 빨라서 C++과 제출 시간의 차이가 있었는데 얘도 마찬가지여서 그랬나. 

테스트 케이스가 너무 궁금하다. 

스택 C언어로 구현하기 (배열)

Stack 

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

그 중 배열을 이용한 구현 방법은 다음과 같다. 

◎ 배열

배열을 스택으로 구현하기 위해 기억해야 할 것은 두 가지이다.

처음 인덱스 0의 배열 요소를 스택의 바닥(Bottom)으로 정의하고 마지막에 저장된 데이터의 위치를 기억해야 한다.

인덱스 0의 요소를 스택의 Bottom으로 정의하면 배열의 길이와 관계없이 항상 인덱스 0의 요소가 스택의 Bottom이 되며 마지막에 저장된 데이터의 위치는 Top이 되기 때문이다. 

◎ 삽입(Push)과 삭제(Pop)

삽입, 즉 Push는 Top Index를 위로 한 칸 올리고 Top이 가리키는 배열의 위치에 해당 데이터를 저장한다.

삭제 Pop은 Top Index의 데이터를 반환하고 Top Index를 한 칸 줄인다. 

void push(int num)
{
	stack[++index] = num;
}

int pop()
{
	return stack[index--];
}

참고 자료;

윤성우의 열혈 자료 구조 (출판사; 오렌지 미디어, 저: 윤성우)

2742번: 기찍 N (acmicpc.net)

..이 문제를 잊지 않기 위해서 포스팅하기로 했다.

#include <iostream>
using namespace std;
int N;
int main()
{
	cin >> N;
	for (int i = 0; i < N; ++i)
	{
		//cout << N - i << '\n';
		printf("%d\n", N - i);
	}
}

슥 채우고 넘어가려고 했는데 실패가 떠서 요근래 가장 당황스러웠다. 

100,000를 출력할 때 확실히 시간이 오래걸리긴 했다.

왜 자꾸 시간초과가 날까 검색해보다가 

cout, cin, endl가 printf나 '\n'보다 연산이 오래걸려서 그렇다고 했다.

그래서 그 출력 한줄 바꿔줬더니 4초만에 완료됐다.

나는 습관적으로 cin, cout을 사용하니까 다음에 시간초과 나거나 할 때 출력부분을 의심해 볼 만도 한 것 같다.

그리고 뭔가 입력과 출력에 대한 부분을 다시 깊게 찾아보는 것도 좋은 방법인 것 같다. 

11047번: 동전 0 (acmicpc.net)

#include <iostream>
#include <vector>
using namespace std;

int N, K;
vector<int> value;
int func()
{
	int answer = 0;
	int i = N-1;
	do {
		answer += (K / value[i]);
		K %= value[i];
		--i;
	} while (i >= 0);

	return answer;
}

int main()
{
	cin >> N >> K;
	int temp = 0;
	for (int i = 0; i < N; ++i)
	{
		cin >> temp;
		value.push_back(temp);
	}
	cout << func();
}

Greedy 알고리즘 문제로 간단하게 풀 수 있는 문제이다.

완전탐색을 진행하더라도 N번. 즉 10번만 돌면 되기 때문에 시간복잡도가 O(N)이다.

1302번: 베스트셀러 (acmicpc.net)

map을 이용해서 입력받은 책의 이름들을 key값으로 넣어주었다. 

이렇게 하면 문제는 출력할 때 동일 우선순위(=value가 같을 때)에서 알파벳 순서대로 출력할 때 발생하게 된다.

그래서 map의 value값과 key값을 따로 정렬해주었다.

#include <iostream>
#include <map>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int N;
map<string, int> m;

bool cmp(const pair<string, int> &a, const pair<string, int> &b)
{
	if (a.second == b.second)
	{
		return a.first < b.first;
	} 
	return a.second > b.second;
}


int main()
{
	cin >> N;

	string temp;
	for (int i = 0; i < N; ++i)
	{
		cin >> temp;
		m[temp] += 1;
	}

	vector<pair<string, int>> vec(m.begin(), m.end());
	sort(vec.begin(), vec.end(), cmp);

	cout << vec[0].first;
}

1475번: 방 번호 (acmicpc.net)

6과 9를 바꿔서 사용할 수 있으므로 0~8까지만 체크하고 그거에 대한 예외처리들만 해줬다.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int roomNumber;

int func()
{
	int temp = 0;
	vector<int> number;
	number.resize(9); // 0~8까지 체크

	do
	{
		temp = roomNumber % 10;
		if (temp == 9)
			number[6] += 1;
		else
			number[temp] += 1;
		roomNumber /= 10;
	} while (roomNumber >= 1);
	

	number[6] % 2 ? number[6]++ : 0;
	number[6] /= 2;

	sort(number.begin(), number.end(), greater<int>());

	return number[0];
}


int main()
{
	cin >> roomNumber;
	cout << func();
}

쉬워보이기도 했고 금방 풀어서 제출했는데 안되길래 0일 때도 해보고 이것저것 해봤는데

while문 조건에 number >= 1 를 해줘야 되는데 그냥 >만 해줘서 1199를 했을 때 두 세트가 아닌 한 세트가 출력되고 있었다. 

간만에 풀어서 그런가 또 초심을 잃었다..