자료구조 1주차_알고리즘과 친해지기

자료구조 1주차_알고리즘과 친해지기

 

editor : Pycharm

파이썬 : Python 3.8 

---

최대값 구하기

 

📄 내 풀이(강의 풀이2와 동일)

input = [3, 5, 6, 1, 2, 4]

def find_max_num(array):
    max = array[0]
    for num in input:
        if max < num:
            max = num
    return max


result = find_max_num(input)
print(result)

 

 

📄 강의 풀이1

def find_max_num(array):
    for num in array:
        for compare_num in array:
            if num < compare_num:
                break
        else:
            return num

num 3일때, 3 통과 5(3 < 5) 불통 break

num 5일때, 3 통과 5통과 6(5<6) 불통 break

num 6일때, 3 통과 5 통과 6통과 1통과 2통과 4통과 

 

for문이 다 돌 때까지 break없이 실행되었으므로 else문으로 이동!

num값 반환.

---

최빈값 구하기

 

활용한 힌트

 

📌 문자인지 확인

print("a".isalpha())    # True
print("1".isalpha())    # False

띄어쓰기(빈 문자열)을 넘어가기 위해 알파펫 여부 확인!

 

📌 배열 초기화

alphabet_occurrence_array = [0] * 26

26개 알파벳 빈도수 저장하기 위해 0으로 초기화 된 배열생성

 

📌 python char to ascii code

# 내장 함수 ord() 이용해서 아스키 값 받기
print(ord('a'))               # 97
print(ord('a') - ord('a'))    # 97-97 -> 0
print(ord('b') - ord('a'))    # 98-97 -> 1

 

📌 python ascii code to char

chr(97) // 'a'
chr(ord('a') + 3) // 'd'

 

 

📄 나의 풀이(강의 풀이 2와 유사)

input = "hello my name is sparta"


def find_max_occurred_alphabet(string):
    alphabet_occurrence_array = [0] * 26

    for character in string:
        if character.isalpha():
            alphabet_occurrence_array[ord('a') - ord(character)] += 1
        # print(alphabet_occurrence_array)

    max = alphabet_occurrence_array[0]
    for i in alphabet_occurrence_array:
        if max < i:
            max = i
    return chr(ord('a') + i)


result = find_max_occurred_alphabet(input)
print(result)

 

📄 강의 풀이1

def find_max_occurred_alphabet(string):
    alphabet_array = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s",
                      "t", "u", "v", "x", "y", "z"]
    max_occurrence = 0
    max_alphabet = alphabet_array[0]

    for alphabet in alphabet_array:
        occurrence = 0
        for char in string:
            if char == alphabet:
                occurrence += 1

        if occurrence > max_occurrence:
            max_alphabet = alphabet
            max_occurrence = occurrence

    return max_alphabet


result = find_max_occurred_alphabet
print("정답 = a 현재 풀이 값 =", result("Hello my name is sparta"))
print("정답 = a 현재 풀이 값 =", result("Sparta coding club"))
print("정답 = s 현재 풀이 값 =", result("best of best sparta"))

---

알고리즘 실시간 특강

 

알고리즘 맛보기 #2

 

📌 문제

1~100 중 랜덤 숫자 하나를 정하였습니다. 과연 당신이 맞출 수 있을까요?!
숫자 입력: 50
DOWN
숫자 입력:25
DOWN
숫자 입력:10
UP
숫자 입력:15
DOWN
숫자 입력:13
UP
숫자 입력:14
CORRECT
숫자 입력한 횟수: 6회

 

📄 나의 풀이

import math

input_value = 97

def find_number(input):
    start = 1
    end = 100
    # goal = 0

    while start <= end:
        mid = (start + end) / 2

        if input < mid:
            end = math.trunc(mid - 1)
        elif input > mid:
            start = math.trunc(mid + 1)
        elif input == mid:
            # goal = mid
            break
    return math.trunc(mid)

result = find_number(input_value)

실시간 강의 문제 잘못보고 이분탐색인지 알고 풀었다.

하지만, 이 풀이 테스트 케이스 돌리니 경계값 오류가 뜬다 ㅠㅠㅠ

