[Megabyte School : AI 데이터 사이언티스트 취업 완성 과정] Day 40.

 

 

안녕하세요 늑대양입니다 :)

 

 

벌써 40일 차네요!!

 

 

다음 주 화요일까지 파이썬 기반 코딩테스트를 학습합니다!! 🤓

 

 

[AI 데이터 사이언티스트 취업 완성 과정]의 40일차 일과를 정리하여 안내해드리도록 하겠습니다.

 

 

 

늑대양 하늘원 버전!!

 

 

 

 

Day 40 시간표:

• 코딩테스트 사전학습 (예습)
• 파이썬 기반 코딩테스트
• 파이썬 기반 코딩테스트 (복습)

 

 

 

Day 40 온라인 학습 범위:

• 12강 + @
• 예상 학습 시간: 2:51:40 + @

대주제(Part)	중주제(Chapter)
Part2. 알고리즘 이론	01. 정렬 알고리즘 개요
Part2. 알고리즘 이론	02. 버블 정렬 - 1
Part2. 알고리즘 이론	03. 버블 정렬 - 2
Part2. 알고리즘 이론	04. 삽입 정렬
Part2. 알고리즘 이론	05. 선택 정렬
Part2. 알고리즘 이론	05. 병합 정렬 - 4
Part2. 알고리즘 이론	01. 이진 탐색 - 1
Part2. 알고리즘 이론	02. 이진 탐색 - 2
Part2. 알고리즘 이론	03. 이진 탐색 - 3
Part2. 알고리즘 이론	04. 순차 탐색
Part2. 알고리즘 이론	01. 탐욕 알고리즘의 이해
Part2. 알고리즘 이론	02. 탐욕 알고리즘 예제와 실습

 

 

 

파이썬 기반 코딩테스트

정렬, 그리디

선택정렬

• 선택정렬은 첫 번째 자료 위치에 첫 번째 자료부터 마지막 자료까지에서 가장 작은 값을 위치 시키고,
• 두 번째 자료 위치에 두 번째 자료부터 마지막 자료까지에서 가장 작은 값을 위치시 키는 이 과정을 계속 반복해서
• 오름차순 정렬을 시키는 정렬방법

def solution(nums):
    n = len(nums)
    for i in range(0, n - 1):
        minIndex = i
        for j in range(i+1, n):
            if nums[j] < nums[minIndex]:
                minIndex = j
        nums[i], nums[minIndex] = nums[minIndex], nums[i]
        # print(nums)
    return nums

nums = [2, 4, 5, 1, 3]


print(solution(nums))

> [1, 2, 3, 4, 5]

 

 

 

버블정렬

• 버블정렬은 인접한 두 자료를 비교하여 크기가 순서대로 되어 있지 않으면 두 자료를 교환하 는 방법으로 정렬하는 알고리즘
• 1회전이 끝나고 나면 가장 큰 자료가 맨 뒤에 위치(오름차순)

def solution(nums):
    n = len(nums)
    for i in range(n - 1):
        for j in range(n-i-1):
            if nums[j] > nums[j + 1]:
                nums[j], nums[j + 1] = nums[j + 1], nums[j]
        # print(nums)
    
    return nums

print(solution([5, 4, 2, 1, 3]))

> [1, 2, 3, 4, 5]

 

 

삽입정렬

• 삽입정렬은 배열의 모든 요소를 자신의 앞 자료까지 차례대로 이미 정렬된 배열 부분과 비교 하여,
• 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘

def solution(nums):
    n = len(nums)
    for i in range(1, n):
        for j in range(i, 0, -1):
            if nums[j-1] > nums[j]:
                nums[j-1], nums[j] = nums[j], nums[j-1]
            else:
                break
        # print(nums)
    
    return nums

print(solution([5, 4, 2, 3, 1]))

> [1, 2, 3, 4, 5]

 

 

교환횟수

