잔잔한 물결로 파도 만들기

오버헤드(overhead) 공부하다 보면 함수의 오버헤드가 발생했다, 메모리 오버헤드가 발생했다 등등 overhead 라는 용어가 자주 등장한다. 여기서 말하는 (컴퓨터과학 관점에서의) overhead는 특정 작업을 수행하기 위해 필요하지만, 실제 유용한 작업에 직접 기여하지는 않는 추가적인 리소스나 시간을 의미한다. 즉 특정 작업을 수행할 때, 그 핵심 동작을 위한 비용은 아니지만 괜히 간접적으로 낭비되는, 따라서 더 최적화할 여지가 있는 비용이라는 거다. GPT한테 물어보니 다음과 같은 예시를 준다. 함수의 오버헤드: 함수 호출 시 발생하는 추가적인 처리입니다. 함수를 호출하면, 인자를 전달하고, 리턴 주소를 저장하고, 필요한 경우 스택 프레임을 설정하는 등의 작업이 필요합니다. 이러한 작업들은 함수..

Computer Science/컴퓨터 구조 (Computer Architecture) 2023. 10. 31. 22:21

CSAPP 3장을 공부중인데, 어셈블리어에 대해서 더 많은 예제가 필요함을 느꼈다. 직접 코드를 쳐보면서 어셈블리어로 변환해보고, 확인해보고 하면 좋지 않을까? 이게 공부효율을 높여줄지는 미지수지만 그냥 재미있기도 해서 해봤다. 어차피 책에서도 직접 어셈블리 코드 뽑아내는 법을 소개하고 있다. C 파일로부터 어셈블리어 파일 생성 C파일로부터 어셈블리어 파일을 생성하는 방법은 다음과 같다. 1. 테스트해보고 싶은 C 소스파일을 아무거나 만든다. (대충 hello.c) 2. 해당 디렉토리로 가서, 터미널에 다음과 같이 입력한다. gcc -S -o hello.s hello.c 쉽쥬? gcc -S 명령어는 컴파일 중간에 어셈블리어 코드를 뽑아내서 따로 파일로 생성해주는 코드이다. 이렇게 하면 hello.s 가 ..

프로그래밍 언어/Assembly 2023. 10. 31. 16:27

그리디 알고리즘 그리디 알고리즘의 기본 아이디어는 각 단계에서 현재의 상황에서 최적의 선택을 하는 것이다. 이러한 선택은 문제 해결에 있어서 전역적으로 최적이며, 각 단계에서의 선택은 이후 단계에 대한 선택을 제한하지 않는다. DP와 마찬가지로, 그리디 알고리즘은 일반적으로 최적화 문제를 해결하기 위해 사용된다. 또한, 그리디 알고리즘은 해를 찾기 위해 반복적인 선택을 해야 하는 문제에도 적용된다. 탐욕 알고리즘이 잘 작동하는 문제는 대부분 탐욕스런 선택 조건(greedy choice property)과 최적 부분 구조 조건(optimal substructure)이라는 두 가지 조건이 만족된다. (...) 이러한 조건이 성립하지 않는 경우에는 탐욕 알고리즘은 최적해를 구하지 못한다. 하지만, 이러한 경우..

Computer Science/알고리즘 (Algorithm) 2023. 10. 27. 16:10

다이나믹 프로그래밍 다이나믹 프로그래밍(동적 계획법, 이하 DP)은 복잡한 문제를 작은 하위 문제로 나누어 해결하고, 이를 조합하여 원래의 문제를 해결하는 알고리즘 설계 기법이다. 핵심 아이디어 자체는 분할정복과 동일하다. 1950년대에 리처드 벨먼이라는 응용수학자가 개발했으며, Dynamic 이라는 단어는 그저 멋있어서😂 붙인거고, Programming은 컴퓨터 코드가 아니라 테이블을 이용한 방법을 일컫는 거라고 한다. 개인적으로 DP는 적용 상황을 판단하는 것도 쉽지 않고, 문제 풀이 단계에서 정확한 점화식을 도출하는 게 쉽지않은 것 같다. . 모두 연습만이 살길 !! 어떤 문제에 DP를 적용하는가? 목적을 따지자면, 일반적으로 최적화 문제(optimmization problem)에 DP를 적용한다...

Computer Science/알고리즘 (Algorithm) 2023. 10. 27. 13:31

