728x90 분류 전체보기63 [TIL] 크래프톤 정글 5주차 - 자료구조(RB Tree) Red-Black Tree란? - 이진 탐색 트리(BST)의 한 종류 - 스스로 균형을 잡는(self-balanced) 트리 - BST의 worst case의 단점을 개선 - 모든 노드는 red 혹은 blackRed-Black Tree의 속성1. 모든 노드는 red 혹은 black 2. 루트 노드는 black 3. 모든 nil(leaf) 노드는 black nil 노드란?- 존재하지 않음을 의미하는 노드 - 자녀가 없을 때 자녀를 nil 노드로 표기(null이면 nil노드로 표기) - 값이 있는 노드와 동등하게 취급 - RB 트리에서 leaf 노드는 nil 노드 4. red의 자녀들은 black이다.(red가 연속적으로 존재할 수 없다.) 5. 임의의 .. 2024. 4. 20. [TIL] 크래프톤 정글 5주차 CS:app 7(링커 Linker) 7장 linker - 링킹(linking)은 여러 개의 코드와 데이터를 모아서 연결하여 메모리에 로드될 수 있고 실행될 수 있는 한 개의 파일로 만드는 작업이다. - 링커는 소포트웨어 개발 시에 독립적인 컴파일을 가능하게 한다. 큰 규모의 응용프로그램을 한 개의 소스 파일로 구성하는 대신 별도로 수정할 수 있고, 컴파일할 수 있는 더 작은 모듈로 나누어 관리할 수 있다. 이 모듈 중 한 개를 변경할 때, 이 파일만을 간단히 재컴파일하고 이 파일을 다시 링크한다. - 이 단원에서는 리눅스와 표준 ELF-64 목적파일 형식(이후 ELF)을 사용하는 x86-64 시스템의 context에서 논의할 것이다. 7.1 컴파일러 드라이버 - 대부분의 컴파일 시스템은 언어 전처리기, 컴파일러, 어셈블러, 링커를 필요에 .. 2024. 4. 19. [알고리즘] 크래프톤 정글 혼자 못 푼 문제 정리(공유기 설치) BOJ 2110 공유기 설치 난이도 : (백준 난이도 기준) 골4, (크래프톤 정글 기준) 중 사용 알고리즘 or 자료 구조 : 이분탐색, 매개변수 탐색 처음 생각한 풀이 처음에는 입력 받은 집의 위치를 정렬을 한 뒤, 시작 집과 끝 집에 공유기가 반드시 설치된다고 생각하고 이상적으로 생각했을 때 공유기끼리의 거리가 얼마나 되어야할지 생각했다. 입력값으로 생각하면 idealD = (house[N - 1] - house[0]) / (C - 1) 가 되어야한다. 그래서 시작 index를 0으로 두고 거리가 idealD가 되는 집이 있으면 해당 집의 index를 반환하고, 없으면 해당 위치에 더 가까운 집의 index를 반환하는 식으로 이분탐색을 구현하려 했다. 하지만 예제와 게시판에 올라온 반례가 모두 맞았.. 2024. 4. 19. [알고리즘] 크래프톤 정글 혼자 못 푼 문제 정리(탑 보기) 크래프톤 정글에서의 알고리즘 커리큘럼은 3주차까지만이다. 이후 문제들은 모두 C++로 풀었으며, 지금부터 정리할 알고리즘 글은 이후에 따로 알고리즘 스터디 중 혼자서 못 푼 문제들을 정리하는 글이므로 참고하길 바란다. BOJ 22866 탑 보기 난이도 : (백준 난이도 기준) 골3 사용 알고리즘 or 자료 구조 : 스택 처음 생각한 풀이 시간 제한과 입력 값의 크기를 봤을 때 반드시 전체 순회 한, 두 번 만에 끝내야된다고 생각을 했다. 그래서 0번 인덱스 ~ N - 1번 인덱스까지 스택을 1개 이용하고, N - 1번 ~ 0번 인덱스까지 스택을 1개 이용하여 순회 두 번만에 끝낼 수 있을 것이라고 생각하여 계속 고민해봤지만 방법이 떠오르지 않아 구글링을 통해 접근법을 찾아보았다. 구글링 이후 풀이 혹시나.. 2024. 4. 17. [CS] 크래프톤 정글(혼자 공부) - GC(Garbage Collection) 익숙하지 않은 파이썬으로 알고리즘 문제를 풀다 보니(알고리즘 주간에는 필수적으로 Python으로 문제를 풀어야한다.) 메모리 초과가 뜨는 일이 시간 초과 만큼 굉장히 빈번하게 일어난다. 어떻게 하면 메모리 초과를 없애고 줄일 수 있을까를 생각해보다가 GC까지 오게 되었다. 가비지 컬렉션이란?메모리 관리 기법 중 하나로 프로그램이 동적으로 할당했던 메모리 영역 중에서 필요없게 된 영역을 해제하는 기능이다. 즉, 동적 할당된 메모리 영역 가운데 어떤 변수도 가리키지 않는 메모리 영역을 탐지하여 자동으로 해제하는 기법이다.쉽게 말하면 메모리에 굳이 남아있을 필요 없는 쓰레기들을 없애 메모리 공간을 깨끗하게 만들어주는 것이라고 생각하면 된다. 원래 C나 C++의 경우에는 malloc()을 통해 동적 할당한 메모.. 2024. 4. 16. [TIL] 크래프톤 정글 4주차 - 동적 메모리 할당(Dynamic Memory Allocation) 메모리 동적 할당이란? - 메모리 동적 할당은 프로그래밍에서 사용하는 변수나 배열은 컴파일 타임에 크기가 결정되는데, 동적 메모리 할당은 런타임 중에 메모리의 크기를 결정하고 할당하는 방식이다. - 예를 들어, 사용자로부터 입력을 받은 크기만큼의 배열을 생성하려는 경우, 동적 메모리 할당을 사용해야한다. - C언어에서는 malloc, calloc 등을 이용해서 동적 메모리 할당을 할 수 있고, realloc을 이용하여 재할당을 할 수 있다. 동적 할당을 사용하는 이유 - 동적 할당을 하면 프로그램의 유연성을 높이며, 데이터의 크기가 런타임에 결정될 때 유리하다. - 더 깊게 설명하려면 스택 메모리와 힙 메모리에 대해 설명해야한다. 1) 스택 메모리(stack memory) · 스택 메모리는 컴파일 타임에.. 2024. 4. 15. 이전 1 ··· 4 5 6 7 8 9 10 11 다음 728x90
