다른 사람들의 코드를 보면서 얻은게 많았던 문제

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <fstream>
#include <string>
#include <vector>

using namespace std;

int main()
{
	int T;
	scanf("%d ", &T);

	vector<string> result;
	char temp;
	int leftCnt = 0, rightCnt = 0;

	for (int i = 0; i < T; )
	{
		temp = getchar();

		if (temp == '(') ++leftCnt;
		else if (temp == ')') ++rightCnt;
		
		if (leftCnt < rightCnt)
		{
			string line;
			getline(std::cin, line);
			result.push_back("NO");
			leftCnt = 0;
			rightCnt = 0;
			++i;
		}
		else if (temp == '\n')
		{
			if (leftCnt == rightCnt)
				result.push_back("YES");
			else
				result.push_back("NO");
			leftCnt = 0;
			rightCnt = 0;
			++i;
		}
	}

	for (const auto & data : result)
	{
		cout << data<<'\n';
	}

	return 0;
}

밑은 감명받은 코드ㅋㅋ

#include<cstdio>
int n;
char s[51];
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%s", s);
		int c = 0;
		for (int j = 0; s[j] && c >= 0; j++) s[j] == '(' ? c++ : c--;
		puts(c ? "NO" : "YES");
	}
	return 0;
}

||풀면서 느낀 것

• 무조건 설계를 잘 세워두자

설계하다가 아 이거 코드로 바로 풀 수 있겠다 라는 생각이 들어서 중간에 코드쓰면서 나머지를 생각했는데

전혀 아니였다 ^~^

깝치지 말고 끝까지 꼼꼼하게 설계를 해두자

||새로 알게 된것

• 문자열의 끝이 반복문의 종료 조건이 될 수 있다

문자열의 끝은 Null, 즉 0이라 당연히 조건이 될 수 있는데

이렇게 응용 할 생각을 못했어서 이번에 다른 사람들의 코드를 보면서 깨달았다.

char test[50];

//for문에 적용
for(int i = 0; test[i]; ++i) { }

//while문에 적용
int i = 0;
while(test[i]) {}

보다 쉽게 문자열의 끝까지 반복문을 돌릴 수 있게 되었다! 정말 개꿀

• stl의 Stack이 비었을 때 pop이나 top을 사용하면 에러가 난다

이건 그냥 질문게시판을 보다가 알아두면 좋을것 같아서 적어본다.

• scanf에서 %s뒤에 공백문자를 넣으면 화이트스페이스가 비워진다.

이건 항상 이렇게 하면 비워지지 않을까? 생각했던건데

이번에 실험해보면서 잘 작동 되는걸 확인했다.

char test[50];
scanf("%s ",test); //%s뒤에 공백이 있다는게 중요
puts(test);
scanf("%s",test);
puts(test);


//input
AA BB

//output
AA
BB

• 백준 관련

이번에 여러가지 해보면서 확실해졌는데

1. 모든 input이 끝나지 않아도 중간 중간 output이 정답대로 나와도 정답처리가 된다.
2. rewind, fflush는 백준에서 지양하더라

오늘 스택을 직접 구현해봤는데 마침 이 알고리즘에서 사용할수 있겠다 싶어서 스택을 사용해봤다.

스택 구현 코드는 길어서 빼겠다

int main()
{
	int N;
	scanf("%d ",&N);

	Stack<char> stack;
	vector<char> result;
	result.reserve(INIT_STACK_SIZE);

	char temp;

	for (int i = 0; i < N; )
	{
		temp = getchar();

		if (temp == '\n')
		{
			while (stack.IsEmpty() == false)
			{
				result.push_back(stack.Pop());
			}
			result.push_back('\n');
			++i;
		}
		else if (temp == ' ')
		{
			while (stack.IsEmpty() == false)
			{
				result.push_back(stack.Pop());
			}
			result.push_back(' ');
		}
		else
		{
			stack.Push(temp);
		}
	}

	for (const auto & data : result)
	{
		cout << data;
	}
}

||사용 기법

• Stack

||풀면서 느낀 것

• 다른 방법도 많다

다른 사람들의 코드도 보았는데 strtok을 사용한게 꽤 인상에 깊었다.

