7/22 학습일지 | 알고리즘을 위한 논리적인 사고력 기르기 실습

오늘은 간단하게 알고리즘과 자료구조에 대한 이론 설명을 듣고 사고력을 기르기 위한 훈련(?)을 했다. 문제를 해결하기 위해 알고리즘을 어떻게 짜야하는지, 규칙을 찾아내는 방법에 관한 것이였는데 이렇게 말하니 엄청 거창한 느낌이지만 실제로는 간단한 문제들을 풀어보는 시간이었다. (하지만 생각보다 간단하지 않았다. 중간 중간 막힌 부분이 있어서 막힌 걸 풀때까지는 엄청 답답했다.)

 

숫자 몇 개 나왔는지 빈도 구하기

그중 하나가 빈도수를 구하는 문제였는데, 리스트 안에 들어있는 숫자들의 빈도수를 출력하는 것이다. 첨에 n1, n2 랑 count1, count2가 어떻게 연결되는건지 잘 이해가 안갔는데 찬찬히 해보니 알겠다. 그냥 숫자 자체를 넘길 수 없어서 숫자의 위치를 변수로 지정해서 다시 표현한거였다. 

그리고 count의 개수는 숫자 중에서 가장 큰 값만큼이니까 0 * max(number) 값이 됨. 

numbers = [1,3,2,4,3,3,1,2]

def counting(numbers):
    max_number=max(numbers)
    cnt = [0] * max_number
    for number in numbers:
        cnt[number - 1] += 1
    for i in range(len(cnt)):
        print(f"{i+1}의 개수: {cnt[i]}개", "*"*cnt[i])

 

최대값과 최소값 찾기

numbers = [6,3,2,4,3,3,9,2]

def find_max_min(numbers):
    maximum = numbers[0]
    minimum = numbers[0]
    for number in numbers:
        if number > maximum :
            maximum = number
        if number < minimum :
            minimum = number
            
    return minimum, maximum

find_max_min(numbers)

처음에는 number의 n1, n2, n3... 위치에 따라 각각 다 비교해서 min, max 값을 갈아끼워주는 방법을 생각했는데, 그냥 아예 max와 min을 첫 번째 숫자로 정해놓고, 리스트 안에서 큰 게 나오기만 하면 바꾸고, 작은 게 나오기만 하면 바꾸는 방법이 더욱 간단! 

 

순차 검색하기

def searching(numbers, target):
    for i in range(len(numbers)):
        if numbers[i] == target:
            return i
    return -1

numbers = [5,1,4,2,3,10,50]
target = 50
print(f"{target}의 인덱스값은 {i}입니다.")

searching(numbers, target)

 

이진 검색하기

정렬된 배열이나 리스트에서 특정값을 효율적으로 찾기 위해 사용되는 알고리즘. left는 0, right는 인덱스 끝값을 주고, 중간값과 타겟을 비교해가며 찾는 과정이다. 

def binary_search(numbers, target):
    left=0
    right=len(numbers)-1
    while left <= right:
        mid = (left+right)//2
        if numbers[mid] == target:
            return mid
        elif numbers[mid] < target:
            left = mid+1
        else :
            right = mid-1
    return -1

numbers=[1, 2, 4, 7, 9, 11, 12, 15]
target=15

binary_search(numbers, target)

 

정렬하기

def selection_sort(numbers):
    for i in range(len(numbers)-1):
        for j in range(i+1, len(numbers)):
            if numbers[i] > numbers[j]:
                temp = numbers[i]
                numbers[i] = numbers[j]
                numbers[j] = temp
    return numbers

numbers=[13,1,7,2,10,22]
selection_sort(numbers)

 

랭킹 매기기

def whatismyrank(scores):
    n=len(scores)
    rank = [0] * n
    for i in range(n):
        r = 1
        for j in range(n):
            if scores[i] < scores[j]:
                r = r + 1
        rank[i] = r
    return rank

scores= [100, 10, 80, 5]
whatismyrank(scores)