원소값이 서로 다른 n개의 원소로 이루어진 nums 배열이 있습니다.

1. i=0으로 초기화하고 정렬알고리즘이 시작됩니다.
2. nums[i]부터 nums[n-1]까지의 최소값을 구합니다. minIndex는 최소값이 위치한 인덱스 번호라고 가정합니다.
3. i와 minIndex 값이 다르면 nums[i]와 nums[minIndex]의 값을 교환합니다.
4. i값을 1 증가시킵니다.
5. 2~4과정을 반복하면서 오름차순 정렬을 합니다.

매개변수 nums에 서로 다른 값으로 이루어진 배열이 주어지면 각 위치의 바뀐 횟수를 인덱스 번호 순으로 배열에 저장해 반환하는 프로그램을 작성하세요.

 

def solution(nums) : 
    n = len(nums)
    answer = [ 0 for x in range(len(nums))]
    
    for i in range(n - 1):
        minIndex = i 
        for j in range(i + 1, n): 
            if nums[minIndex] > nums[j]: 
                minIndex = j
        
        if i != minIndex:
            nums[i], nums[minIndex] = nums[minIndex], nums[i]
            
            answer[i] += 1
            answer[minIndex] += 1
                
    return answer

print(solution([4, 2, 5, 1, 3]))

> [1, 0, 1, 1, 1]

 

 

 

파이썬 sort 함수

1. 오름차순 정렬 : nums.sort() : 한 자리 숫자만 정렬
2. 내림차순 정렬 : nums.sort(reverse = True) 
3. 좌표정렬하기

 

# python sort 함수 사용법

# 1) [x, y]에서 x값에 의한 오름차순 정렬
def solution(nums):
    nums.sort(key = lambda v : (v[0]))
    return nums;