문자열에 관한 문제일때 문자열을 다루는 함수를 같이 잘 생각해 봐야겠다.

||새로 알게 된것

• queue는 range based roop가 불가능하다!

큐와 범위 기반 반복문으로 결과값을 간단하게 뽑으려 했었는데 큐는 begin이 없어서 안되더라..!

좀 더 알아보니 컨테이너 어댑터는 불가능 했었는데 생각해보면

컨테이너를 제한시켜 그에 맞게 사용하는 모든 컨테이너 어댑터에 begin과 end가 있기에는 어렵다고 생각이 들었다.

어떻게 보면 당연했던 것~

• scanf의 문자열 입력 받기

이건 질문에 답변을 해주려 알아보다가 알게 된것인데

scanf의 문자열은 개행문자 뿐만아니라 공백문자도 끝으로 취급한다는 것

기본인데 몰랐던 내가 한심했다 =~=

#include<stdio.h>
typedef unsigned char uc;
typedef unsigned short us;
static const int MAX_SIZE = 2501;

int main()
{
	int i, j, k;
	us N, M;
	scanf("%hu %hu", &N, &M);
	short size = N * M;

	int result = 0;
	uc a[MAX_SIZE];
	uc b[MAX_SIZE];


	for (i = 0; i < size; ++i)
	{
		scanf("%1d", &a[i]);
		/*scanf(" %c", &a[i]);
		a[i] -= 48;*/
	}
	for (i = 0; i < size; ++i)
	{
		scanf("%1d", &b[i]);
		/*scanf(" %c", &b[i]);
		b[i] -= 48;*/
	}
	

	if (N < 3 || M < 3)
	{
		for (i = 0; i < size; ++i)
		{
			if (a[i] != b[i])
			{
				printf("-1");
				return 0;
			}
		}
		printf("0");
		return 0;
	}


	for (i = 0; i <= N - 3; ++i)	
	{
		for (j = M * i; j <= M * (i + 1) - 3; ++j)
		{
			if (a[j] != b[j])
			{
				a[j + (M * 0)] = !a[j + (M * 0)]; a[j + (M * 0) + 1] = !a[j + (M * 0) + 1]; a[j + (M * 0) + 2] = !a[j + (M * 0) + 2];
				a[j + (M * 1)] = !a[j + (M * 1)]; a[j + (M * 1) + 1] = !a[j + (M * 1) + 1]; a[j + (M * 1) + 2] = !a[j + (M * 1) + 2];
				a[j + (M * 2)] = !a[j + (M * 2)]; a[j + (M * 2) + 1] = !a[j + (M * 2) + 1]; a[j + (M * 2) + 2] = !a[j + (M * 2) + 2];
				++result;
			}
		}

		if (a[M - 2] != b[M - 2] || a[M - 1] != b[M - 1])
		{
			result = -1;
			break;
		}
	}

	for (i = size - 1; size - (M * 2) < i; --i)
	{
		if (a[i] != b[i])
		{
			result = -1;
			break;
		}
	}

	printf("%d", result);
	return 0;
}

약 30분동안 고민했지만 로직이 생각나지 않았던 문제.. 나에게는 너무 어려웠다..

||사용 기법

• 그리디

||풀면서 느낀 것

• 여러 Input값을 생각 못하고 테스트 케이스만 통과되면 제출하는 버릇이 있다.

그래서 그런지 여러 예외 처리를 하지 못하는 모습을 보이고 있다.

반례 또한 스스로 생각해야 하는데 질문 게시판에서 찾아보게되더라 =~=

이런 다양한 Input값을 통한 예외, 반례 이런걸 스스로 생각 하는 습관을 들일것이다.

• 올바른 자료형 채택

이번에는 자료형을 무작정 int가 아닌 제한된 범위에 맞는 자료형을 맞추려 시도했다.

근데 꼼꼼히 생각하지 않았는지 이 때문에 여러 문제가 생기고 시간이 많이 소요됐다.

특히 배열의 최대 사이즈가 2500인데 unsigned char로 잡는 바람에 로직이 다 맞음에도 틀렸다. 시발

• 좀 더 꼼꼼한 설계