자료구조, 알고리즘 주차의 두번째 주가 끝났다. 이번에는 팀원 한 분의 사정상 사실상 2인팀으로 진행했는데, 3인팀 대비 오히려 긴밀한(?) 회의를 할 수 있어서 좋은 점도 있었다. 👍 이번주 공부한 내용들 CSAPP 1장 트리 (Tree) 기본적인 트리 순회 방법 (전위, 중위, 후위 순회) 이진 검색 트리 (Binary Search Tree, BST) 힙 (Heap) 우선순위 큐 (Priority Queue) 기타 트리 구조 B-트리, B+ 트리 (주로 데이터베이스와 파일 시스템에서 사용) 트라이 (Trie) (문자열 검색에 유용) 세그먼트 트리 (구간 질의 문제에 사용) 그래프 기초 기본적인 그래프 탐색 알고리즘: DFS, BFS 신장 트리, 최소 신장 트리 최소 신장 트리를 찾는 방법 기초: U..

일상기록장/크래프톤 정글 일지 2023. 10. 26. 20:12

CSAPP 1장의 각 소단원을 읽으면서 주요 내용과 추가적으로 알아본 정보들을 기록하는 포스팅😎 1장은 컴퓨터 시스템 전반을 얕고 넓게 훑는 챕터이다. 글자색이 다른 부분은 내가 따로 추가한 생각 혹은 정보이다 (= 틀릴 수도 있다) 1.1 정보는 비트와 컨텍스트로 이루어진다 소스 프로그램은 byte(= 8 bit) 단위로 구성된다. 대부분의 컴퓨터 시스템은 text 문자를 아스키 표준을 사용하여 표시한다. 아스키 표준은 각 문자를 byte 길이의 정수 값으로 나타낸다. 텍스트 파일: hello.c 처럼 아스키 문자들로만 이루어진 파일 바이너리 파일: 텍스트 파일을 제외한 다른 모든 파일 컨텍스트(context) 모든 시스템 내부의 정보는 bit들로 표시됨. 서로 다른 객체들을 구분하는 유일한 방법은 이..

Computer Science/컴퓨터 구조 (Computer Architecture) 2023. 10. 26. 19:27

우선순위 큐는 대표적으로 다익스트라 알고리즘에서 사용된다. (또 A* 알고리즘, 허프만 코딩 알고리즘 등에서도 쓰인다고 한다) 큐, 데큐가 선형 자료구조인 것과 달리, 우선순위 큐는 주로 힙(Heap)으로 구현되는 경우가 많기 때문에 비선형으로 분류된다. 우선순위 큐를 구현하는데 필요한 힙(Heap)이라는 자료구조가 무엇인지 알아보고, 우선순위 큐에 대해서 알아보자. 힙(Heap) Heap은 완전 이진 트리의 일종으로, 1) 최소 힙 또는 2) 최대 힙으로 나뉜다. 힙 속성(Heap Property) 최소 힙(Min-Heap): 각 노드의 값이 그 자식 노드의 값보다 작거나 같음 (루트 노드가 최소값) 최대 힙(Max-Heap): 각 노드의 값이 그 자식 노드의 값보다 크거나 같음 (루트 노드가 최대값)..

Computer Science/자료구조 (Data Structure) 2023. 10. 26. 17:13

위상 정렬은 방향 그래프(Directed Graph)에서 노드를 정렬하는 방법이다. u -> v 방향을 갖는 각 간선 (u, v)에 대해서, u가 v보다 앞에 오도록 정렬한다. 여러가지 작업이 주어지고, 특정 작업이 특정 작업보다 선행되어야 한다는 순서 조건이 달렸을 때, 전체 순서를 어떻게 전개해야할 것인가와 관련하여 탁월한 답을 내려준다. 이러한 특성 덕에, 위상 정렬은 프로젝트를 스케줄링할 때, 작업 우선순위 지정 등 다양한 분야에서 활용된다. 기본 개념 의존성(Dependency): A 작업이 B 작업에 의존한다는 것은, A 작업이 시작하기 전에 B 작업이 완료되어야 함을 의미한다. 진입차수(in-degree): 한 노드로 들어오는 간선의 수 진출차수(out-degree): 한 노드에서 나가는 간..

Computer Science/알고리즘 (Algorithm) 2023. 10. 23. 14:46