print(solution([[2, 3], [1, 4], [3, 1], [1, 2]));

> [[1, 4], [1, 2], [2, 3], [3, 1]]



# 2) [x, y]에서 y값에 의한 오름차순 정렬 
def solution(nums):
    nums.sort(key = lambda v : (v[1]))
    return nums;

print(solution([[2, 3], [1, 4], [3, 1], [1, 2]]);

> [[3, 1], [1, 2], [2, 3], [1, 4]]



# 3) [x, y]에서 x값에 의한 내림차순 정렬
def solution(nums):
    nums.sort(key = lambda v : (-v[0]))
    return nums;

print(solution([[2, 3], [1, 4], [3, 1], [1 ,2]]));

> [[3, 1], [2, 3], [1, 4], [1, 2]]



# 4) [x, y]에서 y값에 의한 오름차순을 하되 y값이 같은 경우는 x값에 따라 오름차순한다.
def solution(nums):
    nums.sort(key = lambda v : (v[1], v[0]))
    return nums;

print(solution([[2, 3], [1, 4], [3, 1], [1, 1]]));

> [[1, 1], [3, 1], [2, 3], [1, 4]]

 

 

 

카드 가져오기

현수와 영희는 카드게임을 합니다. 테이블에는 n개의 카드가 있습니다.n은 항상 짝수 개수입니다.
n개의 카드에는 자연수가 적혀 있습니다.
현수와 영희는 한 라운드에 1개의 카드를 가져갑니다. 총 n/2 라운드를 합니다.
n/2 라운드 결과 가져간 카드에 적힌 숫자의 총합이 게임의 점수이고 점수가 큰 사람이 이기 는 게임입니다.

현수는 Lady first 정신에 따라 매 라운드 영희가 먼저 카드를 가져가게 합니다.
대신 현수는 k번의 우선권을 가질 수 있습니다. 우선권을 쓰는 라운드에서는 현수가 먼저 카 드를 가져갑니다.
만약 카드에 적힌 숫자가 [7, 8, 5, 9, 3, 1, 3, 1, 1, 9] 이고, k=2이면

1. 첫 번째 라운드에서는 영희가 9를 가져가면 현수도 9를 가져가므로 우선권을 사용하지 않 습니다. 남은 카드는 [7, 8, 5, 3, 1, 3, 1, 1]입니다.
2. 두 번째 라운드에서 영희가 8를 가져가면 현수는 7를 가져갑니다. 남은 카드는 [5, 3, 1, 3, 1, 1]입니다.
3. 세 번째 라운드에서 영희가 5를 가져가고 현수가 3을 가져가야 하지만 현수는 우선권을 써 서 현수가 5를 가져가고 영희가 3을 가져갑니다. 남은 카드는 [1, 3, 1, 1]입니다.
4. 네 번째 라운드에서 우선권을 써서 현수가 3, 영희가 1를 가져갑니다. 남은 카드는 [1, 1]
5. 마지막 라운드에서 각자 1를 가져갑니다.

현수가 얻은 카드에 적힌 숫자의 총합은 9+7+5+3+1 = 25입니다 25는 k번의 우선권을 사용해 서 현수가 얻을 수 있는 최대 점수입니다.

매개변수 nums에 카드에 적힌 숫자가 주어지고, k가 주어지면 현수가 얻을 수 있는 게임의 최대 점수를 반환하는 프로그램을 작성하세요.

 

def solution(nums, k):
    answer = 0
    n = len(nums)
    nums.sort(reverse = True)
    diff = []
    for i in range(1, n, 2):
        answer += nums[i]
        diff.append(nums[i-1] - nums[i])
    
    diff.sort(reverse = True)
    for i in range(k):
        answer += diff[i]
        
    return answer

print(solution([7, 8, 5, 9, 3, 1, 3, 1, 1, 9], 2))
print(solution([8, 2, 12, 12, 12, 12, 2, 2], 2))

>25
34

 

 

 

 

그리디 (Greedy)

욕심쟁이

• 그리디 알고리즘은 탐욕법이라고도 하며, 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미
• 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구
• 그리디 알고리즘을 이용하면 매 순간 가장 좋아 보이는 것만 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 전혀 고려 X

 

예시 문제: 침몰하는 타이타닉

유럽에서 가장 유명했던 유람선 타이타닉이 침몰하고 있습니다. 유람선에는 N명의 승객이 타고 있습니다. 구명보트를 타고 탈출해야 하는데 타이타닉에 있는 구명보트는 2명 이하로만 탈 수 있 으며, 보트 한 개에 탈 수 있는 총 무게도 M kg 이하로 제한되어 있습니다.
N명의 승객 몸무게가 주어졌을 때 승객 모두가 탈출하기 위한 구명보트의 최소개수를 출력하는 프로그램을 작성하세요.

 

입력설명:
매개변수 nums에 N(5<=N<=200,000)명의 몸무게가 주어집니다. 매개변수 m에 M(70<=M<=10,000)이 주어집니다. 승객의 몸무게는 50이상 1,000이하 이며, 각 승객의 몸무게 는 M을 넘지는 않습니다.

 

출력설명:
구명보트의 최소 개수를 반환합니다.

 

매개변수 형식 1:
[90, 50, 70, 100, 60], 140

 

반환값 형식 1:

3

매개변수 형식 2:

[86, 95, 107, 67, 38, 49, 116, 22, 78, 53], 150

 

반환값 형식 2:

5

 

 

def solution(nums, m):
    answer = 0
    left = 0
    right = len(nums) - 1
    nums.sort()
    while left <= right:
        if nums[left] + nums[right] <= m:
            answer += 1
            left += 1
            right -= 1
        else:
            answer += 1
            right -= 1
    
    return answer

print(solution([90, 50, 70, 100, 60], 140))
print(solution([86, 95, 107, 67, 38, 49, 116, 22, 78, 53], 150))

>3
5

 

 

 

 

 

 

 

 

긴 글 읽어주셔서 감사합니다 😆