크래프톤 정글 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

크래프톤 정글 8기 - 19일차 TIL (다익스트라 알고리즘)

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

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

크래프톤 정글 8기 - 18일차 TIL (유니언 파인드 알고리즘)

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

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

크래프톤 정글 8기 - 17일차 TIL (그래프 이론)

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

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

크래프톤 정글 8기 - 16일차 TIL (이분탐색 문제풀이)

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)풀이 소개이 문제는 앞으로 모든 게임이 이긴다는 가정아래 자신의 승률이 변하는 가장 최소 게임 판수를 구하는 것이었다.승률의 경우 소수점은 버리기 때문에 ..

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