TIL 221114

1. 알고리즘에 대한 근원

왜 갑자기 이런 파트를 적게 되었는가?
알고리즘 공부를 하는 이유를 더 명확하게 하고 효율적으로 공부를 하기 위해.

왜 알고리즘을 배우는가?

• 취업하려고.
• 코딩테스트보려고.
• 코딩테스트 문제 뿐만아니라 개발을 하는 과정에서 문제를 해결할 때 더 멋지게 해결하려고.
• 바꿔말하면 이유가 있는 코드를 작성하려고.
• 자료구조에 대한 이해를 높이려고.
• 문제가 풀리는 순간이 재미있어서.

1) 알고리즘이란?

문제를 해결하는 절차나 방법을 자세히 설명하는 과정

결국에는 잘 하기 위해 문제에 접근하는법, 해결하는법을 패턴화시키고 이해하는수밖에 없다. 그래서 정리해 보고자 한다.

2) 문제 해결 접근법

[1] 문제의 이해

문제를 직면했을 때 즉시 문제를 해결해야 할 이유가 없다.
시간의 제약이 있더라도 문제를 이해하고 접근하는것이 훨씬 유리하다.
이해가 되지 않는다면 스스로에게 질문을 통해 조사를 진행할 수 있다.

• 문제를 내 방식대로 다시 생각할 수 있는가?
• 문제가 어떤 인풋을 담고 있는가?
• 문제에 대한 솔루션에서 나와야 할 아웃풋은 무엇인가?
• 입력값이 출력값을 결정할 수 있나?
  (문제를 해결할 충분한 정보가 주어졌는가)
• 문제의 일부인 데이터의 중요한 부분에 어떻게 라벨을 지정할 수 있나?

[2] 구체적인 입출력의 예시

• 간단한 예시로 시작해 볼 것.
• 그 이후 복잡한 예시를 진행 해 볼 것.
• 빈 값이 입력되면 어떻게 되는가?
• 유효하지 않은 값이 입력되면 어떻게 되는가?

[3] 세부사항 분석하기

• Pseudocode(의사코드)를 작성하는 단계.
• 자연어를 이용해 문장을 만들고, 코드화 시키면 된다.
• 의사코드의 틀을 꼭 따르지 않더라도, 그와 유사하게 문제의 해결법을 차례대로 나열해가 보면 몹시 도움이 많이 된다.

[4] 해결 / 단순화

• 작업에서 가장 어려운 부분을 마주하게 된다면,
• 잠시 무시하고 단순한 해결책을 작성한 다음 다시 어려운 부분을 통합시키기.

[5] 되돌아보기 및 리팩토링

• 결과를 확인할 수 있는가?
• 결과를 다른 방식으로 도출할 수 있는가?
• 한눈에 보고 이해할 수 있는가?
• 결과나 방법을 다른 문제에도 적용할 수 있는가?
• 해결책의 성능을 향상시킬 수 있는가?
• 코드를 향상시킬 수 있는 다른 방법을 떠울릴 수 있는가?
  (코딩 컨밴션을 지켰는가)
• 다른 사람들은 이 문제를 어떻게 해결했는가?

3) 알아두면 언젠가는 꼭 도움이 되는 문제 해결 패턴

아래 나오는 패턴들의 이름은, 공식적인 이름이 아닐 수 있습니다. 편의를 위해 강사님이 붙혀놓은 이름입니다.

• 빈도수 세기

def valid_anagram(str1,str2):
    if len(str1) != len(str2):
        return False
    temp_str1 = {}
    temp_str2 = {}
    for str in str1:
        if str not in temp_str1:
            temp_str1[str] = 1
        else:
            temp_str1[str] += 1
    for str in str2:
        if str not in temp_str2:
            temp_str2[str] = 1
        else:
            temp_str2[str] += 1
    
    if temp_str1 == temp_str2:
        return True
    else: return False
 # 각각 딕셔너리로 만들면, 이중for문으로 O(N^2)의 시간을 사용할 필요 없이 O(N)으로 끝낼 수 있다.
 # 더 간단한 풀이법이 있을 것 같은데, 파이썬에대한 숙련도가 낮아 지금은 이계 최선으로 보인다...

function validAnagram(str1, str2) {
  if (str1.length !== str2.length) {
    return false;
  }

  const tempStr1 = {};
  
  for (let str of str1) {
    if (!tempStr1[str]) {
      tempStr1[str] = 1;
    } else {
      tempStr1[str]++;
    }
  }

  for (let str of str2) {
    //js에서는 0 == false 이므로
    if (!tempStr1[str]) {
      return false;
    } else {
      tempStr1[str] -= 1;
    }
  }

  return true;
}

• 다중 포인터

def count_unique_values(arr):
    if len(arr) == 0:
        return print(0)
    curr = 0
    for i in range(1,len(arr)):
        if arr[curr] != arr[i]:
            curr += 1
            arr[curr] = arr[i]
    return print(curr+1)

function countUniqueValues(arr) {
  if (arr.length === 0) {
    return 0;
  }
  let curr = 0;
  for (let i = 1; i < arr.length; i++) {
    if (arr[curr] !== arr[i]) {
      curr++;
      arr[curr] = arr[i];
    }
  }
  return curr + 1;
}

• 슬라이딩 윈도우

def max_subarray_sum(arr,num):
    if len(arr) < num:
        return None
    temp_sum = 0
    max_sum = 0
    for i in range(0,num):
        max_sum += arr[i]
    temp_sum = max_sum
    for i in range(num, len(arr)):
        temp_sum = temp_sum - arr[i-num] + arr[i]
        max_sum = max(max_sum, temp_sum)
    return max_sum

function maxSubarraySum(arr, num) {
  let maxSum = 0;
  let tempSum = 0;
  if (arr.length < num) return null;
  for (let i = 0; i < num; i++) {
    maxSum += arr[i];
  }
  tempSum = maxSum;
  for (let i = num; i < arr.length; i++) {
    tempSum = tempSum - arr[i - num] + arr[i];
    maxSum = Math.max(maxSum, tempSum);
  }
  return maxSum;
}

• 분할과 정복
• 다이나믹 프로그래밍
• 그리디
• 백트레킹
• 등등....