구현(시뮬레이션과 완전탐색)

구현과 시뮬레이션, 완전탐색은 겹치지는 부분이 꽤 있다. 

일단 세개의 알고리즘을 이용한 풀이에 자주 사용될 개념을 먼저 정리한다.

 

 

행렬 

- (0,0)에서 가로 줄을 행, 세로줄을 열이라 한다. 따라서 ( 행 , 렬 ) 이 된다.

 

 

2차원배열

- 위 그림을 2차원배열로 나타내면 아래와 같다.

- int[ ][ ] matrix = new int[5][5] -> Java 표현식.

- (2,1)은 matrix[2][1]을 뜻한다.

 

 

구현 - 방향벡터 사용

- (2,2)가 원점이라 가정할 때, 동쪽으로 +1 이동은 열+1이다. 따라서 (x,y) = (행,렬)이라 가정할 때,

동쪽은 y = +1 이 된다.

- 아래처럼 선언하여 사용할 경우 L의 인덱스에 해당하는 값이 dx와 dy의 인덱스를 사용할 때 정확히 일치하는 동작을 하게 할 수 있다. 

int[] dx = {0, 0, -1, 1};

int[] dy = {-1, 1, 0, 0};

char[] moveTypes = {'L', 'R', 'U', 'D'};

 

 

완전탐색 알고리즘(Brute Forcing)

: 가능한 경우의 수를 모두 검사해보는 탐색방법

 

예시) 시각에 3이 포함되는 경우의 수를 구하기

풀이)

00시 00분 00초 ~ 23시 59분 59초까지 모든 경우의 수인 86,400 임을 인지하고,

시각은 1씩 증가시키며 3이 하나라도 포함되어 있는지 86,400번만 반복하면서 검출 될 때 마다 

특정 변수에 +1을 해주면 된다.

 

이처럼, 특정 경우의 수를 단순반복으로 모두 검사해보는 방식의 문제 풀이 방법을 "완전탐색 유형"이라 한다. 

 

참고 :  동빈나 - 이코테 2021 Youtube 강의 참조