Hello backEnd

문제 설명 1. 연주할 곡 N, 시작 볼륨 S, 최대 볼륨 M이 주어진다. 2. N개의 변경할 볼륨의 크기가 주어진다. 3. 모든 곡의 볼륨은 최대 볼륨 M을 넘어서는 안된다. 4. 마지막 곡에 연주 가능한 최대 볼륨을 구하면 된다. 풀이 과정 1. DP를 사용하는 문제이고, 적용 시점을 잘 고민해 봐야 한다. 2. 먼저 DP의 범위를 볼륨 M으로 설정하고, DP[A]의 값은 그 연주 시점으로 설정한다. 3. 예를 들어, 2번째 곡이 4, 8의 볼륨으로 연주 가능하면 DP[4] = 2, DP[8] = 2 이런 식이다. 4. 처음에 DP[S] = 0으로 설정하여 시작 볼륨을 구한다. 5. 다음 볼륨을 구하려면 현재 시점의 곡 순서에서 이전 시점에 불린 곡(DP[X]=현재시점-1 의 X값) 의 정보를 통해 ..

문제 설명 1. S가 주어진다. 1개의 이모티콘을 갖고 있다. 2. 1초마다 전체복사/붙여넣기/지우기 중 하나를 할 수 있다. 3. 1개의 이모티콘 -> S개의 이모티콘 을 만드는 최소의 연산을 구하면 된다. 풀이 과정 1. BFS를 생각하고 풀었는데, BFS적용 자체는 간단하지만 시간복잡도에서 터지지 않게 하는 것이 복잡했다. 2. BFS풀이법 - Queue를 구현한다. Queue는 ( 현재이모티콘수, 복사한이모티콘수, 걸린시간 ) 세 개의 구성을 갖는 class를 갖는다. - 시작은 1, 0, 0이다. ( 처음이모티콘 1개, 복사x, 0초) - 1초마다 걸리는 연산은 복사하기, 붙여넣기, 지우기이다. - 복사하기 : Queue에 ( 현재이모티콘수, 현재이모티콘수, 걸린시간+1 ) 을 해주면 된다. -..

문제 설명 1. N x N행렬이 주어진다. 2. 숫자들이 주어진다. 3. N번째에 해당하는 숫자를 구하면 된다. 풀이 과정 1. 이거 우선순위 큐를 이용해서 풀었는데, 내가 볼 때에는 문제의 조건 중 하나인 '아래 줄이 윗 줄의 숫자보다 크다'를 이용하려면 우선순위 큐를 두 번 사용하는게 좋을 것 같기는 하다. 2. 그런데 왜인지는 모르겠지만 그걸 쓰지 않고도 해결이 되었다(시간복잡도에서 손해를 많이 보는데도 통과된게 이상한 느낌) 3. 먼저 우선순위 큐를 사용하면 오름차순으로 정리되는데, 우선순위 큐에 큰 순서대로 N개를 저장해서 갱신해주면 맨 위가 해당 답이 될 것이다. 4. 그렇다면 총 N개가 N번 들어오기 때문에 처음에 N번 받을 때는 우선순위 큐에 모든 숫자를 받아준다. 5. 다음부터는 숫자를 ..

문제 설명 1. 세로 두줄, 가로 N칸짜리 표가 주어진다. 2. N에 해당하는숫자들이 주어진다. 3. 0번Line숫자 -> 1번Line숫자 ->0번Line숫자 로 돌아오는 숫자들을 오름차순으로 출력한다. 풀이 과정 1. DFS와 Prority Queue를 이용하여 풀이한다. 2. 문제의 주요 골자는 map에 각 숫자를 적어두고 map[i]와 map[map[i]] 이런 식으로 함수를 쭉쭉 돌리면서 자기 자신의 숫자가 나타나면 되는 것이다. 1 2 3 4 5 3 5 1 5 1 map[1] = 3, map[map[1]] = 3 3. DFS에서 값들을 체크하면서 i -> map[i] -> map[map[i]] -> map[map[map[i]]] ..... 이렇게 도달하지 않은 곳까지 체크한다. 4. 자기 자신이..

문제 설명 1. A, B, C가 주어진다. 2. A를 B만큼 곱하고 이를 C로 나누는 문제이다. 풀이 과정 1. 당연히 그냥 구하면 터진다. 2. 이걸 생각하면 쉽다. A^16 = (((A^2)^2)^2)^2 A^17 = A*(((A^2)^2)^2)^2 3. long형 함수에 B번 반복하기 위해 B를 인자로 넣고 재귀함수를 돌린다. 4. 그 다음 재귀에서 구해진 값을 재곱하고 C로 나누는 것을 반복하면 된다. 5. 그리고 인자가 홀수가 되면 그냥 A를 곱해주면 되는데, 이 이유는 홀수 인자를 갖는 경우는 재귀함수가 인자 1을 가질때까지 반복되거나, 시작할 때 홀수인 경우 두 개 밖에 없기 때문이다. 6. 조금만 생각하면 쉽게 구현할 수 있는 문제이지만, 아이디어를 구현하는것에서 문제가 생기면 오래 걸릴 ..

