CS (14) 썸네일형 리스트형 CPU Pipelining 간단 정리 Stage: Instruction Fetch -> Instruction Decode -> Execution -> Memory Access -> Write BackCPU 단일 코어에서 여러개의 Stage를 실행하는 것을 Pipelining이라 함 Data Hazard, Control Hazard에 의해 실행 중이던 stage를 폐기해야하는 경우가 발생 Control Hazard는 연속된 Stage를 실행할 수 없는 경우를 만나는 상황쉬운 예시로, "if 문에 의해 program counter의 jump가 발생"Data Hazrad로는 Stage 간의 데이터 종속성이 있는 경우쉬운 예시로는, x = x + 1; y = x; 이를 위해서 파이프라인 최적화 기법들을 사용함1. 데이터 종속성 최소화 (Data H.. 알고리즘 스터디 Week9 이진 검색 트리 검색트리 자료를 정렬된 상태로 저장하여 검색에 사용할 수 있는 트리 이진 검색 트리 검색 트리 중 가장 흔하게 사용됨 최대 2개의 자식 노드만을 가질 수 있음 (이진 트리의 정의) 왼쪽 자식을 루트로 하는 서브트리의 모든 노드들의 key값은 현재 노드의 key값보다 작음 반대로, 오른쪽 자식의 모든 노드들은 현재 노드의 key값들은 현재 노드의 key값보다 큼 탐색에서는 이진 탐색(binary search)의 아이디어를 위 특성에서 활용함 순회 중위 순회를 통해 정렬된 노드들을 접근할 수 있음 조작 정렬된 데이터를 사용하지 않고, 트리를 사용할 때 가장 큰 이점을 가지는 부분 삽입: 해당하는 leaf 노드를 생성 삭제: 해당하는 노드를 삭제하고 왼쪽 자식 서브트리의 가장 오른쪽 노드나 오.. 알고리즘 스터디 Week8 트리의 구현과 순회 트리(tree)란? - 정의: 자료구조의 일종이며, 사이클이 없이 모든 정점이 연결되어있는 그래프이다. 사이클이 없는 그래프이므로 정점의 개수가 V개이면 간선의 개수는 V-1개이다. (출처) - 정의를 통해, 계층적 구조를 필연적으로 가지게 된다. 루트 노드를 제외한 노드들의 부모 노드는 한 개이다. 트리 구성, 특징 - 노드(node), 엣지(edge) - 연결된 노드들은 상하관계를 가짐, 그 중 상위 노드를 부모(parent), 하위 노드를 자식(child)라 함 - 모든 상위 노드들을 선조(ancestor)라 부르고, 모든 자식 노드를 자손(descendant)라고 함 - 최상위 노드를 루트(root), 자식이 없는 최하위 노드들은 리프(leaf) - 루트에서부터 몇 번을 거쳐야.. 헤드 퍼스트 디자인 패턴(Head First Design Patterns) 요약 (0) 디자인 패턴 입문으로 매우 좋은 책이라는 추천글을 많이 보았는데, 책을 읽어가면서 리뷰를 하려고 한다. 이 책은 영문판으로 구했고, 부지런히 읽고 정리해야 할 것 같다. 그리고 책의 코드들이 자바로 작성되어 있다고 하는데, 이를 C++로 구현하여 깃허브에 공유할 예정이다. 깃허브 주소: https://github.com/lss0815/design_pattern_implementation 소프트웨어 빌드 시스템 원리와 활용 요약 (3) - 3. 프로그램 런타임 뷰 3. 프로그램의 런타임 뷰 - 이번 챕터에서는 타겟 머신에서 프로그램이 실행되는 구조와 프로그램의 어떤 파일들이 메모리에 올라가는지 설명한다. - 실행 프로그램: CPU에서 실행되는 명령 집합과 데이터값, 메모리에 로드되어 실행되는 코드 전체가 컴파일된 프로그램 - 라이브러리: 여러 프로그램에서 공통으로 사용되는 오브젝트 코드의 집합. 라이브러리 단독적으로 메모리에 로드될 수 없으며, 반드시 실행프로그램과 링크된 후 로드되어 사용된다. - 설정 파일과 데이터 파일: 명령으로 이루어지지 않은, 데이터와 설정 정보. 프로그램이 디스크에서 로드하여 사용 3.1 실행 프로그램 - 우리가 보통 프로그램을 작성하면 최종 산출물로써 생각하는 프로그램. - 네이티브 기계어 코드: C/C++로 만들어낸 머신코드로 이루어.. Codeforces 769(Div2, 1632)-C "Strange Test" https://codeforces.com/problemset/problem/1632/C - DP로 풀려 했는데, 상태 정의가 어려워 보인다. - 비트와이즈 OR 연산이 매우 중요해보인다. $a := a | b$의 연산은 $a >= b$의 상태로 만들어 준다. 총 매칭에서 이 연산을 두 번 하는 것이 의미가 없는 건 아닐까? - "어느 상태에서든 OR 연산을 한 번 진행하면 다시 OR 연산을 하는 것은 불필요한 일이다"라는 걸 증명해야함 - 복잡하게 증명할 필요없이 위에서 말한 것 하나로도 증명이 된다. 문제에서 $a$가 커질 수 있는 방법은 두 가지이지만, $b$가 커지는 방법은 한 가지 방법 밖에 없다. 그렇다면 결국 $a >= b$ 상태가 되었을 때는, $a - b$의 횟수로만 서로 같은 값에 도달할.. 소프트웨어 빌드 시스템 원리와 활용 요약 (2) - 2. Make 기반 빌드 시스템 2. Make 기반 빌드 시스템 - GNU Make의 예시와 작동 방식을 보여주는 챕터이다. - 책에서는 c 파일로 예제를 진행하는데, 나는 c++로 수정하여 작성하였다. 코드와 Makefile은 https://github.com/lss0815/software_build_system_review/tree/main/chap2를 참고하면 된다. 2.1 계산기 프로그램 예제 - add.c, calc.c, muilt.c, numbers.h, sub.c의 소스코드가 있을 때, calculator라는 타겟파일을 생성할 것이다. $ g++ -g -c add.cpp $ g++ -g -c calc.cpp $ g++ -g -c mult.cpp $ g++ -g -c sub.cpp $ g++ -g -o calculator a.. 소프트웨어 빌드 시스템 원리와 활용 요약 (1) - 0. 서론, 1. 빌드 시스템 개요 0. 서론 빌드 시스템 개선의 필요성 - 20인 이하의 개발 조직에서 빌드에 인한 평균 생산성 저하량 10% 책에서 다루는 내용 - 빌드 시스템 원리 이해 - 빌드 시스템 경험 공유 1. 빌드 시스템 개요 1.1 빌드 시스템이란? 특정 유형의 데이터(입력물)를 다른 유형의 데이터(출력물)로 변환하는 과정에 포함된 활동을 관리하는 시스템 - 컴파일형 언어 버전 관리 도구 -> 소스 트리 -> 오브젝트 트리 -> 릴리즈 패키지 1.2 빌드 시스템의 구성 요소 - 버전 관리 도구 git이 대표적인 툴, 소스 파일 협업, 수정 이력 관리 - 소스 트리와 오브젝트 트리 디렉토리에 저장된 구조를 말함 - 컴파일 도구와 빌드 도구 C 컴파일러: C 언어 소스 파일을 기계어 코드로 변환하여 오브젝트 파일 생성 링커(L.. 이전 1 2 다음
