21년 1월 25일 TIL

오늘 배운 것

Toy pronblem 1번 문제

2인 이상의 사람이 동시에 '가위, 바위, 보'를 할 때, 3판의 가위바위보를 할 경우 나올 수 있는 모든 경우의 수를 구하는 문제

 

입출력 예시는 아래와 같다.

let output = rockPaperScissors();

console.log(output);
/*
    [
      ["rock", "rock", "rock"],
      ["rock", "rock", "paper"],
      ["rock", "rock", "scissors"],
      ["rock", "paper", "rock"],
      // ...etc ...
    ]
  */

 

수도코드

1. 가위바위보 게임에서는 '가위, 바위, 보' 3개 중 하나만 낼 수 있다. -> '가위, 바위, 보'를 배열에 담는다.

2. 게임의 판 수는 3판이다. -> 파라미터의 기본값을 3으로 설정하자. num = num || 3;

3. 한 사람은 가위, 바위, 보 3개 중 하나를 낸다. -> '가위, 바위, 보' 배열을 순회하며 하나씩 빈 배열에 담는다.

4. 한번 진행할때 마다 진행 라운드가 한개씩 줄어어야한다. -> 한번 호출 될 때마다 라운드는 1개씩 줄은다. (재귀 함수 사용)

5. 최종적으로 남은 라운드가 0이 되었을 때 결과를 리턴해야한다. -> 라운드가 0이 되었을 때 결과를 배열 안에 담는다.

 

N - Rooks, Queens

4x4 체스판이 있다고 가정하자. N - Rooks, 체스판에서 '룩' 이 놓여졌을 때 죽지 않고 최대한 놓을 수 있는 개수의 알고리즘을 짜는 문제. N - Queens, 체스판에서 '퀸'이 놓여졌을 때 죽지 않고 최대한 놓을 수 있는 개수의 알고리즘을 짜는 문제.

 

룩은 판 위에서 가로, 세로만 움직일 수 있다.

퀸은 판 위에서 가로, 세로, 대각선을 움직일 수 있다.

 

4 x 4 판 안에서 룩이 움직일 수 있는 총 경우의 수를 그림으로 그려가며 생각해보자.

문제를 최소 단위로 하나씩 쪼개보자. 룩은 가로, 세로를 움직일 수 있고, 움직일 수 있는 총 범위는 4 x 4판 안에서이다.

가로 한줄 안에서 룩이 부딫히는 경우가 있는지 확인.

(ex. [1, 0, 0, 0] 0,0에 룩이 놓아졌을때, 만약 [2, 0, 0 , 0] 1을 초과하면 충돌이 발생 한 것 일거다.)

가로 4개가 모였을 때 룩끼리 부딫히는 경우가 있는지 확인.

세로 한줄 안에서 룩이 부딫히는 경우가 있는지 확인.

(배열에서는 세로가 없는 것에 유의하자. 그러면? 4x4 배열 안에서 세로로 부딫히는 경우를 찾아야할 것 같다.) 

세로가 4개 모였을 때 룩이 부딫히는 경우가 있는지 확인.

퀸은 룩의 움직임에 추가적으로 대각선의 방향을 움직인다. 슬래쉬와 백슬래쉬 방향에서 충돌하는 경우를 찾아야 한다.

배열에서 대각선의 움직임은 어떻게 생각해야할까?

[0, 0, 0, 1]

[0, 0, 1, 0]

[0, 1, 0, 0]

[1, 0, 0, 0]

위와같이 대각선으로 움직임을 구하려면 위에서 세로에서 충돌이 발생했을 때 처럼 전체 배열이 필요할 것이다.

배열 안에서 움직임은 어떻게 구현을 하지?

[0, 0, 1]

[0, 1, 0]

[1, 0 ,0]

4 x 4에서 3 x 3으로 이동하면 이러한 모습이 나올것이다. col 왼쪽으로 이동할수록 col이 한개씩 줄어들 것 같다. 백슬래시는 이와 반대로 이동할 것이다.

 

가장 작은 단위의 생각은 이것이다. 우선 배열 한줄부터 보자.

 

가로 1줄안에서의 충돌, 세로 1줄 안에서의 충돌, 대각선 1줄 안에서의 충돌 이 작은 단위들이 합쳐져서 4x4배열 안에서 충돌 하지 않고 최대한 놓을 수 있는 경우의 수를 찾아낸다.

 

오늘 느낀점

일단, 큰 그림으로 문제의 흐름을 파악해보자. 알고리즘이 어떤식으로 동작해야 할지 이해를 하는게 우선이다.

가장 작은 단위로 쪼개서 생각해보자. 컴퓨터는 아주 작은 단위의 행동 명령을 모아서 동작한다.

처음부터 완벽한 코드를 짜려고 하면 어렵다. 동작하는 하나의 코드를 짜고 뭉치자.

더 공부할 것

• 아주 작은 단위부터 쪼개서 생각 할 수 있는 컴퓨터적 사고방식을 기르자.
• 전체 플로우를 파악하는 능력은 좀 생긴 것 같은데, 아직 코드와 친하지 않은 것 같다. 많이 쳐보면서 익숙해지자.