정신과 시간의 방

전체 글 306

카테고리 설명
게임 프로그래머가 되기 위한 청춘의 기록
  • 문제 풀이#include #include using namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int input[9] = { 0 }; for (int i = 0; i > input[i]; } sort(input, input + 9); do { int sum = 0; for (int i = 0; i  메모문제의 기본 원리는 9개의 수 중에서 7개의 수를 조합해 그 합이 100이 되는 경우 해당값들을 출력하는 것이다.DFS 등으로 구하는 방법도 있지만 값을 빠르게 찾기 위해서 순열과 조합을 구할 때 유용한 algrorithm 헤더에 있는 next_permutaion() 함수를 사용했다...

  • 문제 풀이vector에 값을 입력받아서 바로 sort 함수로 푸는 방법이 가장 간단하지만, 단계별로 풀어보기에 제시된 문제 설명에 따르면 이 문제의 원래 의도는 시간 복잡도가 O(n²)인 정렬 알고리즘 즉, 2중 for문을 사용하는 정렬을 사용해보는 것이다.해당 시간복잡도에 해당하는 정렬의 예로 삽입 정렬(시간복잡도상 최고는 O(n), 최악과 평균은 O(n²)), 거품 정렬(=버블 정렬), 선택 정렬이 있다.따라서 이번 문제는 내장 정렬함수, 삽입정렬, 버블정렬, 선택정렬 이렇게 4가지 경우를 모두 풀어보았다.1. sort함수 사용#include #include #include using namespace std;int main(){ vector v; int n = 0; cin >> n; for (int..

  • 문제 풀이#include #include #include using namespace std;int main(){ vector v(5); int sum = 0, avg = 0, mid = 0; for (int i = 0; i > v[i]; sum += v[i]; } sort(v.begin(), v.end()); avg = sum / 5; mid = v[2]; cout  메모입력받은 값을 한번 정렬해주고 평균과 중간값을 출력하기만 하면 되는 간단한 문제이다.vector에 바로 값을 입력받아 sort 함수를 사용해 정렬했다.

  • 문제 풀이#include #include #include using namespace std;int main(){ int n = 0; vector v; cin >> n; // 입력받은 값을 한자리씩 끊어서 벡터에 하나씩 저장 while (n > 0) { v.push_back(n % 10); n /= 10; } // 오름차순으로 sort한 다음 sort(v.begin(), v.end()); // reverse 함수로 내부 데이터를 반대로 뒤집어줌 reverse(v.begin(), v.end()); // 최종 결과 출력 for (int i = 0; i

  • 문제 풀이#include using namespace std;void Swap(int& a, int& b){ int temp = a; a = b; b = temp;}int main(){ int n = 0, k = 0; int input[1000] = { 0 }; cin >> n >> k; for (int i = 0; i > input[i]; } for (int i = 0; i input[j + 1]) { Swap(input[j], input[j+1]); } } } // 끝에서부터 k번째 인덱스에 해당하는 값을 출력해야 하므로 // 최종 결과값은 n - k번째 값이 된다. int result = input[n - k]; cout  메모입력 받은 값을 오름차순 한 뒤 뒤에서부터 K번째에 해..

  • 문제 풀이#include using namespace std;int main(){ int n = 0; unsigned int result = 0; cin >> n; result = n * 4; cout  메모패턴만 알고나면 허무하리만치 간단한 문제다.정사각형이 겹쳐지지 않게 N개까지 아래에 늘어나는 패턴이 있는데, 모든 정사각형의 한 변이 동일하게 설정되어 있다.이때 도형의 둘레 길이는 n * n인 정사각형의 길이와 같기 때문에 결과값은 n * 4가 된다.한가지 주의할 점은 N으로 입력받을 수 있는 값의 범위가 최대 10의 9제곱까지이므로 이는 int형에서 사용 가능한 범위를 초과한다. 따라서 unsigned int를 사용하거나 long long을 사용해서 결과값을 저장 및 출력해야 한다.

  • 문제 풀이#include using namespace std;int main(){ int input[3] = { 0 }; int result = 0; // 입력 for (int i = 0; i > input[i]; } // 정렬 for (int i = 0; i input[j + 1]) { int temp = input[j]; input[j] = input[j + 1]; input[j + 1] = temp; } } } int sum = input[0] + input[1]; int max = input[2]; if (sum  메모삼각형의 전제 조건이 되는, 각 변의 길이를 비교한 기본 성질을 이용한 문제다.변의 길이를 따졌을 때 가장 긴 변의 길이가 나머지 두 변의 길이를 더한 값..

  • 문제 풀이#include using namespace std;int main(){ int n = 0, x = 0, y = 0; int maxY = -10001, minY = 10001; int maxX = -10001, minX = 10001; cin >> n; for (int i = 0; i > x >> y; if (x > maxX) { maxX = x; } if (x maxY) { maxY = y; } if (y  메모문제 설명이 길지만 요구 사항은 무척 간단하다. X1, X2, Y1, Y2에 해당하는 각 끝점의 길이를 구해서 가로와 세로 변의 길이를 구하고 둘을 곱해서 출력해주기만 하면 된다.변의 길이를 구하기 위해 X, Y의 MAX값과 MIN값에 해당하는 값을 입력과 동시에 ..

