공부하자

1405번: 미친 로봇 (acmicpc.net) 1405번: 미친 로봇 첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고, 모든 확률은 100보다 작거나 같은 자 www.acmicpc.net 백트랙킹 문제이다. 로봇이 이동 횟수를 모두 채울 때까지 방문하지 않은 지점만 방문한다면, 해당 경로의 확률을 정답에 더해주면 된다. 이때 방문한 지점은 (2n + 1) * (2n + 1) 크기의 행렬을 만들어서 표시했다. 한 방향으로 최대 n번 갈 수 있기 때문이다. dx, dy = [-1, 0, 1, 0], [0, 1, 0, -1] def dfs(x, y, cnt, p): global ans if cnt =..

5014번: 스타트링크 (acmicpc.net) 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net BFS 문제이다 엘레베이터를 타고 올라가든 내려가든 버튼을 누르는 횟수는 1로 동일하기 때문에 (=가중치가 1로 똑같기 때문에) 중복방문을 허용하지 않는 BFS 문제라고 생각하면 된다. 버튼을 눌러 얼마만큼 이동하느냐는 로직에 큰 영향을 주지 않는다. 범위만 넘어가지 않도록 설정해주면 된다. 가중치가 여러 개여서 중복방문을 허용하는 문제👇 2021.03.18 - [Algorithm/Graph] - [백준 BOJ] 13549 숨..

13549번: 숨바꼭질 3 (acmicpc.net) 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 두 가지 방법으로 풀 수 있다! 다익스트라 (Heap, Priority Queue 활용) 0-1 BFS (Deque 활용) 다익스트라는 힙에서 다음 위치를 꺼낼 때 우선순위를 고려해야하므로, (걸린 시간, 위치)의 형태로 삽입을 하게 된다. 이에 반해 BFS는 가중치(수빈이가 다음 위치로 가는 데 걸리는 시간, 여기서는 0과 1뿐이다.)에 따라 큐에 삽입하는 위치를 달리해서 위의..

1916번: 최소비용 구하기 (acmicpc.net) 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 다익스트라 문제 특정 출발점으로부터 특정 도착점까지의 최소비용을 묻고 있기 때문에, 하나의 출발점에 대한 비용행렬을 만들면 된다!! (1차원 행렬) 📢 주의해야 하는 점 방향 그래프이다!! (처음에 무방향 그래프라고 생각했다가 틀렸다...😥) 한 노드로부터 다른 노드로 가는 간선이 여러 개일 수 있다!! 예를 들어, 입력이 다음과 같이 주어지면, 1 2 3 1 2 10 비용이..

코딩테스트 연습 - 순위 | 프로그래머스 (programmers.co.kr) 코딩테스트 연습 - 순위 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2 programmers.co.kr 처음에는 딕셔너리와 세트로 풀이했는데 시간 초과가 났다. (시초 안 나는 풀이도 있다!!) 기왕 문제 종류가 그래프인만큼 다른 풀이 방법을 떠올려 보려고 했지만 쉽지 않았다... 그런데 질문을 보니 어떤 천사분께서 플로이드-와샬을 써보라고 하신 것을 보고... 바로 풀렸다!! 플로이드-와샬 알고리즘은 원래 모든 노드로부터 다른 노드까지의 최단 거리를 저장하는 알고리즘이다. 이때, 전체 알고리즘은 삼중 반복문으로 수행되는데 다음과 같다. # n = 노드 개수 for k in range(n):# ..

코딩테스트 연습 - 합승 택시 요금 | 프로그래머스 (programmers.co.kr) 코딩테스트 연습 - 합승 택시 요금 6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4 programmers.co.kr 그래프 문제 다익스트라와 플로이드-와샬 두 방법으로 풀 수 있다. 대부분 테스트 케이스에서 다익스..