240907 TIL | 동시성 프로그래밍, 그리디 알고리즘, 예산

0. TIL

잘한 점: 토요일 아침 9시에 카페 출근해서 공부했다! 오홍

9~12시 스터디 완. 그리고 지금 오후 5시에 카페 2차 출석 ㅎㅎ

개선점 : 할 일이 밀려서 플랜이 엉망진창..!!! 얼른 정리+처리해서 계획적으로 할 일 하기..

배운 점: 그리디 알고리즘

1. 데일리 루틴  

  cs 공부

질문 : 동시성 프로그래밍의 개념과 iOS에서의 동시성 처리 방식에 대해 설명해주세요.

 

답변 :
동시성 프로그래밍의 개념
여러 작업을 동시에 효율적으로 처리하여 성능을 최적화하는 방식.

iOS 동시성 처리 방식
GCD (Grand Central Dispatch): 저수준 API로 작업 큐에 비동기 작업을 처리하며, 스레드 관리를 최적화.
Operation & OperationQueue: 고수준 동시성 작업 제어. 작업의 취소, 우선순위, 의존성 설정 가능.
Swift의 async/await: 비동기 작업을 동기 코드처럼 처리할 수 있어 가독성이 높고, 예외 처리가 용이.

고려 사항
UI 업데이트는 반드시 메인 스레드에서 수행.
스레드 안전성과 작업 취소 처리 필요.

---

  1일 1커밋

📜 문제 설명

S사에서는 각 부서에 필요한 물품을 지원해 주기 위해 부서별로 물품을 구매하는데 필요한 금액을 조사했습니다. 그러나, 전체 예산이 정해져 있기 때문에 모든 부서의 물품을 구매해 줄 수는 없습니다. 그래서 최대한 많은 부서의 물품을 구매해 줄 수 있도록 하려고 합니다.
물품을 구매해 줄 때는 각 부서가 신청한 금액만큼을 모두 지원해 줘야 합니다. 예를 들어 1,000원을 신청한 부서에는 정확히 1,000원을 지원해야 하며, 1,000원보다 적은 금액을 지원해 줄 수는 없습니다.
부서별로 신청한 금액이 들어있는 배열 d와 예산 budget이 매개변수로 주어질 때, 최대 몇 개의 부서에 물품을 지원할 수 있는지 return 하도록 solution 함수를 완성해주세요.

제한사항
d는 부서별로 신청한 금액이 들어있는 배열이며, 길이(전체 부서의 개수)는 1 이상 100 이하입니다.d의 각 원소는 부서별로 신청한 금액을 나타내며, 부서별 신청 금액은 1 이상 100,000 이하의 자연수입니다.budget은 예산을 나타내며, 1 이상 10,000,000 이하의 자연수입니다.

⌨️ 입출력 예

✏️ 나의 코드

import Foundation

func solution(_ d:[Int], _ budget:Int) -> Int {

    var arr = d.sorted(by: <)
    var num = budget
    
    var sum = d.reduce(0) { $0 + $1 }
    var count = 0
    
    if sum <= budget {
        return d.count
    }else{
            for i in arr {
                if num - i < 0 { break }
                num -= i
                count += 1
            }
        return count
    }
}

 

처음 마주한 문제점 :

for 문을 while문으로 감싸서 num - i < 0 이 되어도 반복문이 끝나지 않는 현상

-> 굳이 while을 쓰지 않고 for문 내부에서 if 로 처리 가능

 

📚 개선 코드

//가장 효율적인
func solution(_ d:[Int], _ budget:Int) -> Int {
    var remainingBudget = budget
    var count = 0
    
    for amount in d.sorted() {
        if remainingBudget < amount {
            break
        }
        remainingBudget -= amount
        count += 1
    }
    return count
}

// 내 기존 코드를 기반으로 한
func solution(_ d:[Int], _ budget:Int) -> Int {
    var arr = d.sorted(by: <)  // 신청 금액을 오름차순 정렬
    var num = budget
    var count = 0

    for i in arr {
        if num - i < 0 {  // 예산이 부족하면 종료
            break
        }
        num -= i
        count += 1
    }
    return count
}

 

개선 점 :

굳이 .reduce를 쓸 필요가 없었다 ㅎㅎ

그냥 for 문에서 buget - d (code : num -= i )로 그때그때 처리하기

 

그리디 알고리즘 

 

• 단계별 최선 선택: 각 단계에서 최적이라고 판단되는 선택을 하여 전체 문제를 해결.
• 근시안적 접근: 전체 문제를 한꺼번에 고려하지 않고, 부분적인 관점에서만 결정을 내림.
• 빠른 실행 속도: 많은 경우 그리디 알고리즘은 단순하고 빠르기 때문에 시간 복잡도가 낮음.
• 문제에 적합한 경우: 최적 부분 구조(문제를 부분 문제로 나누어도 그 부분 문제에서도 최적해가 동일한 성질)가 성립할 때 가장 효과적.

 

-> 이 문제에서는 금액을 오름차순으로 정렬하고 낮은 금액부터 구매하도록 함으로써 그리디 알고리즘 사용

 

문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/12982

---

  swift 강의

강의명 :