[코딩테스트] 이것이 취업을 위한 코딩테스트다 2

정렬

데이터를 특정한 기준에 따라서 순서대로 나열

Selection Sort

가장 작은 원소를 제일 앞에 배치. $O(N^2)$

Insertion Sort

가장 앞의 원소를 그 이전에 정렬되어 있는 배열에 삽입하는 정렬. $O(N^2)$

Quick Sort

첫 값을 기준으로 작은 데이터와 큰 데이터를 각각 찾아 변경. 교차 시 두개로 분할. $O(N\cdot logN)$

Count Sort

메모리 사용. 테이블 이용해 정렬. $O(N+K)$, $K$ 는 최대값.

파이썬 정렬 라이브러리 $O(N \cdot log \space N)$

1. 정렬 라이브러리로 풀 수 있는 문제
   • 위에서 아래로

     import sys
     
     def solution(arr_):
         arr_.sort(reverse=True)
         return arr_
     
     if __name__ == "__main__":
         n = int(sys.stdin.readline())
         arr_ = [0] * n
         for idx in range(n):
             arr_[idx] = int(sys.stdin.readline())
         print(*solution(arr_))

2. 정렬 알고리즘의 원리에 대해서 물어보는 문제
   • 성적이 낮은 순서로 학생 출력하기

     import sys
     
     def solution(arr_):
         arr_.sort(key=lambda x: x[1])
         ans = [arr_[idx][0] for idx in range(len(arr_))]
         return ans
     
     if __name__ == "__main__":
         n = int(sys.stdin.readline())
         arr_ = [[] for _ in range(n)]
         for idx in range(n):
             arr_[idx] = sys.stdin.readline().split()
             arr_[idx][1] = int(arr_[idx][1])
         print(*solution(arr_))

3. 더 빠른 정렬이 필요한 문제
   • 두 배열의 원소 교체

     import sys
     
     def solution(n, k, A, B):
         A.sort()
         B.sort(reverse=True)
         for i in range(k):
             if B[i] > A[i]:
                 A[i] = B[i]
             else:
                 break
         return sum(A)
     
     if __name__ == "__main__":
         n, k = map(int, sys.stdin.readline().split())
         A = [int(x) for x in sys.stdin.readline().split()]
         B = [int(x) for x in sys.stdin.readline().split()]
     
         print(solution(n, k, A, B))

---

이진 탐색

Sequential Search 특정 데이터를 처음부터 하나씩 확인. $O(n)$

Binary Search 정렬된 데이터에서 시작점, 끝점, 중간점 이용해 확인. $O(log \space n)$

• 코드

  import sys
  
  def binary_search(arr_, target, lo, hi):
  		arr_.sort()
      while lo <= hi:
          mid = (lo+hi) // 2
          val = arr_[mid]
  
          if val > target:
              hi = mid - 1
          elif val < target:
              lo = mid + 1
          else:
              return mid
      return None
  
  if __name__ == "__main__":
      n, target = map(int, sys.stdin.readline().split())
      arr_ = list(map(int, sys.stdin.readline().split()))
      result = binary_search(arr_, target, 0, n-1)
      if result is None:
          print("None value")
      else:
          print(result + 1)

이진 트리 자료구조

부모 노드보다 왼쪽 자식 노드가 작고, 오른쪽 자식 노드가 큰 트리 구조.

이진 탐색을 자연스럽게 수행할 수 있음.

문제

• 부품 찾기

  import sys
  
  def solution(n, m, items, requests):
      items.sort()
      for req in requests:
          if bin_search(items, req, 0, n-1):
              print("yes", sep=" ")
          else:
              print("no", sep=" ")
  
  def bin_search(arr_, target, lo, hi):
      while lo <= hi:
          mid = (lo + hi) // 2
          val = arr_[mid]
          if val < target:
              lo = mid + 1
          elif val > target:
              hi = mid - 1
          else:
              return True
      return False
  
  if __name__ == "__main__":
      n = int(sys.stdin.readline())
      items = list(map(int, sys.stdin.readline().split()))
      m = int(sys.stdin.readline())
      requests = list(map(int, sys.stdin.readline().split()))
      solution(n, m, items, requests)

• 떡볶이 떡 만들기

  import sys
  
  def solution(n, m, arr_):
      arr_.sort()
      lo, hi = 0, arr_[n-1]
      ans = -1
      while lo <= hi:
          mid = (lo + hi) // 2
          val = 0
          for item in arr_:
              val += (item - mid) if item > mid else 0
          if val >= m:
              ans = mid
              lo = mid + 1
          else:
              hi = mid - 1
      return ans
  
  if __name__ == "__main__":
      n, m = map(int, sys.stdin.readline().split())
      arr_ = list(map(int, sys.stdin.readline().split()))
      print(solution(n, m, arr_))

---

동적 프로그래밍

메모리 공간을 약간 더 활용해서 연산 속도를 비약적으로 증가시키는 방법 중 하나.

피보나치 수열을 재귀함수로 푸는 경우 중복해서 계산하는 부분이 많음. → Memoization(cacheing) 기법을 사용 / DP 테이블

• Top-down

  # top down - recursive function
  d = [0] * 100
  
  def fibo(x):
      if x == 1 or x == 2:
          return 1
      elif d[x] != 0:
          return d[x]
      else:
          d[x] = fibo(x-1) + fibo(x-2)
          return d[x]
  
  print(fibo(99))

• Bottom-up

  # bottom-up: DP table
  d = [0] * 100
  d[1] = d[2] = 1
  n = 99
  
  for i in range(3, n+1):
      d[i] = d[i-1] + d[i-2]
  
  print(d[n])

문제

• 1로 만들기

  import sys
  
  def solution(x):
      dp = [0] * (x+1)
  
      for i in range(2, x+1):
          dp[i] = dp[i-1] + 1
          if i % 5 == 0:
              dp[i] = min(dp[i], dp[i//5] + 1)
          if i % 3 == 0:
              dp[i] = min(dp[i], dp[i//3] + 1)
          if i % 2 == 0:
              dp[i] = min(dp[i], dp[i//2] + 1)
  
      return dp[x]
  
  if __name__ == "__main__":
      x = int(sys.stdin.readline())
      print(solution(x))

• 개미 전사

  import sys
  
  def solution(n, foods):
      dp = [0] * n
      dp[0] = foods[0]
      dp[1] = max(foods[0], foods[1])
      for i in range(2, n):
          dp[i] = max(dp[i-1], dp[i-2] + foods[i])
      return dp[-1]
  
  if __name__ == "__main__":
      n = int(sys.stdin.readline())
      foods = list(map(int, sys.stdin.readline().split()))
      print(solution(n, foods))

• 바닥 공사

  import sys
  
  def solution(n):
      dp = [0] * (n+1)
      dp[1] = 1
      dp[2] = 3
      for i in range(3, n+1):
          dp[i] = dp[i-1] + 2*dp[i-2]
  
      return dp[-1] % 796796
  
  if __name__ == "__main__":
      n = int(sys.stdin.readline())
      print(solution(n))

• 효율적인 화폐 구성

  import sys
  
  def solution(n, m, coins):
      coins.sort()
      dp = [-1] * (m + 1)
      dp[0] = 0
      for coin in coins:
          for val in range(coin, m+1):
              if dp[val - coin] != -1:
                  dp[val] = dp[val - coin] + 1
  
      print(dp)
      return dp[-1]
  
  if __name__ == "__main__":
      n, m = map(int, sys.stdin.readline().split())
      coins = [0] * n
      for idx in range(n):
          coins[idx] = int(sys.stdin.readline())
      print(solution(n, m, coins))