Hello backEnd

문제 설명 1. N, M이 주어진다. 2. N개는 들어보지 못한 사람, M개는 보지 못한 사람이다. 3. 두 가지 모두의 경우에 해당하는 사람을 구하면 된다. 풀이 과정 1. 기초적인 HashMap문제이다. 여기서는 HashSet으로 풀면 됨. 2. N개의 배열에 대해 각각을 HashSet으로 받아준다. 3. 그 HashSet에 대해 존재하는 M개의 배열들을 ArrayLIst에 저장한다. 4. 그 ArrayList를 배열을 바꾸고 출력시키면 된다. 코드

문제 설명 1. N이 주어진다. 2. N개의 배열들에 해당하는 숫자들이 각각 주어진다. 3. 가장 긴 증가하는 부분 수열을 구하면 된다. 풀이 과정 1. 처음에는 DP로 풀려 하였는데, 시간 복잡도에서 문제가 발생했다. 이후 DP와 이분탐색을 섞어서 해결하였다. 2. 부분 수열을 저장할 Arraylist를 만들어, 이를 채워 준다.(이걸 쓴 이유는, 부분 수열의 경우 언제까지 값이 있을지 모르기도 하고, 중간에 값을 바꾸려고 하기 때문이다.) 3. 숫자를 순서대로 입력받으며, 현재 입력된 순서의 숫자가 Arraylist의 가장 위의 값보다 큰 값인지 확인한다. 4. 이후, 그 값이 더 큰 값인 경우 배열을 추가해 주면 된다. 4. 그렇지 않은 경우 배열 내부의 값들 중 해당 값보다 큰 수들 중 최소의 숫..

문제 설명 1. N이 주어진다. 2. NxN배열에 해당하는 종이들이 -1, 0, 1로 주어진다. 3. 한 범위의 모든 종이들이 해당 숫자로 이루어진 경우들을 구한다. 4. 범위는 전체 크기 사이즈를 가로세로를 3으로 나눈 총 9개의 범위로 이루어져 있고, 해당 범위에 다른 종이가 있으면 다시 나누어 준다. 5. -1, 0, 1 각각 얼마나 많은 '범위'가 존재하는지 구하면 된다. 풀이 과정 1. 분할 정복 문제이다. 2. 값들을 더 작은 수로 나누고, 그곳에서부터 조합해 맞추어 나가면 된다. 3. 이전 글의 쿼드 트리와 유사한 문제이다. 그냥 범위를 더 잘게 나누고, 괄호를 없애면 된다. 4. 전체 범위에 대해 다른 숫자가 존재하는지 판단하고, 있으면 더 잘게 나누고 없으면 지금 숫자를 해당 배열에 더해..

문제 설명 1. N이 주어진다. 2. NxN배열에 해당하는 숫자들이 주어지고, 1은검은색, 0은흰색이다. 3. 주어진 배열을 왼위/오위/왼아/오아 이렇게 4부분으로나누어 다1이면 1, 다0이면 0을 받는다. 4. 만약 전체가 1또는 0이 아닌 경우 또 4부분으로 나누어 풀이한다. 5. 저 크게 나누면 괄호로 표시해 준다. 그렇게 구한 답을 return하면 된다. 풀이 과정 1. 분할 정복 문제이다. 2. 값들을 더 작은 수로 나누고, 그곳에서부터 조합해 맞추어 나가면 된다. 3. 전체 크기에 대해 모두 같은 영역으로 이루어졌는지 판단하고, 맞으면 그 숫자를 더해주며 아닌 경우 다시 분할해 주면 된다. 4. 예를 들어 모두 1인 경우 - 그냥 답에 1 더하기 중간에 다른 답이 있는 경우 - 괄호를 펼쳐주고..

문제 설명 1. N이 주어진다. 2. 수가 오름차순이어야 한다(현재 자리수의 전에 지금보다 '큰'숫자가 와서는 안된다. 3. 설명할게 더 없다. 풀이 과정 1. DP로 문제를 풀었다( bottom-up으로 풀었음) 2. 이전에 풀었던 쉬운 계단 수 를 보고 생각해보면 거의 비슷한 문제이고, 굉장히 쉽게 풀 수 있을 것이다. 3. 요점은 이전까지의 모든 숫자에 현재 숫자를 더하면 된다는 것이다. 4. 예를 들어 3개 자리수의 4라는 숫자가 있으면 앞에서 (3으로 끝나는 2개 자리수 숫자 전체 수) + (2로 끝나는 2개 자리수 숫자 전체 수) ... 이렇게 하면 된다. 5. 솔직히 더 설명할게 없다... 이제 슬슬 더 어려운 내용들을 풀어야 하는데, 난이도가 높아지니 문제 풀이가 조금 힘들어지는 것다. 코..

문제 설명 1. 터렛1의 좌표 x,y와 마린의 거리r 터렛2의 좌표 xy와 마린의 거리 r 이게 순서대로 주어진다. 2. 마린이 있을 수 있는 위치를 구하면 된다. 3. 있을 수 있는 좌표가 많은 경우 -1을 return하면 된다. 풀이 과정 1. 이건 그냥 수학문제인데 엄청 간단하다. 2. 터렛1, 2에서 마린까지의 거리에 대해 원이 그려질 것이다. ex) (0, 0)위치에서 마린까지 거리가 2이면 반지름 1짜리 원이 그려지겠지 3. 터렛 1, 2와 거리로 그려지는 원에 대해 - 무한한 좌표가 나오려면 둘이 완전히 같은 원이면 된다. - 아예 겹치지 않는 경우는 반지름의 차이가 거리보다 크거나, 거리의 합이 반지름의 합보다 크거나이다. - 좌표가 1개밖에 없는 경우는 반지름의 차이가 거리의 차이랑 같거..

