해킹왕 양선규

이진 탐색 트리(Binary Search Tree, BST) - 왼쪽 서브트리는 부모 노드보다 작고 오른쪽 서브트리는 부모 노드보다 큰 이진 트리 - BST의 최소값은 “트리의 가장 왼쪽”에 존재한다 - BST의 최대값은 “트리의 가장 오른쪽”에 존재한다 이진 탐색 트리의 삽입 - 아무것도 없는 트리라면 그냥 삽입한다. - 삽입할 노드를 루트 노드부터 하나씩 비교한다. 루트 노드보다 작다면 왼쪽, 크다면 오른쪽으로 간다. 빈 자리를 찾을 때 까지 반복한다. - 같은 값을 가지는 노드는 없다. 이진 탐색 트리의 삭제/검색 - 삭제를 하려면 검색부터 해야 한다. - 찾을 노드를 기준으로, 루트 노드부터 하나씩 비교한다. 삽입할 때처럼 루트 노드보다 작다면 왼쪽, 크다면 오른쪽으로 간다. 값이 같다면 해당 노..

선언(declaration)과 정의(definition) 선언(declaration) - 컴파일러가 참조할 식별자(identifier)의 이름을 알린다. - 식별자란 변수의 타입, 함수의 인자목록을 뜻하며 이름은 변수, 함수, 클래스의 이름 등을 뜻한다. - 선언은 메모리 영역 상에 올리지 않기 때문에 중복되어도 문제가 되지 않는다. extern int a; // 전역변수 선언 int add(int a, int b); // 함수 선언 class ClassId; // 클래스의 선언 정의(definition) - 식별자와 이름으로부터 코드를 생성한 것 - 정의는 고유해야 한다. 같은 식별자와 이름의 정의가 2개 이상이면 컴파일 에러 발생 int add(int a, int b) { // 함수의 정의 (함수 본..

x86-64에서 프로시저에서 프로시저로의 데이터 전달 - 레지스터를 통해서 일어난다. ( 인자들이 %rdi, %rsi등으로 전달되고 %rax로써 리턴되는 형태들을 의미 ) - 프로시저 P가 프로시저 Q를 호출할 때, P는 자신이 전달할 인자들을 레지스터에 복사해야 한다. - 전달할 인자들이 레지스터에 복사되거나 스택에 할당된 후에!!!!!! Q를 호출하게 된다. - Q가 일을 끝내고 P로 리턴할 때, P는 Q가 리턴한 값을 %rax에서 접근할 수 있다. x86-64에서 프로시저에서 프로시저로의 데이터 전달2 - x86-64에서는 “최대 여섯 개의 정수형 인자(정수와 포인터)”가 레지스터로 전달될 수 있다. - 레지스터는 “전달되는 데이터 형의 길이”에 따라서, 정해진 순서대로 이용된다. - “프로시저의 ..

프로시저(procedure) - 제공되는 인수(parameter)에 따라서 특정 작업을 수행하는 서브루틴 - 프로그래밍에서의 함수(function)과 같다. 또는 메소드, 서브루틴, 핸들러 등.. 모두 프로시저라고 한다. - 소프트웨어에서의 주요 추상화이다. 내부 동작을 숨기고, 프로시저를 통해 사용자가 쉽게 기능을 사용할 수 있게 한다. 프로시저가 실행될 때 처리되어야 하는 많은 과정들 프로시저 P가 프로시저 Q를 호출하고, Q가 실행된 후에 P로 리턴한다고 가정 - 제어권 전달 : 프로그램 카운터는 진입할 때 Q 코드의 시작주소로 설정된다. 리턴할 때는 P에서 Q를 호출하는 인스트럭션 다음의 인스트럭션으로 설정되어야 한다. - 데이터 전달 : P는 하나 이상의 매개변수를 Q에 제공할 수 있어야 하고,..

스택(stack) - 프로시저 호출 시 “지역 변수와 매개변수”를 저장하기 위한 메모리 공간(지역변수 = 로컬변수) - 후입선출(LIFO, Last In First Out) 구조 스택의 용도 - 함수의 로컬 변수 저장 : 각 함수 호출 시, 그 함수의 로컬 변수들이 스택에 저장된다. - 함수의 제어 흐름 관리 : 함수가 다른 함수를 호출할 때, 반환 주소와 이전 함수의 스택 프레임 정보가 스택에 저장된다. - 장점 : 동적으로 메모리 할당/해제 가능, 구현이 간단함, 메모리 관리 overhead가 낮음 스택의 특징 - 스택에서 데이터가 삽입되고 빠져나가는 쪽을 top 이라고 한다. 반대쪽은 bottom이다. - %rsp 레지스터는 스택 포인터이다. 스택 포인터는 항상 스택의 top 주소를 가리키고 있다...

