코딩테스트 준비

[Java] 프로그래머스 Lv2 - [3차] 압축 (2018 KAKAO BLIND RECRUITMENT)

🔗 문제링크 코딩테스트 연습 - [3차] 압축 TOBEORNOTTOBEORTOBEORNOT [20, 15, 2, 5, 15, 18, 14, 15, 20, 27, 29, 31, 36, 30, 32, 34] programmers.co.kr 📂 분류 구현 💡 풀이 문제 설명에 나와 있는 LZW 압축 과정을 구현하면 되는 문제이다. 접근 방식 A ~ Z까지 HashMap을 이용해 초기화를 한다. 현재 단어 w와 다음 단어 c를 받는다. w + c가 map에 저장되어있는지 확인하고, 저장되어있다면 continue로 건너뛰어 위 과정을 다시 진행한다. w + c가 없다면, w 값을 출력하고 map에 저장한 다음 w를 초기화시켜준다. 💻 코드 import java.util.ArrayList; import java.u..

[Java] 프로그래머스 Lv2 - 3 x n 타일링

🔗 문제링크 코딩테스트 연습 - 3 x n 타일링 programmers.co.kr 📂 분류 DP 💡 풀이 이 문제는 2 x n 타일링을 응용한 문제이다. 세로 길이가 3인 바닥이기 때문에 n이 홀수 일 경우 타일 배치를 하지못한다. 처음 점화식은 dp[i] = dp[i - 2] * 4 - dp[i - 4]로 쉽게 구해졌으나 나머지 연산에 문제가 있어서 이 점화식으로는 문제를 해결하지 못했다. 다른 점화식을 구하려고 고민을 했으나 생각이 나지않아 풀이법을 참고해서 풀었다. 점화식은 다음과 같다. tiles[i] = tiles[i - 2] * 3 + tiles[i - 4] * 2 + tils[i - 6] * 2 ... 💻 코드 public class Solution { private static final ..

[Java] 프로그래머스 Lv2 - 2 x n 타일링

🔗 문제링크 코딩테스트 연습 - 2 x n 타일링 가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 programmers.co.kr 📂 분류 DP 💡 풀이 2 x n 타일링 문제는 메모이제이션을 대표하는 문제이다. 이 문제는 bottom-up 방식과 top-down 방식 두 가지로 해결할 수 있는데, 나는 bottom-up 방식으로 접근하여 문제를 해결했다. 접근 방식 n이 1일 경우 가로로만 배치할 수 있기 때문에 배치할 수 있는 경우는 한 가지만 존재한다. n이 2일 경우 가로로 배치하고 세로로도 배치할 수 있기 때문에 배치할 수 경우는 두 가지가 존재한다. n이..

[Java] 프로그래머스 Lv2 - 가장 큰 정사각형 찾기

🔗 문제링크 코딩테스트 연습 - 가장 큰 정사각형 찾기 [[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]] 9 programmers.co.kr 📂 분류 DP 💡 풀이 DP Bottom-up 방식으로 해결되는 문제이다. 접근방식 정 사각형의 넓이를 구하는 문제이기 때문에 왼쪽, 위쪽이 하나라도 0이라면 넓이는 1이 된다. 따라서 점화식은 아래와 같이 나온다. cache[i][j] = Math.min(cache[i - 1][j - 1], Math.min(cache[i - 1][j], cache[i][j - 1])) + 1; 💻 코드 public class Solution { private int[][] cache; public int solution(int[][] board) { in..