전체 글 (19) 썸네일형 리스트형 [ 백준 1726번 로봇 ] Python 코드 (BFS) 1. 문제 https://www.acmicpc.net/problem/1726 1726번: 로봇 많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 www.acmicpc.net 2. BFS 풀이 (3차원 visited 배열) 나는 처음에 다른 방식으로 풀었다. BFS에서 visited배열의 활용 방식을 살짝 변경해서 최단거리를 찾는 알고리즘으로 사용했는데 혼자 풀고 뿌듯함에 차있을 때, 다른 분들의 3차원 visited 배열을 보고 무릎을 탁 쳤다. 메모리 사용량과 처리시간도 더 적었을 뿐더러, 무엇보다 기본적인 BFS 알고리즘 동작방식을 그대로 따랐다. 3차원 visi.. [ 백준 11265번 끝나지 않는 파티 ] Python 코드 (다익스트라, 벨만포드) 1. 문제 https://www.acmicpc.net/problem/11265 11265번: 끝나지 않는 파티 입력의 첫 번째 줄에는 파티장의 크기 N(5 ≤ N ≤ 500)과 서비스를 요청한 손님의 수 M(1 ≤ M ≤ 10,000) 이 주어진다. 각각의 파티장은 1번부터 N번까지 번호가 붙여져 있다. 다음에는 N개의 줄에 걸 www.acmicpc.net 2. 풀이 2.1. Bellman-Ford 입력이 2차원 배열인데다가, 출발지도 여러개여서 Bellman-Ford 알고리즘을 쓰고 싶은 충동에 휩싸인다. 실제로 Bellman-Ford를 써서 풀 수 있기는 하다! 그런데 파이썬의 비애로 자잘한 최적화를 해줘야 한다. 관련 내용은 이 블로그를 참조했다. 아주 자세하고 친절하게 써주셨다. 무조건 min으로.. [ 백준 1922번 네트워크 연결 ] Python 코드 (MST) 1. 문제 https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 2. 풀이 물구나무 서서 봐도 MST(최소 스패닝 트리) 문제이다. 특별하게 꼰 부분도 없어서 MST 알고리즘 연습하기 딱 좋다. 대표적인 MST 알고리즘으로는 Prim과 Kruskal이 있다. 주어진 그래프의 노드가 V개, 간선이 E개라고할 때 시간복잡도는 다음과 같다. 알고리즘의 반복문 부분을 보면 어렵지 않게 확인할 수 있다. Prim Prim with heap Kruskal 시간복잡도 O(V**2) O(E*logV) O(E*logV) 특징 자료구조 heap을 사용해야 .. 이전 1 2 3 4 5 ··· 7 다음
