Hello backEnd

문제 설명 1. N개의 강의가 주어진다. 2. 강의의 시작시간/끝시간이 주어진다. 3. 강의는 서로 겹치면 안되고, 모든 강의를 성공적으로 할 수 있는 최소 강의실 수를 return하면 된다. 풀이 과정 1. 우선순위 큐, 그리디와 관련된 문제이다. 2. 가장 빨리 끝나는 강의의 끝시간보다 그 다음에 가장 빨리 끝나는 과목의 시작 시간이 더 이르면 강의실을 하나씩 늘려주면 된다. 3. 딱히 설명할 내용이 없다.... 주석으로 적어둠 코드

문제 설명 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개의 도시, 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에 해당하는 숫자들을 더한 숫자로부터 시작하면 된다. 파란영역 크기 전체 + 빨간영역 크기 전체 + 노란영역 크기 전체 -> 초록색 영역이 존재하는..