요깨비's LAB

재귀를 이용하여 Top-Down이 아닌 Bottom-Up 방식으로 문제를 풀었습니다. 그 이유는, Top-Down으로 풀었을 경우에는 풀었던 문제를 다시 풀어야 하는 비효율이 존재하기 때문에 효율을 생각해서 Bottom-Up 방식으로 풀었습니다. Bottom-Up으로 바꾸니까 이 문제에 한해서 DP가 되버린 것 같기도 하네요 class Solution { int[] dp; public int solution(int n) { int answer = 0; dp = new int[n+1]; dp[0] = 0; dp[1] = 1; if(n == 1) { answer = 1; }else { pibo(2,dp[0],dp[1],n); } answer = dp[n]; return answer; } public void..

체스판이라는 것을 명심하고 풀이에 들어가야 합니다. 상하좌우 색깔이 서로 달라야 합니다. 단순하게 한줄에 최적의 경우만 찾아서는 안됩니다. 1. 우선 주어진 맵에서 X = 0번째에서 주어진 M 크기 - 8, Y = 0번째에서 주어진 N크기 - 8의 기준을 주어 8*8의 맵을 가져옵니다. 2. y = 0~6(현재위치 ?= 현재위치 + 1) , x = 0으로 먼저 흰/검 값을 정한 뒤에(흰색 시작, 검정색 시작 두가지) y= 0~7번째 마다 map[y][0], map[y][1] .... map[y][6]으로 x에 대한 흰/검 값들을 정해주면서 map[y][x] == map[y][x+1]이면 count 값을 증가 시키고 map[y][x+1]의 값을 바꿔줍니다. 3. 해당 로직을 마치고 이전 값보다 최소값이면 ..

[ 문제 ] 땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 합니다. 단, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다. 예를 들면, | 1 | 2 | 3 | 5 | | 5 | 6 | 7 | 8 | | 4 | 3 | 2 | 1 | 로 땅이 주어졌다면, 1행에서 네번째 칸 (5)를 밟았으면, 2행의 네번째 칸 (8)은 밟을 수 없습니다. 마지막 행까지 모두 내려왔을 때, 얻을 수 있는 점수의 최대값을 return하는 solution 함수를 완성해 주세요. 위 예의 경우, 1행의 네번째 칸..

Stack을 이용하여 해결하였습니다. 1. 괄호를 한개 읽어온다. 2. (1) '('인 경우 Stack에 PUSH (2) ')'인 경우 Stack Size가 0이면 false / 0보다 크면 POP 1번으로 회귀 3. 모든 괄호를 읽었으면 Stack을 체크해서 Stack이 다 비어있으면 올바른 괄호이므로 TRUE 스택이 비어있지 않으면 ')'의 갯수보다 '('의 갯수가 많은 것이므로 FALSE import java.util.Stack; class Solution { static Stack stack = new Stack(); boolean solution(String s) { char[] carr = s.toCharArray(); int carrLen = carr.length; for (int i = 0..

처음 아이디어는 n을 이진수로 변환하여 저장하고 n+1의 값들을 이진수로 변환하여 이진수끼리 비교하여 1의 개수가 같은지를 비교하려했습니다. 하지만 이것은 값이 매우 커졌을때 매번 이진수 길이만큼 Brute-Force를 수행하기 때문에 시도하기 전에 답이 없겠다는 판단을 했습니다. 그래서 두번째 아이디어로 n의 값을 DFS연산을 하여 n%2, n/2를 이용하여 1인 경우만 체크하여 1의 개수를 count하여 저장. n의 값을 1씩 증가하여 똑같은 DFS연산을 수행한 count값이 n의 count값이 같은지를 비교하여 같으면 연산을 멈추고 답을 출력하는 방식으로 하였습니다. class Solution { public int solution(int n) { int answer = 0; int count = ..

방향그래프인 것을 생각하고, DFS를 이용하여 해결하였습니다. 로직은 아래와 같이 생각했습니다. 행렬에 값을 넣을때 1일 경우 해당 위치 값 x,y를 이용하여 Element객체를 만들어 Queue에 넣는다. Queue에서 Element를 하나 꺼낸다. 해당 위치를 Root로 두고 y는 현재 위치 x는 다음 위치로 DFS 연산을 진행한다. -> DFS 연산은 가리키는 곳이 값이 1이면서 방문하지 않은 곳이면 Root의 next 위치에서 다음 next 값들을 1로 바꿔준다.(이동 가능함을 체크한다는 의미) 그렇지 않으면 종료 -> 만약 Root값과 가리키는 값이 같으면 종료. 그려진 맵을 출력 아래에는 코드입니다. import java.util.LinkedList; import java.util.Queue;..

예... 이번 문제도 나름의 아이디어를 써봤으나 메모리 초과로 다른 아이디어로 접근해서 해결했습니다.. 우선 문제 접근 자체는 크게 어렵지 않았습니다. 일단 이전에 제가 실패 했던 아이디어입니다. 첫 번째 문자는 일단 아무거나 다 선택한다. 현재 문자열의 길이가 초기값과 같은지?(완성 여부) 같으면 해당 값이 이미 있는지? 두번째부터 문자를 선택한다 2번째 문자부터 분기 조건을 부여하는데 (1) 바로 직전 문자와 선택한 문자가 같으면 안됨 (2) 이미 방문한 문자 위치면 안됨 2번으로 다시 재귀 실행... 여기에서 2번을 제외하면 그냥 재귀함수랑 기본적인 분기처리를 그대로 따라가면서 짜면 됩니다. 하지만 2번을 구현하기 위해서는 이전에 완성된 문자열을 저장해주는 공간이 필요한데 저는 자료구조의 Set을 ..

저의 DFS로 풀려는 아이디어로는 시간 초과와 1000 이상의 값에서는 절대 돌아가지 않을 것 같다는 판단에 다른 분들의 아이디어를 보고 이해한 후에 배껴서 풀었습니다. 아이디어 잘 생각 하시는 분들 보면 정말 부럽... 하지만 재능이 나무에서 뚝 떨어지신 분들도 많겠지만 저에게는 그러한 재능이 없기에.. 꾸준히 높이 뛰기해서 쟁취해야겠죠 잡설이 길었습니다. 조건 두 개를 주었습니다. 표의 가로나 세로 크기가 1일 경우 => 이 경우, 정사각형의 원리에 의해 1인 값이 하나라도 있으면 넓이는 1일 수 밖에 없습니다. 모두 0 이면 당연히 0을 출력하겠죠 가로 세로 모두 2 이상일 경우, 1,1에서 부터 시작한다. => 정사각형의 한변의 크기를 구하는 원리에 의해 출처: https://blog.sonim1..