목록알고리즘 (70)

택시짱의 개발 노트

[백준] 2206번 - 벽 부수고 이동하기

링크 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동 www.acmicpc.net 풀이 시작점에서 끝점까지 이동하는데 걸리는 최소 시간을 구하는 문제이다. 저는 최소를 보자마자 BFS가 떠올랐고, 여기서..
알고리즘 2020. 2. 1. 15:55
[백준] 3190번 - 뱀

링크 https://www.acmicpc.net/problem/3190 3190번: 뱀 문제 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다. 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따 www.acmicpc.net 풀이 어렸을때 했던 뱀 게임처럼 사과를 먹으면 길이가 늘어나고 꼬리나 벽에 닿으면 끝나는 그런 게임과 같은 문제이다. 뱀을 구성하기 위해서..
알고리즘 2020. 1. 30. 16:02
[프로그래머스] 가장 먼 노드

링크 https://programmers.co.kr/learn/courses/30/lessons/49189 코딩테스트 연습 - 가장 먼 노드 | 프로그래머스 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr 풀이 간단한 BFS로 풀 수 있다. 일단 양방향 그래프를 만든 후 출발지에서 도착한 위치와 거리를 저장할수 있는 구조체를 만들었다. 이전 노드에서 다음 노드에 도착 하였을때 거리를 1 증가 시켜 주었고 방문 여부를 확인하기 위해서 visited배열을 모두 -1로 초기화 하고 방문한 위치를 기억 하기 위해 visited을 거리만큼 갱신 했고 가장 큰 거리와 visited배열과 비교하여 거장 먼 노드의 갯수를 찾을..
알고리즘 2020. 1. 26. 18:51
[프로그래머스] 예산

링크 https://programmers.co.kr/learn/courses/30/lessons/43237 코딩테스트 연습 - 예산 | 프로그래머스 국가의 역할 중 하나는 여러 지방의 예산요청을 심사하여 국가의 예산을 분배하는 것입니다. 국가예산의 총액은 미리 정해져 있어서 모든 예산요청을 배정해 주기는 어려울 수도 있습니다. 그래서 정해진 총액 이하에서 가능한 한 최대의 총 예산을 다음과 같은 방법으로 배정합니다. 1. 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정합니다. 2. 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 programmers.co.kr 풀이 정해진 예산의 총액 이하에서 가능한 최대의 총 예산을 구해야 한다...
알고리즘 2020. 1. 25. 13:30
[프로그래머스] 섬 연결하기

링크 https://programmers.co.kr/learn/courses/30/lessons/42861 풀이 n개의 섬 사이에 다리를 건설하는 비용이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 최소 비용을 찾아야 한다. 방법을 생각해 보면 섬과 섬사이의 비용이 가장 작은순서대로 정렬하여 연결하면 되지만 이미 연결된 섬을 다시 연결 하면 안되고 건너 뛰어야 된다는 생각을 해볼 수 있습니다. 이때 필요한 알고리즘은 크루스칼(Kruskal)알고리즘을 이용할 수 있습니다. 크루스칼 알고리즘은 탐욕적인 방법을 이용하여 그래프의 모든 정점을 최소 비용으로 연결하는 방법입니다. 1. 최소비용으로 연결된 노드를 찾기 -> priority_queue를 이용 2. 섬과 섬이 이미 연결되어 있..
알고리즘 2020. 1. 24. 20:41
[백준] 2294번 동전 2

링크 https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다. www.acmicpc.net 풀이 위의 문제는 사용한 동전의 최소 개수를 찾는 문제인데 다들 가장 큰 동전 부터 가장 작은 동전까지 이용하여 풀면 되겠지? 라는 생각을 하셨겠지만 여러 반례가 있죠? 그래서 가장 작은 값의 동전부터 가장 큰 동전까지 사용한 개수를 DP배열에 카운트하여 최소개수를 찾을수 있습니다. 1원짜리 동전으로 0~15원까지 만들수 있는 개수를 표로 나타내..
알고리즘 2020. 1. 24. 19:48
Prev 1 ··· 6 7 8 9 Next