[인프런 워밍업 클럽 CS 3기] 1주차 미션

운영체제

1.

    while(true){
      wait(1); // 1초 멈춤
      bool isActivated = checkSkillActivated(); // 체크
    }

위 코드는 1초 마다 플레이어가 스킬을 사용했는지 체크하는 코드입니다. 이 방식은 폴링방식입니다. 1초마다 체크하기 때문에 성능에 좋지 않습니다. 이를 해결하기 위한 방식으로 어떤 걸 이용해야 할까요?

• 인터럽트 방식 사용. 사용자가 플레이어의 스킬을 사용하기 위해 마우스/키보드 등으로 입력을 하면 인터럽트를 발생시켜 확인하도록 하면 됨.

2. 프로그램과 프로세스가 어떻게 다른가요?

• 프로그램

  • 하드디스크 등과 같은 저장장치에 저장된 명령문의 집합체

  • 정적인 상태

• 프로세스

  • 실행 중인 프로그램

  • 동적인 상태

• 저장장치(HDD, SDD)에 저장된 프로그램이 메모리(RAM)에 올라갔을 때 해당 프로그램을 프로세스라 칭함

• 운영체제가 메모리 등의 필요한 자원을 할당해준 '실행 중인 프로그램' 이므로 프로그램을 실행하면 운영체제로부터 실행에 필요한 자원을 할당받아 '프로세스'가 됨

  • 프로세스는 cpu, 운영에 필요한 주소 공간, "code, data, stack, heap"의 구조로 되어있는 메모리 영역 등을 운영체제에서 할당 받음

3. 멀티프로그래밍과 멀티프로세싱이 어떻게 다른가요?

• 멀티프로그래밍

  • 메모리에 여러 개의 프로세스를 올려서 처리할 때 CPU에서 여러 개의 프로세스를 처리하는 것.

    • ex) A프로세스 작업 1초 후 B프로세스 작업 1초 후 C프로세스 작업 1초

• 멀티프로세싱

  • 프로세서(CPU)가 여러 개 있는 것을 멀티프로세서라고 함. 이 멀티프로세서로 작업을 처리하는 것을 멀티프로세싱이라 함.

4.운영체제는 프로세스를 관리하기 위해서 어떤 것을 사용하나요?

• PCB(Process Control Block)

  • 프로세스가 만들어질 때 운영체제가 생성 후 저장

  • 해당 프로세스의 정보(포인터, 프로세스 상태, 프로그램 카운터 등)를 가짐

  • 연결리스트로 저장

  • 프로세스가 종료되면 운영체제는 해당 PCB를 제거

• PCB를 이용해 멀티 프로그래밍을 할 수 있음.

5. 컨텍스트 스위칭이란 뭔가요?

• 프로세스를 실행하는 중에 다른 프로세스를 실행하기 위해 실행 중인 프로세스의 상태를 저장하고 다른 프로세스의 상태값으로 교체하는 작업

• 현재 실행 중인 A 프로세스의 PCB에 현 상태를 저장한 후, 다음으로 실행할 B 프로세스의 PCB에 저장된 상태를 불러와 CPU를 세팅

자료구조와 알고리즘

1. 여러분은 교실의 학생 정보를 저장하고 열람할 수 있는 관리 프로그램을 개발하려고 합니다.

이 때 여러분이라면 학생의 정보를 저장하기 위한 자료구조를 어떤 걸 선택하실 건가요? 이유를 함께 적어주세요.

• 해시테이블.

  • 중복되지 않는 학번 부여를 통해 해당 학생의 정보(이름, 성적, 개인정보(키, 주소, 비상연락망) 등)를 관리해야하므로 (key, value)의 구조로 (학번, 학생 정보)를 저장하여 학번을 검색하면 모든 정보를 볼 수 있게 함.

2. 여러분은 고객의 주문을 받는 프로그램을 개발하려고 합니다. 주문은 들어온 순서대로 처리됩니다. 이 때 여러분이라면 어떤 자료구조를 선택하실 건가요? 이유를 함께 적어주세요.

• 주문이 들어온 순서대로 처리되기 위해서는 선입선출(FIFO)이 필요하므로 큐 구조를 사용함.

3. 우리가 구현한 스택은 0번 인덱스, 즉 입구쪽으로 데이터가 삽입되고 나오는 구조입니다. 반대로 마지막 인덱스, 즉 출구쪽으로 데이터가 삽입되고 나오는 구조로 코드를 변경해주세요.

• 기존 구조

 using warmingup_CS.LinkedList;

namespace warmingup_CS.Stack;

public class StackTest
{
	private LinkedListTest _linkedList;

	public void Push(object data)
	{
		_linkedList.InsertAt(0, data);
	}

	public object Pop()
	{
		try
		{
			return _linkedList.DeleteAt(0);
		}
		catch (Exception e)
		{
			return null;
		}
	}

	public object Peek()
	{
		return _linkedList.GetNodeAt(0);
	}

	public bool IsEmpty()
	{
		return _linkedList.Count == 0;
	}
}

