목록알고리즘 (25)
개발하는 리프터 꽃게맨입니다.
https://www.acmicpc.net/problem/15903 15903번: 카드 합체 놀이 첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다. 두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, www.acmicpc.net 1. 문제 2. 아이디어 기본적으로 그리디 알고리즘이다. 가장 작은 카드를 더해서 카드 뭉치를 업데이트해주면 된다. 그러면 가장 작은 요소로 배열을 정렬해서 하는 방법이 있는데, 이는 조금 문제가 있다. 왜냐면, 업데이트 + 정렬 + 업데이트 + 정렬은 생각보다 비용이 크기 때문이다. 정렬의 경우 아무리 빨라봐야 평균 n log n 시간 복잡도가 소모된다. 시..
https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 문제 아이디어 BFS 문제의 대표격 중 하나인 미로찾기 문제입니다. 그러나 시간 제한이 1초이기 때문에 O(N^2) 인 BFS로는 풀 수 없고, O(N logN) 인 다익스트라 알고리즘을 이용해서 풀어야만 합니다. 맨 좌측 상단에서 시작해서 맨 우측 하단까지 어떻게 도달할 것인가? 에 대한 문제이고 1은 벽인데 필요하다면 벽을 부술수도 있습니다. 단, 벽을 최대한 적게 부수면..
1. 문제 https://www.acmicpc.net/problem/17070 2. 아이디어 다이나믹 프로그래밍으로 풀 수 있는 문제일 것 같다. 특정 좌표를 (y, x) 라고 했을 때 파이프의 우측 좌표를 기준으로 (좌측 좌표는 생각할 필요 없다.) (y, x) 에 가로로 도착할 횟수 + (y, x) 에 세로로 도착할 횟수 + (y, x) 에 대각선으로 도착할 횟수 의 합을 구하면, 해당 좌표에 도달할 수 있는 모든 경우의 수가 된다. 이 때, 벽에 막힐수도 있기에 예외처리에 신경쓴다. 3. 풀이 먼저 전역변수 목록이다. tableSize는 격자의 크기 table은 격자의 정보를 입력하는 부분 dpRight, dpDown, dpRD 는 각각 특정 좌표에 가로로 도착하는 경우, 세로로 도착하는 경우, 대..
참고: https://powerclabman.tistory.com/26 [C++] 경로 역추적: BFS을 이용한 '미로찾기 알고리즘' 개요 위 그림과 같은 임의의 미로가 있고 플레이어와 도착지의 위치가 정해져 있을 때, 플레이어는 도착지를 어떻게 찾을 수 있을까요? 그리고 어떻게 해야 최단 경로로 도착지에 도달할 수 있 powerclabman.tistory.com 참고: https://powerclabman.tistory.com/27 [C++/이론] 다익스트라 알고리즘 (Dijkstra Algorithm) 참고: https://powerclabman.tistory.com/24 참고: https://powerclabman.tistory.com/25 가중치 그래프 이전 포스팅에서 사용했던 그래프는 모두 가중..
참고: https://powerclabman.tistory.com/24 참고: https://powerclabman.tistory.com/25가중치 그래프이전 포스팅에서 사용했던 그래프는 모두 가중치가 없는 그래프였습니다. 즉, 노드와 노드를 이동하는데 비용이 동일하다는 것이죠. 근데, 실제로 상황에서 A->B로 가는 것과 A->C로 가는 것의 비용이 다를 수도 있겠죠? 서울 -> 강원도 서울 -> 부산 두 조건 다 도시와 도시 사이를 이동하는 것이지만, 소모하는 기름, 거리, 톨게이트 비용 등.. 많은 것이 다를 것입니다. 이런 비용을 '가중치' 라고 하고, 가중치를 표현한 그래프를 '가중치 그래프'라고 부릅니다. int adjacent[5][5] = { 0,1,1,0,0, 0,0,1,0,1, 0,0,..