본문 바로가기

📚 전공 공부

(55)

[문제해결기법] 11. 동적 계획법 동적 계획법 (DP) 최적화 문제, 분할 정복 한 문제를 똑같은 문제이면서 크기만 작은 것으로 바꿀 수 있을지 생각해본다. 금화 모으기 문제 D[i][j] : (i, j)까지 오는 동안 모을 수 있는 금화의 최댓값 D[i][j] = max( D[i-1],[j] , D[i][j-1] ) + map[i][j]; 최대 공백 정사각형 (흰색으로만 이루어진 가장 큰 정사각형) mm 크기의 정사각형이 있다면, 4개의 (m-1)(m-1) 크기 정사각형이 있어야 한다는 점에서 착안한다. D[x][y]는 (x,y)가 가장 오른쪽 아래 꼭지점인 정사각형의 최대 크기라고 가정한다. (x,y)가 검은색이면, D[x][y] = 0 흰색이면, x==1 && y==1 : D[x][y] = 1 else : D[x][y] = min(..

[문제해결기법] 10. 계산 기하 계산 기하 2, 3차원 공간상에서 점, 선, 도형 간의 관계를 다루는 문제 기본 가정 : 2차원 공간, 정수좌표만 고려함. 실수 연산은 지양 polygon : 선분들로 이뤄진 닫힌 도형. 두 선분이 만나는 점은 하나뿐이다. 모든 점을 지나는 경로 n개의 점이 주어지면, 이 점들을 모두 지나고 시작점으로 돌아오는 경로를 구하시오. 단, 교차하지 않게 풀이 방법 y좌표가 가장 낮은 점을 기준점으로 잡음. O(n) 이 점을 지나는 직선과 다른 점들을 잇는 직선을 모두 구하고, 각의 크기에 따라 정렬한다. O(n log n). 그리고 이 순서대로 방문하면 됨 각의 계산 : arctan 함수와 비슷한 성질을 가지고, 분모가 0인 경우가 없도록 하는 함수를 직접 만들어서 계산한다. 점과 폴리건의 포함 관계 점의 좌..

[문제해결기법] 9. Flow Networks Flow Networks 가중그래프 G (모든 가중치는 양수) 에지의 가중치 = c(e) 시작점 s에는 들어오는 에지 없고, 도착점 t에는 나가는 에지가 없다 Flow : 이용가능한 용량을 기반으로, 간선을 따라 이동하는 값 모든 에지에 대해서, 0 ≤ f(e) ≤ c(e) flow 값 ( |f| )은 s에서 나가는 플로우 총량 = t로 들어오는 플로우 총량 최대 플로우 = 최소 cut 컷(cut) 주어진 노드 V를 두 집합으로 분할 컷 X에 대해서, f(X)는 X를 지나는 flow 총량 c(X)는 X를 지나는 에지의 c값 총량 최대 플로우 구하기 Ford-Fulkerson algorithm s→t 경로를 찾는다. BFS 진행 각 경로의 c(e) 최솟값을 m이라고 하자 각 경로의 에지마다, c(e) -=..

[문제해결기법] 8. 서로소인 집합의 표현 (Disjoint Sets) 서로소인 집합의 표현 (Disjoint Sets) 서로소인 집합 : 전체집합의 부분집합들 중, 둘을 고르면 교집합=공집합, 전체 합집합=U U의 두 원소가 같은 부분집합의 원소인지 아닌지 어떻게 알 수 있을까? 신장트리 : 그래프 G의 노드를 모두 포함하는, E에 속하는 에지로 만든 트리 최소신장트리 : 트리에 속한 가중치의 합이 가장 작은 신장 트리. 최소 신장 트리 (MST) 만들기 Prim’s algorithm : 현재 집합(노드들)과 연결된 에지 중 가중치가 최소인 것을 MST 집합에 포함시킴. 구현법에 따라 시간복잡도가 차이남 다익스트라 알고리즘 = 특정 시작노드부터 다른 노드들까지의 최단거리를 구함. 유/무향 그래프 프림 알고리즘 = 모든 노드들을 최소비용으로 연결 / 두 노드사이의 거리는 최..

[블록체인] 5. 비트코인의 한계 : The Limits of Bitcoin 목차 : 비트코인의 한계 / 비트코인의 대안 비트코인의 한계 트랜잭션 처리 속도 - 트랜잭션 하나가 완료되려면? 트랜잭션 생성, 인근노드 전파, 풀노드와 마이너 노드가 검증, 검증 후 다른 트랜잭션들과 함께 새 블록 생성 이후 블록 6개가 더 추가되어야 비로소 완전 승인 - 새 블록 생성에 필요한 평균 시간 = 10분 블록 6개 => 최소 60분(1시간) 필요! 트랜잭션이 바로 다음에 생성될 블록에 반드시 포함된다는 보장도 없음 초당 3~7개의 트랜잭션이 처리. 사실상 보안을 위해 속도를 포기. 높은 에너지 사용량 - 비트코인의 연간 에너지 소비량은 91 TWh로, 필리핀의 연간 에너지 소비량과 비슷하다. 함께 소모되는 탄소발자국도 스웨덴의 탄소발자국과 비슷한 수준.(50.89 Mt) 채굴자 연합의 등장..

[소프트웨어공학] 14장. 최신 기술 & 15장. 미래 동향 14장. 최신 기술 Cleanroom Software Engineering 소프트웨어에 정확성을 구축할 필요성을 강조하는 접근 방식입니다. 고전적인 분석, 설계, 코드, 테스트 및 디버그 사이클 대신 클린룸 접근 방식은 다른 관점을 제시한다. 결함을 방지하기 위해 "사전 준비(up-front)"에 많은 노력을 기울임. 점진적 발전 신뢰성을 보장하기 위한 통계적 방법 "상자 구조 사양" 채택 'Box'는 시스템을 캡슐화함. 요구사항 수집(Requirements Gathering) - 고객 수준 요구사항에 대한 설명 정의(각 증분에 대한) 박스 구조 사양(Box Structure Specification) - 기능 사양을 설명합니다. 형식 설계(Formal Design) — 사양("블랙박스"라고 함)은 아키..

[소프트웨어공학] 13장. 형상관리 및 유지보수 13장. 형상관리 및 유지보수 Software Configuration Management (SCM : 소프트웨어 형상 관리) 컴퓨터 소프트웨어가 구축되면 변화가 불가피하다. 혼란을 최소화하기 위해 구성 관리가 필요하다. 소프트웨어 구성 관리(SCM)는 소프트웨어 프로세스 전반에 걸쳐 적용되는 포괄적인 활동이다. SCM 활동은 다음과 같이 개발된다. (1) 변경사항 확인 (2) 변화 통제 (3) 변화가 적절하게 이행되고 있는지 확인 (4) 관심을 가질 수 있는 다른 사람에게 변화를 보고 SCM 행위에는 버전 관리, 베이스라인 확립이 포함된다. Baselines (기준선) 기준선은 공식적으로 검토되고 합의된 사양이며 이후 추가 개발의 기초가 된다. 공식적인 변경 관리 절차를 통해서만 변경할 수 있다. 기준..

[소프트웨어공학] 12장. 테스팅 12장. 테스팅 SW testing : 테스트는 최종 사용자에게 전달하기 전에 오류를 발견할 목적으로 프로그램을 연습하는 과정이다. 테스트를 통해 얻을 수 있는 것 Errors (논리적 오류) Requirements conformance (요구사항 일치 여부) Performance (성능) Indication of quality (품질 수준) 누가 테스트해야 할까? Developer 시스템을 이해하고 있음 조심스럽게 테스트하고 전달을 이끌어냄 “구성 작업” Independent Tester 시스템에 대해 배워야 함 고장내려고 시도함 품질을 이끌어냄 “파괴적인 일” 전략적 접근 테스트는 사전에 계획하고 체계적으로 수행할 수 있는 일련의 활동입니다. 특성 효과적인 기술 검토 수행 구성 요소 수준에서 시작하여..

이전 1 2 3 4 ··· 7 다음

728x90

티스토리툴바