Computer Sci.

6.1 아키텍처 특성 측정 아키텍처 특성을 정의할 때 흔히 다음과 같은 문제들이 발생한다. 물리학이 아니다 : 아키텍처 특성은 대부분 의미가 모호하다. 정의가 너무 다양하다 : 부서마다 정의를 통일하기 전까지는 원활한 소통이 어렵다. 너무 복합적이다 : 바람직한 아키텍처 특성은 대부분 더 작은 다른 여러 특성들로 구성된다. 이 세가지 문제들은 아키텍처 특성을 객관적으로 정의하면 모두 해결된다. 6.1.1 운영적 특성 아키텍처 특성은 성능, 확장성처럼 비교적 정확하게 측정할 수 있는 것도 많지만, 팀 목표에 따라 그에 따른 해석은 미묘하게 갈릴 때가 많다. 예를 들어 특정 요청에 대한 평균 응답 시간을 측정할 경우, 어떤 경계 조건 때문에 1%의 요청이 다른 요청보다 처리 시간이 10배 오래 걸리면 어떻게..

2.1 중복 없애기 정렬되어 있지 않은 연결리스트가 주어졌을 때 이 리스트에서 중복되는 원소를 제거하는 코드를 작성하라. 연결리스트에서 중복되는 원소를 제거하기 위해서는 원소를 추적할 수 있어야 한다. 여기서는 해시 테이블을 사용해서 처리한다. 연결리스트를 순회하며 각 원소를 해시 테이블에 저장한다. 그러다가 중복된 원소를 발견하면, 그 원소를 제거한 후 계속 진행한다. void deleteDups(LinkedListNode n) { HashSet set = new HashSet(); LinkedListNode previous = null; while (n != null) { if (set.contains(n.data)) { previous.next = n.next; } else { set.add(n.d..

1.1 중복이 없는가? 문자열이 주어졌을 때, 이 문자열에 같은 문자가 중복되어 등장하는지 확인하는 알고리즘을 작성하라. 자료구조를 추가로 사용하지 않고 풀 수 있는 알고리즘 또한 고민하라. 문자열은 ASCII 문자열임을 가정하자. 문자 집합은 boolean 타입의 배열로 만들어서 i 번째 원소는 문자열에 해당 인덱스의 문자가 존재하는지를 확인한다. 배열의 길이는 128이 아니라 256이 되어도 괜찮다. boolean isUniqueChars(String str) { if (str.length() > 128) return false; boolean[] charSet = new boolean[128]; for (int i = 0; i < str.length(); i++) { int val = str.cha..

4. 아키텍처 특성 정의 아키텍트는 개발팀과 함께 도메인 또는 비즈니스 요구사항을 정의할 수 있지만, 주로 소프트웨어로 처리할 일 중 도메인 기능과 직접적인 관련이 없는 모든 것들, 즉 아키텍처 특성(architectural characteristic)을 정의, 발견, 분석하는 일을 수행한다. 아키텍처 특성은 다음 세 가지 기준을 충족한다. 비도메인(nondomain) 설계 고려 사항을 명시한다. 어플리케이션 설계 시 어플리케이션으로 처리할 일은 구체적인 요구사항으로 정리한다. 아키텍처 특성은 이 요구사항을 구현하는 방법, 어떤 선택을 하게 된 이유와 관련된 운영/설계 기준을 명시한다. e.g. 일반적으로 어느 정도의 어플리케이션의 성능은 중요한 아키텍처 특성이지만, 요구사항 정의서에는 적혀있지 않는 경..

7 분할 정복 7.1 분할 정복 분할 정복(Divide & Conquer)은 가장 유명한 알고리즘 디자인 패러다임으로, 각개 격파라는 말로 간단히 설명할 수 있다. 분할 정복 패러다임을 차용한 알고리즘들은 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산해 낸다. 분할 정복이 일반적인 재귀 호출과 다른 점은 문제를 한 조각과 나머지 전체로 나누는 대신 거의 같은 크기의 부분 문제로 나누는 것이다. 이 차이점이 아래 그림이다. 그림 (a)는 항상 문제를 한 조각과 나머지로 쪼개는 일반적인 재귀 호출 알고리즘을 보여주고, 그림 (b)는 항상 문제를 절반씩으로 나누는 분할 정복 알고리즘을 보여준다. 분할 정복을 ..

06 무식하게 풀기 6.1 도입 흔히 전산학에서 무식하게 푼다(brute-force)는 말은 컴퓨터의 빠른 계산 능력을 이용해 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법을 의미한다. 이렇게 가능한 방법을 전부 만들어 보는 알고리즘들을 가리켜 흔히 완전탐색(exhaustive search)이라고 부른다. 얼핏 보면 이런 것을 언급할 가치가 있나 싶을 정도로 간단한 방법이지만, 완전탐색은 사실 컴퓨터의 장점을 가장 잘 이용하는 방법이다. 컴퓨터의 최대 장점은 속도가 빠르다는 것이기 때문이다. 6.2 재귀 호출과 완전 탐색 재귀 호출 재귀 함수란 자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한 조각을 수행하고, 나머지를 자기 자신을 호출해 실행하는 함수를 가리킨다. 예를 들면 ..

플랫폼마다 제공하는 코드 재사용 메커니즘은 제각각이지만, 연관된 코드를 모듈(module)로 묶는 방법은 모두 지원한다. 본인이 선택한 개발 플랫폼에서 모듈성과 그것을 구현한 수 많은 코드를 이해하는 것은 아키텍트에게 대단히 중요한 일이다. 우리가 아키텍처를 분석해야 할 (메트릭, 피트니스 함수, 시각화 등) 많은 도구가 이 모듈성에 기반하기 때문이다. 모듈성은 일종의 구성 원리(organizing principle)이다. 아키텍트가 대충 아무렇게나 조각들을 이어 붙여 시스템을 설계하면 무수한 난관에 봉착해 옴짝달싹 못 하는 시스템이 되어 버린다. 물리학에 비유 하자면, 소프트웨어 시스템은 엔트로피(entropy, 무질서)가 증가하는 방향으로 움직이는 복잡한 시스템을 모델링한다. 질서를 유지하려면 물리적..

02 알고리즘 분석 (04 ~ 05) 04 알고리즘 시간 복잡도 분석 4.1 도입 두 알고리즘의 속도를 비교하는 가장 직관적인 방법은 각각을 프로그램으로 구현한 뒤 같은 입력에 대해 두 프로그램의 수행 시간을 측정하는 것이다. 하지만 프로그램의 실행 시간은 알고리즘의 속도를 일반적으로 이야기하는 기준이 되기에는 부적합하다. 가장 큰 이유는 프로그램의 수행 시간은 사용한 프로그래밍 언어, 하드웨어는 물론이고 운영체제, 컴파일러까지 수 많은 요소에 의해 바뀔 수 있기 때문이다. 두 번째 이유는 실제 수행 시간이 다양한 입력에 대한 실행 시간을 반영하지 못하기 때문이다. 알고리즘의 수행 시간을 지배하는 것은 반복문이다. 입력의 크기가 작을 때는 반복외의 다른 부분들이 갖는 비중이 클 수가 있지만, 입력의 크기..