문제 설명 1. N, M크기의 체스판이 주어진다. 2. 8x8크기로 잘라서 위아래양옆으로 다른 색깔이 와야 한다. 3. 최소한으로 체스판을 칠하려면 어떻게 해야 하는지 구하면 된다. 풀이 과정 1. 간단한 브루트포스 문제이다. 2. 먼저 체스판의 색은 두 개이기 때문에 브루트포스를 진행하기 앞서 bit로 처리하기 위해 boolean값으로 바꾸어 준다. 물론 그냥 시간복잡도를 줄이기 위함으로 굳이 바꾸지 않아도 된다. 3. 전체 크기를 0,0위치를 기준으로 오른쪽, 아래 8칸씩 짤라서 진행한다. 체스판의 최대 X축의 길이가 N이라고 하면 N-8까지 잘라서 구하면 된다. 4. 여기서 나는 조금 새로운 방법으로 문제를 해결했다. -> 자르는 기준이 된 체스판의 기준으로 상하좌우는 그것과 달라야 한다. -> (..

문제 설명 1. 책의 개수와 팔린 책들이 주어진다. 2. 하루 동안 팔린 책들 중 가장 많이 팔린 책을 return하면 된다. 3. 같은 숫자가 팔렸으면 사전순으로 먼저 오는 것이 오늘의 베스트셀러이다. 풀이 과정 1. 해쉬맵과 트리셋을 이용했다. 2. 해쉬맵의 getOrDefault 메소드를 이용하여 해당하는 Key(책이름)의 Value(팔린개수)를 구해주었다. 3. 이후 해쉬맵을 Value기준으로 정렬하여 가장 많이 팔린 순서대로 배치했다. 4. 그 해쉬맵의 최대 개수 Value를 갖는 Key들을 순서대로 가져와서 TreeSet에 저장하면 가장 사전의 앞에 해당하는 값을 구할 수 있다. 코드

문제 설명 1. 12줄 - 6칸짜리 보드가 있다. 2. .과 각각의 색깔로 구분되는 뿌요가 주어진다. 3. 뿌요가 상하좌우로 같은 색의 뿌요가 있으면 터진다. 중요한 점은 여러 뿌요들이 터져야 하는 경우 동시에 터지고, 1연쇄가 늘어난다. 4. 아래 뿌요가 터지면 위의 뿌요가 내려온다. 이렇게 전체 뿌요를 구하면 된다. 풀이 과정 1. 오늘 진행된 데브매칭 3번문제와 거의 유사한 문제이다... 해당 문제는 진짜 거의 다 풀었는데 시간이 넘어서 못풀었다. 그래서 아쉬워서 이 문제라도 풀었다... 2. BFS를 사용하고, 이전에 풀었던 2048(easy)에서의 정렬 방식을 참고하면 간단히 구현할 수 있다. 3. 간단하게 코드에 대해 설명하자면 - 하나씩 char로 하면 귀찮으니까 01 2 3 4 ... 이렇..

문제 설명 1. N개의 크기가 정해진 보드가 주어진다. 2. 보드에 2~ 1024의 크기 내의 숫자들이 주어진다. 3. 숫자들은 위로, 아래로, 왼쪽으로, 오른쪽으로 딱 붙여서 정리할 수 있으며, 위로 이동하는 경우 이전의 숫자와 이후의 숫자가 같으면 두 숫자는 합쳐진다( 8에 8이 이동하면 16하나가 되는 느낌이다.) 4. 5번의 이동이 있은 후 가능한 최대 숫자를 return하면 된다. 풀이 과정 1. 엄청나게 코드를 더럽게 풀었다. 모든 경우를 하나하나 만들었음... 2. 재귀함수 문제이다. 적절한 범위를 지정해 주면 된다. 3. 간단하게 코드에 대해 설명하자면 - 위, 아래, 오른, 왼 코드를 하나씩 만들어서 모든 경우를 탐색한다 (위 - 위 - 위 - 위 - 위), (위, 위, 위, 위, 아래)..

문제 설명 1. 8*8 크기 배열이 주어진다. 2. '.'은 말이 없는 상태, 'F'은 말이 놓여진 상태이다. 3. 흰색 말은 0,0 0,2 0,4 ...이런식으로 주어질 때 흰색 말의 개수를 return하면 된다. 풀이 과정 1. 간단한 문제인데, 더 쉽게 풀 수 있다. 배열도 필요없다. 2. 0,0 0,2 0,4 0,6 1,1 1,3 1,5 .... 이렇게 주어지는거면 흰색 말은 x축 y축의 합이 짝수인 곳마다 주어진다. 3. 배열을 받으면서 그 배열이 짝수가 되는 곳의 말을 판별하면 된다. 코드 알고리즘 풀이의 비중을 낮추고 자바 웹 개발 기초를 더 공부하기로 했음..이번주는 백신을 맞아서 조금 쉬어가기로 했다.