본문 바로가기

알고리즘 문제147

[알고리즘문제] 프로그래머스 -멀리 뛰기 문제는 한번 읽어서 바로 이해가 안되서 두 세번정도 읽었습니다. 문제에서 남은 작업량, 남은 N시간이 주어지고 야근피로도 구하는 공식(남은 작업량들의 각각 제곱근의 합)이 주어질 때 최소한의 야근 피로도를 구하는 문제 입니다. 단 1시간에 1의 일을 할 수 있습니다. 예를 들어 남은 작업량이 [4,3,3]이고 N시간이 주어졌을 때 4시간 동안일을 했을 때 남은 작업량의 경우의 수는 다음과 같습니다. [4,2,2] [3,0,3] [2,2,2] .... 이 경우에서 야근 피로도를 구해보면 [4,2,2] = 4^2 + 2^2 + 2^2 = 24 [3,0,3] = 3^2 + 0^2 + 3^2 = 18 [2,2,2] = 2^2 + 2^2 + 2^2=12 더 많은 경우가 있겠지만 위의 경우에서 야근 피로도가 최소값.. 2020. 2. 8.
[알고리즘문제] 프로그래머스 -멀리 뛰기 효진이는 1칸, 2칸을 이동할 수 있습니다. 이동해야 할 n칸이 주어질 때 1칸, 2칸을 n칸에 도달할 수 있는 방법을 구하면 됩니다. 문제는 보자마자 앞서 이동했던 경우의 수를 사용하여 현재 구하려는 경우의 수를 구할 수 있을 것 같다는 생각을 했습니다. dp를 사용하였고 먼저 각 n마다 이동할 수 있는 경우를 구해보았습니다. 1 : (1) - 1가지 2 : (1,1), (2) - 2가지 3 : (1,1,1), (1,2), (2,1) - 3가지 4 : (1,1,1,1), (1,1,2), (1,2,1), (2,1,1), (2,2) - 5가지 5 : (1,1,1,1,1), (1,1,1,2), (1,1,2,1), (1,2,1,1,), (2,1,1,1), (1,2,2), (2,1,2), (2,2,1) - 8가.. 2020. 2. 8.
[알고리즘문제] 프로그래머스 - 가장 긴 팰린드롬 펠린드롬 문제는 몇번 풀어봐서 자신있었는데 음..시간제한이 걸려서 애를 먹었습니다. 1. 첫번째 방법 효율성 테스트 1번을 제외하곤 다 통과했는데, 아무래도 substr에서 많은 시간을 잡아먹은 것 같습니다. #include #include #include using namespace std; bool isPalindrome(string s){ if(s.size() % 2 == 1){ // 문자열이 홀수인 경우 s.replace(s.size()/2,1,""); } int count = s.size()/2; string s1 = s.substr(0,count); string s2 = s.substr(count,count); reverse(s2.begin(),s2.end()); return s1 == s2;.. 2020. 2. 5.
[알고리즘문제] 프로그래머스 - 보행자 천국 m,n크기의 map이 주어질 때, 1,1에서 m,n까지 이동가능한 경로가 몇개 있는지 구하는 문제입니다. 단, 이동을 하는데는 다음과 같은 조건이 있습니다. 1. 오른쪽, 아래 방향으로만 움직일 수 있다. 2. 맵에서 0으로 표시된 부분은 오른쪽/아래 모두 이동 가능하다. 3. 맵에서 1으로 표시된 부분은 지나갈 수 없다. 4. 맵에서 2로 표시된 부분은 이전에 진행된 방향으로만 진행할 수 있다. 예를 들어, a->b로 이동하는데 x축으로 오른쪽으로 한 칸 이동했고 b는 2로 표시되어 있다면 b는 오른쪽으로만 이동할 수 있다) 1. bfs(시간초과) 처음에 dfs로 문제를 풀면 어떨까 생각을 했는데 map의 크기가 500 x 500이었기 때문에 시간이 너무 오래걸릴 것 같았습니다. 그래서 bfs로 문제를.. 2020. 2. 4.

티스토리툴바