위와 비슷한 맥락이다. 항상 문제를 파악하고 설계를 하고 손코딩을 해보지만 설렁설렁한다는 느낌이 있어서

이번에 시간이 많이 소요되었다. 이번에 반복문에서 out of range, out of bound 도 많이 났었고

인덱스 규칙도 하나를 빼먹거나 해서 좀 꼼꼼하게 설계를 해야겠다.

||새로 알게 된것

• byte라는 타입은 C++ 17에 추가 되었으며(std::byte) 산술 연산이 불가능하다.

이번에 알맞은 자료형을 사용하려고 하면서 byte를 사용해봤는데 산술연산이 불가능했다.

나중에 연산이 안되는 점을 이용할 수 도 있겠다.

연산을 하려면 char종류나 uint8을 사용하면 되겠다.

||나아 진것

• 문제 파악

예전에는 난독증 마냥 읽어도 무슨말인지 모르는 경우가 많았는데 

최근에는 문제 해석은 잘 되는듯 하다!

개요

이번에 한 알고리즘 풀이에 사용되어서 공부하게 됐다.

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

특징

힙은 이진트리의 종류중 하나이고 최대 힙, 최소 힙 으로 나누어져 있고

루트 노드가 언제나 그 트리의 최대값 혹은 최소값을 가진다는 특성이 있다.

이는 루트 노드 뿐만 아니라

루트노드가 최대값이라면 모든 노드가 자기 자식 노드보다 큰 값을 가지고 있고 = 최대 트리

루트노드가 최소값이라면 모든 노드가 자기 자식 노드보다 작은 값을 가지고 있다. = 최소 트리

또한 완전 이진 트리어야 한다. 중간에 빈 노드가 없다는게 중요!

그래서 완전 이진 트리이기 때문에 배열로 구현하는게 정말 효율적이다.

배열로 구현하는게 정말 효율적이다 :

● 자기의 Index로 자식의 Index를 알수있고 그 반대도 가능하다

● 또한 특정 레벨의 최대 노드 개수도 간단히 구할 수 있다.

●

배열의 단점인 중간에 값을 삽입하는 일이 없다.● 인덱스 순서대로 삽입하면 트리가 기울어질일이 없다.

주의 할 것은 이 힙은 최대, 최소에 중점을 두었기 때문에

그 나머지 노드에 대해서는 느슨한 정렬 상태를 유지한다. [이진 탐색 불가능]

최대 트리여도 하위 레벨 노드보다 작을수도, 최소 트리라면 하위 레벨 노드보다 클 수도 있다는 말이다.

암튼 정리하면

최대 힙 = 최대 트리 + 완전 이진 트리

최소 힙 = 최소 트리 + 완전 이진 트리

왜 사용하는가?

오직 어떤 최소값이나 최대값을 얻고 싶다면 리스트나 배열을 한번 정렬해서 앞에서 쭉 가져오면 된다.

하지만 어떤 데이터가 추가되어 다시 정렬 후 최대, 최소 값을 가져올때 이 힙이 굉장히 강력한데

힙을 이용한 priority_queue과 퀵정렬을 사용하여 실험해 보았다.

데이터를 계속 추가하면서 내림차순으로 정렬하여 최대값을 출력한다.

암튼 데이터의 추가,삭제가 빈번할 때 최대, 최소 값을 얻고자 할 때 사용해야겠다 !

구현

생성 & 소멸

Private 멤버

데이터 삽입

데이터 삭제

결론

사용처

언리얼에서 포스트 프로세스라는 기능이 있는데 여기서 우선 순위를 정하여 렌더링 순서를 정할 수 가 있다.

이때 힙을 이용하면 편리할거 같다.

나머지는 또 생각해봐야겠다.

추가

stl::prioirity_queue & stl::make_heap

더보기

stl에 저 두가지가 비슷하게 쓰이는데

N3337에서 priority_queue은 힙으로 구현되고 생성자로 make_heap이 사용 된다고 한다.

 

 코드 내 주석으로 보면 복사나 이동이 필요할때 make_heap이 사용된다.

 

가장 뚜렷한 차이는

make_heap같은 경우는 이미 있던 컨테이너를 힙구조로 만들기때문에

