나의 개발일지 TIL(Today I learned) - 알고리즘 특강 및 복습

Today I learned

• 강창민 튜터님의 알고리즘 특강
• 배열을 이용한 알고리즘 복습

 

강창민 튜터님의 알고리즘 특강

프로그래머는 생각할 수 있는 알고리즘 중에 어떤 게 최선의 알고리즘인지를 찾아내는 능력이 필요하다!

알고리즘이 왜 필요한가? 좋은 프로그램을 만들기 위해서 좋은 프로그램을 만들기 위해 꼭 필요한 자료구조와 알고리즘

알고리즘은 Computational thinking(컴퓨팅 사고) 능력을 극대화할 수 있는 과목이다!

알고리즘은 처음에 누구에게나 어렵다 시간이 걸려도 천천히 확실하게 꾸준히 공부하자!

중요한 건 꺾이지 않는 마음이다!

 

우리는 node.js를 배우는 반인데 왜 파이썬을 배우고 파이썬으로 알고리즘을 하는가?

파이썬은 어떤 언어에 비해서 짧은 코드로 빠르게 짤 수 있다 코딩 테스트는 시간과의 싸움이라고 생각하면 짧은 코드로 빠르게 짤 수 있는 게 중요하다!

파이썬은 문자열을 다루는 방법이 사기적이라 무조건 좋다

 

알고리즘 맛보기 #1

최댓값 구하기!

def find_max_num(array):
    max_num = array[0]
    
    for num in array: 
        if num > max_num: 
            max_num = num 
            
    return max_num


print("정답 = 6 / 현재 풀이 값 = ", find_max_num([3, 5, 6, 1, 2, 4]))
print("정답 = 6 / 현재 풀이 값 = ", find_max_num([6, 6, 6]))
print("정답 = 1888 / 현재 풀이 값 = ", find_max_num([6, 9, 2, 7, 1888]))

 

알고리즘 맛보기 #2

UP & DOWN 게임

import random

def up_down(random_num):
    cnt = 0
    while True:
        input_num = int(input())
        cnt += 1
        if input_num == random_num:
            print("CORRECT")
            return f"숫자 입력한 횟수: {cnt}"
        elif input_num < random_num:
            print("UP!")

        elif input_num > random_num:
            print("DOWN!")


random_num = random.randrange(1, 100)
print(up_down(random_num))

 

알고리즘 맛보기 #3

문자열 요약하기

def summarize_string(target_string):
    n = len(target_string)
    count = 0
    result_str = ''

    for i in range(n - 1):
        if target_string[i] == target_string[i + 1]:
            count += 1
        else:
            result_str += target_string[i] + str(count + 1) + '/'
            count = 0

    result_str += target_string[n - 1] + str(count + 1)

    return result_str


input_str = "acccdeee"

print(summarize_string(input_str))

이 문제는 문제를 이해하기까지 시간이 걸렸다 연속된 문자를 요약한다고 생각하면 된다

이 알고리즘 코드는 연속된 문자가 있는 문자열이 아니라면 비효율적이다

1일차 알고리즘 수업은 여기까지다 가볍게 알고리즘에 대해서 설명해 주셨다 내일은 2일 차 알고리즘 수업인데
더욱 어려워진다고 하셨다 그래도 최대한 쉽게 설명해 주신다고 하셔서 괜찮을거 같다

 

알고리즘 복습

배열을 배우고 배열을 이용한 알고리즘을 백준 문제를 통해서 복습을 진행했다

 

배열을 이용한 알고리즘 문제를 보자

10808번: 알파벳 개수

def alphabet_numbers(string):
    count_lits = [0] * 26

    for i in string:
        count_lits[ord(i) - 97] += 1

    for i in count_lits:
        print(i, end=" ")


alphabet_numbers("baekjoon")

배열을 이용해서 알파벳의 개수를 담을 그릇을 만들고 아스키코드 a인 97을 이용해서 해당 알파벳이 나오면

