Problem solving 문제해결

Understand the Problem 문제 이해

Explore Concrete Examples 구체적 예시 살펴보기

우선적으로 해야할 일은 문제를 이해하는 것 입니다.

1. 문제를 여러분 방식대로 다시 생각할 수 있나요? 여러분만의 방식으로 바꿔서 질문이 무엇인지 실제로 이해하는 것입니다.
2. 문제가 어떤 입력값을 담고 있는가를 이해하는 건 정말 중요한 과정입니다.
3. 어떤 출력값이 나와야 할까요? 문제에 대한 해결책에서 나와야 할 결과는 무엇일까요?
4. 입력 값으로부터 출력값을 결정할 수 있나요? 즉, 문제를 해결하기에 충분한 정보가 있나요?
5. 문제의 일부인 데이터의 중요한 부분에 어떻게 라벨을 지정할 수 있을까요? 어떤 용어를 사용해야 좋을지 이 질문은 이 문제에서 정말 중요한 것이 무엇인가

예제) 두 숫자를 가지고 합계를 반환하는 함수를 작성할 것이다.

// 1. 이 문제를 여러분 방식대로 바꿀 수 있나요?
숫자를 더하거나 덧셈을 수행하는 함수를 작성하면 될 것이다.
// 2. 문제에 해당하는 입력값은 무엇인가요?
- int?
- float
- string? or large numbers?
// 3. 출력값의 형태는 어ㅏ떻게 될까요?
int, float, string
// 4. 입력값이 출력값을 결정할 수 있는지, 즉 문제를 해결하기에 충분한 정보를 가지고 있는지
// 5. 문제의 일부인 중요한 데이터의 라벨을 어떻게 지정해야할까요?
무엇이 중요한가에 대해 생각부터 해보자 - 현재 필요한 전부는 입력값과 출력값 두가지다

• 구체적 예시 알아보기

1. 예시를 떠올리는 것이 문제를 잘 이해하는 데 도움이 될 것이다.
2. 예시를 제공함으로써 우리는 코드가 예상한 대로 작동하는지 여부를 더욱 강력하게 검증할 수 있습니다. 예시를 사용하여 코드의 출력이 예상한 것과 일치하는지 확인할 수 있으며, 예외 상황에 대한 적절한 처리가 이루어지는지 확인할 수 있습니다. 예시는 코드를 검증하고 디버깅하는 데 유용한 도구입니다.
   예시 알아보는 법
3. 입력값과 출력값을 쉬운 예시를 두세 개 작성해봐
4. 더 복잡한 예시들을 작성해봐
5. 인풋값이 비어있을 경우
6. 유효하지 않은 값일 경우

문자열을 취하고 각 문자의 수를 반환하는 함수를 작성하라고 한다면!
일단 예시를 생각해보자 그래 ..charCount()함수를 작성한다하고
charCount(“aaaa”) // {a: 4} 이런식으로 입력과 반환이 될 거고
charCount(“hello”) // { h: 1, e: 1, l: 2, o: 1 } 이 예제는 이런식으로 될 것이다.

2. 더 복잡함 예시
   “my phone number is 158857” // 공백, 숫자, 특문 이런건 어떻게 해야할까?
   “Hello hi // 대 소문자는 어떻게 해야할까?

3. 비어있는 인풋을 주었을때
   charCount(“”) // 무엇을 반환해야할까요? Null? Undefined?, false? 뭘 해야힐ㄲ라 .. ㅣㅇ는 유요하지 않은 입력값이 주어진 예시를 살펴보는것과 관련있다 .4번!

4. Null, undefined 같은 갑슬 반환하면 어떡하냐 .. 이런 모든 종류의 경계조건들이 있다.

• 문제를 세분화 하자
  문제를 해결하겠단 말은 문제에 대한 단계들을 실제로 수행하면서 작성한다는 것이다.
  면접관에게 내가 밟아야할 단계들을 명확하게 작성해보이는걸 추천한다.

Ex) 주석으로 해야할 것들을 세분화해서 적어두자
function () {
// make object to return at end
// loop over string, for each character…
// 만약 char문자가 (문자/ 숫자)가 객체에 있다면 , 즉, 키로써 객체이 있다면 1을 더해주고 // 여기서 (문자/숫자)라고 적어준 이유는 공백과 특수문자를 제외시켜야하기 때문이다
// 만약 char문자가 (문자/ 숫자)가 객체에 없다면 추가하고 값을 1로 설정한다.
// 만약 char문자가 공백, 마침표 등과 같은 다른 것이라면 아무것도 하지 않는다.
// return object at end
}

