세리프 따라잡기

Red-Black Tree : 가장 많이 사용되는 균형 이진 탐색 트리 NIL = c언어에서는 NULL / 파이썬에서는 None을 의미하는 노드를 말하는 것 앞에 트리를 설명할 때 none값에 대해 그림상 표현하지 않는다 (아무것도 없기 때문에) 하지만 RBtree에서는 독립된 노드로 그린다. 그리고 이 노드를 '리프 노드(leaf)'라고 부른다. 리프 노드를 제외한 노드를 '내부 노드'라고 한다. RBtree는 다음의 5가지 조건을 만족해야만 한다. [당연히 이진 탐색 트리] 1. 모든 노드는 Red나 Black의 색깔이 있어야 한다. (둘중에 하나 무조건) 2. 루트 노드는 무조건 Black이어야 한다. 3. 리프 노드 또한 무조건 Black이어야 한다. 4. red node는 두 개의 자식 노드를 ..

- 변수 / 주소 연산자 / 역참조 연산자 / 포인터의 차이 1. 포인터 사용하기 변수는 어디에 생기는 걸까? 변수는 컴퓨터의 메모리에 생성된다. 메모리에 일정한 공간을 확보해놓고, 원하는 값을 저장하거나 가져오는 방식이다. 포인터가 어렵게 느껴진다면? 메모리를 이해하지 못한 것! > 메모리를 이해하면 어렵지 않다. 보통 변수는 이름으로 사용하는데, 변수는 메모리의 특정 장소에 위치하고 있으므로 메모리 주소로도 표현할 수 있음 == 일상생활에서 집을 구분할 때 주소를 사용하는 것과 같은 원리. 변수의 메모리 주소를 구해보자. &변수 ← 사용법 #include int main(){ int num1 = 10; printf("%p\n", &num1); //0x7fff61f81fe4 → 메모리 주소 출력. 컴퓨..

1. include와 헤더파일 - 헤더파일이란? c언어의 문법을 가지고 있는 프로그램. 헤더파일이 코드에 추가되어 있지 않다면, 컴퓨터는 아무것도 하지 못한다. (컴퓨터가 글자들을 알아볼 수가 없어서) == 헤더파일이 없다면 컴퓨터가 컴파일을 못한다. #include //stdio.h is inputed #include //stdilb.h is inputed 2. main 함수 - c언어는 프로그램이 시작되면 무조건 main부터 찾기 때문에 main 함수 안에 코드를 짜야 명령어가 실행된다. main 앞에 쓰는 int의 의미는 정수 '-21억' ~ '+21억'을 의미하는데, 이는 main의 반환값을 의미한다. 따라서 반환값에 따라 반환을 해야 하는 값이 다른데, 반환값을 정하지 않으면 무조건 0으로 반환..

1. AWS-EC2 linux에 연동 AWS 홈페이지에 접속해서 다음과 같은 화면으로 들어간다 인스턴스를 누르고 인스턴스 ID를 클릭하면 아래와 같은 화면이 나오는데, 여기서 저 퍼블릭 IPv4주소가 필요하다! 복사 버튼을 눌러줘서 이제 터미널에 가서 연동해주자 ssh -i (발급받은 key.pem 경로 괄호 빼고 적기) ubuntu@(괄호 빼고 퍼블릭 IPv4주소 복붙) 예시. → ssh -i /c/Users/gothic/Desktop/malgun.pem ubuntu@13.111.111.11 이런식으로~ 이후 터미널창에 시작이 ubuntu@주소 로 바뀌었다면 성공 끗! 2. vscode C언어 연동 오류 (could not establish connection to '~') vscode에서 remote..

$ vi (file name)을 이용해 실행하면 편집기가 열리고 해당 편집기를 다 작성하고 저장 및 종료하고자 한다면 일단 esc키부터 눌러야 한다! 모드 명령키 설명 마지막 행 모드 :q vi에서 작업한 것이 없을 때 vi 종료 :q! 작업한 내용을 저장하지 않고 종료 :w[file name] 작업한 내용을 저장만 하고, 파일명을 지정하면 새 파일로 저장 :wq. :wq! 작업한 내용을 저장하고 vi를 종료 명령 모드 ZZ 작업한 내용을 저장하고 vi를 종료 참고한 사이트~

그리디(greedy) 알고리즘이란? = 그리디 알고리즘은 말그대로 탐욕적인 알고리즘을 말하는데, 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 답에 도달하는 방법을 의미한다. = 일반적으로 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다. = 그리디 해법은 그 정당성 분석이 중요하다. [단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토] Q. 루트 노드부터 시작해 거쳐 가는 노드 값의 합을 최대로 만들면? A. 최적의 해는 5-7-9 현재 위치에서 가장 큰 값만 선택하는 방법 A. 루트(5)부터 시작해 현 위치에서 가장 큰 값을 선택하면 5-10-4가 된다. → 다만 이 상황에선 5+10+4=19라 최적의 해인 ..

https://www.acmicpc.net/problem/9084 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net Q> 2,4원으로 8원 만들기 동전 0원은 항상/무조건 1가지의 방법으로 만들 수 있다. - 4원짜리로 0원을 만드는 건 = 0개를 내면 만들 수 있음 = 1가지 방법 0 1 2 3 4 5 6 7 8 0원 1 0 0 0 0 0 0 0 0 0원+2원 1 0 1 0 1 0 1 0 1 0원+2원+4원 1 0 1 0 2 0 2 0 3 → dp[8] = dp[8-4] = dp[4] = 2 ..

피보나치 수열 문제를 예시로, def fibo(s): if s ==1 or s == 2: return 1 if dp[s] != 0: return dp[s] dp[s] = fibo(s-1)+fibo(s-2) return dp[s] print(fibo(n)) 아래와 같이. from collections import defaultdict import sys input = sys.stdin.readline n = int(input()) dp = defaultdict(int) def fibo(n): if n

다이나믹 프로그래밍(Dynamic Programming)이란? - 메모리를 적절히 사용해 수행 시간 효율성을 비약적으로 향상시키는 방법 - 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장해두었다가 나중에 해당 결과가 필요할 때 메모리 영역에 기록되어 있던 정보를 그대로 사용하도록 한다. 즉, 한 번 계산해서 해결한 문제는 다시 해결하지 않도록 함 └> 굉장히 비효율적인 시간 복잡도를 가진 문제여도, DP를 이용해서 시간 복잡도를 줄일 수 있는 경우가 많다! - DP의 구현은 일반적으로 탑다운(하향식), 바텀업(상향식)의 두 가지 방식으로 구성된다. - DP는 동적 계획법이라고도 부른다. └> 여기서의 동적(Dynamic)의 의미는, 별다른 의미가 없다..! 더보기 ex. 자료구조에서 동적 할당..

위상정렬이란? - 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것을 의미한다. 진입차수와 진출차수 - 진입차수(indegree): 특정한 노드로 들어오는 간선의 개수 - 진출차수(outdegree): 특정한 노드에서 나가는 간선의 개수 위상 정렬 알고리즘 동작 과정 1. 진입차수가 0인 모든 노드를 큐에 넣는다. 2. 큐가 빌 때까지 다음 과정을 반복한다. -1. 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거 -2. 새롭게 진입차수가 0이 된 노드를 큐에 넣는다. → 결과적으로 각 노드가 큐에 들어온 순서가 위상 정렬을 수행한 결과와 같음! 위상 정렬의 특징 - 위상 정렬은 순환하지 않는 방향 그래프(DAG)에서만 수행할 수 있다. - 위상 정렬에..