티스토리

왕도를 찾아서

검색하기

블로그 홈

왕도를 찾아서

wangdo.tistory.com/m

코딩의 왕도를 찾아서 To the royal road of coding

구독자: 0

방명록 방문하기

주요 글 목록

FWA 2부: 플로이드 워셜 알고리즘에서 경로 복원하기 플로이드 워셜 알고리즘(Floyd-Warshall Algorithm)은 모든 노드들 간 최단 경로를 찾는 알고리즘이다.전 글에서 소개한 플로이드 워셜 알고리즘의 구현을 그대로 가져오겠다. for(int x=0;x 이는 노드 a와 b를 잇는 최단 거리를 d[a][b]에 저장하는 알고리즘이다. 근데 경로 그 자체는 구할 수 없다. d[a][b]=min(d[a][b],d[a][x]+d[x][b]);이 부분을 보자.d[a][b]보다 d[a][x]+d[x][b]가 작다면 d[a][b]를 그 값으로 업데이트하는 부분이다. 무슨 뜻이냐면 기존에 a에서 b로 가는 경로보다 a에서 x를 갔다가, x에서 b로 가는 경로의 길이가 더 짧으면 그 길을 택한다는 뜻이다. 최종적으로 그 길을 택했다면 a에서 b로 가는.. 공감수 0 댓글수 0 2025. 3. 8.
FWA 1부: 플로이드-워셜 알고리즘과 주의사항 (반복문의 순서가 중요한 이유) 플로이드 워셜 알고리즘(Floyd-Warshall Algorithm)은 모든 노드들 간 최단 경로를 찾는 알고리즘이다. 일단적으로 노드 N개와 두 노드를 잇는 간선 K개가 주어지고, 특정 두 노드를 잇는 최단 거리를 찾아야 하는 상황이 주어진다.이럴 때는 다익스트라 알고리즘을 쓰면 된다. 다익스트라(데이크스트라) 알고리즘(Dijkstra Algorithm)은 두 노드 간 최단 경로를 찾는 알고리즘이다. 플로이드 워셜 알고리즘은 언제 쓰느냐?가능한 모든 두 노드들 사이 최단 거리를 구할 때 쓴다. 그러니까 하나만 구하면 될 때는 다익스트라, 모두 구해야 할 때는 플로이드 워셜을 쓴다. 다익스트라 알고리즘의 시간 복잡도는 O(KlogK)이고 플로이드 워셜의 시간복잡도는 O(N^3)이다.https://www... 공감수 0 댓글수 0 2025. 3. 6.
고려대학교의 마이크로디그리 제도 나는 현재 고려대학교에서 수학과를 이중전공중이다. (현재 군휴학 중) 수학과 홈페이지를 둘려보던 도중 새로운 것을 발견했다. 바로 마이크로디그리 Microdegree 제도이다.https://www.youtube.com/watch?v=jL1FJf8LHTc 2023년에 생겼다는데, 나는 오늘 처음 알았다. 수학과를 이중전공으로 택한 것은 순전히 내가 수학을 좋아하기 때문이었지만 깊이 공부하다보면 힘들다. 마이크로디그리 제도는 이중전공까지는 아니고 한 15학점 정도만 선별된 전공과목을 들으면 micro한 degree를 주는 제도이다. (크게 쓸모가 있을지는 잘 모르겠다.) https://math.korea.ac.kr/%ec%9d%b8%ea%b3%b5%ec%a7%80%eb%8a%a5%ec%9d%98%ec%88%.. 공감수 1 댓글수 0 2025. 2. 16.
[C++] 코딩할때 '\b' 문자에 관하여 https://www.acmicpc.net/problem/5430백준 5430: AC 문제를 풀고 있었다. 이 문제는 어떤 deque 배열이 {1,2,3,4} 이런 식으로 있으면 답을 [1,2,3,4] 형태로 출력해야 하는 문제다. cout 나는 이런 식으로 출력을 했다.즉, 먼저 '['를 출력 후 deque 속 모든 값에 대해 그 값과 이어서 ','를 출력한다. 그 후 ']'를 출력한다.그럼 이런 식으로 될 것이다.[1,2,3,4,]마지막 값 이후에 필요없는 ','이 하나 추가된 것이다.그래서 나는 "한 칸 뒤로가기" 문자인 '\b'로 그 쉼표를 지우려 한 것이다. 그러면 출력 시 정상적으로[1,2,3,4]로 출력이 된다. 다만, 이걸 백준에 그대로 제출하면 틀렸다고 나온다.정확한 원리는 모르지만.. 공감수 1 댓글수 1 2024. 12. 15.
게일 섀플리 알고리즘(Gale–Shapley algorithm) 수학이 필요한 순간우리가 익숙하게 사용하는 연산, 매일 이야기하는 확률, 쉽게 그리는 좌표 등도 한때는 전문가들조차 이해할 수 없는 복잡한 이론이었다. 페르마, 뉴턴, 아인슈타인은 물론, 지금 잘 알지 못하는www.aladin.co.kr 김민형 작가가 쓴 수학이 필요한 순간을 읽고 있다. 본문 5장에 소개되는 알고리즘으로, 게일 섀플리 알고리즘이라는 것이 있다. 남자 n명과 여자 n명이 소개팅을 할 때, 짝을 지어주는 최적의 방법을 찾아주는 알고리즘이다. 그러기 위해서는 각 남자가 어떤 여자를 좋아하는 지 순위를 매긴 정보가 필요하다. 이를 테면 n이 4일 때 1번 남자는 1번 여자-4번 여자-3번여자-2번여자 순서대로 좋다는 정보를 말한다. 그리고 반대로 각 여자가 남자들의 순위를 매긴 정보도 필요하다.. 공감수 2 댓글수 1 2024. 11. 10.
C++과 Java에서 Priority Queue의 차이점 C++에서는 #include 를 해주고 Java에서는 import java.util.PriorityQueue; 를 해주어 Priority Queue(우선순위 큐) 자료구조를 사용할 수 있게 해준다. 1. Priority Queue 선언 C++: priority_queue pq_int; priority_queue pq pq_ll; 이와 같이 priority_queue으로 선언할 수 있다. Java: PriorityQueue pq = new PriorityQueue(); 자바에서는 new 뒤까지 써주어야 한다. 2. 우선 순위 C++에서는 기본적으로 Priority Queue가 큰 값을 우선순위로 두지만 Java는 작은 값을 우선순위로 둔다. 예를 들어 1, 3, 5, 7이 Priority Queue 안에 .. 공감수 0 댓글수 0 2023. 10. 19.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.