문제 해결 단계

anonymous·2021년 5월 8일

알고리즘

목록 보기

8/12

🎈 문제 해결 단계

1 명확한 문제 해석/분석 단계

핵심 규칙, 요구사항 파악/요약
자료구조 파악/구분 (필요한 속성 등)
파라미터 구분, 도출 (INPUT)
리턴 데이터 구분, 도출 (OUTPUT)

2 간단하고 실질적인 예제 만들어서 사용하기

최대한 간단한 INPUT, 최적화는 나중에 생각
필요하면 시각적으로, 물리적으로 구현
다음엔 psudocode 작성
Invalid (유효X), Empty Input(null) 인수값을 상황에 따라서 도입.
최대한 간단한 예제로 구현 후 조금씩 더 복잡한 예제로 넘어가기
FIND INFANT STAGE ( 초기 개념에서 시작하기 )

3 문제를 나눠서 따로 (쉬운 부분을 우선) 해결한 후 다시 조합

답이 안맞으면 문법과 순서, 요구사항, 규칙 다시 한번 확인
그래도 어려우면 Benchmarking 다른 사람 솔루션 확인

4 리펙토링 - 최적화

다양한 테스트 케이스 환경에서 유효한지?
최적화 + 유지보수 편의성까지 담겨 있는지?
다른 방법/솔루션을 알고 있는지?
해당 방법을 다른 문제를 해결하는데 쓸 수 있는 패턴인지?
가장 중요한 단계!

예제)

//Write funciton which takes in string and returns counts of each char. in the string

// 1 문제 분석
// get string return count of string char

// 2 간단한 예제
charCount("aaaa") // --> 4
charCount("ttttt") // --> 5 
//좀 더 복잡한 예제
charCount("Take new letter 123")
/*
count chars
1: 1,
2: 1,
3: 1,
a: 1,
e: 3,
k: 1
...
*/
//Psudocode 구현
function charCount(str){
// make object to return at end
// loop string for each char.
    // if char is a number/letter AND is a key in object, add one to count
    // if char is a number/letter AND not in object, add it and set value to 1
    // if char is sth else (space, period, etc...) X execute
// return object at end
}

// 3 문제 해결 / 아직 어려우면 문제를 나눠서 좀 더 쉽고 단순한 부분을 해결하기 

function charCount(str){
// make object to return at end
  var result = {};
// loop string for each char.
  for(var i = 0; i < str.length; i++){
    var char = str[i].toLowerCase(); // toLowerCase()는 나중에 추가함. 
    if(result[char] > 0){
    // if char is a number/letter AND is a key in object, add one to count
      result[char]++;
    }else{
    // if char is a number/letter AND not in object, add it and set value to 1
      result[char] = 1;
    }
  }
  return result;
}
    // if char is sth else (space, period, etc... non-alphanumeric) X execute
// return object at end
}

// 4 리펙토링
function charCount(str){
  var obj = {};
  for(var i=0; str.length; i++){
    var char = str[i].toLowerCase();
    if( /[a-z0-9/.test(char) ){
      if(obj[char] > 0){
        obj[char]++;
      }else{
        obj[char] = 1;
      }
    };
  };
  return obj;
}
/*
추가적인 리펙터
직관성을 위해서 코드 수정. 
*/
  for(var i=0; str.length; i++)
   -->
  for(var char of str){
     char = char.toLowerCase()
     if( /[a-z0-9/.test(char) ){
       obj[char] = ++obj[char] || 1;
     }
  }
// regex -> must check performance issue depending on browser.

// 최종 결과물
function isAlphaNumeric(char){
	var code = char.charCodeAt(0);
  if(!(code > 47 && code < 58) && //0-9
     !(code > 64 && code < 91) && //A-Z
     !(code > 96 && code < 123)) { //a-z
    return false;
  }
  return true;
}

function charCount(str){
  var obj = {};
  for(var char of str){
    if( isAlphaNumeric(char)){
      char = char.toLowerCase();
      obj[char] = ++obj[char] || 1;
    };
  };
  return obj;
};

Inductive Reasoning (귀납 추론) :

Bottom-up approach (cause-and-effect)
Finding patterns from observations.

Deductive Reasoning (연역적 추론) :

if A(명제)=B and B=C, the A=C
Top-down approach to drawing conclusion.
알려진 이론(명제)을 어떤 현상에 대입(추론 규칙을 찾아)해서 결론을 도출.

Tips to improve

Be curious ( Deduce from info. you already have )
Be observational
Increase your knowledge
Break problems into smaller pieces
Try to anticipate outcome of decisions.
Practice Math

문제 해결 예제

369 게임


//3,6,9 게임 
import java.io.*;
class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		Integer input = Integer.parseInt(br.readLine());
		// 유효성
		if(input < 1){
			return;
		}
		//1 N 횟수 입력을 받으면 횟수만큼 루프를 돌기
		int count = 0;
		int result = 0;
		String chkNum = "";

		for(int i=1; i<input; i++){
			chkNum = String.valueOf(i);
			for( int j=0; j<chkNum.length() ; j++ ){
				//*** 방법 1 
				/*
				result = Character.getNumericValue(chkNum.charAt(j));
				if( result%3==0 || result%6==0 || result%9==0 ){
				  count++;
				}
				if( result==0 ){ // 10,20,30 등에서 
					System.out.println("result "+result);
					count--;
				}
				*/
				// *** 방법 2	
				result = chkNum.charAt(j);
				if( result == '3' || result == '6' || result == '9' ){
					count++;
			  }			
			}
		}//end
		//4 count한 만큼 출력- 짝 횟수
		System.out.println(count);
  }//end
}

/*
//1 
369 게임 규칙
- 3, 6, 9 짝
&&
- 3, 6, 9 가 들어가면 들어간 횟수 만큼 짝
예)
1
2
3 짝 
33 짝짝 
36 짝짝

//2
N = 게임 횟수 
result  = 값 체크 변수  
count = 짝 횟수 담기 

//
1 N 횟수 입력을 받으면 횟수만큼 루프를 돌기
2 각 횟수를 세고 3,6,9의 배수면 짝을 clap에 담고 
3 3,6,9가 포함되도 clap에 담기 
4 clap에 담긴만큼 print 짝 횟수 
*/