안드 공부를 해볼까?

1. 문제분석 전형적인 BFS 문제 토마토를 보관하는 창고가 있고 익은 토마토는 사방면으로 안 익은 토마토에 영향을 준다. 먼저 익은 토마토의 좌표를 큐에 넣어준다. 익지 않은 토마토의 개수는 따로 저장해둔다. (그래야 큐에서 빼고 사방면으로 옮기기 때문) 만약 안 익은 토마토가 존재하고, 큐에 데이터가 있으면 익은 토마토가 주변 토마토를 익게 해줄 수 있다. 큐에 뺀 토마토의 좌표에서 사방면으로 옮겨주고 안 익은 토마토에서 익은 토마토가 됐으면 그 토마토의 좌표를 큐에 넣는다. 이런식으로 반복하고 만약 안익은 토마토가 여전히 존재하면 -1, 다 익었다면 걸린 일 수를 출력해주자. 2. 구현 import java.io.BufferedReader; import java.io.IOException; impo..

1. 문제분석 격자판 위에 봄버맨이 폭탄을 놓는다. 그 후 폭탄이 설치되지 않는 곳에 폭탄을 둔다, 즉 모든 칸이 폭탄이 있는 상태다. 그 후 앞서 봄버맨이 설치한 폭탄이 터진다, 여기서 중요한 점은 폭탄이 터진다면 연쇄 폭발은 나오지 않는다. 즉, 폭탄이 터지면 그 곳은 평지가 되는 것이다. 이제 순서대로 생각해보자. 0초 -> 봄버맨이 폭탄 설치(설치한 폭탄은 3초) 1초 -> 아무것도 하지 않음(설치한 폭탄은 2초) 2초 -> 나머지 빈 공간에 폭탄설치(봄버맨이 설치한 폭탄 1초, 빈 공간 폭탄 3초) 3초 -> 봄버맨이 설치한 폭탄 폭발(빈 공간 폭탄 2초) 4초 -> 아무것도 하지 않음(빈 공간 폭탄 1초) 5초 -> 빈 공간 폭탄 폭발 즉, 2초부터 홀수면 폭발, 짝수면 폭탄 설치가 되는 것이..

1. 문제 분석 LCS, 즉 각 문자의 수열에서 공통된 부분을 가진 수열의 최대 길이를 구하는 문제다. 처음에는 모든 문자열의 수열을 구해 문제를 해결할려고 했지만 도저히 구하지 못해 DP로 문제를 해결했다. 먼저 DP 테이블을 만들어보자. 행은 1번째 문자열, 열은 2번째 문자열을 넣어주었다. A C A Y K P C A P C A K 다음과 같은 형태가 나오고 열을 기준으로 하나씩 구해보자. 1. A일 때 A C A Y K P C 0 A 1 P 1 C 1 A 1 K 1 ({A},{C}), ({A}, {CA}), ({A}, {CAP}), ..., ({A}, {CPACAK})까지 구한 값이다. A랑 곂친다면 공통된 부분은 {A}가 되기때문에 1을 더해줬다. 2. AC일 때 A C A Y K P C 0 1..

1. 문제 분석 배낭에 담을 수 있는 최고 가치의 물건을 넣는 문제다. DP로 풀 수 있었고 DP테이블을 통해 문제를 해결했다. Weight 1 Weight 2 Weight 3 Weight 4 Weight 5 Weight 6 Weight 7 Item 1 Item 2 Item 3 Item 4 먼저 무게를 하나씩 증가시키면서 아이템을 넣을 수 있는지 없는지 확인한다. 못 넣는다면 전에 있는 값을, 넣는다면 큰 값을 넣어줘야 한다. 1. 무게가 1 ~ 2일 때 Weight 1 Weight 2 Weight 3 Weight 4 Weight 5 Weight 6 Weight 7 Item 1 0 0 Item 2 0 0 Item 3 0 0 Item 4 0 0 현재 넣을 수 있는 무게가 1,2 이라면 테스트 케이스에 있는..

1. 문제 분석 DP(Dynamic Programming)문제다. 각 계단을 걸어갈 때를 생각해보며 점화식을 만들어 보았다. arr는 각 계단에 존재하는 점수의 집합이다. dp[계단 없음] = arr[0](0이 된다.) dp[계단 1개] = arr[1] dp[계단 2개] = arr[1] + arr[2] 여기까지는 간단하게 세울 수 있다. 하지만 조건에서 연속된 세 개의 계단은 밟으면 안된다고 한다. 3개일 때 1번째 -> 3번째, 2번째 -> 3번째가 가능하다. 그러므로 dp[계단 3개] = arr[3] +((arr[2] + dp[0]), (dp[1])중 최댓값 dp테이블은 각 계단일때의 최댓값을 저장해둔 상태다. 그러므로 위와 같은 점화식을 얻을 수 있다. 4개일 때는 1번째 -> 2번째 -> 4번째,..

1. 개요 사이드 프로젝트 중, View의 Background를 코드로 적용해야할 일이 있었다. 기존 코드인 resource.getDrawable()로 가져올려고 했는데 Lint 오류가 나서 찾아본 결과 새롭게 나온 것이 있었다. 2. 본문 우리가 기존 사용했던 getDrawable를 통해 가져오는 방법이다(context가 필요하다) 하지만 이렇게 구현하면 Lint오류가 나오게 된다. @SuppressLint("UseCompatLoadingForDrawables") API 21부터는 context.getDrawble이 deprecated 됐다고 한다. 우리는 이제 ResourceCompat.getDrawable(context.resources, R.drawable.file_name, theme)로 구현을..

1. 문제분석 전위 순회한 결과값으로 후위 순회를 한 값을 출력하는 문제다. 전위 순회는 (왼쪽 -> 루트 -> 오른쪽), 후위 순회는(왼쪽 -> 오른쪽 -> 루트)로 순회한다. 하지만 데이터를 넣을 때도 순회한 순서대로 넣어줘야할까? 위의 세가지 조건을 보자. 1. 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다. 2. 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다. 3. 왼쪽, 오른쪽 서브트리도 이진 검색 트리다. 어찌 됐던 데이터가 들어갈 때, 위의 조건대로 만들어진다. 결과적으로 전위 순회한 값 순서대로 넣어주면 우리가 원하는 트리 모습이 나오고 그 트리로 후위 순회를 한다. 2. 구현 import java.io.*; class Node { int value..

1. 문제분석 모든 쌍의 GCD = 최대공약수를 구하는 문제다. 최대공약수를 구하는 방법은 많다. 이 문제에서는 유클리드 호제법을 사용했다. 유클리드 호제법은 다음과 같다. 1. 두개의 수 중, 작은 수 / 큰 수의 나머지를 구한다. 2. 나머지가 0일 때, 현재 작은 수를 return한다. 3. 0이 아니라면 원래 작은 수를 큰 수로, 나머지는 작은 수로 다시 구한다. 주의할 점은 구하는 값을 long으로 해야한다. 만약 테스트 케이스 개수가 100개, 값이 999,999라면 int로는 데이터를 표현할 수 없다. 2. 구현 import java.io.*; import java.util.*; public class Main { //유클리드 호제법 //두 수가 주어지고 큰 값을 작은 값으로 나눌때 0이라면..