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

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

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

TIL - 2025.03.29 (토요일)📝 오늘 배운 것 (다익스트라 알고리즘 (Dijkstra Aglorithm))다익스트라 알고리즘은 최단거리를 구하는 알고리즘이다.다익스트라 알고리즘최단거리를 구할 노드에서 시작하여, 거리가 입력된 노드 중 최단거리가 가장 작은 노드를 돌아가며 선택한다.노드를 돌아가면서, 더 거리가 짧은 경우 값을 경신한다.다만 음의 간선을 포함할 수 없다.이론 설명초기 모든 거리를 무한으로 설정한다.INF = 1e8distance = [INF] * (n+1)거리12345XINFINFINFINFINF 처음에 자기 자신의 거리를 0으로 놓고 1번 노드와 직접 연결된 노드까지의 거리를 입력한다.이후 1번 노드를 방문처리한다.거리12345X013INFINF관련 코드def get_smal..

TIL - 2025.03.28 (금요일)📝 오늘 배운 것 (유니언 파인드(Union-Find))유니언 파인드 개념유니언-파인드 알고리즘은 주로 그래프 문제에 적용하는데 노드들을 특정 집합으로 나눈 때 사용한다. 같은 집합에 속한 노드들을 확인할 수 있다.서로소 집합(disjoint sets)서로소 집합은 공통 원소가 없는 두 집합을 뜻한다. 예를 들어서 {1, 2, 3}과 {4, 5, 6}은 서로소이며 {1, 2, 3}과 {3, 4, 5}는 아니다.;Union-Find는 서로소 집합 자료 구조를 만들 수 있다. 집합에서 노드를 합치고 부모를 찾아 서로소 집합을 찾아내는 알고리즘이다.2개의 서로소 집합을 합치는 과정을 거친다.구현 방법1. 부모 노드 배열 초기화노드 번호에 대응하도록 초기 부모 노드를 자..

TIL - 2025.03.27 (목요일)📝 오늘 배운 것 (그래프 종류/표현방식)그래프의 기본 개념그래프는 이산수학과 컴퓨터 과학에서 중요한 자료구조로, 정점(vertices)과 간선(edges)의 집합으로 구성된다.기본용어정점(vertex/Node)그래프의 기본 단위로, 노드라고 불린다.그래프 이론에서는 특징이 없는 불가분의 객체로 취급되지만. 응용에 따라 추가 구조를 가질 수 있다.그래프 G에서 정점 집합은 V로 표기된다.간선(Edge/Arc)두 정점을 연결하는 선으로, 아크(arc)라고 불린다그래프 G에서 간선 집합은 E로 표기한다.무방향 그래프에서는 간선이 순서가 없는 정점 쌍 {u, v}로 표현된다.방향 그래프에서는 간선이 순서가 있는 정점 쌍(u,v)로 표현된다.관련용어인접(Adjacent)..

TIL - 2025.03.26 (수요일)📝 오늘 배운 것 (이분 탐색 문제 풀이)백준 1072번 게임백준 1072번 게임풀이 코드x, y = map(int, input().split())start_rate = (y * 100) // xif x == y: print(-1)elif start_rate >= 99: if ((y + 10**9) * 100) // (x + 10**9) start_rate: end = mid - 1 else: start = mid + 1 print(start)풀이 소개이 문제는 앞으로 모든 게임이 이긴다는 가정아래 자신의 승률이 변하는 가장 최소 게임 판수를 구하는 것이었다.승률의 경우 소수점은 버리기 때문에 ..

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

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

📝 주간 학습 회고 (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주차 문제의 난이도가 올라가 문제가 이해되지 않았다.필기를 통한 정리와 동기들과의 대화..