Hello backEnd

문제 설명 1. NxM크기의 격자판이 주어진다. 2. 상하좌우로 움직일 수 있으며, 각 방의 이동은 최단 경로로 움직인다. 3. 이렇게 최단 경로로 움직여서 가장 먼 거리를 움직이면, 그 시작점과 도착점이 비밀번호가 된다. 4. 가장 먼 거리가 여러개면 그 중 시작점과 도착점의 합이 큰 것이 비밀번호가 된다. 풀이 과정 1. 최단 경로 -> BFS 그냥 공식처럼 외워서 진행하자. 2. 우리는 어디서부터 시작하는게 최고로 가까울지 모른다. 그러므로 모든 점에 대해 그곳부터 시작하는 경우를 싹 다 구해야 할 것이다. 이 말은 완전탐색 + BFS로 진행해야 한다는 것이다. 3. BFS를 통해 나아가면서, 해당 위치가 마지막인지 어떤지 모르므로 매번 거리를 재서 진행하는것이 속편할 것이다. 이는 BFS여서 쉽게..

문제 설명 1. N권의 책, 한번에 들수있는 양 M이 주어진다. 2. 현재 위치 0으로부터 해당 책이 들어가야하는 위치가 N개 주어진다. 3. 모든 책을 원래 위치에 가져다 놓는 최소 거리를 구하라. 4. 마지막 책을 가져다가 두면 더이상 0위치로 돌아올 필요는 없다. 풀이 과정 1. 그리디 문제이고, 문제 풀이를 떠올리는것은 힘들지만 구현은 쉬운 문제이다. 2. 중요한 것은 거리가 +, - 두 가지로 주어진다는 것이고, 0의 위치를 지나가기 때문에 각각의 이동이 따로따로 행해져야 한다는 것이다. 3. 그리고 어느 쪽이든 가장 먼곳까지 갔다가 돌아오면 된다. 4. 마지막 책을 갖다 놓았을 때 더이상 0의 위치로 돌아올 필요는 없으니, 가장 먼곳에 마지막으로 책을 가져다 두면 될것이다. 5. (2)번의 문..

문제 설명 1. N명의 스태프, 만들어야 하는 풍선M이 주어진다. 2. 각 N명의 스태프가 1개의 풍선을 부는 데 들어가는 시간이 주어진다. 3. M개의 풍선을 만드는 최소시간을 구하라 풀이 과정 1. 이분탐색이다. 2. 이분탐색 -> Long타입에 주의하자...허헣 풀이방법 자체는 이전하고 별반 차이는 없다. - 몇 분의 시간이 주어지고, 해당 시간동안 몇개의 풍선을 불 수 있는지 구하면 된다. 3. 왼쪽 -> 0으로 시작하면 된다. 4. 오른쪽 -> 풍선 부는데 제일 오래걸린 시간 * 풍선 개수면 일단 가장 오래걸리는 시간이 구해진다. 5. 만약 3, 5, 6분마다 한개씩 풍선을 만든다고 가정하면 7분이 주어지면 각각 2, 1, 1개를 만들것이다. 6. 현재 시간에 분 최대 풍선개수가 원하는 개수보다..

문제 설명 1. 인원수 N, 보석의 색깔수 M이 주어진다. 2. M가지 색에 대해 각각의 개수가 주어진다. 3. 이 M개의 보석을 N명의 학생에게 나누어 줄 때, 모든 인원에게 나누어 줄 수 있는 최소 보석 개수를 구해주면 될것이다. 풀이 과정 1. 이분탐색이 어려워서 공부하기 위해 하나 더 풀어보았다. 이전문제에서 공부했어서 풀이 자체는 금방 도출했는데... 이번에는 뭔가 구현이 어려웠다. 더 풀어봐야 할 것 같다. 2. 중요한 값들에 대해 이야기하자면 A. 주어지는 보석개수의 차이가 아니라 개수 자체에 관한 문제라는것 -> 그냥 보석을 N명에게 모두 나누어 줄 수 있는 최소개수를 가지면 된다. B. 아예 보석을 못받는 학생이 있어도 괜찮다는것 -> 학생수보다 주는보석방법의 개수가 작거나 같으면 싹다 ..

문제 설명 1. 강의의 수 N, 블루레이 녹화 개수 M이 주어진다. 2. N에 맞추어 강의가 하나씩 주어진다. 3. N개의 강의를 M개로 나누어 저장할 수 있는 가장 최소의 분단위를 구하면 된다. 풀이 과정 1. 이분 탐색 문제이다. 실버1 난이도인데 나는 왜이리 이분탐색이 어려운지 모르겠다... 2. 중요한 값들에 대해 이야기하자면 A. N개의 강의를 M개로 나누어 담는다는것 -> 한 개의 블루레이의 크기를 늘리고 줄이며 담을 수 있는 강의를 만들어가면 될것. B. 블루레이는 모두 같은 크기를 갖고, 최소의 크기로 만들어야 한다는것 -> 이분탐색을 M개의 값을 갖자마자 나가지 말고 그 최소를 구할것 이다. 3. 먼저 M은 N보다 작거나 같으므로 최소 블루레이 크기는 최대 길이 강의로부터 시작할 것이다...

