Hello backEnd

문제 설명 1. NxN크기의 거리와 그 드는 힘에 대한 숫자, 연산자가 주어진다. 2. 집(0, 0) 과 도착점(N-1, N-1)은 숫자로 주어진다. 3. 집에서 도착점까지 가는 최대, 최소의 숫자를 구하면 된다. 풀이 과정 1. DFS문제이고, 다이나믹 프로그래밍은 사용하지 않았다. 2. 다만, 현재 위치에서 다시 위로 돌아가는 경우는 일어나지 않으며, 오른쪽/아래 로 가는 경우밖에 없다. 따라서 check할 필요는 없다. 3. 간단하게 말하자면 0, 0은 무조건 숫자이기 때문에, x+y가 짝수이면 그 위치는 숫자이다. 4. 현재 위치가 숫자임 -> 이전은 연산자이기 때문에 그 이전의 연산자를 통해 현재기준 2번째 전의 숫자에 연산한 숫자를 구해주면 된다 현재 위치가 연산자임 -> 이전은 숫자이고, 그..

문제 설명 1. NxM크기의 기존 세포와 백신 이후 세포가 있다. 2. 백신을 투여하면 그 위치에서 상하좌우가 다른 색으로 변경된다. 3. 변경되는색은 랜덤이며, 기존에 있는 색으로 변경될 수도 있다. 4. 이게 제대로 백신을 투여한게 맞는지 구하면 된다. 풀이 과정 1. DFS문제이고, compare를 통해 구하면 쉽게 알 수 있다. 2. 백신은 한 장소에만 맞기 때문에, 두 가지 map을 기존/이후 둘로 나눠서 둘이 다른 부분을 구한다. 3. 둘이 다르면 그 위치는 뭔가 변형이 일어났다는 것이므로 그곳을 기준으로 DFS를 진행한다. 4. 그 위치를 기준으로 상하좌우를 검색하여 본래 해당 위치 색과 동일한 색이라면 기존 세포와 연결된 곳이므로 백신이후 색으로 변경해 준다. 5. 모든 위치를 탐색한 후,..

문제 설명 1. N개의 도시, M개의 버스가 있다. 2. M개의 버스에 대해 출발도시, 도착도시, 가는데 필요한 비용이 각각 주어진다. 3. 시작도시 A에서 도착도시 B로 가는 최소비용을 구하면 된다. 풀이 과정 1. 다익스트라 문제이다. 다익스트라는 개념을 알고 있어도 생각보다 적용하는 데에 힘이 들기 때문에 주석으로 자세히 설명해 놓도록 하겠다. 2. 기본적인 개념에 대해 설명하자면, 한 도시를 기준으로 출발하여 다음 도시에 도달하는 모든 방법을 한꺼번에 처리하고, 그 처리 도중 저렴한 방법을 계속 업데이트하여 진행하는 것이다. 3. 주석을 통해 설명하도록 하겠다... 코드

문제 설명 1. N x M 크기의 맵이 나타난다. [ 0은 이동가능 ] [ 1은 이동불가 ] 이다. 2. 근데 벽을 한번은 부수고 이동할 수 있다. 3. 0, 0 -> N-1, M-1 로 가는 최소거리를 구해라~ 풀이 과정 1. 최소거리 -> BFS를 이용하고 벽을 부수는 것은 class내에 벽을 부술 수 있는 값을 주면 된다. 2. 최소 거리를 구하는 경우 BFS를 사용하고 간 길을 check해 주면, 뒤에 도달하는 경우 무조건 현재상황보다 늦게 도달하거나, 동시에 도달함으로 check해 준 길을 다시 오지 않게 해 주면 된다. 3. 그런데 만약에 한번 벽을 부수어서 그냥 오는 것보다 빠르게 해당 route에 도달했는데, 목적지에 도달하려면 목적지 앞의 벽을 부숴야 하는 경우가 생긴다면 곤란할 것이다...

문제 설명 1. 동굴의 길이 N, 높이 H미터가 주어진다. 2. 동굴의 길이에 맞춰 장애물이 석순 / 종유석 이렇게 번갈아가며 주어진다. 3. 개똥벌레는 그 장애물을 그냥 뿌수고 지나간다. 4. 개똥벌레가 부수는 최소의 장애물 개수와 그 경우가 몇 개인지 구하면 된다. 풀이 과정 1. 이분 탐색 문제라는데...내가 푼게 이분 탐색이 맞나? 그냥 구현 + DP로 푼 느낌이다. 누적합 2. 먼저 배열을 하나 만들어서 장애물의 높이에 따른 개수를 가져간다. 예를 들어 2가 입력되면 arr[2]++ 이런식으로. 3. 그리고 석순 / 종유석 이렇게 번갈아가면서 주어지기 때문에 두 개의 배열은 각각 다르게 설정하고, 번갈아가면서 하나씩 넣어준다. 4. 입력받은 장애물을 표현하자면 1 5 3 3 5 1 이렇게 주어지..

문제 설명 1.2^N x 2^N 크기 배열에 대해 배열의 N, x축 r, y축 c가 주어진다. 2. Z모양으로 0, 1, 2, 3 ... 이렇게 숫자가 하나씩 늘어나며 들어간다. 3. r,c위치에 존재하는 숫자를 구하면 된다. 풀이 과정 1. 가장 전형적인 분할 정복 문제이다. 2. r, c의 위치를 생각할 때에 전체 배열을 4가지 범위로 나누어 찾으면서 구해나간다. ex 초록색으로 존재하는 위치의 값을 찾으려 한다고 생각해 보자 전체 크기를 기준으로 4개의 frame으로 나누어서 현재 frame은 4번째에 해당한다. 그렇다면 현재 위치 이전의 모든 frame에 해당하는 숫자들을 더한 숫자로부터 시작하면 된다. 파란영역 크기 전체 + 빨간영역 크기 전체 + 노란영역 크기 전체 -> 초록색 영역이 존재하는..

문제 설명 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. 핼렬의 크기, 회전할 영역이 주어진다. 2. 그 영역을 회전시키고, 회전한 값들 중 가장 작은 값을 저장한다. 3. 출력하면 된다. 풀이 과정 1. 간단한 구현 문제이다. 2. 하나씩 이동하면 된다. 3. 현재 위치의 값을 locNum로 저장한다. locNum값을 temp에 저장한다. 이후 다음 위치로 이동한다. 4. 현재 위치의 값을 locNum에 저장한다. 현재 위치에 temp값을 저장한다. 이후 다음 위치로 이동한다. 5. 위의 3, 4로직을 시작부터 끝까지 프레임에 맞추어 진행하면 된다. 6. 실제 코드를 보면 쉽게 이해 가능하다. 코드