알파벳의 그릇에 개수를 +1 증가시켜준다 시간 복잡도는 O(N)이다 배열을 사용하지 않으면 O(N^2)의 시간 복잡도로 풀어야 하지만 배열을 사용하면 O(N)의 시간 복잡도로 더 효율적인 코드를 만들 수 있다

 

2577번: 숫자의 개수

def number_of_numbers():
    result = 1
    numbers = [0] * 10

    for _ in range(3):
        input_num = int(input())
        result *= input_num

    while result > 0:
        numbers[result % 10] += 1
        result //= 10

    for i in numbers:
        print(i)

number_of_numbers()

배열을 이용해서 0~9까지의 개수를 담을 수 있는 그릇을 만들고 입력받은 값으로 만든 숫자가 0이거나 작을 때까지

반복해서 10으로 나눈 나머지의 숫자 그릇에 1 증가시키고 비교할 숫자를 다시 10으로 나눈 몫으로 바꾸면서 반복한다

배열을 사용해 시간 복잡도를 O(N)으로 효율적인 코드를 작성했다

 

1475번: 방 번호

def room_number():
    input_num = int(input())
    numbers = [0] * 10

    while input_num > 0:
        numbers[input_num % 10] += 1
        input_num //= 10

    nine_six = numbers[6] + numbers[9]
    if nine_six % 2 == 0:
        numbers[6] = nine_six // 2
        numbers[9] = nine_six // 2

    else:
        numbers[6] = (nine_six + 1) // 2
        numbers[9] = (nine_six + 1) // 2

    answer = max(numbers)

    print(answer)

room_number()

0 ~ 9번까지 한 세트에 하나씩 들어있으니 배열을 이용해서 필요한 숫자의 개수를 구하면 세트의 최솟값을 구할 수 있다

여기서 중요한 부분이 있다 9, 6은 뒤집어서 서로가 될 수 있다 그렇기에 사용 숫자의 개수를 구하고 반으로 나누면 된다

배열로 0 ~ 9까지 그릇을 만들고 숫자의 개수를 구하고 9, 6은 더한 후 짝수면 2로 나누어 몫을 구하고 홀수면 반올림해야 하기 때문에 몫에 +1 해준다 모든 숫자의 개수를 구하고 제일 많이 사용된 숫자를 찾으면 세트의 최솟값을 구할 수 있다

시간 복잡도는 O(N)이다

 

3273번: 두 수의 합

def sum_of_two_numbers():
    n = int(input())
    a = list(map(int, input().split(" ")))
    x = int(input())
    num_list = [0] * 2000001
    answer = 0

    for i in a:
        if num_list[x - i] == 1:
            answer += 1

        num_list[i] = 1

    print(answer)

sum_of_two_numbers()

x의 배열 그릇을 만들어서 입력된 숫자와 더해서 x값이 되는 숫자가 나왔었는지 확인하고 있으면 만족하는 쌍의 개수를 증가시킨다 그리고 해당 숫자는 있는 숫자이니까 1을 해준다 이런 식으로 입력된 숫자 리스트를 처음부터 돌려보면서
배열 안에 자신과 쌍의 숫자가 존재하는지 확인하고 증가시켜주거나 다음 숫자로 넘어가면 된다

자연스럽게 예외를 처리하기 위해 1 ≤ x ≤ 2000000의 범위를 보고 한 번에 최댓값의 배열을 잡았다

시간 복잡도는 O(N)이다

 

10807번: 개수 세기

def count_strength():
    N = int(input())
    input_numbers = list(map(int, input().split(" ")))
    v = int(input())
    numbers = [0] * 201

    for i in input_numbers:
        numbers[i + 100] += 1

    print(numbers[v + 100])

count_strength()

v는 -100보다 크거나 같으며, 100보다 작거나 같다. 라는 조건이 있어서 -100 ~ 100까지의 숫자의 개수를 담을 수 있게

