wooHappening

트리계층적인 구조를 나타내는 자료 구조 (비선형 구조)부모 자식 관계의 노드들로 이루어진다.[응용 분야]1. 계층적인 조직 표현2. 컴퓨터 디스크의 디렉토리 구조 트리 용어노드 - 트리의 구성요소 간선 - 노드와 노드를 연결하는 선루트 - 최상위 노드서브 트리 - 하나의 노드와 그 노드들의 자손들로 이루어진 트리단말 노드 - 자식이 없는 노드레벨 - 트리의 각층 번호높이 - 트리의 최대 레벨차수 - 노드가 가지고 있는 자식 노드의 수 이진트리모든 노드는 최대 2개의 서브 트리를 가질 수 있다.서브트리는 공집합일 수 있음**** 이진트리에는 서브 트리 간의 순서가 존재왼쪽 서브트리, 오른쪽 서브트리 이진트리 성질1. 노드의 개수가 n개이면 간선의 개수는 n-1개이다.2. 높이가 h인 이진트리의 경우 최소 ..

정렬[안정적인 정렬 알고리즘] 중복된 값을 입력 순서와 동일하게 정렬[안정적이지 않은 알고리즘] 중복된 값을 입력 순서와 상관없이 무작위로 정렬[제자리 정렬] 원본 배열 외에 추가적인 큰 메모리 공간을 사용하지 않는 정렬 알고리즘- 버블정렬, 선택정렬, 삽입정렬, 퀵정렬퀵정렬가장 빠른 정렬 알고리즘퀵정렬은 불안정 정렬 알고리즘 [장점]빠르게 정렬 가능 O(NlgN)제자리 정렬로 추가 메모리 사용이 적음 [단점]불안정 정렬이므로 동일한 값에 대하여 순서 보장 못함 최악의 경우 O(N^2) 소요 // 정렬된 배열이거나, 거의 정렬된 경우 최악의 경우 발생피벗 선택 방법에 따라 성능 차이가 발생할 수 있다.재귀호출로 인한 오버헤드가 발생한다. p (피벗, 중심축) - 그룹을 나누는 기준 pl - 왼쪽 커서 p..

