알고리즘&자료구조 2편 - 문제 해결(1) 접근법

김영현·2023년 5월 15일

알고리즘 & 자료구조

목록 보기

2/6

알고리즘이란?

문제를 해결하기위한 수행해야하는 일련의 수학적 단계.

문제 해결의 단계.

문제 해결을 위한 계획 수집.
- 문제를 이해하기
- 구체적인 예시를 알아보기
- 문제를 세분화 하기
- 문제를 해결 || 단순화 하기
- 복습/재구성 하기
일반적인 문제 해결 패턴들을 마스터 하기.

1. 문제를 이해하기

a. 문제를 나만의 방식대로 이해할 수 있는가?
b. 문제의 입력은 어떤 값을 담고 있는가?
c. 문제에 대한 해결, 출력값은 무엇인가?
d. 문제의 입력값이 출력값을 결정하는가?
e. 문제에서 제일 중요한것은 무어인가?
=> 순서대로 파악.

예시로 문제 하나를 들어보자.

문자열 입력이 주어진다. 각 문자의 수를 반환하라.

강의 영상에서는 단계별로 차근차근 설명해줬다. 강의를 다 보고나서 적는터라 실수가 있을수도 있다!

a. 문제를 나만의 방식으로 이해하기
=> 문자열을 입력받아 스펠링 갯수를 나타낸다. 즉, 문자열을 한번 순회하고 결과를 리턴해준다.

const countChar(str) => {
...return result; 
  // countChar("hello") => {h:1, e:1, l:2, o:1} 이런식
}

b. 문제의 입력은 어떤 값을 담고있는가?=>
=> 문자열.

c. 문제에 대한 해결, 출력값은 무엇인가?
=> 문자열 Key, 숫자를 Value로 하는 Object를 return.

d. 문제의 입력값이 출력값을 결정하는가?
=> 그렇다.

e. 문제에서 제일 중요한것은 무엇인가?
=> 문자열을 순회하며 같은 갯수를 카운팅 하는것.

2. 구체적인 예시를 알아보기

a. 쉬운 예제로 시작하라. (입력값-출력값 예제를 3개정도 써놓아라)
b. 더 복잡한 예를 들어라.
c. 빈 입력이 들어오는 예.
d. 유효하지않은 입력이 들어오는 예.

a. 쉬운예제로 시작하라

countChar("aaaaa") => {a:5}
countChar("hello") => {h:1, e:1, l:2, o:1}

b. 더 복잡한 예를 들어라

countChar("My Phone Number is 1234") => {숫자처리}
countChar("Hello hi") => {공백과 대문자 처리}
countChar("") => {empty처리}

3. 문제를 세분화 하기

a. 내가 해야할 단계를 명확하게 작성하라.

const countChar(str) => {
  //순회 로직
  let result = {};
  for(let i = 0; i<str.length; i++){
  //String을 순회한다. 대문자는 소문자로, 공백은 관여x
  //문자나 숫자가가 obj안에 없으면 추가하고 value를 1, 있으면 obj[char](obj.char과 같은기능이지만 동적접근)의 value를 +1.
    //공백이나 특수문자라면 행동x
  }
  return result;
}

4. 문제를 해결 || 단순화 하기

일단 문제를 단순화 해보자!

const countChar(str) => {
  let result = {};
  for(let i = 0; i<str.length; i++){
    const char = str[i]
	if(result[char]>0) {
      result[char]++;
    } else {
    result[char] = 1;
    }
  }
  return result;
  //{h:1, e:1, l:2, o:1} 이렇게 잘 나온다. 하지만 대문자, 공백, 특수문자는 거르지 못함.
}

단순화 했다면 예외사항을 추가하자.

...for(let i = 0; i<str.length; i++){
    const char= str[i].toLowerCase(); //소문자
	if(소문자와 숫자만받는 정규식){
    	if(result[char]>0) {
      result[char]++;
    } else {
    result[char] = 1;
    }
    }
}