문제 설명 1. 미로의 크기 R, C가 주어진다. 2. 불이 나고, 지훈이가 미로안에 있다(지훈이는 한명) 3. 불과 지훈이가 상하좌우로 움직일수 있고 지훈이는 불과 벽을 뛰어넘지 못한다. 4. 지훈이가 미로를 탈출(가장자리 도착)하는 가장 짧은 방법을 구하라. 풀이 과정 1. BFS에 약간의 구현을 더해서 진행하는 문제이다. 2. 먼저 둘이 동시에 이동한다 가정해보면 코드상에서는 지훈이의 이동보다 불의 이동이 먼저 일어나야 하는데, - 코드에서 지훈이가 불보다 먼저 움직이면 이후에 타죽는다. - 불이붙은 지역에 지훈이는 갈 수 없다. 그러므로 지훈이를 불보다 늦게 움직이도록 생각한다. 3. 지훈이는 미로의 가장자리에 있으면 탈출 가능하다. 즉 처음부터 가장자리에 있으면 그냥 탈출하면 된다. 4. 지훈이..

문제 설명 1. 좌석의 개수가 주어진다. 2. 각 좌석은 자신의 양옆으로 이동 가능하며, VIP는 이동이 불가능하다. 3. VIP의 위치가 주어질 때 가능한 좌석의 전체 방법 수를 구하여라 풀이 과정 1. DP를 통해서 풀 수 있다. 2. 좌석을 한 칸씩 늘려가며 방법을 구해주면 점화식을 세울 수 있다. 먼저 VIP석이 아예 없는 경우를 예를 들어 1칸 -> 1개 2칸 -> (1 2) (2 1) 2개 3칸 -> (1 2 3) (1 3 2) (2 1 3) 3개 4칸 -> (1 2 3 4) (1 3 2 4) (2 1 3 4) / (1 2 4 3) (2 1 4 3) 5개 .... 이렇게 된다. 4번째 칸을 기준으로 구할 때에는 -> 3칸을 구하는 방법 뒤에 4번째 위치 / 3으로 끝나는 좌석을 4와 위치를 바..

문제 설명 1. 2xn크기의 우리를 갖는 동물원이 있다. 2. 사자를 넣는데, 사자의 양옆위아래에는 다른 사자가 있으면 안된다. 3. 모든 사자를 배열하는 방법을 찾는다. 사자의 수는 제한이 없고 아무도 없는 경우도 방법으로 친다. 풀이 과정 1. DP를 통해서 풀 수 있다. 2. 나는 DP의 경우 한번 n이 3이나 4가 될 때 까지는 무작정 경우의 수를 구하는 것이 쉽게 풀 수 있는 방법이라 생각한다. 그래서 그냥 방법을 구해 보았다. 우리 집에 있는 무서운 사자를 우리에 넣어보도록 하겠다. 먼저 2x1의 크기 우리에 사자가 배열되는 경우는 다음 세 가지에 해당한다. 그럼 다음으로 2x2의 우리에 사자를 넣는 경우는 어떻게 될까? 먼저 가장 왼쪽 ox의 경우(o는 사자, x는 빈칸) 이렇게 다음 우리가..

문제 설명 1. 센서의 개수 N, 집중국의 개수 K가 주어진다. 2. N개의 센서에 대해 집중국을 세워야 한다. 3. 문제가 이해가지 않아 한참을 해맸다... 문제에서 구해야 하는 내용에 대해 말하자면 - 직선 상에 센서들이 좌표를 갖고 주어진다. [2, 8, 10, 12, 13, 4] 요렇게 센서들이 주어지고, 만약 3개의 집중국을 세워야 한다고 해 보자 센서를 정렬하면 이렇게 될 것이고, 이 중 3개의 집중국이 커버 하도록 한다면 이런 식으로 나타낼 수 있다. -> [2, 2, 1]의 범위를 커버한다. 풀이 과정 1. 위의 내용을 기준으로 한번 생각을 해보면 센서들을 정렬한 후, 그 거리의 차를 구해주면 각각 센서들의 거리의 차를 구할 수 있다. 2. 그렇다면 집중국이 커버해야 하는 최소의 거리를 구..

문제 설명 1. 테스트 케이스가 T번 주어진다. 해당 테스트 케이스들에 우선 순위 큐에 시도학 연산 N번이 주어진다. 2. I는 입력, D는 삭제이고 D에서 -1이면 최소값, 1은 최대값을 삭제한다. D시도 시 큐가 비어있으면 연산하지 않는다. 3. 각 테스트 케이스마다 최대값과 최소값을 구하면 된다. 참고로 큐가 비어있으면 EMPTY를 출력한다. 풀이 과정 1. 문제가 우선순위 큐이기 때문에 가장 간단히 구현할 수 있는 우선순위 큐를 사용하면 시간 초과가 난다....??? 2. 문제의 난이도 자체는 별로 어려울 것이 없다. 분기를 여러 번 하면 된다. D일때 -> 비어있으면 continue, 아니면 1과 -1에 따라 삭제하기 I면 그냥 add하기 3. 그렇지만 우선순위 큐로는 구하려 하면 에러가 나기 ..