크래프톤 정글 8기 - 15일차 TIL

TIL - 2025.03.25 (화요일)📝 오늘 배운 것 (위상정렬 알고리즘 (Topology Sort))위상 정렬 (Topology Sort)DAG에서 정점을 나열하는 알고리즘DAG란?Directed Acyclic Graph방향이 있고, 사이클이 없는 그래프노드 간 선 후 관계를 나타내기 위해 사용한다.ex) 작업 공정, 스케줄링B 작업은 A작업이 선행되어야 진행할 수 있다.사이클이 존재하는 그래프는 위상 정렬을 할 수 없다.구현 방법진입 차수가 0인 정점 선택선택된 정점을 위상 정렬된 대상으로 출력해당 정점과 연결된 간선을 제거 (진입 차수를 감소)모든 노드를 다 정렬할 때까지 1 ~ 3을 반복시간 복잡도모든 노드를 확인하며 해당 노드와 연결된 간선을 제거해야 하므로 시간 복잡도 O(V+E)가 된다..

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

크래프톤 정글 8기 - 14일차 TIL

TIL - 2025.03.24 (월요일)📝 오늘 배운 것 (라인 스위핑 Sweeping Algorithm)라인 스위핑라인 스위핑(line Sweeping) 알고리즘은 선 하나를 여러 가지 상황에서 움직이면서 문제를 해결하는 방법스위프트(빗자루)가 평면을 가로지르면서 이벤트를 처리하는 방식을 모방한 것으로 일반적으로 평면상의 선이나 구간과 관련된 문제를 해결하는 데 사용한다.사용 예시선분 교차겹치는 구간 찾기최근접 점 쌍 찾기 등시간 복잡도O(NlogN)의 시간 복잡도를 평균적으로 가진다.스위핑 적용 과정스위핑 알고리즘을 적용하기 위해 살펴봐야 할 부분은 다음과 같다.선들이 완전히 겹치는 경우선들이 일부 겹치는 경우선들이 겹치지 않는 경우왼쪽부터 움직이며 start, end 값을 변경해야 한다.선들이 완..

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

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

📝 주간 학습 회고 (TWL) - 2025년 03월 W주차🎯 이번 주 목표 분할 정복 정복 하기 스택, 큐, 우선순위 큐 문제를 풀며 발견한 추가 키워드 정리📚 학습한 내용정렬분할 정복슬라이딩 윈도우스택, 큐, 우선순위 큐💡 새롭게 알게 된 것슬라이딩 윈도우고속 거듭제곱 알고리즘def power(a,b,m): result = 1 while b > 0: if b % 2 != 0: result = (result * a) % m b //= 2 a = (a * a) % m return result🔍 어려웠던 점 / 해결 방법어려웠던 점해결 방법2주차 문제의 난이도가 올라가 문제가 이해되지 않았다.필기를 통한 정리와 동기들과의 대화..

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

크래프톤 정글 8기 - 13일차 TIL

TIL - 2025.03.23 (일요일)📝 오늘 배운 것 (슬라이딩 윈도우 알고리즘)슬라이딩 윈도우 알고리즘 (Sliding Window)슬라이딩 윈도우는 고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용해 문제를 풀이하는 알고리즘이다.교집합의 정보를 공유하고, 차이가 나는 양쪽 끝 원소만 갱신하는 방법이다.배열이나 리스트의 요소의 일정 범위 값을 비교할 때 사용하면 좋다.투 포인터 알고리즘과 연동하여 많이 사용된다.주로 정렬된 배열을 대상으로 하는 투 포인터와 달리 슬라이딩 윈도우는 정렬 여부에 관계없이 활용된다.좌측의 투 포인터는 주로 정렬된 배열을 대상으로 한다. [1,2,3,4,5]가 모두 순서대로 정렬되어 있으며, 처음에는 2개의 포인터가 1과 5를 가리키고 있으나 그다음에는 ..

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

크래프톤 정글 8기 - 12일차 TIL

TIL - 2025.03.22 (토요일)📝 오늘 배운 것 (CSAPP 1-5 ~ 1.7)1.5 캐시가 중요하다.앞선 예제로부터 얻을 수 있는 중요한 교훈은 시스템이 정보를 한 곳에서 다른 곳으로 이동시키는 일에 많은 시간을 보낸다는 것이다.hello 프로그램의 기계어 인스트럭션들은 본래 하드디스크에 저장되어 있다가 프로그램이 로딩될 때 메인메모리로 복사된다. 프로세서가 프로그램을 실행할 때 인스트럭션들은 메인 메모리에서 프로세서로 복사된다."hello, world\n" 데이터 스트링도 본래는 디스크에 저장되어 있었다가 메인 메모리로 복사되었다가 디스플레이 장치로 복사된다. 프로그래머의 관점에서 이러한 여러 복사과정들이 프로그램의 실제 작업을 느리게 하는 오버헤드이다.그래서 시스템 설계자들의 주요 목적은..

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

크래프톤 정글 8기 - 11일차 TIL

TIL - 2025.03.21 (금요일)📝 오늘 배운 것 (분할 정복 알고리즘 (Divide and Conquer))분할 정복 알고리즘이란분할 정복 알고리즘(Divide and Conquer Algorithm)은 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 해결하는 방법이나 알고리즘이다.분할 정복 알고리즘은 재귀적인 방법을 통해 문제를 해결하며, 대표적인 예시로 이진탐색(Binary Search), 병합 정렬(Merge Sort), 퀵정렬(Quick Sort)이 예로 들 수 있다.동적계획법(Dinamic Programming)과 다른 점다이나믹 프로그램 역시 한 문제를 작게 나눈 다는 점에서 유사한 접근 방식을 가지고 있지만 차이가 있다.분할 정복 - 문제를 작게 나누어 해결하고, 이 해결을 결..

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