문제 설명 1. 2x1, 1x2, 2x2 세가지 타일로 2xn의 타일을 채워야 한다. 2. 채우는 모든 방법을 구하면 됨. 3. 설명할게 더 없다. 풀이 과정 1. DP로 문제를 풀었다( bottom-up으로 풀었음) 2. 2x1을 채우는 방법은 1개, 2x2를 채우는 방법은 3개이다(11, 二, ㅁ) 3. 2x3을 채우려면 2x2타일 뒤에 1짜리 하나를 두는 방법과 2x1타일 뒤에 (ㅁ, 二) 이 오는 두 가지이다. 주의) 여기서 1 이 모양이 왜 못오냐면 앞의 경우와 무조건 겹칠 수밖에 없다. 예를들어 - 111, 二1, ㅁ1 이 모든 경우를 2x2타일을 구할 때에 사용한다. 2x2타일을 채울 때에 1을 마지막에 썼기 때문에 모든 경우의 수를 사용한 것이다. 4. 즉 dp[i] = dp[i-1](앞의..

문제 설명 1. 계단 수란, 인접한 수의 차이가 1인 수이다. - 맨 앞이 0이되면 안됨. 2. 자릿수가 1이면 1,2,3,4,5,6,7,8,9 / 자릿수가 2이면 10,21,12,32,23,43,34,54,45,65,56,76,67,87,78,98,89 ..... 3. 정답을 1000000000으로 나눈 나머지를 출력하면 된다. 풀이 과정 1. DP로 문제를 풀었다( bottom-up으로 풀었음) 2. 저기 문제 설명에서 자리수가 2이면에서 적어놓은 숫자들을 보면 왜 저렇게 적어 놓았는지 알 수 있을 것이다. 3. 뒷자리 숫자가 0,1,2,3,4,5,6,7,8,9 이 순서대로 가면서 진행되고, 앞의 숫자들에서 법칙이 보일 것이다. 4. 맨뒷자리 앞자리 0 1 1 0, 1 2 1, 3 ..... 호롤로 ..

문제 설명 1. N개의 숫자를 입력받는다. 2. 숫자들의 합을 구해서 최소숫자를 return하면 된다. 3. 최소 1000 최대 1000까지 간다. 풀이 과정 1. DP를 통해 쉽게 구할 수 있다. 2. 계속 숫자가 커지도록 만들기만 하면 부분합들을 구할 수 있다. 3. DP배열에 현재 숫자를 더했을 때 만들어지는 최대 합을 구하면 된다. 그 방법은 이전 숫자가 양수이면 그곳에 지금수를 더하고, 음수면 0에다가 더하면 된다. ex) 2, 3, -6, 3, -2, 4가 주어지는 경우의 합은 -> 2, (2+3), (2+3-6), 3, (3-2), (3-2+4) 앞의 숫자가 0보다 작으면 없애고 그보다 크면 쓰면 된다. 4. 구해진 합들 중 최대값을 return하면 된다. 코드 mport java.util...

문제 설명 1. 음이 아닌 정수 N개가 들어있는 리스트가 주어진다. 2. 이걸로 만들 수 있는 가장 큰 수를 return한다. 3. 답이 0이면 무조건 0하나만 출력되어야 한다. 0이 아닌 모든 수는 0으로 시작하지 않는다. 풀이 과정 1. 진짜 쉽게보고 풀었는데 생각보다 난이도가 있었다.. 또 다 풀어놓고 뻘짓해서 시간 엄청 보냈다. 문제의 내용을 잘 읽어봐야 할 것이다. 2. 먼저 입력은 String으로 입력받는다. 이걸 사용하면 더 쉽게 풀 수 있다. 3. 입력받은 String들을 배열로 만들고 내림차순으로 정렬한다. 45,4,44,43,42,41 그런데 위의 3까지만 진행하면 이렇게 정렬될 것이다. -> 45,44,43,42,41,4 이걸 해결하는 방법을 생각해 보았는데, '4'라는 자리수로 시작..