알고리즘/백준 문제풀이13 [백준 JAVA] 10826 피보나치 수4 문제 https://www.acmicpc.net/problem/10826 10826번: 피보나치 수 4 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 풀이방법 간단한 피보나치 수 문제 같지만, 일반적인 피보나치 수처럼 문제를 풀면, ArrayIndexOutOfBounds 런타임 에러가 나는 문제였다. 입력값을 보면 n은 10,000까지 가기 때문이다. 이 문제를 해결하기 위해서는 BigInteger를 사용해야 했다. Int는 메모리 크기는 4byte로 표현할 수 있는 범위는 -2,147,483,648.. 2022. 9. 18. [백준 JAVA] 17406 배열 돌리기 4 문제 https://www.acmicpc.net/problem/17406 17406번: 배열 돌리기 4 크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 www.acmicpc.net 풀이방법 회전 순서에 따라 최종 배열이 다르기 때문에 순열코들르 사용하여, 회전연산의 순서를 정해주어야 한다. 순서를 정하면, 움직일 정도인 sx, sy, ex,ey를 구해준 후 spin함수를 사용해서 배열을 돌려준다. 시계 방향으로 한 칸씩 돌리기 위해서 아래와 같이 방향을 4가지로 나눠서 배열을 돌려주었다. spin 코드는 아래와 같다. //배열 돌리기 st.. 2022. 9. 18. [백준 JAVA] 14500 테트로미노 문제 14500번: 테트로미노 (acmicpc.net) 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 풀이방법 처음에는 모든 모양을 다 고려해서 풀어야하는 줄 알았는데 시간 제한을 보니 그렇게 풀 수 없는 문제였다. 다음에 생각해낸 방법은 dfs를 사용하는 것이다. dfs를 사용하면 ㅗ,ㅜ,ㅓ,ㅏ를 제외한 모든 모양을 만들어낼 수 있고, 그 중에서 최대값을 찾으면 된다. 4방탐색을 진행하며 sum에 map값을 더해준 값을 매개변수로 계속 전달하고, 그중에서 최대값을 찾는다. 그 외의 ㅗ,ㅜ,ㅓ,ㅏ는 각각의 범.. 2022. 9. 16. [백준 JAVA]2636 치즈 문제 2636번: 치즈 (acmicpc.net) 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 풀이방법 우선 처음 생각했던 방법은 치즈입장에서(숫자가 1이라면) 1이아닌곳을 bfs를 돌리면서 숫자가 가장자리에 도달한다면 map을 0으로 바꿔주는 방법을 생각했다. 그렇게 푸니 답은 나오지만 메모리 초과가 떠서 조금 더 효율적으로 풀 수 있는 방법을 고민했다. 두번째로 생각해낸 방법은 굳이 치즈입장에서 생각하지말고, 가장자리에서 치즈쪽으로 bfs를 돌리다가 치즈가 나오면 map을 0으로 바꿔주는 방법을 생각했다. 근데 다시 생각해.. 2022. 9. 15. 이전 1 2 3 4 다음