플로이드 워셜(Floyd-Warshall) 알고리즘 - 다익스트라가 특정 정점과 특정 정점까지의 최단 경로를 구하는 알고리즘 이라면, 플로이드 워셜은 모든 정점에서 다른 모든 정점까지의 최단 경로를 모두 찾는 탐색 알고리즘 - 다익스트라는 그리디, 플로이드 워셜은 DP - 노드의 개수가 N개일 때 알고리즘상으로 N번의 단계를 수행하며, 단계마다 O(N2)의 연산을 통해 ‘현재 노드를 거쳐 가는 모든 경로’를 고려한다. 따라서 총 시간 복잡도는 O(N3)이다. 플로이드 워셜(Floyd-Warshall) 알고리즘의 과정 1. 인접 행렬 방식으로 출발노드, 도착노드, 비용을 입력한다. 갈 수 없다면 INF로 설정한다. 2. k(거쳐갈 노드), a(출발 노드), b(도착 노드) 순서로 3중 for문을 만든다. ..

DP(Dynamic Programming, 동적 계획법) - 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 이용해, 다시 큰 문제를 해결할 때 사용한다. - DP는 특정 알고리즘이 아니라 하나의 방법론이므로 다양한 문제해결에 쓰인다. - “큰 문제를 작은 문제로 쪼개서 그 답을 저장해두고, 재활용” - DP라는 이름은 그냥 멋있어 보여서 지은 이름이다. DP를 쓰는 이유 - 일반적인 재귀방식도 DP와 유사하지만, 일반적인 재귀를 단순히 사용 시 “동일한 작은 문제가 반복”되어, 비효율적인 계산이 될 수 있다. ex) 피보나치 수열. 한번 한 계산을 또 하고 또 하고 반복한다. --->>> DP 방식으로 작은 문제의 결과를 저장해두고 “재사용”하면 매우 효율적으로 해결할 수 있다. --->>..

매일매일 엄청난 양의 지식을 머리에 꾸역꾸역 넣고 있다. 공부가 잘 안 되는 것 같고, 집중도 안 되는 것 같고. 남들은 더 열심히 하는 것 같고, 나는 부족한 것 같고 하는 생각이 계속계속 들어도, 멈춰서 차근히 돌아보면 지금의 나는 입소날인 3월18일보다 몇 배로, 말도 안되게 빠른 속도로 성장했다. 실질적인 웹 개발이나 프로젝트 경험이 전무하던 내가 입소 4일만에 어엿한 웹사이트를 하나 만들어 냈고, 프로젝트 경험이 생겼다. 알고리즘의 ㅇ자도 모르던 내가 2주만에 DFS, BFS, 백트래킹, 최소스패닝트리, 위상정렬, 여러가지 그래프 이론, 스택, 큐, 힙, 정렬, 재귀함수, CS지식 등등 이것보다 훨씬 많은 말도 안되게 많은 지식을 습득했으며, 백준 티어도 어느새 골드5가 되었다. 하루하루가 정말..

신장 트리(Spanning Tree) - 그래프 내의 모든 정점을 포함하면서 사이클이 없는 부분 트리 최소 스패닝(신장) 트리(Minimum Spanning Tree, MST) - 가중치가 있는 양방향 그래프에서 싸이클 없이 모든 정점을 포함하며 가중치의 합이 최소인 트리 - 모든 정점을 연결하는 트리를 형성하면서, 가중치 합이 최소화되도록 하는 것 프림(Prim) 알고리즘 - 크루스칼 알고리즘과 더불어 그리디 알고리즘을 기반으로 최소 신장 트리를 구하는 대표적인 알고리즘 - 가중치가 작은 순으로 노드를 그래프에 포함시켜야 하기 때문에 우선순위 큐를 사용한다. - 이미 그래프에 속한 노드엔 적용시키지 않기 위해 visited를 사용한다. 프림 알고리즘 동작원리 1. 임의의 시작 노드를 설정하고 T(트리)..

캐시 메모리를 사용하면 컴퓨터의 성능이 향상되는 이유 지역성(Locality) - 프로그램이 메모리에 접근할 때, "특정 부분을 집중적으로 사용"하는 경향 시간적 지역성(Temporal Locality) - 한 번 접근된 데이터는 가까운 미래에 다시 접근될 가능성이 높다. - ex) 루프 내에서 반복적으로 사용되는 변수 공간적 지역성(Spatial Locality) - 메모리의 특정 주소에 접근한 후, 그 주변 주소에 있는 데이터에 접근될 가능성이 높다 - ex) 배열, 연속적인 메모리 블록 등 캐시 메모리는 지역성 원리를 활용하여, 자주 사용되거나 연속적으로 사용될 가능성이 높은 데이터를 미리 캐시에 저장한다. 이로 인해 CPU는 필요한 데이터를 캐시에서 빠르게 찾을 수 있다. 메모리 계층구조 L0 :..