컴퓨팅 사고력2 메모리 계층 구조와 알고리즘의 공학적 한계 1. 개발에 있어서 컴퓨터 하드웨어 문제 컴퓨터 기계 장치의 하드웨어적인 본질은 무엇일까? 폰 노이만 아키텍처에 따르면, 컴퓨터의 기계적 본질은 프로세서인 CPU와, 데이터와 명령어가 저장된 스토리지인 RAM이다. RAM와 CPU 두 하드웨어만 있으면 그것이 곧 흠 잡을 데 없는 컴퓨터다. 튜링 기계와 등가다. 실제로 컴퓨터 장치를 공부할 때, NAND 게이트를 차곡차곡 조립해나가 8비트나 16비트 컴퓨터를 만들 때가 있는데, 이때도 간단한 CPU와 RAM만으로 컴퓨터를 완성할 수 있다. 이것만으로도 컴퓨터의 원리를 설명하는데 충분하기 때문이다. 그러나 컴퓨터는 기계 장치다. 물리적인 제약 조건에 강하게 결합되어 있다. 실제 컴퓨터는 구체적인 재료와 물리적인 비용을 바탕으로 설계된다. 즉, 그 속도와 명.. 2023. 11. 3. 수열에서 중간값 찾기 문제와 분할/정복 알고리즘의 정수 1. 중간값 찾기 문제 임의의 N개의 원소를 가진 수열이 주어졌을 때, 그 중간값을 찾는 문제다. 여기서 중간값이란 그 값을 기준으로 작은 모든 원소들과 그 값보다 큰 모든 원소들을 이등분하는 값을 말한다. 간단하게 생각하면 정말 정의 그대로, 그냥 주어진 배열을 정렬하고 중간에 있는 값을 선택하면 될 것 같다. 물론 그렇게 해도 풀리며, O(N logN) 정렬 알고리즘을 선택해 사용하면 될 것이다. 그러나 이렇게 푸는 것은 매우 아쉽다. 컴퓨팅 사고력에서 중요한 능력 중 하나는 쓸데없는 계산을 줄이는 것이라고 배웠다. 지금 문제는 중간값을 찾으면 되지, 굳이 정렬까지 할 필요는 없다. 위치만 알면 되기 때문이다. 나는 이 문제를 N/2 크기의 힙(Heap) 자료구조를 이용하는 식으로 생각했다. Min .. 2023. 11. 2. 이전 1 다음
