알고리즘 복습 1차(그리디, 구현, DFS/BFS, 정렬)

03. 그리디

실전문제 3) 1이 될 때까지

  1. N에서 1을 뺀다.

  2. N을 K로 나눈다.

n, k = map(int, input().split)
result = 0

# N이 K 이상이라면 K로 계속 나누기
while n >= k:
    while n % k != 0:
        # N이 K로 나누어 떨어지지 않는다면 N에서 1씩 빼기
        n -= 1
        result += 1
    # K로 나누기
    n //= k
    result += 1

    #마지막으로 남은수에 대하여 1씩 빼기
    While n > 1:
        n -= 1
        result += 1
    
    print(result)

10만 이상일 경우, 효율적으로 한번에 빼는 방식을 고려해봐야함.

주의) 몇번 더 봐야함!

#효울적으로 빠르게 접근하는 방식
n, k = map(int, input().split())
result = 0

While True:
    # (N == K로 나누어떨어지는 수)가 될 때까지 1씩 빼기
    target = (n//k) * k
    result += (n - target)

    if n < k:
        break
    result += 1
    n //= k # // 연산자 : 몫 , % 연산자 : 나머지


result += (n -1)
print(result)

 

04. 구현

실전문제 2) 게임 개발

 

05. DFS/BFS

실전문제 1) 음료수 얼려 먹기

 

06. 정렬

실전문제 3) 두 배열의 원소 교체

# 성적이 낮은 순서로 학생 출력하기
n = int(input())

array = []
for i in range(n):
    input_data = input().split()
    # 이름은 문자열 그대로, 점수는 정수형으로 변환하여 저장
    array.append((input_data[0], int(input_data[1])))

    array = sorted(array, key = lambda student: student[1])

    for student in array:
        print(student[0], end=' ')

[헷갈린 부분]

# 이름은 문자열 그대로, 점수는 정수형으로 변환하여 저장

array.append((input_data[0], int(input_data[1])))

[배우게 된 점]

append([원소1, 원소2]) 로 2차원 배열 만들기 가능
sorted(member, key=lambda x: x[0]) 는 member배열에서 안쪽 리스트의 0번째 원소를 기준으로 정렬

www.tcpschool.com/c/c_array_twoDimensional

코딩교육 티씨피스쿨