gominzip / algorithm Goto Github PK

이번 주 알고리즘 🥔

정렬

📝 TO DO

• H-Index (정렬)
• 합승 택시 요금
• 소수 완제품 확률
• 점심 식사시간

~ 4주차 JS로 ~

• 연속된 부분 수열의 합
• 야근 지수
• 소수찾기
• 베스트앨범
• 방금그곡
• 단속카메라

🍟 비고

이번 주 알고리즘 🥔

최단경로 최소비용 - 크루스칼, 프림

크루스칼 (Kruskal)

• 최소신장트리를 구하는 알고리즘

  • 모든 정점을 최소 비용으로 연결하여 최소신장 트리를 구한다 (섬 연결하기)

• 시간복잡도

  • Union-Find 알고리즘은 O(1)으로, 간선을 정렬하는 로직이 전체 시간복잡도 좌우
  • 일반적인 퀵 정렬의 시간복잡도 **O(ElogE)**가 크루스칼의 시간 복잡도 (E : 간선 개수, V : 정점 개수)

• 구현 방법

  1. 모든 간선을 가중치 기준으로 오름차순 정렬
  2. 정렬된 간선 리스트를 순서대로 선택하여, 간선의 정점들을 연결
     1. 이때 정점을 연결하는 것을 Union-Find의 Union으로 구현
  3. 만약 간선의 두 정점 a,b가 이미 연결되어 있다면 스킵
  4. 위 과정을 반복하여 최소비용의 간선들만 이용하여 모든 정점이 연결됨

• 코드

  function find(x, parent){
      if (parent[x] == x) return x
      parent[x] = find(parent[x],parent)
      return parent[x]
  }
  function union(a, b, parent){
      const rootA = find(a,parent);
      const rootB = find(b,parent);
      
      if (rootB > rootA) parent[rootB] = rootA
      else parent[rootA] = rootB
  }
  function solution(n, costs) {
      var answer = 0;
      costs.sort((a,b)=>a[2]-b[2]);
      parent = [...new Array(n)].map((_,i)=>i);
      
      for (let i = 0; i<costs.length; i++){
          if (find(costs[i][0],parent) !== find(costs[i][1],parent)){
              union(costs[i][0],costs[i][1],parent);
              answer += costs[i][2]
          }
      }
      return answer;
  }

프림 (Prim)

• 최소신장트리를 구하는 알고리즘
  • 임의의 시작점에서 현재까지 연결된 정점들에서 연결되지 않은 정점들에 대해, 가장 가중치가 작은 정점을 연결하는 정점선택 기반으로 동작
  • 트리 집합을 단계적으로 확장
  • 새로운 정점에서 갈 수 있는 아직 연결되지 않은 정점들에 대한 간선을 추가
  • 우선순위 큐를 이용한 최소 힙으로 구현 (다익스트라와 유사)
• 시간복잡도
  • O(ElogV)
• 구현 방법
  1. 임의의 정점을 시작점으로 선택
  2. 시작점에서 갈 수 있는 정점 중 가장 가중치가 작은 정점을 연결함
  3. 2번 과정에서 시작점과 어떠한 정점들이 연결됨
     1. 시작점과 연결된 정점들을 a집합이라 할 때, a집합에서 갈 수 있는 a집합에 속하지 않은 정점들에 대해 가중치가 가장 작은 정점을 연결
  4. a집합의 크기가 늘어남(시작점을 포함한 a집합에 새로운 정점을 연결함) 위의 과정을 모든 정점이 연결될 때까지 반복

⇒ 그래프 내의 간선이 많은 경우는 프림 알고리즘, 간선이 적은 경우는 크루스칼 알고리즘이 유리~

📝 TO DO

주차 복습 & JS로 풀어보기

• [2주차] 삼각달팽이
• [2주차] 큰 수 만들기(그리디)
• [2주차] 메뉴 리뉴얼(카카오)
• [2주차] 전력망을 둘로 나누기(완전탐색)
• [2주차] 하노이의 탑(DP)
• [5주차] 섬 연결하기
• [5주차] 배달
• [6주차] 보석 쇼핑
• [6주차] 시소 짝꿍
• [6주차] 징검다리 건너기 - 이분탐색
• [6주차] 가장 먼 노드
• [6주차] 파일명 정리
  ~ 추가 문제 ~
• 같은 숫자는 싫어
• K번째 수
• 모의고사
• 실패율

🍟 비고

이번 주 CS 🥔

• 네트워크

📝 TO DO

• 작업순서
• 양궁대회

~ 기존 3주차 JS ~

• 이중우선순위 큐
• 네트워크
• 124나라의 숫자

🍟 비고

• 여유 있으면 자료구조 문제도 풀어보기

이번 주 알고리즘 🥔

Divide & Conquer (분할정복)

💡 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병해 문제의 답을 얻는 알고리즘

대표적인 예 ) 정렬 알고리즘 중 퀵 정렬, 합병 정렬, 이진 탐색, 선택 문제, 고속 푸리에 변환(FFT)

분할정복 설계

이 프로세스는 작게 분할한 문제가 직접 해결 가능할 만큼 충분히 작아질 때까지 재귀적으로 계속됨

1. Divide (분할)

   : 원래 문제가 분할하여 비슷한 유형의 더 작은 하위 문제로 분할이 가능할 때까지 나눈다

2. Conquer (정복)

   : 각 하위 문제를 재귀적으로 해결한다. 하위 문제의 규모가 나눌 수 없는 단위가 되면 탈출 조건을 설정하고 해결한다.

3. Combine (결합)

   : Conquer한 문제들을 통합하여 원래 문제의 답을 얻어 해결한다.

❗️Divide를 제대로 나누면 Conquer과정은 자동으로 쉬워진다. Divide를 잘 설계하는 것이 중요!!

분할정복 장단점

• 장점
  1. 빠른 속도 : 전체 문제를 해결하는 데 걸리는 시간을 줄일 수 있음
  2. 쉬운 병렬화 : 하위 문제를 병렬로 처리하기 쉬우므로 멀티코어 시스템에서 성능을 크게 향상할 수 있음
  3. 유연성 : 여러 응용 분야에 사용될 수 있음. 문제의 복잡도와 데이터 크기에 상관없이 적용할 수 있음
  4. Top-down 재귀방식으로 구현하기 때문에 코드가 직관적
• 단점
  1. 추가적인 메모리 요구 : 재귀적으로 호출되므로 많은 추가적인 메모리를 필요로 할 수 있음
  2. 최악의 경우 시간복잡도 : 일부 문제에 대해선 최악의 경우에도 빠른 해결책을 제공하지 못할 수 있음
  3. 구현의 복잡성: 구현이 비교적 복잡

시간복잡도 : 평균의 경우 O(NlogN)

📝 TO DO

• 디스크 컨트롤러 (Heap)
• 입국심사 (이분탐색)
• 보물상자 비밀번호
• 홈 방범 서비스 (BFS)
• 최적경로 (심심해서 추가로)

~ JS 문제 (기존 1주차) ~

• 모음사전 (완전탐색)
• 더 맵게 (Heap)
• 주차요금 (카카오)
• 주식가격 (스택/큐)
• 오픈채팅방 (카카오)
• 가장 큰 수 (정렬)

🍟 비고

• SW Expert Academy 코테 시작