지연 로딩객체나 리소스를 실제로 필요할 때까지 로드하지 않는 방법 메모리 사용량을 최적화하고 시스템 성능을 향상시키는 강력한 기법- 가상 메모리 주소를 할당 했지만, 물리 메모리 주소와 매핑되어 있지 않은 상태 (물리 메모리에 적재도 되어 있지 않음)- 배틀그라운드에서 필요한 부분만 렌더링하고 필요하지 않은 부분은 렌더링하지 않는 것과 유사 (이는 지연 로딩은 아니지만 유사)익명 페이지와 파일 기반 페이지[익명 페이지]익명 페이지의 경우 가상 메모리만 할당되어 지연 로딩을 수행한다.해당 가상 메모리 주소로 최초 접근이 발생하면, 주 페이지 폴트가 발생하고 물리 메모리 할당 후 메모리 공간을 0으로 초기화한 뒤 (Demand Zero Memory)가상 메모리 주소와 물리 메모리 주소 매핑한다.[파일 기반 ..

문제숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.입력첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,0..

문제알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.1. 길이가 짧은 것부터2. 길이가 같으면 사전 순으로단, 중복된 단어는 하나만 남기고 제거해야 한다.입력첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다.출력조건에 따라 정렬하여 단어들을 출력한다.sort 함수를 사용하면 쉽게 풀 수 있다.N = int(input())setA = set()listA = list()for i in range(N) : data = input() setA.add(data)for i in setA : l..

물리 메모리 크기의 극복 : 정책캐시 관리메인 메모리는 시스템의 가상 메모리 페이지를 가져다 놓기 위한 캐시로 생각될 수 있음 캐시를 위한 교체 정책의 목표는 캐시 미스의 횟수를 최소화하는 것 즉, 디스크로부터 페이지를 가져오는 횟수를 최소로 만드는 것이다. (캐시 히트 최대화) 캐시 히트와 미스의 횟수를 안다면 프로그램의 평균 메모리 접근 시간을 계산할 수 있다. 캐시 성능을 측정할 때 사용하는 미터 법TM - 메모리 접근 비용TD - 디스크 접근 비용PHit - 캐시 히트 확률PMiss - 캐시 미스 확률 PHit와 PMiss는 0.0 ~ 1.0 사이의 값을 갖으며, 둘의 합은 1.0을 만족한다. **디스크 접근 비용이 너무 크기 때문에 아주 작은 미스가 발생하더라도 전체적인 AMAT에 큰 영향을 ..

리다이렉션리다이렉션은 명령의 입력이나 출력을 파일이나 다른 장치로 보내거나 받을 수 있게 해주는 것출력 리다이렉션(>)// 명령어의 표준 출력을 파일로 보낸다. 파일이 이미 존재하는 경우 내용을 덮어쓴다.ls > 파일목록.txt출력 추가 리다이렉션(>>)// 명령어의 표준 출력을 파일 끝에 추가한다. 파일이 없으면 새로 추가echo "새로운 내용" >> 로그.txt입력 리다이렉션(// 파일의 내용을 명령어의 표준 입력으로 사용한다.sort 표준 오류 리다이렉션(2>)// 명령어의 표준 오류 출력을 파일로 보낸다.gcc hello.c 2> 오류.log컴파일 중 발생한 오류 메시지를 오류.log에 저장표준 출력과 표준 오류를 모두 리다이렉션 (&> 또는 파일 2>&1)명령어 &> 전체출력.log == 명령어..

메모리 계층에 레이어의 추가 필요- 지금까지 모든 페이지들이 물리 메모리에 존재한다고 가정- 현재 크게 필요하지 않은 일부를 보관해 둘 공간이 필요- 현대 시스템에서 보통 하드 디스크가 이를 담당**주소 공간이 충분히 크면, 프로그램의 자료구조들을 위한 충분한 메모리 공간이 있는지 걱정 X필요 시 메모리 할당을 운영체제에게 요청하기만 하면 된다.스왑공간은 실행되는 각 프로세스들에게 큰 가상 메모리가 있는 것 같은 환상을 줌 - 멀티 프로그래밍 시스템이 발명되면서 많은 프로세스들의 페이지를 물리 메모리에 전부 저장하는 것은 불가능- 일부 페이지를 스왑 아웃하는 기능이 필요- 멀티 프로그래밍과 사용 편의성 등의 이유로 실제 메모리보다 더 많은 용량의 메모리가 필요스왑공간디스크(HDD)에 페이지들을 저장할 수..

지역성좋은 프로그램은 최근에 참조했던 데이터 근처의 데이터나최근에 자신을 참조했던 데이터를 참조하려는 경향이 있다.두 가지 지역성시간 지역성한 번 참조된 메모리 위치는 가까운 미래에 다시 여러 번 참조될 가능성이 높다.공간 지역성특정 메모리 위치가 참조되면, 가까운 미래에 근처의 메모리 위치를 참조할 가능성이 높다.** 운영체제 수준에서 지역성의 원리는 시스템이 메인 메미로리르 갖아 최근에 참조한 가상 주소 공간 블록에 대한 캐시로 사용될 수 있게 해준다.프로그램 데이터 참조의 지역성int sumvec(int v[N]) { int i, sum = 0; for ( i = 0 ; i sum 변수는 for문에서 반복 참조되므로 좋은 시간 지역성을 갖는다.반면 sum은 물리량이므로 공간 지역성이 ..

페이징프로세스의 주소 공간을 고정된 크기의 단위로 분할하여, 가상 메모리와 물리 메모리를 관리하는 기법페이지각각의 고정된 크기의 단위를 [페이지]라고 한다.상응하여 물리 메모리도 각각의 고정된 크기의 단위로 나눈 것을 [페이지 프레임]이라고 부른다.-> 고정 크기의 슬롯의 배열이라고 생각가상 주소 공간의 페이지들은 물리 메모리 전체에 분산 배치되어 있다.페이징 장점- 프로세스의 주소 공간 사용 방식과는 상관없이 효율적으로 주소 공간 개념을 지원 → 힙과 스택이 어느 방향으로 커지는가, 어떻게 사용되는가에 대한 가정을 하지 않아도 됨- 빈 공간 관리의 단순함 → 모든 비어 있는 페이지의 빈 공간 리스트를 유지하고, 할당 시 페이지들을 선택하여 배치주소 공간 페이지 0 - 물리 프레임 3가상 페이지 1 ..