dbsalstj2310 님의 블로그

우리가 동적 메모리 할당을 사용하는 주요 이유 중 하나는 메모리 사용의 효율성을 높이기 위해서이다. C언어에서 변수를 선언한다면, 우리는 배열 등의 경우에 크기를 미리 정해주어야한다. 하지만 프로그램 실행 중 필요한 메모리 크기를 정확히 예측할 수 없는 경우가 많다. 우리가 무작정 크기를 크게 설정하고 막상 사용하는 메모리는 a little bit이라면 메모리 낭비이고, 반대로 너무 작게 할당하면 메모리 부족 문제나 프로그램의 비정상 종료를 야기할 수 있다. 이 경우 동적 메모리 할당을 사용한다면 앞서 말한대로 메모리 사용의 효율성을 높일 수 있다. 동적 할당된 메모리를 힙(Heap)영역에 malloc과 free를 사용해 할당되고 해제된다. 아래의 그림처럼 표현된다.각 블록은 4바이트인데 그 이유는 32..

RB트리는 이진탐색트리(BST)의 한 종류이다. 스스로 균형을 잡게되어 BST의 worst case의 단점을 개선하였다. 그래서 시간 복잡도를 O(N)이 아닌 O(logN)으로 개선하였다. RB트리는 꼭 만족해야하는 속성이 5가지가 있는데 아래에 있다.모든 노드는 red 혹은 black이다.루트 노드는 black이다.모든 nil(leaf) 노드는 black이다.red의 자녀들은 반드시 black이어야하고, red가 연속적으로 존재할 수 없다.임의의 노드에서 자손 nil 노드들까지 가는 경로들의 black 수는 같다. (자기 자신은 카운트에서 제외)여기서 말하는 nil 노드란존재하지 않음을 의미하는 노드자녀가 없을 때, 자녀를 nil노드로 표기값이 있는 노드와 동등하게 취급RB트리에서 leaf 노드는 ni..

정글의 하루는 TIL을 쓰고 끝난다던데 나의 하루는 지금까지 안 끝났다고 치자 ,,암튼 알고리즘도 풀고 C언어도 처음 접해보고 꽤 많은걸 얻었다 나에게 맞는 공부방법도 슬슬 어떻게 해내가야하는지도 깨닫고 있는ing알고리즘에서 DP와 그리디알고리즘 그리고 linked list를 알게되었고 C언어의 문법들과 포인터, linked list를 C언어로 구현을 하면서 C언어도 재밌구나 느꼈다. 지금은 RB트리를 공부하고있는데 삽입은 괜찮은데 삭제가 어렵다 나중에 블로그로 올려서 기억해놔야겠다.  맞다 이클립스 컬렉터됨.

연결 리스트는 각 노드가 다음 노드를 가리키는 포인터를 갖는 데이터 구조로, 삽입과 삭제가 O(1) 시간에 이루어질 수 있어 스택과 큐를 구현하기에 적합하다.그렇기에 우리 팀의 팀장이 코어 타임 때 Linked-List로 스택과 큐를 구현할 수 있는 구현예제를 파이썬으로 만들고 주석을 달아보라고 하셨다. 스택은 LIFO(Last In, First Out) 구조로, 가장 마지막에 추가된 항목이 가장 먼저 제거된다.class Node: # 연결 리스트의 노드를 정의하는 클래스이다. def __init__(self, value): # Node 클래스의 생성자이다. 노드를 생성할 때 호출된다. self.value = value # 노드가 저장할 값을 초기화한다. self.nex..

최소신장트리란 신장트리 중에서 사용된 간선들의 가중치 합이 최소인 신장 트리를 지칭한다.여기서 신장 트리란 모든 정점이 연결된 그래프다. 조건1. 연결 그래프의 부분 그래프이며 그래프에서 모든 정점을 표현한다.2. 정점간 서로 연결 되어있어야 한다(N개의 정점이라면 N-1개의 간선)3. 사이클이 존재하면 안된다.4. 연결 그래프에서 나올 수 있는 신장트리는 1개가 아닌 다수이다.-> 최소신장트리는 그래프에 있는 모든 정점들을 가장 적은 수의 간선과 비용으로 연결하는 것이다. MST의 특징1. 간선의 가중치의 합이 최소여야한다.2. N개의 정점을 가지는 그래프에 대해 반드시 (N-1)개의 간선만을 사용한다.3. 사이클이 포함되어선 안된다. MST 구현방법먼저 프림(Prim)에 대해 다뤄보겠다.1.1. 변수..

