[TIL] 2021.08.30 - 2021.09.05

todo

• programmers level 1-2 문제 풀기

  • TODO: 42860 43162, 43164
  • DONE: 12917, 12918, 12919, 12925, 12928, 12930, 12939, 12940, 12943, 12985, 12933, 42889, 42839, 43105, 64065, 67256, 70128, 76501, 84512

• programmers 10,000등 -> 11,765등 (해결한 문제수: 54)

• 백준 알고리즘 문제 풀기

  • TODO: 그래프와 BFS, DFS+BFS 필수 문제, 다이나믹 프로그래밍

    7569, 9205, 13023, 13549, 14226, 2225, 9465, 11054, 13398, 15990, 15988, 16194

    • 복습 1208, 2206, 2309, 15650

  • DONE: 1261, 2468, 2644, 5014, 10974, 14002

• 다익스트라 알고리즘 정리 포스트: 1753
• 최소신장트리: 프림 알고리즘
• Class101 비즈니스 영어 1-3장 복습 (60문장)
• Class101 비즈니스 영어: 미팅&컨퍼런스 콜하기, 판매추이 및 마케팅 관련 보고 하기

What I learned

• 정수 내림차순 배치

  String(n.toString().toCharArray().sortedArrayDescending()).toLong()
  

• python list empty check

  lst = []
  if lst:
    print("list not empty")
  else:
    print("list empty")
  

• BFS: 1) 몇 번만에 도착했는지 파악 쉬움 2) 도착했을 때 횟수가 최소임을 보장함 (너비우선)

• 순열 템플릿 코드 42839

  val set = hashSetOf<String>()
  permutation("", numbers, set)
  
  fun permutation(str1: String, str2: String, set: HashSet<String> ) {
    if (str1.isNotEmpty()) {
      set.add(str1)
    }
    for (i in 0 until str2.length) {
      permutation(str1 + str2[i],
                  str2.substring(0, i) + str2.substring(i + 1), set)
    }
  }
  

• BFS 문제에서 visited = [] 대신에 steps = [0] * (N+1) 를 사용하여 해당 위치까지 이동하는 최소 step을 구할 수 있다. (참고: 2644, 5014)

  def bfs(graph, start, end):
    need_visit = deque([start])
    while need_visit:
        node = need_visit.popleft()
        if node == end:
            return steps[node]
  
        for n in graph[node]:
            if steps[n] == 0:
                steps[n] = steps[node] + 1
                need_visit.append(n)
    return -1
  
  graph = [[] for _ in range(N+1)]
  steps = [0] * (N+1)
  

• CI/CD

  • CI (Continous Integration): 작은 단위의 주기적이고 빈번한 Merge / 스크립트로 자동 Build / 스크립트로 자동 Test
    • 기대효과: 작은 단위의 문제가 빠르게 발견 -> 코드 퀄리티와 생산성 UP
  • CD (Continous Delivery/Deployment): 수동(자동) 배포.
  • 참고: 드림코딩 by 엘리

• arr에 “Kim”이 있는 index 찾기: arr.indexOf("Kim") (12919)

• BFS 문제에서 먼저 방문이 필요한 경우, appendleft() 로 큐의 제일 앞에 넣는다. (노래방 우선예약이 생각났다) need_visit.appendleft((nx, ny, sum)) # 0인 곳을 우선 방문하기 위함 1261

• 중간 결과값은 Long 형을 고려해보기. (약 20억) 12943

• String 이 숫자로만 구성되었는지 체크: s.all { it.isDigit() } 12918

• 최소공배수를 구할 때, oveflow가 발생할 수 있기 때문에 (A/gcd(A, B)) * B 로 수행.12940

• 최대공약수: 유클리드호재법 -> gcd(a, b) == gcd(b, a%b)

  fun gcd(a: Int, b: Int) : Int {
    if(a%b==0) return b
    return (b, a%b)
  }
  

Life

알고리즘 문제풀기 계획을 조금 무리하게 잡아서 todo 가 꽤 남기는 했지만, 열심히 공부한 한주라 뿌듯하다 :)

영어 스피킹 강의도 새로 시작했는데, 재미있다!