Hello backEnd

문제 설명 1. NxN크기의 땅이 있다. 2. 인구 이동은 인접 국가와의 인구 차이가 최소보다 많아야 하고, 최대보다 적어야 한다. 3. 인구 이동은 인접 국가들의 인구의 평균으로 된다. 풀이 과정 1. BFS를 사용하여 해결 가능하다. 2. 총 3가지 process를 구현해주면 된다. (1) 맨 위 테두리(0, 0) 바꾸면서 그 변경할 수를 세준다. (3) 전체 판을 탐색하며 더이상 녹을 치즈가 있을지 확인해주기. 3. 이걸 처음부터 실시하면 테두리의 치즈를 체크한다 -> 체크된 치즈가 녹는다(녹은 치즈수 세기) -> 확인후 더 치즈가 있으면 다시 처음부터 -> 더 녹을 치즈가 없으면 녹은 치즈 수를 return하기 위의 process를 할 때마다 날짜를 더해주면 최대날짜 구하기 가능. 코드

문제 설명 1. NxN크기의 땅이 있다. 2. 인구 이동은 인접 국가와의 인구 차이가 최소보다 많아야 하고, 최대보다 적어야 한다. 3. 인구 이동은 인접 국가들의 인구의 평균으로 된다. 풀이 과정 1. BFS와 몇 가지 구현을 통해 해결 가능하다. 2. 먼저 모든 국가의 인원에 대해 검색을 진행해 준다. 3. 현재 국가에 대해 인접 국가가 있으면, 그 국가들을 통해 BFS를 진행한다. 추가로, 현재 국가와 인접한 국가들 모두의 정보를 새로운 Queue united에 저장해 준다. 4. BFS가 완료되면 이 BFS를 시행한 나라 기준으로 모든 인접 국가들이 united에 저장되었을 것이다. 그렇다면 이 united에 연합국이 존재하는 경우 그 국가들에 평균값을 저장시켜 준다. 예를 들어 크기가 4, 최대..

문제 설명 1. 현재 채널은 100에 있다. 2. 도착하고 싶은 채널과, 고장난 숫자들이 주어진다. 3. 위, 아래, 고장나지 않은 숫자들을 이용해 현재 위치에서 원하는 채널로 갈 때에 필요한 클릭 수를 구하면 된다. 풀이 과정 1. 완전탐색을 통해 해결 가능하다. 2. 현재 고장난 버튼들을 모두 기억한다. 3. 도착하고 싶은 채널의 최대숫자는 500000이기 때문에, 0~1000000까지의 모든 채널로부터 해당 채널에 도착하는 경우를 구한다. 4. 그리고 그 0~1000000의 채널에 대해 그 채널로 이동할 수 있는 경우(고장난 숫자가 없음)는 이동 후 +나 -를 통해 이동하면 된다.(차이의 절대값) 예를 들어 도착하고 싶은 채널이 1517, 고장난 숫자가 1, 4, 6로 주어진 경우 0번 채널 -> ..

문제 설명 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 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 ) 을 해주면 된다. -..