Euclidean space

문제 보자마자 짠 코드N = int(input())cards = [int(input()) for _ in range(N)]cards.sort()s = 0for i in range(1, N): s += (cards[i-1] + cards[i]) cards[i] = (cards[i-1] + cards[i])print(s) = 메모리 초과뿐만 아니라 코드 내용도 잘못된 부분이 있었다..일단 나는 그냥 정렬하고, 누적하며 더해줌 매번 계산 시점에서 가장 작은 두 값을 선택해서 더하는 것이 핵심인데예를 들어 카드 1, 1, 10, 10, 10의 경우 따라서 Priority Queue를 사용하여, 항상 가장 작은 두 묶음을 합쳐야 한다.(이걸 왜 미리 고려하질 못할까...?_?) import he..

n개의 물건이 각각 다른 가치, 무게를 가지고 있다고 하자.나의 배낭에는 무게 w만큼의 물건을 담을 수 있다. 제한된 용량을 가진 배낭(Knapsack)에 최대한의 가치를 넣어보자.  물건을 하나씩 넣으면서, 넣는 경우와 안 넣는 경우를 비교하며 최대값을 선택하면 된다. dp[i][w]: i번째 물건까지 고려했을 때, 배낭용량이 w인 경우 얻을 수 있는 최대 가치 이 경우 시간 복잡도는 O(n*w)이다.  역시 문제를 풀어봐야 제 맛knapsack 문제집: https://www.acmicpc.net/workbook/view/19494 OR https://www.acmicpc.net/problemset?sort=ac_desc&algo=148 ✘ 백준 1535 안녕 classic knapsack proble..

Stack은 LIFO (List In, First Out) 자료구조입니다.가장 최근에 삽입된 데이터가 가장 먼저 제거됩니다. python에서 Stack은 주로 List로 구현됩니다.   python에서 Queue은 주로 Deque로 구현됩니다.Deque는 양 끝에서 O(1) 시간복잡도의 자료구조입니다.    ✘ python List 특성Dynamic array: 메모리 관리 측면에서 효율적Over allocation: 리스트 크기를 초과하여 여유 메모리 할당python list는 새로운 요소가 추가될 때마다 매번 메모리 할당 XReference counting: 참조 카운팅 방식으로 메모리 관리Garbage collector로 참조 카운트가 0이 된 객체를 자동 메모리 해제+ deque는 이중 연결 리..

import sysinput = sys.stdin.readlineN,M = map(int, input().split())fuel = []for _ in range(N): fuel.append(list(map(int, input().split())))dp = [[[float('inf'),float('inf'),float('inf')] for _ in range(M)] for _ in range(N+1)]for i in range(M): dp[0][i] = [fuel[0][i], fuel[0][i], fuel[0][i]]for i in range(1, N): for j in range(M): for k in range(3): if (j == 0 and k ==..

*이 글은 Operating Systems: Three Easy Pieces(운영체제 아주 쉬운 세 가지 이야기)를 바탕으로 작성되었습니다. 첨부한 모든 그림은 해당 도서에서 가져온 자료입니다. 내용 중 잘못된 부분이 있다면 알려주세요 :) 지난 글에서 paging 기법으로, linear page table을 사용할 때 메모리 접근 비용이 성능 저하를 가져왔다. Address translation 속도를 어떻게 줄일 수 있을까? 메모리 접근 비용이 부담이라면....하드웨어의 도움을 받아보자  🧐 TLB (Translation-Lookaside buffer)자주 참조되는 가상 주소-물리 주소 변환 정보를 저장하는 하드웨어 캐시address translation cacheMMU에 속해있다.가상 메모리 참조..

*이 글은 Operating Systems: Three Easy Pieces(운영체제 아주 쉬운 세 가지 이야기)를 바탕으로 작성되었습니다. 첨부한 모든 그림은 해당 도서에서 가져온 자료입니다. 내용 중 잘못된 부분이 있다면 알려주세요 :)  우리는 여러 프로그램을 동시에 실행하길 원한다.이를 위한 OS의 핵심 개념이 process, 실행 중인 program이라는 것을 지난 글에서 알아보았다.OS는 CPU를 time-sharing하여, 실행 중인 process를 다른 process로 scheduling하여 context switch함으로 여러 프로그램이 동시에 실행하는 환상을 만들어준다고 했었다. 그럼 어떻게 CPU time-sharing을 효율적으로 할 수 있을까?시스템에 오버헤드 없이 구현할 수 있을..

