구현

boyeonJ·2023년 6월 17일

알고리즘

목록 보기

11/17

구현이란??

머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정
모든 범위의 코딩테스트 문제 유형을 포함하는 개념
풀이를 떠올리는 것은 쉽지만, 소스코드로 옮기기 어려운 문제
피지컬을 요구하는 문제

그럼 어떤 문제가 구현하기 어려운 문제인가

알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제
특정 소수점 자리까지 출력해야 하는 문제
문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야 하는 문제 등등

프로그래밍 언어의 문법에 익숙하지 않거나 라이브러리 사용 경험이 많이 없을 경우 더욱 어렵게 느껴질 수 있는 문제이다.

구현의 유형중 2가지!

완전탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법
시물레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행하는 문제 유형

구현 시 고려해야 할 사항

먼저 코딩 테스트 시스템의 제약에 대해 알아보자

메모리 제약 사항

변수 메모리 제약
리스트 메모리 제약

채점 환경

보통 채점시 시간 제한과 메모리 제한이 주어질 수 있다. 이때, 시간 제한과 데이터의 개수를 먼저 확인 한 뒤에 이 문제를 어느 정도의 시간 복잡도 알고리즘으로 풀 수 있을 것인지 예측 할 수 있어야 한다.

예를 들어 시간 제한이 1초이고, 데이터의 개수가 100만 개 일때, 일반적으로 시간 복잡도 O(NlogN)이내의 알고리즘을 이용하여 문제를 풀어야 한다.

문제 풀이

1. 상하좌우

R이면 y하나 늘리고, L이면 y를 하나 내리기
D이면 x를 하나 늘리고, U이면 x를 하나 내리기

이후에 계산된 x와 y들이 범위안에 있는지 검토 후 실제 값에 적용

const solution = (number, inputArray) => {
    let x=1, y=1;
    const array = inputArray.split(' ');
    
    for(let value in array){
        const now = array[value];
        let tempX=x;
        let tempY=y;
        if(now === 'R') tempY++;
        else if(now === 'L') tempY--;
        else if(now === 'U') tempX--;
        else if(now === 'D') tempX++;
    
        if(tempY > 0 && tempY <= number) y = tempY;
        if(tempX > 0 && tempX <= number) x = tempX;
    }
    
    return `${x} ${y}`   
}

console.log(solution(5,'R R R U D D'));

const solution = (number, inputArray) => {
    let x=1, y=1;
    const array = inputArray.split(' ');
    
    for(let value in array){
      switch(array[value]){
        case 'R': 
          y < number && y++;
          break;
        case 'L': 
          y > 1 && y--;
          break;
        case 'D': 
          x < number && x++;
          break;
        case 'U': 
          x > 1 && x--;
          break;
      }
    }
    
    return `${x} ${y}`   
}

console.log(solution(5,'R R R U D D'));

2.

const solution = (num) => {
    let result = 0;
    let count = num;
    while(count>0){
        if(count === 3 || count === 13 || count === 23){
            result += 60*60;
        }else{
            result += (54*6) + (60*6);
        }
    }
    return result;
}

console.log(solution(5));

3. 왕실의 나이트

let count = 0;
const BOARD_SIZE = 8;

const solution = (input) => {
    const array = input.split('');
    const x = array[0].charCodeAt(0) - 96;
    const y = Number(array[1]);
    checkFirstDeep(x,y);
    checkFirstDeep(y,x);
    return count;
}

const checkFirstDeep = (value, value2) => {
    if(value + 2 <= BOARD_SIZE) checkSecondDeep(value2);
    if(value -2 > 0) checkSecondDeep(value2);
}

const checkSecondDeep = (value) => {
    if(value+1 <= BOARD_SIZE) count++;
    if(value-1 > 0) count++;
}

console.log(solution('g7'))

다른 풀이

function solution(place) {
	const col = parseInt(place[0].charCodeAt(0)) - 96; // a ~ h -> 1 ~ 8
	const row = parseInt(place[1]); // 0 ~ 8
	const stepList = [[-2, 1], [-2, -1], [2, 1], [-2, -1], [1, -2], [1, 2], [-1, 2], [-1, -2]];
	let count = 0;
	
	for(let i = 0; i < stepList.length; i++) {
		let stepCol = stepList[i][0];
		let stepRow = stepList[i][1];
		
		if((col + stepCol >= 1 && row + stepRow >= 1) && (col + stepCol <= 8 && row + stepRow <= 8)) {
			count++;
		}
	}
	
	console.log(count);
  return count;
}

// 실행 결과 8개
solution("e4");

// 실행 결과 2개
solution("a1");