• 수정 구조

using warmingup_CS.LinkedList;

namespace warmingup_CS.Stack;

public class StackTest
{
	private LinkedListTest _linkedList;

	public void Push(object data)
	{
		_linkedList.InsertLast(data);
	}

	public object Pop()
	{
		try
		{
			return _linkedList.DeleteLast();
		}
		catch (Exception e)
		{
			return null;
		}
	}

	public object Peek()
	{
		return _linkedList.GetNodeAt(this._linkedList.Count - 1);
	}

	public bool IsEmpty()
	{
		return _linkedList.Count == 0;
	}
}

4. 해시테이블의 성능은 해시 함수에 따라 달라집니다. 수업 시간에 등번호를 이용해 간단한 해시 함수를 만들어봤습니다. 이번엔 등번호가 아닌 이름을 이용해 데이터를 골고루 분산시키는 코드로 수정해주세요.

힌트: charCodeAt() 함수를 이용

예시: name1 = "이운재"; name1.charCodeAt(0); // 51060 이운재의 0번 인덱스 ‘이’의 유니코드 출력

• 기존에 string을 Key로 받는 함수를 오버로딩

  • C#과 JS의 차이로 이렇게 구현했는데 다음에는 JS코드로 해보는 것이 더 편할 것 같음

public class HashTableTest
{
	private DoublyLinkedListTest[] _array;

	public HashTableTest()
	{
		_array = new DoublyLinkedListTest[10];
		for (int i = 0; i < 10; i++)
		{
			_array[i] = new DoublyLinkedListTest();
		}
	}

	public int HashFunction(int number)
	{
		return number % 10;
	}

	public void Set(int key, object value)
	{
		_array[HashFunction(key)].InsertAt(0, new HashTableData(key, value));
	}

	public object Get(int key)
	{
		var current = _array[HashFunction(key)].Head;
		while (current != null)
		{
			if ((int)((HashTableData)current.Data).Key == key)
			{
				return ((HashTableData)current.Data).Value;
			}
			current = current.Next;
		}
		return "null";
	}

	public object Remove(int key)
	{
		var list = _array[HashFunction(key)];
		var current = list.Head;
		int deleteIndex = 0;
		while (current != null)
		{
			if ((int)((HashTableData)current.Data).Key == key)
			{
				return list.DeleteAt(deleteIndex).ToString();
			}
			current = current.Next;
			deleteIndex++;
		}
		return "null";
	}

	//문자열 Key에 대한 해시 함수
	public int HashFunction(string str)
	{
		int sum = 0;
		for (int i = 0; i < str.Length; i++)
		{
			sum += str[i];
		}
		return sum % 10; // 해시 값 계산
	}
	public void Set(string key, object value)
	{
		_array[HashFunction(key)].InsertAt(0, new HashTableData(key, value));
		Console.WriteLine($"{key}, {HashFunction(key)}");
	}

	public object Get(string key)
	{
		var current = _array[HashFunction(key)].Head;
		while (current != null)
		{
			if (((HashTableData)current.Data).Key.ToString() == key)
			{
				return ((HashTableData)current.Data).Value;
			}
			current = current.Next;
		}
		return "null";
	}

	public object Remove(string key)
	{
		var list = _array[HashFunction(key)];
		var current = list.Head;
		int deleteIndex = 0;
		while (current != null)
		{
			if (((HashTableData)current.Data).Key.ToString() == key)
			{
				return list.DeleteAt(deleteIndex).ToString();
			}
			current = current.Next;
			deleteIndex++;
		}
		return "null";
	}
}

public class HashTableData
{
	private object _key;
	public object Key => _key;
	private object _value;
	public object Value => _value;

	public HashTableData(object key, object value)
	{
		_key = key;
		_value = value;
	}

	public override string ToString()
	{
		return JsonSerializer.Serialize(this);
	}
}

• 이름으로 바꿨을 때 Key값

이운재, 4

최진철, 8

홍명보, 2

유상철, 5

송종국, 9

박지성, 4

김남일, 0

이영표, 3

최태욱, 5

설기현, 4

이천수, 8

• 이천수와 최진철이 8이므로 해당 키를 이용하여 비교 출력

var hashTable2 = new HashTableTest();
hashTable2.Set("이운재", 1);
hashTable2.Set("최진철", 4);
hashTable2.Set("홍명보", 20);
hashTable2.Set("유상철", 6);
hashTable2.Set("송종국", 22);
hashTable2.Set("박지성", 21);
hashTable2.Set("김남일", 5);
hashTable2.Set("이영표", 10);
hashTable2.Set("최태욱", 8);
hashTable2.Set("설기현", 9);
hashTable2.Set("이천수", 14);

Console.WriteLine("최진철: " + hashTable2.Get("최진철"));
hashTable2.Remove("최진철");
Console.WriteLine("최진철: " + hashTable2.Get("최진철"));
Console.WriteLine("이천수: " + hashTable2.Get("이천수"));

• 출력값