FrontEnd/알고리즘 및 코테

알고리즘 초보자의 문제 해결 접근법

1-2단계의 경우, 지난 게시물 참고하기!

알고리즘을 풀 때 어떻게 푸는 것이 좋을까? 문제 해결 접근법

🐣 문제 해결1. 개념해결법을 모르는 문제를 풀기 위한 기본 접근 방식 공부작업을 쉽게 수행할 수 있게 해주는 단계다음 섹션(문제해결패턴)에서는 많은 문제들을 해결할 만한 특정 상황에 응

haileyham.tistory.com

🐣 3단계 : 세부 분석 (Break It Down)

1. 어떻게?

문제 세분화 하기
- 단계들의 틀을 잡고 코드 입력하도록

2. 예시로 살펴보기

2단계와 같이 문자열의 각 문자수를 반환하는 함수

우선 주어진 것을 다시 확인하기
- 아래와 같이 출력값 나오도록
charCount("Your PIN number is 1234!")
문제 세분화
- 코드 작성하기 전에 주석을 입력하며 문제 세분화
- 가장 간단하게 무언가를 한다 추가하고
- 출력값이 문자열 내의 소문자, 영문자 문자인 키를 지닌 객체를 반환한다 추가
  - 만약 면접관이 모영숫자 문자 소문자만 가능하다 한다면, 모든 숫자와 모든 문자를 고려하고, 대문자는 소문자로 변경해야 함
```
function charCount(str){
// do something
// 출력값이 문자열 내의 소문자, 영문자 문자인 키를 지닌 객체를 반환한다
}
```
출력 값이 나오도록 간단히 구현
- 실제 단계에서 어떤 작업을 해야하는지 생각
- 현 예시에서는 문자열 내의 각 문자에 대한 어떤 작업이 필요할지에 대해 생각
  - 마지막에 반환할 객체부터 만들기
  - 문자열에 루프를 적용하고 세부적인 부분 작성 후 (for each character)
    - char(문자)가 객체에 숫자나 문자 그리고 key값이 있다면, 1을 더하고, 없다면 추가하고 값을 1로 설정한다고 작성
    - 문자가 공백, 마침표 등과 같은 다른 것이라면 아무것도 하지 않도록 함
    - charCount("Your PIN number is 1234!") 에서 Y부터 시작
      1. Y의 경우 Y를 찾아 소문자로 바꾸어 처음부터 문자열 전체가 소문자 되도록
      1. 혹은 진행하면서 각 문자를 소문자로 바꾸기
    - 빈 객체의 상태로 시작하기 때문에 처음에는 아무것도 없는 상태
    - y를 추가하여 1을 개수도록 해야 함
  - 마지막에 객체 반환
  - 이러한 단계를 거치는 이유?
  🔥 복잡한 문제의 경우 위와 같은 방법이 좋음
  - 단계를 작성한다는 것은 달성하는 방법에 확신이 없더라도
  - 수행해야 할 작업을 알고 있다는 의미이기 때문
  - 문제를 끝내 풀지 못하더라도 풀 수 있는 능력을 보여준 것이기 때문에 못 풀어도 과정을 보여줄 수 있음
  - 아래는 코드에 주석
```
function charCount(str){
// make object to return at end
// loop over string, for each character
	// if the char is a number/letter AND is a key in object, add one to count
	// if the char is number/letter AND not in object, add it to object and set value to 1
	// if character is somthing else (space, period, etc.) dont' do anyhing
// return object at end
}
```

🐣 4단계 : 해결 또는 단순화

1. 어떻게?

문제를 쉽게 해결 혹은 해결하지 못할 경우에는 단순화 시켜서 보기
- 어려운 문제의 경우 진도를 못 나가면 멈추지 말고
- 단순화 시켜서 나중에 코드 통합을 고려하며 풀기
보통 문제를 단순화 하는 과정에서 실제 해결책을 깊이 이해할 수 있고, 문제의 어려운 부분을 파악하며 점차 해결 가능

2. 단순화

어려운 부분을 무시하고 단순한 해결책 작성
이후 다시 어려운 부분 보며, 가능할 경우 다시 통합
이러한 과정을 거치며 어떻게 작동하는지 이해 가능