그래프와 BFS / DFS, 위상정렬, 최소신장트리의 프림과 크루스칼 그리고 find union 방식을 공부하고 예제코드까지 구현해보았다. 또한 그리디와 다이내믹 프로그래밍, 포인터도 잠깐 맛 봤다. 뭔가 정신없이 흘러가서 TIL잘 못적었다. 이제부터 TIL뿐만 아니고 공부한 내용 좀 정리 해봐야겠다,, 화이팅  이클립스 색깔 별로 모아봐야지

스택 / 큐 / 덱 : 스택, 큐, 덱은 추상적 자료구조(ADT)인데 여기서 추상적 자료구조란 자료구조의 방법이 코드로 정의 된 것이 아니라, 그 구조의 행동 양식만 정의 된 것을 뜻한다. 먼저 스택을 알아보자.스택 ( Stack ) :스택은 가장 마지막에 저장된 데이터가 가장 먼저 삭제되는 LIFO(후입 선출)구조인데, 스택은 한쪽 방향에서만 data의 삽입과 삭제가 가능하다.스택의 자료 구조는 삽입과 삭제 시에 O(1), 탐색에는 O(n)의 시간 복잡도를 가지게 된다.우리 주변에서 스택의 예로는 뒤로가기 버튼을 누르는 것이다. 우리가 뒤로가기 버튼을 누른다면, 웹페이지 히스토리 스택의 맨 위에 한 페이지를 가져가는 것이기 때문에 뒤로가기 버튼은 스택의 예 이다.스택 주요 함수 : top(peek) :..

7월 7일 알고리즘: 팩토리얼, 수 정렬하기(1)이론: 정렬(버블, 선택, 삽입) 7월 8일알고리즘: 단어 정렬, 일곱 난쟁이이론: 정렬(셸, 퀵), CSAPP(1-1 ~ 1-4) 7월 7일생각보다 공부속도가 느려서 TIL을 쓸 시간이 부족했어서 오늘에서야 쓴다.오늘은 재귀함수를 이용하며 팩토리얼을 풀었더니 재귀함수를 왜 쓰는지 알거같았다. def factorial(n): output = 1 for i in range(1, n + 1): output *= i return outputprint(factorial(10))# 재귀함수를 사용하지 않은 코드 def factorial(n): if n > 0: return n * factorial(n-1) else..

오늘 한 일...노트북 노려보기...백준 알고리즘 파이썬 기초2675 문자열 반복1978 소수 찾기9020 골드바흐의 추측10872 팩토리얼 알고리즘 어제부터 처음 시작해봤는데 오늘에서야 깨달음 그동안 내가 했던 건 책 오래 쳐다보기 노트북 오래 쳐다보기 였던거.. 공부방식 바꾸자 친구야,,  아무튼 파이썬 기초에 조금 더 다지게되었다,, 옛날에 진짜 조금 해봤다고 기초 건너 뛴 나를 혼내줘서 고마워,, ㅊㅅ아,, 그래도 이제 팩토리얼은 알겠다.## 팩토리얼def factorial(n): if n > 0: return n * factorial(n-1) else: return 1a = int(input())a = factorial(a)print(a)앞으로 재귀 알고리즘 ..

이런거 처음 써본다.그래도 크래프톤 정글에서의 0주차 마음가짐과 생각, 그리고 실력이자 지식을 미래의 내가 보기 위해 써보려고 한다. 먼저 나의 공부방식은 그동안 중고등, 학원에서 배웠던 대로 아무튼 정해진 커리큘럼과 정해진 방식으로 교육을 받으며 공부해왔던 나는 정글을 통해 공부방식을 바꾸고 싶다. 인생은 독고다이인데 나는 혼자 찾아가며 공부를 하는 법을 잘 알지 못했고, 그래서 개발에 흥미를 가졌음에도 공부하는 방식을 몰라서 부트캠프, 국비학원만 알아보느라 너무 많은 시간을 사용했다. 크래프톤 정글도 물론 부트캠프지만, 혼자 찾아가며 공부하는 법을 알려준다는 것에 망설임없이 지원했었고, 합격해서 지금은 정글에서 공부를 하고 있다. 근데 정말 혼자 찾아가며 공부한다. 첫날부터 프로젝트를 하게 되는데, ..