적용하면
function () {
// make object to return at end
 var result = {};
// loop over string, for each character…
for( var i =0; i<str.length; i++) {
var char = str[i];
// 만약 char문자가 (문자/ 숫자)가 객체에 있다면 , 즉, 키로써 객체이 있다면 1을 더해주고
// result[char]가 0보다 크면 이미 객체에 있다는 의미이다. true를 반환함
if(result[char] > 0) {
}
}
// 만약 char문자가 (문자/ 숫자)가 객체에 있다면 , 즉, 키로써 객체이 있다면 1을 더해주고 // 여기서 (문자/숫자)라고 적어준 이유는 공백과 특수문자를 제외시켜야하기 때문이다
// 만약 char문자가 (문자/ 숫자)가 객체에 없다면 추가하고 값을 1로 설정한다.
// 만약 char문자가 공백, 마침표 등과 같은 다른 것이라면 아무것도 하지 않는다.
// return object at end
}

마지막으로 리팩터링
리팩터링 질문 나에게 하는 ㅇㅇ

• 결과를 확인할 수 있나요? (코드가 제대로 작동하는지)
• 결과를 다른 방식으로 도출할 수 있나요? (해결한 이 방법외에 생각난는 다른 접근방식 있니?
• 앞서 생각하지 못한 다른 방법을 적용할 수 있나요?
• 한눈에 보고 이해할 수 있나요?
• 그렇다면 해결책이 얼마나 직관적인가요?
• 결과나 방법을 다른 문제에도 적용할 수 있나요? 
문제를 해결함으로써 얻을 수 있는 큰 이점 중 하나는 직감을 발달시켜 다른 문제를 해결할 수 있는 직관력을 길러준다는 것 입니다.
  따라서, 해결책을 작성할 때마다 잠시 멈추고 이 해결책이나 이 문제가 이전에 접했던 다른 문제와의 유사점이 있는지를 자문해 보는것이 좋습니다.
• 해결책의 성능을 향상시킬 수 있나요? 
시간복잡도와 공간복잡도로 분석한다.

애너그램(Anagram) 패턴

Frequency Counter (횟수, 빈번, 빈도)
문자열 같은거 비교할 때 사용
문자가 그 안에 있는 경우 뿐만 아니라 안에 있는 문자들이 나타나는 정확한 횟수, 빈도가 정확한지 확인해야함

다중 포인터 패턴

정렬되있다는 조건하에 적용 만약 정렬이 안되있다면 존나 운 없는거 ㅠ ㅠ 화이팅!
이 패턴의 개념은 인덱스나 위치에 해당하는 포인터나 값을 만든 다음 특정 조건에 따라 중간지점부터 시작지점이나 끝 지점이나 양쪽 지점을 향해 이동시키는 것입니다.
결론적으로 말하면 배열이나 문자열과 같은 일종으의선형 구조 ex) [-4, -3, -2, -1, 0, 1, 2, 6, 8] “asosajdighfujeddsfkl” 한 쌍의 값이나 조건을 충족시키는 무언가
양 끝 지점은 반대방향 왼쪽, 오른쪽은 같은 방향으로 흘러가게 인덱스(기준점)을 잡고 움직인다 .그러면 for문 하나로 해서 O(N)이다 .. 예를들면 알맞는 쌍 찾기
싸용법
각각 0과 1 의 위치(index) 를 i, j 로 잡고 큰 값 쪽으로 이동하면서 첫 번째 포인터를 특정한 조건을 준다 즉, 일치하지 않는!
두 개의 고유 값을 찾는 경우에만 바꿔줍니다.

슬라이딩 윈도우 패턴

특정 방식으로 연속적인 배열이나 문자열과 같은 일련의 데이터를 입력하거나 해당 데이터의 하위 집합을 찾는 경우에 유용하다.
시작점 or 끝나는점 인덱스를 기준으로 설정하면 되겠네
Ex) [2,4,2,4,5,6,7,5,4,2,1,4], 5 가 주어질때 연속된 5개 숫자를 더해서 가장 큰 값을 구해라 하면
여튼 0번 부터 시작한다하면 loop는 i=0 시작이면 arr.length-5+1 까지다 ㅇㅇ .. 그래야 ㄷ마지막까지 딱 5개 더하니까 ㅇㅇ
근데 마지막 까지로 하고싶으면 일단 0부터 4번까지 5개 합계 구했다는 가정하게 시작을 i= 5 주고. i<arr.length 하게되면 이제 밑에서 방식이
sum - arr[i-num] + arr[i ] 해서 하면 됨 여튼 방식은
5개 합 구할때 0~4 인덱스 합 구하기 vs 1~5합 구하기 이런식으로 하면 계속 더하기가 발생하니
0~4 합 구하고 다음 창으로 이동하면 합에서 0번 인덱스 빼고 5번 인덱스 더해주면 됨 조금 씩 이동한다! 그러면 연산은 조금만 발생함

분할 정복 패턴
이진 탐색
어떤 특정한 값을 찾을떄는 탐색 하면 됳듯
여튼 이런거다 정렬이 된 기준임 ㅇㅇ 그래야 반 나눠서 하니까