이분탐색 ❗️
오늘은 이분탐색 알고리즘을 사용하여 level3문제를 생각보다? 빠르게 풀었다.
1시간 조금 덜 걸렸던 거 같다. 흠 ,, 제대로 이해하고 풀었는지 점검도하고 필자의 풀이하는 과정도 공유하고 싶어서 이렇게 글을 작성한다 !
오늘은 총 2문제를 업로드할 예정이다. 복습 개념으로 조금 후에 2문제를 더 풀건덴 그 문제들은 이미 풀었던 문제들이니 업로드 하지 않을 거 같다!
오늘의 문제는 다음과 같다 !
입국심사 ❓
필자는 먼제 제한사항에 눈이 갔다. 10억;; 인풋은 10억이다;;
근데 알고보니 인풋은 10억 * 10억이다. 왜냐면 심사관이 1명당 심사하는 시간은 최대 10억분 심사를 기다리는 사람은 최대 10억명
그렇다면 이 큰 인풋을 어떻게 획기적으로 줄일 수 있을까. 이분탐색 !!
먼저 다음과 같이 생각했다. 결국 return 해야하는 건 심사를 받는데 걸리는 시간의 최솟값
그렇다면 answer은 시간이 될거고 시간의 범위는 정해져있다. 그럼 시간을 범위 안에서 나눠가면서 최소가 되는 그 시간을 찾으면 되겠네??
만약 [7,10]이 걸리는 검사관이 있고 n = 6 이라면 (즉 검사받는 인원은 6명) 직관적으로 생각해보면 28분이 되면 4명 2명이 끝나서 딱 최소의 시간이 걸린다. 그럼 코딩으로는 어떻게 표현할 수 있을까
범위는 ?? 1~1000000000
그럼 시간을 절반씩 줄이면서 원하는 시간을 찾아보자
let left=1
let right = 1000000000
while(){
const mid = Math.floor((left+right)/2))
그럼 이 mid를 판단해서 left와 right의 값을 조절하며 원하는 시간을 찾으면된다 !
}
먼저 mid는 어떤 기준이어야할까
문제에서는 times라는 감독관 별 1사람을 처리하는 시간에 대한 정보가 주어진다.
예를들어 [7,12]가 times라면 7분이 걸리는 감독관 1명과 12분이 걸리는 감독관 1명이 있는 것이다.
그럼 1400분이면 ?? 1400/7 => 200명 , 1400/12 => 약 116명
총 316명이 된다.
그럼 다음과 같이 표현할 수 있지 않을까
let passedPerson =0
for(let i = 0 ; i < times.length; i++){
passedPerson = passedPerson+Math.floor(mid/times[i])
if(passedPerson>n){
//>=로 하지 않는 이유는
//그래야 가장 최소의 값을 찾을 수 있기 때문
return false
}
return true위 판단을 활용해 left와 right를 조절하면서 찾으면된다.
그럼 최종 코드는 다음과 같을 수 있다.
function solution(){
let left =1
let right = 1000000000
const check =(mid)=>{
let passedPerson =0
for(let i = 0 ; i < times.length; i++){
passedPerson = passedPerson+Math.floor(mid/times[i])
if(passedPerson>n){
return false
}
return true
}
while(left<=right){
const mid = Math.floor((left+right)/2)
if(!check(mid)){
right = mid-1
}
else if(check(mid)){
left=mid+!
}
}
return left
}결과는 ??? 엥? 50점
왜 그러지? 하고 봤더니
범위에 문제가 있었다. right가 10억이아닌 10억 * 10억이어야한다.
이분탐색을 할 땐 최종 범위가 어떻게되는지 파악해야한다.
그렇게 right= 1000000000*1000000000
으로 변경 후 100점으로 통과할 수 있었다.
DFS ❗️
다음은 완전탐색 중 DFS !!
그래도 dfs,bfs는 문제가 어렵긴하지만 푸는과정은 고민을 많이하게되고 재미가 있는 거 같다. 이번에는 level3의 카카오 인턴십에 나온 문제를 풀어봤다.
문제는 다음과 같다.
예전에 풀었던 게임 최단거리 문제와 비슷한데 거기에 + 코너가 추가된 느낌이다.
최단거리문제도 DFS로 풀었었는데 오랜만에 비슷한 유형의 문제를 마주하게되서 복습도 되고 반가웠다.
그럼 코드를 어떻게 짤 수 있을까
function solution(board){
먼저 뭐가 필요할까
바로 위치를 담는 x,y좌표
const visited= []
board.forEach((item)=>{
const arr = Array.from({length:item.length},()=>false)
visited.push(arr)
})
const dfs=(UD,RL)=>{
여기서 이제 UD,RL을 통해 return해주면서 관리해야지
if(UD<0 || RL<0 || UD>=board.length || RL>=board[0].length || board[UD][RL]===1){
return;
}
if(!visited[UD][RL]){
visited[UD][RL]=true
dfs(UD,RL+1)
dfs(UD+1,RL)
dfs(UD,RL-1)
dfs(UD-1,RL)
이게 기본모습이겠지? 근데 방문하지않았던 곳을 가야지
그 위치에서 모든 방향의 순회를 마치면? 그 점은 이제 다시 올 수 있는 위치가 되어야해
visited[UD][RL]=false
}
}
dfs(0,0)
}
위 코드의 형태가 가장 기본이 되는 모습이다.
이제 이곳에 이동 흔적? 을 추적하고 코너를 유추하면 가능하다. 코너를 유추하기 위해 다양한 방법을 시도했는데, 코너는 결국 상하의 움직임에서 좌우로 변경되거나 좌우의 움직임에서 상하이 움직임으로 변경될 때 코너가 발생한다고 볼 수 있다.
그래서 수정한 코드는 다음과 같다.
첫번째 시도 (실패_70점)
function solution(board) {
const answer = [];
const visited = [];
board.forEach((item) => {
const arr = Array.from({ length: item.length }, () => false);
visited.push(arr);
});
const dfs = (RL, UD, sum) => {
if (
RL < 0 ||
UD < 0 ||
RL >= board[0].length ||
UD >= board.length ||
board[UD][RL] === 1
) {
return;
}
if (RL === board[0].length - 1 && UD === board.length - 1) {
let corner = 0;
let target;
sum.split(``).forEach((item) => {
if (target === undefined) {
target = item;
}
if (target !== item) {
corner = corner + 1;
target = item;
}
});
answer.push(corner * 500 + sum.length * 100);
return;
}
// 방문 하는 곳을 기억하긴해야할듯
if (!visited[UD][RL]) {
visited[UD][RL] = true;
dfs(RL + 1, UD, sum + "R");
dfs(RL, UD + 1, sum + "U");
dfs(RL - 1, UD, sum + "R");
dfs(RL, UD - 1, sum + "U");
visited[UD][RL] = false;
}
};
dfs(0, 0, ``);
console.log(answer);
}다음과 같이 코드를 짜니 시간초과가 발생했다. 재귀를 한번 순회할 때마다 sum을 순회하고 또 그 값을 모두 계산해야하기 때문에 배열의 크기가 커지면 그 값이 감당이 안됐다.
그럼 코너를 배열로 순회하지않고 매개변수로 들고다녀야겠다는 생각을 했고 또, 모든 sum에 대해 계산을 하지 않도록 해 만약 expense(비용)이 현재 정답후보보다 커버린다면 그냥 도중에 return 해버리는식으로 코드를 변경했다.
두번째 시도 (실패_80점)
function solution(board) {
let answer = 10000000;
const visited = [];
board.forEach((item) => {
const arr = Array.from({ length: item.length }, () => false);
visited.push(arr);
});
const dfs = (UD, RL, sum, corner) => {
if (
UD < 0 ||
RL < 0 ||
UD >= board.length ||
RL >= board[0].length ||
board[UD][RL] === 1
) {
//이건 범위 바깥
return;
}
if (
sum.substr(sum.length - 2) === "RU" ||
sum.substr(sum.length - 2) === "UR"
) {
corner++;
}
const expense = corner * 500 + sum.length * 100;
if (expense > answer) {
return;
}
if (UD === board.length - 1 && RL === board[0].length - 1) {
//이건 최종
answer = expense;
return;
}
if (!visited[UD][RL]) {
visited[UD][RL] = true;
dfs(UD, RL + 1, sum + "R", corner);
dfs(UD + 1, RL, sum + "U", corner);
dfs(UD, RL - 1, sum + "R", corner);
dfs(UD - 1, RL, sum + "U", corner);
visited[UD][RL] = false;
}
};
dfs(0, 0, ``, 0);
return answer;
}다음과 같이 코드를 리펙토링해서 순회와 처리속도를 줄일 수 있었지만 결과는 ..
더 효율성있는 코드를 구성해야할 거 같다. 후..
또 다시 리펙토링 해서 100점짜리로 다시 포스팅하러 오겠습니다 ㅎㅎ
남은 시간은 위 코드를 리펙토링하고 복습풀이를 해야겠다! 모든 분들 화이팅 ~ 🔥
