본문 바로가기

알고리즘 문제147

[알고리즘문제] 프로그래머스 - 단어 퍼즐 같은 문자를 여러번 사용할 수 있다고 하였으니 재귀로 해결하는 방법을 생각해 보았다. tmp+=strs[n+1]를 계속하면서 tmp의 길이가 t보다 길면 재귀를 탈출하고 tmp+=strs[n+1]을 더하는 구조로 생각해 보았다. 하지만 틀렸다고 나왔고 다른 분의 풀이를 참고하였다. 2중 for문을 사용하여 dp로 최선의 값을 계속 갱신할 수 있다. #include #include #include #include #include using namespace std; int solution(vector strs, string t) { int answer = 0; set s; vector dp(t.length() + 1, INT_MAX); for (int i = 0; i < strs.size(); i++) {.. 2020. 11. 12.
[알고리즘 문제] 백준1238 - 파티 www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net N개의 집이있고 서로의 집을 이동하는데 시간이 다를때(a->b,b->a는 서로 다름) 하나의 집으로 모이는데 가장 오랜 시간을 걸리는 시간을 구하는 문제입니다. 문제 분류는 다익스트라 알고리즘으로 되어있는데 저는 플로이드 와샬 알고리즘으로 풀었습니다. 두개의 알고리즘 모두 최단거리를 구하는 알고리즘 이지만, 조금 다릅니다. 다익스트라 알고리즘 : 하나의 정점에서 다른 정점으로 가는.. 2020. 10. 23.
[알고리즘 문제] 백준5014 - 스타트 링크 www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net bfs를 사용하여 문제를 해결할 수 있다. 만약 현재 강호 위치에서 위/아래로 이동할 수 있으면 그 위치를 que에 계속 넣어주고 만약 현재 위치가 도착지점이라면 그때 이동한 횟수를 출력해주면 된다. 단순히 que에 넣고 빼는 과정이지만 신경써주어야 할 부분이 2가지 있다. 1. 현재의 que 사이즈 만큼 검사해준다. 검사를 진행하면서 계속 que에 넣는 과정이 진행되는데 이렇게 되면 하루가 어떻게 지났는지 확인할 수 없다.. 2020. 10. 23.
[알고리즘 문제] 백준1937 - 욕심쟁이 판다 www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net 조건을 만족하면서 판다가 가장 멀리 움직일 수 있는 경로를 구하는 문제 입니다. 그냥 일반적인 dfs방식으로 풀면 4^500의 시간복잡도를 가지므로 dfs + dp로 문제를 해결해야 합니다. 먼저 dp[][]를 모두 -1로 초기화 해주어야 하는데 이는 아직 해당 좌표를 한번도 방문한 적이 없다는 것을 의미합니다. 만약 dp[][]값이 -1이면 검사를 해주어야 하고 dp[][]값이 -1이 아닌 경우는 해.. 2020. 10. 23.

티스토리툴바