알고리즘 문제 풀어보기
쿼드압축 후 개수 세기
문제 설명
0과 1로 이루어진 2n x 2n 크기의 2차원 정수 배열 arr이 있습니다. 당신은 이 arr을 쿼드 트리와 같은 방식으로 압축하고자 합니다. 구체적인 방식은 다음과 같습니다.
- 당신이 압축하고자 하는 특정 영역을 S라고 정의합니다.
- 만약 S 내부에 있는 모든 수가 같은 값이라면, S를 해당 수 하나로 압축시킵니다.
- 그렇지 않다면, S를 정확히 4개의 균일한 정사각형 영역(입출력 예를 참고해주시기 바랍니다.)으로 쪼갠 뒤, 각 정사각형 영역에 대해 같은 방식의 압축을 시도합니다.
arr이 매개변수로 주어집니다. 위와 같은 방식으로 arr을 압축했을 때, 배열에 최종적으로 남는 0의 개수와 1의 개수를 배열에 담아서 return 하도록 solution 함수를 완성해주세요.
제한사항
arr의 행의 개수는 1 이상 1024 이하이며, 2의 거듭 제곱수 형태를 하고 있습니다. 즉, arr의 행의 개수는 1, 2, 4, 8, ..., 1024 중 하나입니다.
arr의 각 행의 길이는 arr의 행의 개수와 같습니다. 즉, arr은 정사각형 배열입니다.
arr의 각 행에 있는 모든 값은 0 또는 1 입니다.
풀이 코드
function solution(arr) {
if(arr.length === 1) return arr[0][0] ? [0,1] : [1,0];
const answer = [0,0];
const len = arr.length;
const half = len / 2;
const number = arr[0][0];
let flag = true;
out:for(let i=0; i<len; i++){
for(let j=0; j<len; j++){
if(number !== arr[i][j]){
flag = false;
break out;
}
}
}
if(flag){
answer[number]++;
return answer;
}
for(let i=0; i<2; i++){
for(let j=0; j<2; j++){
const compressArr = [];
for(let k=0; k<half; k++){
compressArr.push(arr[(half * i) + k].slice(j * half, (j+1) * half));
}
const [zero, one] = solution(compressArr);
answer[0]+=zero;
answer[1]+=one;
}
}
return answer;
}풀이 과정
배열 크기가 1이면 값에따라 0, 1 개수를 반환해준다.
각 절차마다 반환을 위한 정답 배열 answer를 선언 후 정사각행렬 arr를 총 4개의 가장 큰 정사각형으로 나눠야 하기 때문에 절반 값을 취한다.
현재 재귀단계에서, 모든 행렬의 구성 값이 같다면 하나로 압출해줄 number을 만들어 주고 flag변수로 행렬 구성 상태를 파악해준다.(만약 행렬의 구성값이 모두 같지 않다면 flag를 통해 빠르게 반복문을 탈출한다. / 행렬의 구성값이 모두 같다면 number값에 따라 0, 1 개수를 반환한다.)
행렬 구성 값이 통일 되지 않았을 때 진행될 반복문을 만들어 준다.
압축을 위해 다음 재귀에 넣어줄 compressArr행렬을 선언 후 i,j값이 변할 때 arr을 구성하는 가장 큰 정사각행렬의 값을 총 i*j = 4로 4개를 구해준다.
이후 4개의 정사각행렬을 각각 다음 재귀로 넣어주고 반환 값을 [zero, one] 변수에 담아서 answer 배열에 넣어준다.
기술면접 문제 풀어보기
15. DFS와 BFS의 차이를 말해주세요.
- 두 방법 모두 그래프를 탐색하는 방법.
DFS (Depth-First Search) - 깊이 우선 탐색
- 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식.
- ex) 미로찾기를 할때 최대한 한 방향으로 갈 수 있을 때까지 쭉 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 그 갈림길부터 다시 다른 방향으로 탐색을 진행하는 것.
- 모든 노드를 방문하고자 하는 경우 해당 방법 선택.
- BFS(너비 우선 탐색)보다 좀 더 간단함.
- BFS(너비 우선 탐색)보다 검색 속도가 느림.
BFS (Breadth-First Search)
- 루트 노드(혹은 다른 임의의 노드)에서 시작해 인접한 노드를 먼저 탐색하는 방식.
- 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문.
- 주로 두 노드 사이의 최단 경로를 찾고 싶을 때 사용.
- ex) 지구 상에 존재하는 모든 친구 관계를 그래프로 표현한 후 Sam과 Eddie사이에 존재하는 경로를 찾을 때
- DFS : 모든 친구 관계를 다 살펴봐야 할 수 있음.
- BFS : Sam과 가까운 관계부터 검색.
차이점
| DFS(깊이우선탐색) | BFS(너비우선탐색) |
|---|---|
| 현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색 | 현재 정점에 연결된 가까운 점들부터 탐색 |
| 스택 또는 재귀함수로 구현 | 큐를 이용해서 구현 |
최종프로젝트
merge후 있는 오류들을 해결 후 moveHandler를 작성했다.
내일 작업할 것 : 우선 맡은 부분 마무리(Despown, Animation)
