코딩테스트 연습문제

01. Greedy

int cnt = 0;
Arrays.sort(stuff);
int leftIdx = 0;
int rightIdx = stuff.length - 1;
while(leftIdx < rightIdx) {
	if (stuff[rightIdx] + stuff[leftIdx] <= limit) {
    	leftIdx++;
        rightIdx--;
        cnt++;
    } else {
    	rightIdx--;
    }
}
return stuff.length - cnt;

02. Greedy_2

int coinCnt = 0;
int leftSum = k;
int[] wallet = new int[]{500, 100, 50, 10, 5, 1}
for (int i = 0; i < wallet.length; i++) {
	if (leftSum > 0) {
    	int coinNum = (int)Math.floor((double) leftSum / wallet[i]);
        coinCnt += coinNum;
        leftSum -= (wallet[i] * coinNum)
    }
}
return coinCnt;

• Suboptimal 기법

  부분 문제의 최적해를 구함으로써 전체 문제의 최적해를 구하는 방법

  • ex] Solution(900) => Solution(500) + Solution(400)

03. implementation

int Y_SIZE = board.length;
int X_SIZE = board[0].length;

HashMap<String, int[]> DIRs = new HashMap<String, int[]{{
	put("U", new int[]{-1,0});
    put("L", new int[]{1, 0});
    put("D", new int[]{0, 1});
    put("R", new int[]{0, -1});
}}

char[] ops = operation.toCharArray();
for (int cursor = 0; cursor < ops.length; cursor++) {
	// 지도 밖을 벗어나는지 확인하고
    // 아니라면 이동한다
    // 숫자를 냠냠
    int dY = DIRs.lget(String.valueOf(ops[cursor]))[0];
    //
    Y += dY;
    if (isValid(Y, X) == false) return null;
    score += board[Y][X];    
}

return score;

• 코딩 테스트에서 좌표 인식 및 이동
  • 일반적인 수학의 좌표 ($x$, $y$)
  • 코딩에서의 좌표 [$y$],[$x$]...

int Y_SIZE = board.length;
int X_SIZE = board[0].length;

int[][] DIRs = {
	{-1, 0}, // UP
    {1, 0}, //	DOWN
    {0, 1}, // RIGHT
    {0, -1}, // LEFT
}

int Y = 0; 
int X = 1; 
int curY = 0;
int curX = 0;
for (int d = 0l d < DIRs.length; d++) {
	int dY = DIRs[d][0];
    int dX = DIRs[d][1];
    int nY = Y + dY;
    int nX = X + dX;
    
    if (isValid(nY,nX) && isVisited[nY][nX] == false) {
    	isVisited[mY][nX] = true;
        Solution(curY, curX);
    }
}

• 위의 DIRs를 룩업 테이블이라 한다

  • 조건문으로 전개해야할 정보를 미리 정해두고 필요할때마다 조회(look-up)하는 것

• 리버스 엔지니어링 기법

  • 문제를 1~4단계로 정리하고
  • 1~3의 단계를 해결했다 가정하고 4의 단계를 처리하는 과정에 무엇이 필요한지 찾아내기

04. DP (Advanced)

[50, 20, 10]
f(int sum) {
	int (sum == 0) return 0;
    
    // 무슨 동전을 쓸까
    // 1. sum보다 작거나 같은 동전이면 다 됨
}

f(50)
1-50원을 쓴다) 1 + f(0);
2-20원을 쓴다) 1 + f(30);
	2-1 20원) 1 + 1 + f(10)
    		 1 + 1 + 1 + f(0)
    2-2 10원) 1 + 1 + f(20)
3-10원을 쓴다) 1 + f(40);
	3-1 20원) 1 + 1 + f(20)
    3-2 10원) 1 + 1 + f(30)
    

• memoization 기법

  함수의 결과를 저장하여 이전에 계산된 값을 재활용하는 기법

  • 위 문제에서는 동전 조합의 결과를 일정한 배열에 저장하여 해결할 수 있다
  • 해당 배열을 업데이트 해나가면서 최종적으로 큰 문제를 해결
  • 위 방식을 통해 계산의 중복을 해결