크래프톤 정글 8기 - 24일차 TIL (다이나믹 프로그래밍 입문)

TIL - 2025.04.03 (목요일)📝 오늘 배운 것 (동적 계획법)동적 프로그래밍 (Dynamic Programming)동적 프로그래밍은 복잡한 문제를 더 작은 하위 문제로 나누어 해결하는 알고리즘 설계 기법이다. 큰 문제를 작은 문제로 분할하여 각 하위 문제의 해를 계산하고, 이를 이용하여 상위 문제의 해를 구하는 방식으로 동작한다.기본 원리문제 분할: 복잡한 문제를 더 작은 하위 문제로 나눈다.메모이제이션(Memoization): 이미 계산한 결과를 저장하여 재사용함으로써 중복 계산을 피한다.상향식 접근법: 가장 작은 하위 문제부터 해결하여 점차 상위 문제를 해결해 나간다.동적 프로그래밍분할 정복부분 문제가 중복되어 재활용 됨부분 문제가 서로 붕복되지 않음메모이제이션 기법 사용메모이제이션 기법..

• format_list_bulleted 크래프톤 정글
• · 2025. 4. 3.
• textsms

크래프톤 정글 8기 - 23일차 TIL (트라이 Trie)

TIL - 2025.04.02 (수요일)📝 오늘 배운 것 (트라이 Trie)트라이(Trie)?트라이(Trie)는 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조이다. 주로 문자열이 키인 경우가 많으며, 문자열 특화 자료구조의 대표적인 예이다.특징이진 탐색 트리와 달리 노드 자체에 키를 저장하지 않고, 노드가 트리에서 차지하는 위치가 연관된 키를 정의한다.노드의 모든 자손은 해당 노드에 연관된 문자열의 공통 접두사를 공유한다.루트는 빈 문자열에 연관된다.각 노드는 자식 노드들에 대한 포인터를 가지고 있으며, 일반적으로 형태의 Map 구조를 사용한다.시간 복잡도트라이 생성 시간 복잡도 : O(M*L) - M은 총 문자열의 수, L은 가장 긴 문자열의 길이삽입 시간 복잡도 : O(L) - ..

• format_list_bulleted 크래프톤 정글
• · 2025. 4. 2.
• textsms

크래프톤 정글 8기 - 22일차 TIL (B-Tree)

TIL - 2025.04.01 (화요일)📝 오늘 배운 것 (B-Tree)B-Tree?자가 균형 트리로 이진트리를 확장하여 하나의 노드가 두 개 이상의 자식을 가질 수 있도록 설계되었다.B-Tree는 AVL 트리로 레드-블랙 트리와 더불어 skewed tree(한쪽으로 치우친 트리)를 해결할 수 있는 자료구조 중 하나이다. AVL 트리나 레드-블랙 트리를 모든 데이터가 메모리에 적재할 수 있는 경우에 적용함과 달리 B-Tree는 대용량 데이터를 다뤄야 하는 DB나 디스트에 주로 적용된다.대부분 트리에서의 연산이 높이에 따라 결정됨을 볼 때 B-Tree는 h를 줄이기 위해 B-Tree의 노드에 가능한 많은 값을 집어넣어 높이를 낮춤으로써 fat tree의 형태를 보인다. 이렇게 하나의 노드에 여러 정보를 ..

• format_list_bulleted 크래프톤 정글
• · 2025. 4. 1.
• textsms

크래프톤 정글 8기 - 3주차 시작 전 회고

📝 주간 학습 회고 (TWL) - 크래프톤 정글 3주 차🎯 이번 주 목표시뮬레이션 문제 풀어보기DFS/BFS 문제 풀어보기그래프 이론 공부다익스트라/벨만 포드/플루이드 워셜 문제 풀어보기📚 학습한 내용다익스트라플루이드-워셜위상 정렬amdhal의 법칙🔍 어려웠던 점 / 해결 방법어려웠던 점해결 방법다익스트라개념 이해 및 문제 풀어보기위상정렬개념 이해 및 문제 풀어보기🛠️ 만든 것 / 작업한 것❌🤔 생각 / 느낀 점각종 코테 유형을 학습하고 있지만 여전 히 응용문제나 풀이 해법이 생각하는 것이 어렵다.시뮬레이션(노가다) 문제 어렵다.다익스트라, 위상정렬, 최소 스패닝, 플루이드 워셜, 벨만 포드... 알아야 하는 게 많기도 하다.📊 주간 진행 상황목표진행 상태비고알고리즘 공부(그래프이론)70% ..

• format_list_bulleted 크래프톤 정글
• · 2025. 3. 31.
• textsms

크래프톤 정글 8기 - 21일차 TIL (CSAPP 1장 마무리)

TIL - 2025.03.31 (월요일)📝 오늘 배운 것 (CSAPP 1.8 ~ 1.10)1.8 시스템은 네트워크를 사용하여 다른 시스템과 통신한다.최신 시스템들은 네트워크에 의해 다른 시스템과 종종 연결된다.개별 시스템의 관점에서 볼 때 네트워크는 또 다른 입출력 장치로 볼 수 있다.시스템은 다른 컴퓨터로부터 받은 데이터를 읽어서 메인 메모리에 복사할 수 있다.이메일, 메신저, 웹 페이지, FTP, Telnet 같은 것들이 네트워크를 통해 정보를 복사하는 기능을 이용한 것이다.1.9 중요한 주제들시스템이라는 것은 하드웨어 그 이상의 것이다. 응용프로그램의 실행이라는 궁극의 목적을 달성하기 위해 협력해야 하는 하드웨어와 시스템 소프트웨어가 서로 연결된 것을 말한다.1.9.1 Amdahl의 법칙계산학 분..

• format_list_bulleted 크래프톤 정글
• · 2025. 3. 31.
• textsms

크래프톤 정글 8기 - 20일차 TIL (플로이드-워셜)

TIL - 2025.03.30 (일요일)📝 오늘 배운 것 (플로이드 워셜 알고리즘)플로이드 워셜 알고리즘플로이드 워셜(Floyd_Warshall) 알고리즘은 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 수해야 하는 경우 사용하는 알고리즘이다.다익스트라 알고리즘에서 최단거리가 가장 짧은 노드를 탐색하는 과정을 생략할 수 있다.모든 노드가 다른 노드로 가는 최단 거리 정보를 2차원 리스트에 저장한다. 노드의 개수 N만큼 점화식에 맞게 2차원 리스트를 갱신하는 다이나믹프로그램으로 볼 수 있다.⏱️ 시간 복잡도모든 최단 경로를 2차원 리스트에 담아 처리하기 때문에 매번 O(N^2)의 시간이 소요된다.노드의 개수 N만큼 O(N^2)연산을 통해 해당 노드가 거치는 모든 경로를 고려한다.현재 노드를 거쳐 ..

• format_list_bulleted 크래프톤 정글
• · 2025. 3. 30.
• textsms