201의 길이의 배열을 준비해두고 반복문을 돌려 해당 숫자의 그릇에 1 증가시켜주는데 여기서 음수의 값을 해결하기 위해
100을 더한 인덱스에 위치한 그릇을 찾아 1 증가시켜줬다 그리고 개수를 다 구한 후 v를 이용해 해당 숫자의 개수를 찾을 때도 100을 더해서 찾는다 시간 복잡도는 O(N)이다

 

13300번: 방 배정

def room_assignment():
    student_list = [[0] * 7 for _ in range(2)]
    answer = 0

    N, K = map(int, input().split())

    for i in range(1, N + 1):
        S, Y = map(int, input().split())
        student_list[S][Y] += 1

    print(student_list)
    for i in range(2):
        for j in range(1, 7):
            answer += student_list[i][j] // K

            if student_list[i][j] % K:
                answer += 1
    
    print(answer)

room_assignment()

이 문제는 성별 남자와 여자로 나누고 학년으로 나눈 후 한 방에 정해진 인원수로 방이 몇 개 필요한지 구하는 문제이다

배열을 이용해서 남자 여자를 담을 그릇과 학년을 담을 그릇을 2중 배열로 준비한다

입력받은 배열에 1씩 증가시켜 학생의 수를 센다 모든 학생의 수를 센 다음 그릇을 채웠으면 각 배열의 값에다가

제한 인원수를 나누어 필요한 방의 개수를 구하고 딱 나누어 떨어지지 않을 경우 방이 하나 무조건 더 필요하기 때문에

조건문으로 남은 인원이 있나 확인 후 방하나를 추가한다 시간 복잡도는 아래 반복문은 정해져 있는 상수이기에 제거한다면 위 반복문 N만 남는다 O(N) 인가?

 

11328번: Strfry

def strfry():
    N = int(input())

    for i in range(N):
        array = [0] * 26
        s1, s2 = map(str, input().split())

        for c in s1:
            array[ord(c) - 97] += 1

        for c in s2:
            array[ord(c) - 97] -= 1

        isPossible = True
        for i in array:
            if i != 0:
                isPossible = False

        if isPossible:
            print("Possible")
        else:
            print("Impossible")

strfry()

이 문제는 첫 번째 문자열과 두 번째 문자열을 비교해서 서로 재배열이 되는지 확인하는 문제이다

배열로 알파뱃 그릇을 만들고 첫 번째 문자열부터 알파뱃의 개수를 증가시키고

두 번째 문자열로 알파뱃의 개수를 제거한다

알파뱃 그릇이 모두 비었다면 서로 재배열이 가능하다 이 문제도 시간 복잡도가 O(N)인가?

 

1919번: 애너그램 만들기

def create_anagram():
    array = [[0 for _ in range(26)] for _ in range(2)]
    s1 = input()
    s2 = input()
    answer = 0

    for c in s1:
        array[0][ord(c) - 97] += 1

    for c in s2:
        array[1][ord(c) - 97] += 1

    for i in range(26):
        answer += abs(array[0][i] - array[1][i])

    print(answer)

create_anagram()

이 문제는 첫 번째 문자열의 알파뱃 그릇과 두 번째 문자열 알파뱃 그릇을 만들어 알파뱃수를 센 다음

각 알파뱃의 차이를 구한다 차이를 구하기 때문에 음수가 나올 수 있어서 abs함수로 절댓값으로 만들어 버린다

그러면 제거해야 할 알파뱃을 구할 수 있다 이것도 시간 복잡도는 O(N)인 거 같다

8가지의 문제를 풀었는데 하루가 가버렸다 별로 안풀었는데 생각보다 어렵다 알고리즘 친해지려면 시간 좀 걸리겠다

 

오늘의 느낀 점

자료구조와 알고리즘은 매우 중요하니까 포기하지말고 꾸준하게 공부를 하자 오늘은 하루 종일 8문제 푼 거 같은데

점점 더 빠르게 풀 수 있도록 계속 알고리즘과 친해지자 혹시나 시간이 없을 때는 무조건 1문제라도 풀어서

알고리즘을 옆에 끼고있어야겠다