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

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