루트 노드 뿐만아니라 다른 노드에도 접근이 가능할수도 있다는 것과

 

priority_queue같은 경우는 어댑터 클래스로 public한 함수가 루트 노드에만 접근이 가능하다는 점이 있다.

어떻게 보면 힙의 캡슐화 같은 느낌이 더 강하게 든다.

 

https://stackoverflow.com/questions/11266360/when-should-i-use-make-heap-vs-priority-queue

 

When should I use make_heap vs. Priority Queue?

I have a vector that I want to use to create a heap. I'm not sure if I should use the C++ make_heap function or put my vector in a priority queue? Which is better in terms of performance? When shou...

stackoverflow.com

https://leeminju531.tistory.com/20?category=979284 

 

(C++ STL) priority_queue, make_heap 제대로 이해하기(1)

http://www.cplusplus.com/reference/algorithm/make_heap/ make_heap - C++ Reference custom (2)template void make_heap (RandomAccessIterator first, RandomAccessIterator last, Compare comp ); www.cplusp..

leeminju531.tistory.com

이 문제 덕분에 우선순위 큐를 처음으로 사용하게 되었다.

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;

int main()
{
	int N;
	cin >> N;

	priority_queue<int, vector<int>,greater<int>> list;
	for (int i = 0; i < N; ++i)
	{
		int temp = 0;
		cin >> temp;
		list.push(temp);
	}

	int result = 0;
	while (list.size() != 1)
	{
		int cardA = list.top();
		list.pop();
		int cardB = list.top();
		list.pop();
		list.push(cardA + cardB);
		result += cardA + cardB;
	}

	cout << result;

	return 0;
}

근데 최근에 삽입정렬을 보아서 문득 든 생각이였는데

어차피 최소값 두개를 합쳐서 그 값을 다시 넣는걸 반복하는거면

처음에 값을 받고 퀵정렬로 정렬 후에 연산을 하면 거의 정렬 된 상태이니까 삽입정렬도 메리트 있지 않을까? 생각했다.

결과는 정답은 나오지만 시간초과였다

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

void Swiching(int & a, int & b)
{
	int temp = a;
	a = b;
	b = temp;
}

void InsertionSort(vector<int> & numList, int size)
{
	for (int i = 1; i < size; ++i)
	{
		for (int j = i; 0 < j; --j)
		{
			if (numList[j] < numList[j - 1])
			{
				Swiching(numList[j - 1], numList[j]);
			}
		}
	}
}

int main()
{
	int N;
	cin >> N;

	vector<int> list;
	for (int i = 0; i < N; ++i)
	{
		list.push_back(0);
		cin >> list[i];
	}

	sort(list.begin(), list.end());

	int result = 0;
	for (int i = 0; i < N - 1; ++i)
	{
		list[i + 1] = list[i] + list[i + 1];
		result += list[i + 1];
		InsertionSort(list, N);
	}

	cout << result;

	return 0;
}

이렇게 업데이트 되는 배열속에서 최대, 최소값을 계속 확인해야하는 상황이라면

일단은 우선순위 큐를 사용하는게 빠르다고 느꼈다 =~=

#include <iostream>
using namespace std;

typedef int integer;

void Merge(integer * arr, integer * temp, int start, int mid, int end)
{
	for (int i = start; i <= end; ++i)
	{
		temp[i] = arr[i];
	}

	int part1 = start;
	int part2 = mid + 1;
	int index = start;

	while (part1 <= mid && part2 <= end)
	{
		if (temp[part1] <= temp[part2])
		{
			arr[index] = temp[part1];
			++part1;
		}
		else
		{
			arr[index] = temp[part2];
			++part2;
		}
		++index;
	}

	for (int i = 0; i <= mid - part1; ++i)
	{
		arr[index + i] = temp[part1 + i];
	}
}


void MergeSort(integer * arr, integer * temp, int start, int end)
{
	if (start < end)
	{
		int mid = (start + end) / 2;
		MergeSort(arr, temp, start, mid);
		MergeSort(arr, temp, mid + 1, end);
		Merge(arr, temp, start, mid, end);
	}
}