3. 예시

문자열을 취하고 문자열의 각 문자의 개수를 반환하는 함수를 작성
만약 위의 예제에서 루프를 만드는 것에 어려움을 느낀다면, 객체를 만들어 하드 코딩 할 수도 있음. 면접에 합격을 못하더라도 시작은 할 수 있음 (어려운 문제의 경우, 이렇게 접근을 시작하면 시작이라도 가능하니)
- 만약 문제를 풀며, 대소문자 변경이 기억이 안 난다면, 다른 것들을 먼제 진행하고 마지막에 대소문자 변경 진행해도 됨. 화이트보드에 손코딩 중이라면 해당 파트를 진행하며, 사실 기억이 안난다라고 말하며, 이러한 과정을 진행하려 했다는 것을 말해줄 수 있음.
아래의 경우 대소문자까지 진행하지 않았지만, 반복문을 통해 해당 문자들을 출력해줌

function charCount(str){
	// make object to return at end
	let result = {};
	// loop over string, for each character
	for (let i=0; i<str.length; i++){
		// if the char is a number/letter AND is a key in object, add one to count
		let char = str[i]; // i 문자열을 여기저기 입력하지 않도록 변수 생성 / char은 각 문자
		if(result[char] > 0){ // if문을 통해 result 전달 / result에 char이 있는지 확인
			result[char]++;
			// if the char is number/letter AND not in object, add it to object and set value to 1
		}else{ // result 에 char 없을 경우 1 넣어줌
			result[char] = 1;
	}

		// if character is somthing else (space, period, etc.) dont' do anyhing
	// return object at end
	return result;
}

charCount("hello") // {h:1, e:1, l:2, o:1}
charCount("Hi there") // {H:1, i:1, " ":1, t:1, h:1, ...}

아래의 경우 toLowerCase()를 통해 대소문자 변경까지 진행

영숫자가 아닌 문자가 아직 남음

function charCount(str){
	// make object to return at end
	let result = {};
	// loop over string, for each character
	for (let i=0; i<str.length; i++){
		// if the char is a number/letter AND is a key in object, add one to count
		let char = str[i].toLowerCase(); // i 문자열을 여기저기 입력하지 않도록 변수 생성 / char은 각 문자
		if(result[char] > 0){ // if문을 통해 result 전달 / result에 char이 있는지 확인
			result[char]++;
			// if the char is number/letter AND not in object, add it to object and set value to 1
		}else{ // result 에 char 없을 경우 1 넣어줌
			result[char] = 1;
	}

		// if character is somthing else (space, period, etc.) dont' do anyhing
	// return object at end
	return result;
}

charCount("hello") // {h:1, e:1, l:2, o:1}
charCount("Hi there") // {h:1, i:1, " ":1, t:1, h:1, ...}

영숫자 변경을 하는 과정
- 알파벳 순서의 대문자 소문자, 모든 영숫자 문자를 지닌 배열 (긴 배열) 만들기
- 정규 표현식을 이용하여 해결 할 수도 있음 (다음 단계에서 진행 ⇒ 리팩터 단계)
- 혹은 문자 코드 ASCII 코드도 가능
- 유효한 문자인지 확인하는 작업의 경우 if문 내에 if문 추가 가능
- 다양한 방법 존재, 해당 부분의 경우 최선책을 찾아서 진행하면 됨

🐣 5단계 : 되돌아 보기와 리팩터 (Refactor) ★

1. 어떻게?

리팩토링 과정을 항상 거치도록 하기
코드의 형태, 해석 방법, 효율, 가독성 등 구글링 통해 더 찾아보기
다른 방법으로 문제 풀기
다른 문제와 유사점 여부 확인
성능 향상 여부
- 시간 복잡도 & 공간 복잡도 분석

2. 리팩토링

위에서 살펴본 예제 리팩토링 1

정규식 추가하여 영숫자 구분하도록
- RegExp.prototype.test()
- test() 메서드는 주어진 문자열이 정규 표현식을 만족하는지 판별하고, 그 여부를 true 또는 false로 반환

function charCount(str){
	let obj = {};
	for (let i=0; i<str.length; i++){
		let char = str[i].toLowerCase();
		if(/[a-z0-9]/.test(char)){ // 정규식 추가하여 영숫자 아닌 것은 false하도록
			if(obj[char] > 0){
				obj[char]++;
			}else{
				obj[char] = 1;
			};
		}
	}
	return obj;
}

리팩토링1 에서 코드 개선 (미적 부분 개선)
- for 반복문 대신에 for of 사용
  - for...of 명령문은 반복가능한 객체 (Array, Map, Set (en-US), String, TypedArray, arguments 객체 등을 포함)에 대해서 반복하고 각 개별 속성값에 대해 실행되는 문이 있는 사용자 정의 반복 후크를 호출하는 루프를 생성합니다.
  - for...in 문은 상속된 열거 가능한 속성들을 포함하여 객체에서 문자열로 키가 지정된 모든 열거 가능한 속성에 대해 반복합니다. (Symbol로 키가 지정된 속성은 무시합니다.
- if else 문 || 로 변경
  - obj[char] = ++obj[char] || 1;
  - obj[char]이 있다면 ++ 해주고
  - 그게 아니라면 1 하도록
    1. obj[char]이 있을 경우에는 ++obj[char]의 obj[char]가 true가 되어 ++됨
    2. 만약 없을 경우 false가 되어 || 의 뒤의 것인 1; 출력 됨
    - obj[char] = ++obj[char]을 비교하는 것이 아님ㅇㅇ
    </aside>
  - <aside> 🔥 이해 쉽도록 obj[char] = ++obj[char] 을 먼저 보면,
  - ‘||’ OR의 경우 앞에가 true 면 앞에 출력, 아니라면 뒤에꺼 출력
    - 논리적 OR (||) (논리적 분리) 연산자는 피연산자 중 하나 이상이 참인 경우에만 참입니다. 일반적으로 불리언(논리적) 값과 함께 사용되며, 이 경우에는 불리언 값을 반환합니다. 그러나 || 연산자는 실제로 지정된 피연산자 중 하나의 값을 반환하므로, 이 연산자를 불리언이 아닌 값과 함께 사용하면 불리언이 아닌 값이 반환됩니다.
    - obj[char]++ 와 ++obj[char] 차이
      1. obj[char]++: 후위 증가 연산자입니다. 먼저 **obj[char]**의 현재 값을 반환한 다음 **obj[char]**을 1씩 증가시킵니다.
      예:
      1. ++obj[char]: 사전 증가 연산자입니다. 먼저 **obj[char]**를 1씩 증가시킨 다음 증가된 값을 반환합니다.
      예:따라서 **obj[char]++**와 **++obj[char]**의 주요 차이점은 값 검색과 관련된 증분 작업의 타이밍입니다. **obj[char]++**에서는 값이 검색된 후에 증가가 발생하는 반면, **++obj[char]**에서는 값이 검색되기 전에 증가가 발생합니다.
    - </aside>
    - javascriptCopy code var obj = {a: 5}; var char = 'a'; console.log(++obj[char]); // Output will be 6 console.log(obj[char]); // obj[char] is already 6
    - javascriptCopy code var obj = {a: 5}; var char = 'a'; console.log(obj[char]++); // Output will be 5 console.log(obj[char]); // Now obj[char] is 6
    - <aside> 🔥 obj[char]++ 와 ++obj[char] 차이
```
function charCount(str){
	let obj = {};
	for(let char of str){ //여기서 char 정의하여 다시 정의할 필요가 없음
		char = char.toLowerCase();
		if(/[a-z0-9]/.test(char)){
			obj[char] = ++obj[char] || 1; // obj[char]이 있으면 증가시키고, 없으면 1
		}
	}
	return obj;
}
```
정규표현식 대신에 사용할 수 있는 charCodeAt
1. 정규 표현식보다 빠름(정규 표현식 사용하면 55% 느려짐)
2. 여담이지만 MDN 문서에 charCodeAt 한국어 버전이 없다. 번역에 기여하고 싶다면 https://choar816.tistory.com/161 혹은 https://github.com/mdn/translated-content/issues/827 참고해서 하자 쿄쿄
- “hi”.charCodeAt(0) // 104 ⇒ 소문자 h 해당하는 문자 코드
- “i”.charCodeAt(0) // 105 ⇒ 소문자 i 해당하는 문자 코드
- 영숫자 검사할 수 있는 charCodeAt 코드 & 정규식 코드

코드 리팩토링

function charCount(str){
	let obj = {};
	for(let char of str){
		char = char.toLowerCase();
		if(isAlphaNumeric(char){ // 정규표현식 대신에 charCodeAt 사용
			obj[char] = ++obj[char] || 1; 
		}
	}
	return obj;
}

function isAlphaNumeric(char){
	let code = char.charCodeAt(0);
	if(!(code > 47 && code << 58))&& // numeric (0-9)
		!(code > 64 && code < 91))&& // upper alpha (A-Z)
		!(code > 96 && code < 123)){ // lower alpha(a-z)
		return false;
		}
	return true;
}

4. toLowerCase(); 위치

처음부터 모두 소문자로 바꾼 다음 각 문자 영숫자 확인보다
영숫자 문자 확인하고, (공백, 구두점, 유효하지 않은 것들) 걸러낼 것 걸러내고 소문자로 바꾸는 방법이 더 나음

function charCount(str){
	let obj = {};
	for(let char of str){
		if(isAlphaNumeric(char){
			char = char.toLowerCase(); // toLowerCase(); 이쪽으로 이동
			obj[char] = ++obj[char] || 1; 
		}
	}
	return obj;
}

function isAlphaNumeric(char){
	let code = char.charCodeAt(0);
	if(!(code > 47 && code << 58))&& 
		!(code > 64 && code < 91))&& 
		!(code > 96 && code < 123)){ 
		return false;
		}
	return true;
}

🐣 복습과 인터뷰 전략

1. 다시 보기

5단계 복습
1. 문제 이해
2. 구체적 예제
3. 세부 분석
4. 해결 or 단순화
5. 되돌아 보기 & 리팩토링
각 단계 다시 보기

문제의 이해
1. 나만의 방식
2. 문제 입력값
3. 문제 출력값
4. 입력값으로 출력값 가능 여부
5. 문제 데이터 라벨
구체적 예제
1. 간단 예제
2. 복잡한 예제
3. 빈 입력값 예제
4. 유효하지 않은 값 예제 출력
세부 분석 (주석)
1. 주어진 상황 확인
2. 문제 세분화
3. 출력 값 간단 구현
  1. 마지막 반환 객체부터 만들기
  2. 문자열 루프 및 세부 작성
    1. 숫자 문자열 출력
    2. 공백 등 출력 안하도록
  3. 객체 반환
해결 or 단순화
1. 문제 해결
2. 단순화 시키기
  1. 하나씩 단계별 진행
되돌아보기 & 리팩토링
1. 구글링 통해 형태, 해석 방법, 효율, 가독성 등 찾아보기
2. 다른 방법으로 문제 풀기
3. 다른 문제와의 유사점 찾기
4. 성능 향상 여부 (시간 복잡도 & 공간 복잡도 분석)
5. 리팩토링 할 경우, 단계별 진행

'FrontEnd > 알고리즘 및 코테' 카테고리의 다른 글

[알고리즘JS] 다중 포인터 패턴 (0)	2024.06.26
[알고리즘JS] 빈도 수 세기 패턴 (0)	2024.06.26
알고리즘을 풀 때 어떻게 푸는 것이 좋을까? 문제 해결 접근법 (0)	2024.06.16
배열과 객체의 성능평가 (배열과 객체의 Big O) (0)	2024.06.16
[백준] 콜드바흐의 추측 6588 (0)	2024.06.16

Contents

새소식

인기 검색어

알고리즘 초보자의 문제 해결 접근법

🐣 3단계 : 세부 분석 (Break It Down)

1. 어떻게?

2. 예시로 살펴보기

🐣 4단계 : 해결 또는 단순화

1. 어떻게?

2. 단순화

3. 예시

🐣 5단계 : 되돌아 보기와 리팩터 (Refactor) ★

1. 어떻게?

2. 리팩토링

🐣 복습과 인터뷰 전략

1. 다시 보기

'FrontEnd > 알고리즘 및 코테' 카테고리의 다른 글

당신이 좋아할만한 콘텐츠

티스토리툴바