작성일
2024. 8. 20. 22:02
작성자
risehyun
  • 문제

 

  • 풀이
#include <iostream>
#include <algorithm>

using namespace std;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int input[9] = { 0 };

	for (int i = 0; i < 9; i++)
	{
		cin >> input[i];
	}

	sort(input, input + 9);

	do
	{
		int sum = 0;
		for (int i = 0; i < 7; i++)
		{
			sum += input[i];
		}

		if (sum == 100)
		{
			break;
		}
	} while (next_permutation(input, input + 9));

	for (int i = 0; i < 7; i++)
	{
		cout << input[i] << '\n';
	}

	return 0;
}

 

  • 메모
    문제의 기본 원리는 9개의 수 중에서 7개의 수를 조합해 그 합이 100이 되는 경우 해당값들을 출력하는 것이다.
    DFS 등으로 구하는 방법도 있지만 값을 빠르게 찾기 위해서 순열과 조합을 구할 때 유용한 algrorithm 헤더에 있는 next_permutaion() 함수를 사용했다.
     
    <next_permutaion() 함수>
    이 함수는 값이 들어있는 컨테이너에서 원하는 범위를 입력하면 해당 범위 안의 값을 사전 순의 다음 순열로 바꾼 뒤, 해당 순열이 사전 상의 마지막이라면 true를, 마지막이 아니라면 false를 리턴해준다.

    따라서 do-while문과 함께 해당 함수를 사용하면 해당 값을 사용해 만들 수 있는 모든 순열의 경우를 만들 수 있게 된다.
    주의할 점은 모든 경우의 수를 따져보기 위해서는 해당 함수를 사용하기 전에 먼저 sort 함수로 컨테이너의 값을 오름차순으로 정렬해주어야 한다는 점이다.
    이와 비슷하게 내림차순으로 구하는 함수로는 prev_permutation()이 있다.

    https://cplusplus.com/reference/algorithm/next_permutation/
 

https://cplusplus.com/reference/algorithm/next_permutation/

function template <algorithm> std::next_permutation default (1)template bool next_permutation (BidirectionalIterator first, BidirectionalIterator last);custom (2)template bool next_permutation (BidirectionalIterator first, BidirectionalIterator last, Compa

cplusplus.com

 

카테고리
작성일
2024. 8. 20. 20:20
작성자
risehyun
  • 문제

 

  • 풀이
    vector에 값을 입력받아서 바로 sort 함수로 푸는 방법이 가장 간단하지만, 단계별로 풀어보기에 제시된 문제 설명에 따르면 이 문제의 원래 의도는 시간 복잡도가 O(n²)인 정렬 알고리즘 즉, 2중 for문을 사용하는 정렬을 사용해보는 것이다.
    해당 시간복잡도에 해당하는 정렬의 예로 삽입 정렬(시간복잡도상 최고는 O(n), 최악과 평균은 O(n²)), 거품 정렬(=버블 정렬), 선택 정렬이 있다.

    따라서 이번 문제는 내장 정렬함수, 삽입정렬, 버블정렬, 선택정렬 이렇게 4가지 경우를 모두 풀어보았다.

    1. sort함수 사용
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int main()
{
	vector<int> v;
	int n = 0;

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		int input = 0;
		cin >> input;

		v.push_back(input);
	}

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

	for (int i = 0; i < n; i++)
	{
		cout << v[i] << '\n';
	}

	return 0;
}

 


    2. 삽입 정렬 사용

// 삽입정렬

#include <iostream>
#include <vector>

using namespace std;
int main()
{
	vector<int> v;
	int n = 0, key = 0, i = 0, j = 0;

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		int input = 0;
		cin >> input;

		v.push_back(input);
	}

	for (i = 1; i < n; i++) 
	{
		key = v[i];
		for (j = i - 1; j >= 0 && v[j] > key; j--) 
		{
			v[j + 1] = v[j];
		}
		v[j + 1] = key;
	}

	for (int i = 0; i < n; i++)
	{
		cout << v[i] << '\n';
	}

	return 0;
}



    3. 버블 정렬 사용

