JS Algorithm & Data Structure 1

시작

이제 JS로 알고리즘 및 자료구조 공부를 시작한다.(2024-04-16)
하필 왜 JS 냐? 라고 물어본다면…
내가 JS를 좋아하기도 하고, 개인적으로 JS를 제일 대단한 언어중 하나라고 생각하기도 하고,
무엇보단 나는 프론트엔드에 관심이 있다. (디자인 감각은 없다..)
다른 커뮤니티나 개발자 분들은 정적언어로 공부하거나 취준생이면 Python 해라!
라고 많이 하시는데, 일단 나는 취업을 할 때도, 프론트엔드 아니면 Node 백엔드만 넣을 생각이다.
그래서 JS를 정복하는 것 자체가 나의 평생? 의 업이지 않을까 싶다.

문제 접근법

우리는 코딩테스트를 준비하면서 문제 에 많이 부딪힌다.
근데 문제 라는 것이 비단, 알고리즘 문제만 문제일까?
무엇인가를 구현하기 위해 파악해야할 이슈, 세부사항, 경계값 같은 것들도 문제 라고 생각한다.
문제를 어떻게 받아들이고 이해하고 정의하냐에 따라 그것에 대한 해결방법이 달라진다.

문제 접근법에서 필수로 진행해야할 사항은 다음과 같다.

• 문제 이해
• 구체적인 예시 이해 및 알아보기
• 문제 세분화
• 문제 해결 & 단순화
• 문제 되돌아보기 & 재구성

순서대로 공부한 내용을 요약해보겠다.

① 문제 이해

1. 문제를 나만의 스타일로 다시 정리할 수 있나
2. 문제는 어떤 입력값을 담고 있는가
3. 어떤 출력값이 나와야 하는가
4. 문제를 해결할 충분한 정보가 나에게 주어졌는가?
5. 내가 문제에 일부분인 데이터에 어떻게 라벨을 지정할 수 있는가

위의 내용을 통해(스스로에게 질문하면서) 문제를 파악해 나간다.

② 예시 탐색

1. 간단한 예시 부터 생각하자
2. 점진적으로 복잡한 예시를 생각하자
3. 빈 값 이 입력값인 경우의 예시를 생각해보자
4. 유효하지 않은 값 이 입력값인 경우의 예시를 생각해보자

중요한것은, 간단한 예시에서 끝나지 않고, 이렇게 값이 들어오면 어떡하지?
저렇게 값이 들어오면 어떡하지? 하는 의심 의 마인드가 뿌리내려야 하는것 같다.

③ 문제 세분화

• 💡문제 해결을 위한 단계를 명시적으로 작성한다.

/* 문자열을 입력받아 해당 문자열에 속한 문자의 갯수를 객체로 출력하는 함수를 작성하라*/

function solution(str) {
	// 1. 결과로 반환될 Object를 생성한다.
	// 2. 입력값인 문자열을 순회한다. (각 문자 마다)
		// 2-1. 문자가 숫자/문자 And Key로써 Object에 존재한다면 해당 value를 +1
		// 2-2. 문자가 숫자/문자 And Key로써 OBject에 존재하지 않는다면 value = 1
		// 2-3. 문자가 특수문자나 숫자/문자가 아니라면 continue
	// 3. 최종 Object를 반환한다.
}

• 위에서 처럼 단계를 명시적으로 작성하여 해결해야할 부분들을 확인하는 것이 큰 도움이 된다.

④ 문제 해결 또는 단순화

• 문제가 해결 가능하면 해결
• 해결할 수 없다면, 단순화 하자

단순화

1. 가장 어려운 부분을 찾는다.
2. 어려운 부분을 무시하고 단순한 해결책을 작성한다.
3. 이 때, 가능하다면 어려운 부분을 통합시킨다.

⑤ 문제 되돌아보기 & 재구성(Refactor)

스스로 해볼 질문들

1. 결과를 확인 할 수 있는가?
2. 결과를 다른 방식으로 도출할 수 있는가?
3. 해결한 방법 이외에 생각나는 접근 방식이 있는가?
4. 앞서 생각지 못한 다른 방법을 적용할 수 있나?
5. 한눈에 보고 이해할 수 있나?
6. 결과나 방법을 다른 문제에도 적용할 수 있는가?
7. 해결방법의 성능을 향상 시킬 수 있는가?
8. 다른 사람들은 이 문제를 어떻게 해결했는가?

문제를 정해진 기간안에 해결하였다면, 우리는 이제 해결의 퀄리티를 높여야 한다!
해결의 해결의 해결까지 해보는 것이다!

⑥ 문제 해결 접근법

1. 문제를 위한 계획을 세운다.
2. 일반적인 문제 해결 패턴 (알고리즘 패턴) 을 습득한다.

⑦ 문제 해결 패턴

• Frequency Counter (빈도수 세기)
• Multiple Pointer
• Sliding Window
• Divide And Conquer (분할과 정복)
• Dynamic Programming
• Greedy Algorithm (탐욕 알고리즘)
• Back Tracking
• +…. 그외의 많은 패턴