TIL (12) 썸네일형 리스트형 99클럽 코테 스터디 4일차 TIL: DFS 문제https://www.acmicpc.net/problem/24479 풀이오늘은 챌린저 문제가 아닌 미들러 문제를 풀었다.그 이유는 챌린저 문제를 1시간안에 풀어보려 했지만 풀이하지 못했다.힌트를 확인해보니 벨만포드 알고리즘이였고,벨만포드 알고리즘 하면 기억나는데 음의간선에서도 최단거리를 구할 수 있다는점..? 그래서 사이클이 존재하면 안된다는 점 밖에 기억이 나지 않았다..그래서 일단은 미들러 문제를 풀고, 주말에 벨만포드 알고리즘에 대해 더 학습하고 풀어야겠다고 생각했다.미들러문제는 DFS의 기본적인 문제였고, 챌린저 문제와 난이도 차이가 있다고 느꼈다.DFS에 대해 알고, 조금만 응용한다면 쉽게 풀 수있다.방문 여부를 확인하는 visited 배열을 Int로 사용하였고, 0일 때는 아직 방문하지 않.. 99클럽 코테 스터디 3일차 TIL: 최단 경로 문제https://www.acmicpc.net/problem/2660풀이이 문제도 보자마자 BFS를 떠올렸다.일단 간선의 비용이 1이라는 점에서 최단거리를 구할 수 있기 때문이다.어제 풀었던 문제와 거의 유사한 문제여서 빠르게 풀 수 있었다.회원의 수가 50명 즉 N이 50으로 아주 작았다.또한 플로이드-워셜로도 풀 수 있을 것이라고 생각했는데,오늘은 약속도 있고 요즘에 작곡 레슨을 받아.. 시간이 없어서 일단 BFS로 풀고 내일 다시 플로이드-워셜로 풀어봐야겠다.이 문제는 진짜 빨리 풀었고 (5분?) 한 방에 풀이했다.BFS가 젤 자신있어서 그런 것 같다.. 다른 알고리즘에도 자신감이 생기게 열심히 해봐야지..소스코드후기BFS를 조금 응용하면 쉽게 풀 수 있는 문제였다. 99클럽 코테 스터디 2일차 TIL: 최단 경로 문제풀이이 문제를 처음 봤을 때, 간선의 비용이 동일하다는 점. 최단 경로를 구해야 한다는 점에서 BFS 알고리즘을 떠올렸다.BFS의 시간복잡도가 어떻게 될까도 생각해봤다.$O(V + E)$ 라는 점, 최악의 경우 $O(100 + 5000)$ 이 될 것이라고 생각했다.또한 모든 친구($N$)에 대해 검사를 해봐야 하므로, $O(V * (V + E))$ 이지 않을까..?$100 \times 5100$라면 충분히 통과할 것이라고 생각했다.처음엔 다음과 같이 생각했다.1번노드에서 각 노드로 도달하는 depth를 전부 구해 더해줘야겠다라고 생각했다.즉, 1번 -> 2번으로 가능 최소비용 + 1번 -> 3번으로 가능 최소비용.. 이렇게 전부 구해야지 하고 생각하면서bfs를 1번에서 특정 노드 까지의 비용을 모두 .. 99클럽 코테 스터디 1일차 TIL: 플로이드-워셜 오랜만에 우연히 백준을 들어갔는데 향해99 광고를 보고 스터디 참여 신청을 했다.취업을 한 뒤 코테 공부를 거의 하지 않아서 기억이 가물가물..코테 공부하는게 재밌었기도 하고, 공부해야지 해야지.. 하는데 맨날 하지 않아서 스터디라도 해보면 어떨까 생각이 들었다.대학교 친구 단톡방에 공유해서 한명의 친구와 같이 참여하고 있다.언어랑 난이도도 선택할 수 있었는데, 나는 Swift/챌린저로 선택을 했다.챌린저 문제는 다음과 같았다.문제https://www.acmicpc.net/problem/11403 풀이기존에 풀어봤던 문제였다.문제 딱 보자마자 느낀점은 그래프 문제라는 것. 그 이후 모든 경로를 구해야한다는 점에서 플로이드-워셜 알고리즘을 떠올렸다.플로이드-워셜 알고리즘에 대한 이해만 있다면 쉽게 풀 수 .. 이전 1 2 다음