void MergeSort(integer * arr, const int & size)
{
	integer * temp = new integer[size];
	MergeSort(arr, temp, 0, size - 1);
}


int main()
{
	int many = 0;
	cin >> many;
	
	integer * num = new integer[1'000'000];
	for (int i = 0; i < many; ++i)
	{
		cin >> num[i];
	}
	MergeSort(num, many);
	for (int i = 0; i < many; ++i)
	{
		cout << num[i] << '\n';
	}
}

퀵정렬로도 풀어지는 문제지만

N^2의 경우를 생각해서 N log N을 보장하는 병합정렬로 풀었다.

이번에 숫자 정렬자(digit separator)를 처음 알게됐는데 앞으로 자주 써야겠다. 보기 훨씬 편한듯ㅎㅎ

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <functional>
using namespace std;
typedef int integer;

int main()
{
	string N;
	cin >> N;

	integer tempInt = 0;
	for (const char & data : N)
	{
		tempInt += data - '0';
	}

	if (tempInt % 3 == 0)
	{
		sort(N.begin(), N.end(), greater<>());
		if (N[N.length() - 1] == '0')
		{
			cout << N;
			return 0;
		}
	}
	cout << "-1";
	return 0;
}

좀 오래 걸렸었는데 그만큼 배우는게 있었다

1. 일단 문제 파악을 처음에 잘못했다

들어오는 N이 100,000 이하 라고 처음에 이해를 해버려서 처음엔 Out of range가 났었다.

자리수가 100,000 이하 였던 것.. =_=

굉장히 큰 수이므로 정수로 해결하던 부분을 문자열로 해결하는 방식으로 변경했다.

2. 복잡한 방식 채택

그 후에는 시간 초과가 났었는데

그 이유는 불필요한 for문을 사용했었다.

30의 배수가 되려면 각 자리의 합이 3의 배수이고 마지막 자리가 0이면 순서가 어떻든지 가능한 조건이였다.

근데 나는 내림차순으로 정렬하여 prev_permutation 을 사용하면서 매번 3, 2, 5 로 나눈 값이 0인지 확인하였는데

이부분이 시간 초과의 범인이였다

3.  잘못알고 있었던 atoi

입력을 123을 한다면

처음엔 예상 값이 그대로

1

2

3

이 나올줄 알았는데

123

23

3

이 나온다..

주소를 받아 integer가 아닌 문자가 나올때까지 읽기때문에 이러한 값이 나왔다..

그래서 '0'을 빼주어 integer로 변환 시켜 주었다.

4. 새로 알게 된 사용법

생각해보면 string은 char의 집합이고 char또한 정수형이기 때문에 sort함수를 이용할수 있지 않을까 해서

실행해봤는데 잘 됐다

그리고 시간초과가 나와서 여러가지 보다가

cout의 endl이 개행문자 출력과 함께 출력버퍼를 비우는 역할을 하기에 시간을 좀 먹는다고 한다.

'\n'을 통해 개행을 해야겠다.

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <functional>
using namespace std;

int main()
{
	int N;
	cin >> N;

	vector<int> ropeList;
	
	for (int i = 0; i < N; ++i)
	{
		int rope = 0;
		scanf("%d", &rope);
		ropeList.push_back(rope);
	}

	sort(ropeList.begin(), ropeList.end(), greater<>());

	int maxW = 0;
	for (int i = 0; i < ropeList.size(); ++i)
	{
		int temp = ropeList[i] * (i + 1);
		if (maxW <= temp) maxW = temp;
	}
	cout << maxW;
	return 0;
}

분명 맞다고 생각했는데 여러번 틀렸다

틀린 부분은 저 마지막 for문에서 최대값 구하는 부분인데

이전 코드에서는 최대값이 아니면 바로 끝냈기 때문.

"5 1 1 1 3 1" 같은 입력값을 예로 들면

먼저 내림차순을 한다. 3 1 1 1 1 (5는 로프 개수 이므로 제외)

3 최대 3

1 최대 2

나는 여기서 멈추었었는데 끝까지 가보면

1 최대 3

1 최대 4

1 최대 5

으로 최대 중량 5를 구할 수 있다.

이러한 끝까지 생각해야하는 문제도 신경써야겠다.!