// 버블정렬

#include <iostream>
#include <vector>

using namespace std;
int main()
{
	vector<int> v;
	int n = 0;

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		int input = 0;
		cin >> input;

		v.push_back(input);
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n - 1 - i; j++)
		{
			if (v[j] > v[j + 1])
			{
				int temp = v[j];
				v[j] = v[j + 1];
				v[j + 1] = temp;
			}
		}
	}

	for (int i = 0; i < n; i++)
	{
		cout << v[i] << '\n';
	}

	return 0;
}

 

    4. 선택 정렬

// 선택정렬

#include <iostream>
#include <vector>

using namespace std;
int main()
{
	vector<int> v;
	int n = 0, index = 0, tmp = 0;

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		int input = 0;
		cin >> input;

		v.push_back(input);
	}

	for (int i = 0; i < n - 1; i++)
	{
		int min = 1001;
		for (int j = i; j < n; j++)
		{
			if (min > v[j])
			{
				min = v[j];
				index = j;
			}
		}

		tmp = v[i];
		v[i] = v[index];
		v[index] = tmp;
	}

	for (int i = 0; i < n; i++)
	{
		cout << v[i] << '\n';
	}

	return 0;
}
작성일
2024. 8. 19. 21:20
작성자
risehyun
  • 문제

 

  • 풀이
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int main()
{
	vector<int> v(5);
	int sum = 0, avg = 0, mid = 0;

	for (int i = 0; i < 5; i++)
	{
		// vector의 할당 크기가 이미 정해진 경우 cin으로 바로 인덱스에 접근해서 값 할당 가능
		cin >> v[i];
		sum += v[i];
	}

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

	avg = sum / 5;
	mid = v[2];

	cout << avg << '\n' << mid;

	return 0;
}

 

  • 메모
    입력받은 값을 한번 정렬해주고 평균과 중간값을 출력하기만 하면 되는 간단한 문제이다.
    vector에 바로 값을 입력받아 sort 함수를 사용해 정렬했다.

카테고리
작성일
2024. 8. 18. 23:38
작성자
risehyun
  • 문제

 

  • 풀이
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int main()
{
	int n = 0;
	vector<int> v;

	cin >> n;

	// 입력받은 값을 한자리씩 끊어서 벡터에 하나씩 저장
	while (n > 0)
	{
		v.push_back(n % 10);
		n /= 10;
	}

	// 오름차순으로 sort한 다음
	sort(v.begin(), v.end());

	// reverse 함수로 내부 데이터를 반대로 뒤집어줌
	reverse(v.begin(), v.end());

	// 최종 결과 출력
	for (int i = 0; i < v.size(); i++) 
	{
		cout << v[i];
	}

	return 0;
}
카테고리
작성일
2024. 8. 17. 21:27
작성자
risehyun
  • 문제

 

  • 풀이
#include <iostream>

using namespace std;

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

int main()
{
	int n = 0, k = 0;
	int input[1000] = { 0 };

	cin >> n >> k;

	for (int i = 0; i < n; i++)
	{
		cin >> input[i];
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n - 1; j++)
		{
			if (input[j] > input[j + 1])
			{
				Swap(input[j], input[j+1]);
			}
		}
	}

	// 끝에서부터 k번째 인덱스에 해당하는 값을 출력해야 하므로 
	// 최종 결과값은 n - k번째 값이 된다.
	int result = input[n - k];

	cout << result;

	return 0;
}

 

  • 메모
    입력 받은 값을 오름차순 한 뒤 뒤에서부터 K번째에 해당하는 값(n - k)을 출력한다.
    메모리 제한이 1024MB이고 N의 최대 범위가 1000까지로 크지 않기 때문에 동적할당 하지 않고 배열에 입력받아 사용했다.
카테고리
작성일
2024. 8. 16. 23:25
작성자
risehyun
  • 문제

 

  • 풀이
#include <iostream>

using namespace std;

int main()
{
	int n = 0; 
	unsigned int result = 0;

	cin >> n;

	result = n * 4;

	cout << result;

	return 0;
}

 

  • 메모
    패턴만 알고나면 허무하리만치 간단한 문제다.
    정사각형이 겹쳐지지 않게 N개까지 아래에 늘어나는 패턴이 있는데, 모든 정사각형의 한 변이 동일하게 설정되어 있다.
    이때 도형의 둘레 길이는 n * n인 정사각형의 길이와 같기 때문에 결과값은 n * 4가 된다.

    한가지 주의할 점은 N으로 입력받을 수 있는 값의 범위가 최대 10의 9제곱까지이므로 이는 int형에서 사용 가능한 범위를 초과한다. 따라서 unsigned int를 사용하거나 long long을 사용해서 결과값을 저장 및 출력해야 한다.

