24.09.09 코테, CS

코테

2920 음계

내 풀이

#include <bits/stdc++.h>

int temp1;
int temp2 = 0;
bool ascend = true;
int main() {
	for (int i = 0; i < 8; i++)
	{
		std::cin >> temp1;
		if (temp1 == 1 and i == 0)
		{
			ascend = true;
			temp2 = temp1;
		}
		else if (temp1 == 8 and i == 0)
		{
			ascend = false;
			temp2 = temp1;
		}
		else
		{
			if (temp2 == 0)
			{
				temp2 = temp1;
				continue;
			}
			int ans = temp2 - temp1;
			if (ans < 0)
				ans *= -1;
			if (ans > 1)
			{
				std::cout << "mixed";
				return 0;
			}
			temp2 = temp1;
		}
	}
	if (ascend)
		std::cout << "ascending";
	else
		std::cout << "descending";

	return 0;

오랜만에 코테 문제를 풀어봤다.

배열을 이용해도 풀 수 있을 것 같지만 1-8까지 나온다는 점과 한 번씩 등장한다는 점에 꽂혀서 좀 이상하게 코드를 짜봤다.

중간 중간 예외처리를 안해줘서 좀 문제가 있었다.

문제 풀이

1. 리스트에서의 원소를 차례대로 비교
2. 비교할 때 두 원소를 기준으로 오름차순/내림차순 여부를 체크
   1. 오름차순 및 내림차순이 모두 False 인 경우 mixed 출력

#include <bits/stdc++.h>
using namespace std;

int main() 
{
	bool ascend = true;
	bool descend = true;
	vector<int> array;

	for (int i = 0; i < 8; ++i)
	{
		int temp;
		cin >> temp;
		array.push_back(temp);
	}

	for (int i = 1; i < 8; ++i)
	{
		if (array[i] > array[i - 1])
			descend = false;
		else if (array[i] < array[i - 1])
			ascend = false;
	}

	if (ascend)
		cout << "ascending";
	else if (descend)
		cout << "descending";
	else
		cout << "mixed";

	return 0;
}

확실하게 편해졌다.

코테를 너무 많이 놔서 그냥 머리가 돌덩이가 됐다.. 복구를 언능 해야할 듯

2798 블랙잭

n장의 카드중 3장을 골라서 플레이어의 카드 합이 m을 넘지 않으면서 m과 최대한 가깝게 만들어야 한다.

내 풀이

#include <bits/stdc++.h>
using namespace std;

int main()
{
	int n, m, max = 0;
	vector<int> array;
	cin >> n >> m;
	for (int i = 0; i < n; ++i)
	{
		int temp;
		cin >> temp;
		array.push_back(temp);
	}

	for (int i = 0; i < n-2; ++i)
	{
		for (int j = i + 1; j < n - 1; ++j)
		{
			for (int k = j + 1; k < n; ++k)
			{
				int temp = array[i] + array[j] + array[k];
				if (temp <= m)
					if (temp > max)
						max = temp;
			}
		}
	}

	cout << max;
	return 0;
}

브루트포스 방식을 사용했다.

문제 풀이

1. 카드 중 3개씩 뽑는 모든 경우의 수는 C(n, 3)이며, n은 최대 100이다.
2. 단순 3중 반복문으로 모든 경우의 수를 확인하여 문제를 해결할 수 있다.
   1. 보통 파이썬 1초에 2000만 정도

1874 스택 수열

문제 풀이

1. 스택에 원소를 삽입할 때는, 단순히 특정 수에 도달할 때까지 삽입하면 된다.
2. 스택에서 원소를 연달아 빼낼 때 내림차순을 유지할 수 있는지 확인한다.

#include <bits/stdc++.h>
using namespace std;

int main()
{
	int n, cnt = 1;
	vector<int> array;
	vector<char> ans;
	cin >> n;
	for (int i = 0; i < n; ++i)
	{
		int data;
		cin >> data;
		while (cnt <= data)
		{
			array.push_back(cnt);
			cnt += 1;
			ans.push_back('+');
		}
		if (array.back() == data)
		{
			array.pop_back();
			ans.push_back('-');
		}
		else
		{
			cout << "NO";
			return 0;
		}
	}

	for (int i = 0; i < ans.size(); ++i)
	{
		cout << ans[i] << "\\n";
	}

	return 0;
}

문제파악이 아직 좀 부족하다 어려운 것 같다.

CS

가상 메모리와 스택, 힙

• 가상 메모리(virtual memory)는 현대 컴퓨터 시스템에서 중요한 개념으로, 물리적 메모리(RAM)를 확장하여 프로그램이 더 많은 메모리를 사용할 수 있도록 하는 기술이다. 스택(stack)과 힙(heap) 메모리 또한 가상 메모리 공간 내에서 관리되며, 각각의 역할과 관계가 있다. 이를 이해하기 위해서는 가상 메모리의 기본 개념과 스택, 힙이 어떻게 가상 메모리 내에서 동작하는지에 대해 알아야 한다.

1. 가상 메모리의 개념

• 가상 메모리는 운영체제(OS)가 각 프로세스에 대해 독립적인 메모리 주소 공간을 제공하는 메모리 관리 기법이다. 이로 인해 각 프로그램은 자신의 가상 주소 공간을 사용하며, 실제 물리적 메모리의 크기와 관계없이 더 큰 주소 공간을 사용할 수 있다.

가상 메모리의 주요 특징

• 주소 공간 분리
  • 각 프로세스는 독립적인 가상 메모리 주소 공간을 가지므로, 다른 프로세스의 메모리와 격리된다.
• 메모리 보호
  • 가상 메모리 시스템은 프로세스 간 메모리 침범을 방지하여 안정성을 보장한다.
• 페이징(paging)과 스와핑(swapping)
  • 물리적 메모리가 부족할 경우, 운영체제는 디스크의 일부(보통 페이지 파일 또는 스왑 영역)를 사용하여 덜 사용되는 페이지를 스왑할 수 있다.
• 물리 메모리 확장
  • 가상 메모리는 RAM보다 더 큰 주소 공간을 프로세스에 제공함으로써, 물리적 메모리의 한계를 극복할 수 있다.

3. 가상 메모리에서의 스택과 힙의 관계

• 스택과 힙은 서로 반대 방향으로 확장된다. 이 구조는 가상 메모리 내에서 스택과 힙이 서로 충돌하지 않도록 설계된 것이다. 프로그램이 실행되면서 스택이 위에서 아래로(높은 주소 -> 낮은 주소), 힙이 아래에서 위로(낮은 주소 -> 높은 주소) 확장되기 때문에 두 영역이 만날 때까지 사용할 수 있는 메모리 양을 최대로 확보할 수 있다.
• 이 방식은 프로그램이 사용하는 메모리를 효율적으로 관리하며, 스택 오버플로우(stack overflow)나 힙 오버플로우(heap overflow)와 같은 오류를 방지한다.

4. 가상 메모리와 스택, 힙의 메모리 관리

• 가상 메모리는 페이지(page) 단위로 관리되며, 스택과 힙의 메모리 할당 역시 가상 메모리의 페이지를 기반으로 이루어진다.

4.1. 페이지 폴트(Page Fault)와 스택 확장

• 스택이 확장될 때는, 사용 가능한 메모리 페이지를 할당받기 위해 운영체제에 요청해야 한다. 만약 스택이 기존에 할당된 페이지를 넘어 확장되면 페이지 폴트(page fault)가 발생하고, 운영체제는 추가 페이지를 할당하여 스택을 확장한다.
• 페이지 폴트는 메모리 액세스 시 일시적인 지연을 발생시킬 수 있으며, 프로그램의 성능에 영향을 미칠 수 있다.

4.2. 동적 메모리 할당과 힙 관리

• 힙 메모리는 동적 메모리 할당 요청이 들어올 때마다 malloc이나 new와 같은 메모리 할당 함수가 가용 페이지를 검색하고, 메모리를 할당한다.
• 힙은 비연속적으로 메모리를 할당할 수 있기 때문에 단편화(fragmentation)가 발생할 수 있다. 이는 힙 메모리 할당과 해제를 반복할 때 가용 메모리가 충분히 있음에도 불구하고 큰 연속 블록이 없어 메모리 할당이 실패하는 현상을 의미한다.

5. 가상 메모리의 장점과 스택, 힙의 사용

• 효율적 메모리 사용
  • 가상 메모리를 사용하면 물리적 메모리보다 더 큰 프로그램을 실행할 수 있고, 여러 프로그램이 동시에 실행될 수 있다.
• 메모리 보호
  • 가상 메모리 시스템에서는 각 프로세스가 독립된 메모리 공간을 가지므로, 스택과 힙 오버플로우로 인한 다른 프로세스의 메모리 침범을 방지할 수 있다.
• 유연한 메모리 할당
  • 동적 메모리 할당을 통해 프로그램이 실행 중에 필요에 따라 메모리를 사용할 수 있다. 스택과 힙은 서로 반대 방향으로 확장되므로, 프로그램이 요구하는 메모리 양에 따라 유연하게 사용할 수 있다.