*이 글은 Operating Systems: Three Easy Pieces(운영체제 아주 쉬운 세 가지 이야기)를 바탕으로 작성되었습니다. 첨부한 모든 그림은 해당 도서에서 가져온 자료입니다. 내용 중 잘못된 부분이 있다면 알려주세요 :) 우리는 여러 프로그램을 동시에 실행하길 원한다. 운영체제는 여러 프로그램들이 실행되는 것처럼 환상을 만들어(CPU를 가상화), 이를 가능하게 만든다. 이 과정에서의 운영체제의 핵심 개념 중 하나는 프로세스이다. 프로세스는 현재 실행 중인 프로그램으로 정의된다. 하나의 프로세스를 실행하고, 중단하고 다른 프로세스를 scheduling하여 실행을 반복하며, 실제로 여러 프로그램이 실행되고 있다고 느끼게 만든다. 이를 time-sharing이라고 하며, 하나의 프로세스를 ..

*이 글은 Operating Systems: Three Easy Pieces(운영체제 아주 쉬운 세 가지 이야기)를 바탕으로 작성되었습니다. 첨부한 모든 그림은 해당 도서에서 가져온 자료입니다. 내용 중 잘못된 부분이 있다면 알려주세요 :) 메모리 관리의 계속해서 언급한 문제가 무엇인가?!!!! 바로 단편화(fragmented)이다... 가변 크기로 메모리를 분할하여 할당하는 방법인 segmentation도 단편화 문제... 그럼 고정된 크기로 메모리를 분할하여 사용하면 어떨까? 이 방법이 바로 페이징 Paging 이다. 이번 글에선 이 페이징에 대해 알아보자! 🧐 Paging이란 공간을 동일 크기의 조각으로 분할하는 방법이다. 이 fixed-size(고정된 크기)를 page라고 부른다. 아래 그림으로 ..

*이 글은 Operating Systems: Three Easy Pieces(운영체제 아주 쉬운 세 가지 이야기)를 바탕으로 작성되었습니다. 첨부한 모든 그림은 해당 도서에서 가져온 자료입니다. 내용 중 잘못된 부분이 있다면 알려주세요 :) 지난 글에서 segmentation으로 메모리를 관리하여도 외부 단편화 문제가 있다는 것을 보았다. 메모리의 빈 공간들은 여러 크기로 분할되다가 결국 단편화된다. 예시로, 위 그림을 보자. 현재 빈 공간의 총 크기는 20byte로, 10bytes 짜리 공간 2개가 나눠져있다. 하지만, 15byte짜리 요청을 실패한다. 빈 공간들을 어떻게 관리해야할까? 단편화를 최소화 시키기 위해 어떻게 해야할까? 가변 사이즈 요청을 어떻게 만족할 수 있을까? 여러 가지 방법들의 시간..

*이 글은 Operating Systems: Three Easy Pieces(운영체제 아주 쉬운 세 가지 이야기)를 바탕으로 작성되었습니다. 첨부한 모든 그림은 해당 도서에서 가져온 자료입니다. 내용 중 잘못된 부분이 있다면 알려주세요 :) Dynamic allocation은 heap, stack 사이의 공간이 낭비되는 내부 단편화 문제가 있었다. 이를 방지하기 위해 만들어진 segment에 대해 알아보자! 🧐 Segment란 Address Space는 Code, Heap, Stack 영역 등으로 구성되어있다. 이 각각의 영역을 세그먼트(Segment)라고 한다. 다시 말해, 세그먼트은 특정 길이를 가지는 연속적인 주소 공간이다. 우리가 기존에 공부했던 base, bound를 생각해보자(맨 위 그림 참고..