인프런 워밍업 클럽 3기 CS - 1주차 미션
1주차 학습 내용 - 미션
자료구조 & 알고리즘
1. 여러분은 교실의 학생 정보를 저장하고 열람할 수 있는 관리 프로그램을 개발하려고 합니다.
이 때 여러분이라면 학생의 정보를 저장하기 위한 자료구조를 어떤 걸 선택하실 건가요? 이유를 함께 적어주세요.
학생의 정보를 저장하기 위해서는 이름, 학번, 반 번호 등의 데이터를 함께 관리해야 한다.
이때 빠르게 학생을 검색하고 관리할 수 있도록 키-값(Key-Value) 구조를 사용하는 해시테이블(Hash Table)을 선택하는 것이 적절하다.
2. 여러분은 고객의 주문을 받는 프로그램을 개발하려고 합니다. 주문은 들어온 순서대로 처리됩니다.
이 때 여러분이라면 어떤 자료구조를 선택하실 건가요? 이유를 함께 적어주세요.
주문이 들어온 순서대로 처리되어야 하므로 먼저 들어온 데이터가 먼저 처리되는 FIFO(First In, First Out) 구조가 필요하다.
따라서 큐(Queue)를 사용하는 것이 가장 적절하다.
3. 우리가 구현한 스택은 0번 인덱스, 즉 입구쪽으로 데이터가 삽입되고 나오는 구조입니다.
반대로 마지막 인덱스, 즉 출구쪽으로 데이터가 삽입되고 나오는 구조로 코드를 변경해주세요.
// 원래 스택 코드 -> 0번 자리에 삽입하고 0번 자리를 삭제함
push(data) {
this.list.insertAt(0, data);
}
pop() {
try {
return this.list.deleteAt(0);
} catch (e) {
return null;
}
}
--------------------------------
// 문제에서 요구하는 스택 코드 -> 마지막 자리에 삽입하고 마지막 자리를 삭제함
push(data) {
this.list.insertAt(this.list.count, data);
}
pop() {
try {
return this.list.deleteAt(this.list.count - 1);
} catch (e) {
return null;
}
}
this.list.count는 현재 연결 리스트에서 저장된 노드의 개수를 의미한다.
그러므로 this.list.count를 응용해서 0자리에 넣어줬다.
pop의 경우 마지막 인덱스를 알기위해서는 -1 까지해줘야 끝자리를 알 수 있다.
4. 해시테이블의 성능은 해시 함수에 따라 달라집니다. 수업 시간에 등번호를 이용해 간단한 해시 함수를 만들어봤습니다. 이번엔 등번호가 아닌 이름을 이용해 데이터를 골고루 분산시키는 코드로 수정해주세요.
힌트: charCodeAt() 함수를 이용 예시: name1 = "이운재"; name1.charCodeAt(0); // 51060 이운재의 0번 인덱스 ‘이’의 유니코드 출력
// 원래 코드, 등번호를 10으로 나눠서 데이터를 분산시킴
hashFunction(number) {
return number % 10;
}
--------------------------------------
// 문제에서 요구하는 코드, 아스키코드를 활용해서 이름의 성으로 데이터를 분산시킴
hashFunction(name){
return name.charCodeAt(0) % 10;
}
--------------------------------------
// 실행 코드
import { HashTable } from "./HashTable_mission.mjs";
let hashTable = new HashTable();
hashTable.set("이운재", 1);
hashTable.set("최진철", 4);
hashTable.set("홍명보", 20);
hashTable.set("유상철", 6);
hashTable.set("송종국", 22);
hashTable.set("박지성", 21);
hashTable.set("김남일", 5);
hashTable.set("이영표", 10);
hashTable.set("최태욱", 8);
hashTable.set("설기현", 9);
hashTable.set("이천수", 14);
console.log(`이운재: ${hashTable.get("이운재")}`); // 1
console.log(`박지성: ${hashTable.get("박지성")}`); // 21
console.log(`홍명보: ${hashTable.get("홍명보")}`); // 20
hashTable.remove("이운재");
console.log(`이운재: ${hashTable.get("이운재")}`); // null (제거됨)
charCodeAt을 활용해서 코드를 수정했고,
문제점이 생기게 됨.
1. TypeError: name.charCodeAt is not a function원인은 기존 코드에서는 키가 등번호, 값이 이름이었기 때문에 등번호(숫자)와
charCodeAt()이 만나면서 에러가 발생했다.이를 해결하기 위해 키와 값의 역할을 바꿔 이름을 키로, 등번호를 값으로 사용하도록 수정했다.
그 결과 에러는 해결되었고, 각 이름이 올바르게 해시 테이블에 저장되도록 변경할 수 있었다.
2. 하지만 새로운 문제 발생
현재 로직에서는 배열 크기가 10이므로, 이름의 첫 글자의 유니코드 값을
this.arr.length로 나눈 나머지를 사용하여 10개의 버킷 안에서만 데이터를 분산시키게 된다.즉, 같은 나머지 값을 가지는 성씨끼리 같은 버킷을 공유해야 하는 문제가 발생한다.
예를 들어,
"이"씨(유니코드 51060)와"한"씨(유니코드 54620)는51060 % 10 = 0, 54620 % 10 = 0이므로 둘 다
arr[0]에 저장된다.이는 실행 코드에서 주어진 인원들에게는 문제가 되지 않지만,
새로운 성씨가 추가될 경우 충돌(Collision)이 발생할 가능성이 높다.
3. 유니코드를 직접 키 값으로 사용할 경우?
유니코드를 직접 해시 키로 사용해봤지만, 그렇게 되면 해시 키 값이 51060, 44608, 48149 같은
5만이 넘는 숫자가 되어 배열을 활용한 해시 테이블의 장점(빠른 접근)이 사라지는 문제가 생긴다.
4. 결론 & 의문점
결국, 내가 문제를 잘못 이해한 것인지, 아니면 단순히 실행 코드에 있는 인원들만 고려하면
되는 문제인지 애매한 부분이 남았다.
운영체제
1. 해당 코드는 1초 마다 플레이어가 스킬을 사용했는지 체크하는 코드입니다.
while(true){
wait(1); // 1초 멈춤
bool isActivated = checkSkillActivated(); // 체크
}이 방식은 폴링방식입니다. 1초마다 체크하기 때문에 성능에 좋지 않습니다. 이를 해결하기 위한 방식으로 어떤 걸 이용해야 할까요?
폴링 방식은 CPU가 일정한 주기로 이벤트 발생 여부를 확인해야 하기 때문에 불필요한 연산이 많아 성능이 저하된다.
즉, 이벤트가 발생하지 않아도 CPU가 계속 체크해야 하므로 CPU 자원이 낭비됨이 문제를 해결하려면 인터럽트 방식을 사용해야 한다.
인터럽트 방식은 이벤트가 실제로 발생할 때만 CPU가 반응하여 처리하는 방식이므로, CPU가 불필요한 작업을 하지 않고 효율적으로 사용할 수 있다.
결론적으로 CPU는 이벤트가 발생할 때만 작업을 중단하고 처리를 한 후, 다시 원래 작업을 수행할 수 있다.
2. 프로그램과 프로세스가 어떻게 다른가요?
프로그램은 저장장치에 보관된 실행 가능한 명령어들의 집합으로 실행되지 않은 상태를 의미한다.
프로세스는 프로그램이 메모리에 적재되어 CPU에서 실행되는 상태를 뜻하며 실행 중인 코드와 필요한 메모리 공간 그리고 시스템 자원을 포함한다.
3. 멀티프로그래밍과 멀티프로세싱이 어떻게 다른가요?
멀티프로그래밍은 단일 CPU에서 여러 프로그램을 번갈아 실행하며 CPU 활용도를 높인다.
멀티프로세싱은 여러 개의 CPU를 사용해 실제로 동시에 여러 작업을 수행한다.
4. 운영체제는 프로세스를 관리하기 위해서 어떤 것을 사용하나요?
프로세스가 생성되면 운영체제는 해당 프로세스의 상태, 메모리 정보, CPU 레지스터 값, 우선순위 등의 정보를 담은 PCB(Process Control Block) 를 생성하고 저장한다. 운영체제는 PCB를 이용해 프로세스를 추적하고 관리하며, 문맥 전환(Context Switching) 시 필요한 정보를 저장하고 복원한다.
5. 컨텍스트 스위칭이란 뭔가요?
컨텍스트 스위칭(Context Switching)은 현재 실행 중인 프로세스를 중단하고 다른 프로세스를 실행하기 위해 CPU의 상태(레지스터 값, 프로그램 카운터, 스택 포인터 등)를 저장하고 복원하는 과정이다.
운영체제는 프로세스 간 전환을 원활하게 하기 위해 각 프로세스의 상태 정보를 PCB(Process Control Block) 에 저장하며 이후 프로세스가 다시 실행될 때 저장된 정보를 복원하여 이어서 작업을 수행한다.
댓글을 작성해보세요.
