n x n 의 이차원 배월이 있다고 하자.
arr[n][n]
hasRowConflictAt 메소드의 역할
hasRowConflict는rowIndex값을 가지고 와서 그 행을 탐색하는 것이다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
hasRowConflictAt: function (rowIndex) {
let arr = this.rows();
arr = arr[rowIndex];//특정인덱스가 있는 배열..
let count = 0;
for(let i=0;i<arr.length;i++){
if(arr[i]===1){
count++;
}
//두개이상이면 안되기떄문에 true를 반환한다.
if(count>1){
return true;
}
}
return false; // fixme
},
|
cs |
hasAnyRowConflicts 모든 행의 값을 탐색하는것.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
hasAnyRowConflicts: function () {
let arr = this.rows();
for(let i=0;i<arr.length;i++){
let count = 0; //행이 넘어갈떄는 초기화를 시켜야한다...
for(let j=0;j<arr[i].length;j++){
if(arr[i][j]===1){
count++;
}
if(count>1){
return true;
}
}
}
return false; // fixme
}
|
cs |
hasColConflictAt 특정 열에서의 충돌을 탐색하는 것.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
hasColConflictAt: function (rowIndex) {
let arr = this.rows();
let count = 0;
for(let i = 0 ;i<arr.length;i++){
if(arr[i][rowIndex]===1){
count++
}
if(count>1){
return true;
}
}
return false; // fixme
}
|
cs |
hasAnyColConflicts 모든 열마다의 모든행의 값을 조회해서 충돌 값을 가져온다.
이중 포문을 돌려서 각 행마다 count를 돌려서 1보다 커지면 true리턴
다음 열로 갈경우에 count를 초기화하면서 시작한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
hasAnyColConflicts: function () {
let arr = this.rows();
for(let i=0;i<arr.length;i++){
let count = 0;
for(let j=0;j<arr.length;j++){
if(arr[j][i]===1){
count++
}
if(count>1){
return true;
}
}
}
return false; // fixme
}
|
cs |
hasMajorDiagonalConflictAt 메소드의 역할..
가져오는 파라미터는 무엇인가? ..
majorDiagonalColumnIndexAtFirstRow ?? 첫번쨰 열?..
일단 무슨말인지도 모르겟고 그냥 처음이라는 말에 결국엔 시작??이중요하다고 생각을 했다.
필자는 그림을 그려보았다.
majorDigonal 주요 대각선?? 암튼 왼쪽 위에서 오른쪽 아래로 내려가는 대각선이다.
그냥 그림으로 이해하는 게 편합니다 여러분...ㅎㅇㅎ!!
아래 그림을 보자 ...
colIndex - rowIndex 로 규칙을 찾아 계산이 가능하다고 한다.
같은 대각선(왼쪽위에서 오른쪽아래로 대각선) 의 있는 값이 같게할려면
colIndex >=rowIndex 이기 떄문인거같다. 그래서 그갓을 다 적어두었다.
|
[0,0] =0 |
[0,1] = - 1 |
[0,2]= - 2 |
[0,3]= - 3 |
|
[1,0] = 1 |
[1,1] = 0 |
[1,2]= - 1 |
[1,3]= - 2 |
|
[2,0] = 2 |
[2,1] = 1 |
[2,2]=0 |
[2,3]= - 1 |
|
[3,0] =-3 |
[3,1] = 2 |
[3,2]= 1 |
[3,3]=0 |
규칙이 보이는가?..
일단 범위는 ㅡ(배열의 길이 -1) ~ (배열의길이 - 1)
그럼 코드 구현을 어떻게 할지 생각 해보자.
왼쪽위에서 오른쪽 아래로 이동한다 행과 열의 값이 1씩 증가한다.
같은 색깔끼리 표시했다. 같은 대각선에 있는 값
majorDiagonalColumnIndexAtFirstRow의 값에 따라 경우를 나누면
n 값이 양수이면 (n,0) colindex 값이 n이다 rowIndex 값은 0이다.
n 값이 0이면 (0,0) colindex 값과 rowindex 값 둘다 0이다.
n 값이 음수이면 (0,n) colindex 값은 0 row인덱스 값은 n 이다.
그리고 다음 대각선으로 갈떄는 colindex 와 rowindex값이 1씩 증가한다
위의 내용을 바탕으로 밑의 코드를 작성한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
hasMajorDiagonalConflictAt: function (majorDiagonalColumnIndexAtFirstRow) {
// 음수일경우,,, (n ,0) = -n 영일경우 0,0 양수일경우 (0,n) = n //시작지점...
let arr = this.rows();
let row_index =0;
let col_index =0;
//초기의 시작지점을 정해주는 index값 설정..
if(majorDiagonalColumnIndexAtFirstRow>0){
row_index = majorDiagonalColumnIndexAtFirstRow;
}
else if(majorDiagonalColumnIndexAtFirstRow<0){
col_index = Math.abs(majorDiagonalColumnIndexAtFirstRow);
}
let count = 0;
while(true){
if(arr[col_index][row_index]===1){
count++;
}
//2개이상일떄 충돌...
if(count>1){
return true;
}
//오른쪽아래로 가기떄문에 row,col 인덱스가 1씩증가..
row_index++;
col_index++;
//범위를 벗어날 경우에...
if(row_index>arr.length-1||col_index>arr.length-1){
break;
}
}
return false; // fixme
}
|
cs |
hasAnyMajorDiagonalConflicts 모든 왼쪽위에서 오른쪽아래로 내려가는 대각선을 구현하는 것이다.
위의 코드를 참고해서 구현하면 된다 재사용이 가능하기 떄문이다.
시작지점을 잘 설정해서 for문을 돌리면 된다
코드는 밑에 ... 고민해보고 구현해보고 고통받고 열어보라...
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
hasAnyMajorDiagonalConflicts: function () {
function hasMajor(arr,majorDiagonalColumnIndexAtFirstRow) {
// 음수일경우,,, (n ,0) = -n 영일경우 0,0 양수일경우 (0,n) = n //시작지점...
let row_index =0;
let col_index =0;
//초기의 시작지점을 정해주는 index값 설정..
if(majorDiagonalColumnIndexAtFirstRow<0){
row_index = Math.abs(majorDiagonalColumnIndexAtFirstRow);
}
else if(majorDiagonalColumnIndexAtFirstRow>0){
col_index = majorDiagonalColumnIndexAtFirstRow;
}
let count = 0;
while(true){
if(arr[col_index][row_index]===1){
count++;
}
//2개이상일떄 충돌...
if(count>1){
return true;
}
//오른쪽아래로 가기떄문에 row,col 인덱스가 1씩증가..
row_index++;
col_index++;
//범위를 벗어날 경우에...
if(row_index>arr.length-1||col_index>arr.length-1){
break;
}
}
return false; // fixme
}
let arr = this.rows();
//시작지점을 정해주고 돌린다..
let leng = arr.length-1; //n값을 가지고온다 최대값.. n부터 -n 범위를 설정하기 위해서 가져옴..
// -n -> n n> -n
for(let i = leng ;i>=-leng;i--){ //-n ~ n까지
//시작지점 정하기..
let check = hasMajor(arr,i); //재사용...
if(check){
return true;
}
}
return false; // fixme
}
|
cs |
hasMinorDiagonalConflictAt ( index ) 를 풀떄는
index = colindex+ rowindex를 더한 값을 기준으로 파라미터 값을 가져와서 풀어야 하는데... 그것을 표로 나타내면 다음과 같다.
|
[0,0] =0 |
[0,1] = 1 |
[0,2]= 2 |
[0,3]= 3 |
|
[1,0] = 1 |
[1,1] = 2 |
[1,2]= 3 |
[1,3]= 4 |
|
[2,0] = 2 |
[2,1] = 3 |
[2,2]=4 |
[2,3]= 5 |
|
[3,0] =-3 |
[3,1] = 4 |
[3,2]= 5 |
[3,3]= 6 |
다음 규칙을 보고 위 코드를 참고해서 풀기를 바란다...
그럼 solve로 넘어가보도록하자.
findNRooksSolution 라는 함수는 n을 입력하면 rook의 위치가 충돌나지 않도록 꽉 채우는 nxn 배열을 출력하는 함수다.
어떻게 하면 만들 수 있을까?..
앞에서 했던 것들을 이용하면 편하게 할수 있다.
모든 행과 모든 열을 탐색하는 함수를 만들어서 열을 탐색하고 충돌이일어나지 않을떄....(함수사용)
다음 행으로 넘어가면 되는것이다.
그렇게 재귀를 돌린뒤에... row길이가 지정했던 n값과 같으면 리턴시키면 된다.
다만 이것을 구현할때 조심할 점은 스코프와 함수가 리턴할떄 값을 어떻게 받아올지 고민하는 것이 매우 중요하다.
countNRooksSolutions 라는 함수는 n을 입력하면 ..
nxn배열의 크기에 따라서 배치할수 있는 findNRooksSolution 경우의 수를 출력하는 함수다.
사실 위에 말했던 것과 비슷하다 이것도.. 다만 위에는 깊은탐색(재귀를 돌리고 재귀를 돌려서...)을 해서 끝에 다다르면 그것을 리턴해서 가져와야하지만 여기에서는 그 상태가 되었을떄 충돌이 일어나지 않으면 그것을 count를 세는 것이다.
다시 한번 말하지만.. 스코프와 함수가 리턴할떄 어떤 값을 가져오는지.. 잘 살펴봤으면 한다. 진짜 중요한 문제다.
findNQueensSolution 라는 함수는 n을 입력하면 queen의 위치가 충돌나지 않도록 꽉 채우는 nxn 배열을 출력하는 함수다.
어떻게 하면 만들 수 있을까?..
이것도 마찬가지로 우리가 앞에서 행했던 queens 충돌인지 아닌지 함수를 만들수 있도록 만든것이 있는데.. 대각선과 세로와 가로의 모든 함수를 합쳐서 or 연산을 쓰면 그것을 만들 수 있다.
모든 행과 모든 열을 모든 대각선 탐색하는 함수를 만들어서 열을 탐색하고 충돌이일어나지 않을떄....(함수사용)
다음 행으로 넘어가면 되는것이다.
그렇게 재귀를 돌린뒤에... row길이가 지정했던 n값과 같으면 리턴시키면 된다.
다만 이것을 구현할때 조심할 점은 스코프와 함수가 리턴할떄 값을 어떻게 받아올지 고민하는 것이 매우 중요하다.
findNQueensSolutions 라는 함수는 n을 입력하면
nxn배열의 크기에 따라서 배치할수 있는 findNQueensSolution 경우의 수를 출력하는 함수다.
사실 위에 말했던 것과 비슷하다 이것도.. 다만 위에는 깊은탐색(재귀를 돌리고 재귀를 돌려서...)을 해서 끝에 다다르면 그것을 리턴해서 가져와야하지만 여기에서는 그 상태가 되었을떄 충돌이 일어나지 않으면 그것을 count를 세는 것이다.
다시 한번 말하지만.. 스코프와 함수가 리턴할떄 어떤 값을 가져오는지.. 잘 살펴봤으면 한다. 진짜 중요한 문제다.
'알고리즘구현능력 > 문제해결능력' 카테고리의 다른 글
| [javascript] 구명보트 - 탐욕법 (0) | 2020.08.19 |
|---|---|
| self assment tree.map 구현에 대하여.... (0) | 2020.01.09 |
| 알고리즘 토이 문제 4 피보나치함수를 구현하라.!! (0) | 2020.01.09 |
| 알고리즘 토이 문제 3번째 부분집합인지 아닌지 불린값 반환문제 (0) | 2020.01.08 |
| 알고리즘 토이 문제 2. 중복되지 않는 문자를 반환하는 문제. (0) | 2020.01.08 |