'코딩테스트' 카테고리의 다른 글

[백준/1427번/C++] 소트인사이드  (0) 2024.08.18
[백준/25305번/C++] 커트라인  (0) 2024.08.17
[백준/14215번/C++] 세 막대  (0) 2024.08.15
[백준/9063번/C++] 대지  (0) 2024.08.14
[백준/3009번/C++] 네 번째 점  (0) 2024.08.13
카테고리
작성일
2024. 8. 15. 23:45
작성자
risehyun
  • 문제

 

  • 풀이
#include <iostream>

using namespace std;

int main()
{
	int input[3] = { 0 };
	int result = 0;

	// 입력
	for (int i = 0; i < 3; i++)
	{
		cin >> input[i];
	}

	// 정렬
	for (int i = 0; i < 3; i++)
	{
		for (int j = 0; j < 2; j++)
		{
			if (input[j] > input[j + 1])
			{
				int temp = input[j];
				input[j] = input[j + 1];
				input[j + 1] = temp;
			}
		}
	}

	int sum = input[0] + input[1];
	int max = input[2];

	if (sum <= max)
	{
		// 삼각형이 형성 되기 위한 조건 미충족
		// 따라서 max값 대신 sum - 1을 해준 값을 사용한다.
		result = (sum * 2) - 1;
	}
	else
	{
		result = sum + max;
	}

	cout << result;
	

	return 0;
}

 

  • 메모
    삼각형의 전제 조건이 되는, 각 변의 길이를 비교한 기본 성질을 이용한 문제다.
    변의 길이를 따졌을 때 가장 긴 변의 길이가 나머지 두 변의 길이를 더한 값보다 같거나 작아야 한다.

    따라서 이번 문제에서는

    1. 삼각형의 기본 성질을 미충족 한 경우
    2. 충족한 경우

    이렇게 2가지 경우의 수에 맞춰 결과를 출력해야 한다.

    문제에 따르면 막대의 길이를 연장하는 것은 불가능하지만 줄이는 것에는 제한이 없다.
    따라서 우선 입력받은 값을 오름차순으로 정렬해서 가장 긴 변과 나머지 변이 구별되도록 만든다.
    정렬 후에는 가장 긴 변이 input [2]에 입력된다. 

    이 값들을 사용해서 먼저 비교값이 될 input[0] + input [1]의 값을 변수 sum에 저장해 주고,
    가장 긴 변 input [2]를 max 변수에 할당해 준다.

    만약 1번에 해당하는 경우 max값이 sum의 값보다 작거나 같게 만들어 주기만 하면 되기 때문에
    (sum * 2)를 한 값에 -1을 해주면 조건에 맞는 결과값이 도출된다.

    반대로 2에 해당하는 경우 추가적인 연산이 필요하지 않기 때문에 바로 sum + max를 한 둘레를 그대로 출력했다.

카테고리
작성일
2024. 8. 14. 17:11
작성자
risehyun
  • 문제

 

  • 풀이
#include <iostream>

using namespace std;

int main()
{
	int n = 0, x = 0, y = 0;
	int maxY = -10001, minY = 10001;
	int maxX = -10001, minX = 10001;

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		cin >> x >> y;

		if (x > maxX)
		{
			maxX = x;
		}
		if (x < minX)
		{
			minX = x;
		}
		if (y > maxY)
		{
			maxY = y;
		}
		if (y < minY)
		{
			minY = y;
		}
	}

	x = maxX - minX;
	y = maxY - minY;

	int result = x * y;

	cout << result;


	return 0;
}

 

  • 메모
    문제 설명이 길지만 요구 사항은 무척 간단하다. X1, X2, Y1, Y2에 해당하는 각 끝점의 길이를 구해서 가로와 세로 변의 길이를 구하고 둘을 곱해서 출력해주기만 하면 된다.

    변의 길이를 구하기 위해 X, Y의 MAX값과 MIN값에 해당하는 값을 입력과 동시에 판별해서 저장해 주고 연산에 사용한다.

    처음에는 쭉 X,Y의 값을 받아 정렬해서 가장 앞과 뒤에 오는 수를 구해서 점을 구하려 했으나 입력값의 경우가 최대 10만까지 되기 때문에 자료구조에 따로 저장을 하기보다는 입력과 동시에 최대 최소 값을 판별 및 변경하는 것이 더 효율적이라고 생각해 이와 같이 코드를 작성했다.