start와 end 역전되는 순간(경계)에서 값 설정을 해줘야 할듯 하다.

이 부분도 추가적으로 공부해야 할 듯하다. 검색해보니 백준 나무자르기 문제로 친절하게 설명해주신 분이 계신다!!

일단 1주차 강의를 다 듣고 주말에라도 이해해 보려고 노력해야겠다.

 

📄 특강 듣고 다시 푼 내 풀이

random_num = 78

def find_num(target):
    count = 1

    while True:
        num = int(input('숫자 입력 : '))

        if num < target:
            print('UP')
        elif num > target:
            print('DOWN')
        else:
            print('CORRECT')
            break
        count += 1

    return print(f'숫자 입력한 횟수 : {count}')

find_num(random_num)

 

📌 코드 오류? 의문점(None 반환)

처음에 result = find_num(random_num) 하고 print(result)라고 출력했는데, 제대로 작동하나 마지막에 None을 자꾸 리턴했다.

그래서 찾아보니 print를 반환하는 함수인데 이 함수를 print명령어로 출력하니 자동으로 None을 반환하는 거라고 한다.

그래서 고치니 None이 반환되지 않아서 신기했다.

 

튜터님 풀이를 봤는데, 튜터님은 1~100까지 숫자 중 랜덤하게 값이 나오도록 코드를 짜셨다.

import random

answer = random.randint(1, 100)

그리고 함수를 사용하지 않고 반복문으로 푸셨다.

random값을 주는 법을 알고 넘어가면 좋을 듯 하다.

---

 

알고리즘 맛보기 #3

 

📌 문제

# 문제의 번호별 조건에 대한 입력 예시와 출력
Ex 1)
abc 	# a1/b1/c1

Ex 2-1)
aaabbbc	# a3/b3/c1

Ex 2-2)
abbbc	# a1/b3/c1

Ex 3-1)
ahhhhz	# a1/h4/z1

Ex 3-2)
acccdeee	# a1/c3/d1/e3

 

접근방법이 그려지지 않았다. 앞에 이분탐색을 좀 붙잡고 있기도 했지만,

숫간 알파벳 빈도값 풀듯이 배열을 만들어야 하나 했지만, 문제를 자세히 보니 정렬된 알파벳이었다. 

바로 옆 값을 비교하면서 보면 좋겠다. 싶었는데, 배열 index 초과 오류가 발생!! ㅠㅠ

 

강의를 다 듣고 튜터님 코드 로직까지 이해한 뒤 풀어보았다.

이해했으니 술술 풀릴 줄 알았는데... 꽤 오래 걸렸다.

 

📄 내가 푼 풀이

input = 'acccdeee'

def alphabet_count(string):
    n = len(string)
    count = 1
    result_str = ''

    for i in range(n-1): #for(int i=0; i<n; i++)
        if string[i] == string[i+1]:
            count += 1
        else:
            result_str += string[i] + str(count) + '/'
            count = 1
    result_str += string[i+1] + str(count)
    return result_str

print(alphabet_count(input))

첫번째 인덱스와 두번째 인덱스 비교 :  같다면, count를 늘려주고 다르면, 결과 result_str에 이어붙이고 count 초기화

두번째 인덱스와 세번째 인덱스 비교 : ...

이런식으로 진행하다보면 결국 마지막인덱스와 (마지막인덱스 + 1)을 비교하게 되어 배열 초과 에러가 발생!

문자열 인덱스를 벗어나는 (마지막인덱스 + 1) 값은 없으므로 반복문을 n-1까지만 돌아줘야 한다.

 

값이 바뀔때마다 result_str에 넣어주니 마지막 반복되는 값이나 마지막 반복되지 않는 값이 result_str에 포함되지 않아 당황. 마지막값을 넣어주기 위해 string[i]도 넣어보고 string[i+1]도 넣어줘 결과값을 비교해봤다.

string[i+1]이 문자열 배열의 마지막 값을 의미하므로 이 값을 넣어줘야 했다.

 

튜터님 코드 설명을 듣고 풀다보니 count 초기값을 1로 해줬냐, 0으로 해줬냐의 차이만 있고 큰 차이는 없었다.

주말에 다시 풀어보는 시간을 가져야할 것 같다.