자료구조/ 알고리즘 특강: 2

구현 훈련하기 1

•  
• 다음과 같이 숫자로 이루어진 배열이 있을 때, 이 배열 내에서 가장 큰 수를 반환 하시오.

def find_max_num(array):
    max_num = array[0]
    for num in array:
        if max_num < num:
            max_num = num
    return max_num
a = find_max_num([1, 2, 3, 4, 5, 6, 7, 8, 9])
print(a)

구현 훈련하기 2

• 프로그램이 1~100 숫자 중 하나를 랜덤으로 정함.
• 사용자는 이 숫자를 찾추어야 함.
• 입력한 숫자보다 크면 UP 아니면 DOWN 정답이면 CORRECT 출력.
• 지금까지 숫자를 입력한 횟수를 알려줌.

import random


def game():
    correct = random.randint(1, 100)
    count = 0
    while True:
        print(f'현재 {count}번 시도')
        count += 1
        answer = int(input('정답을 입력해주세요'))
        if answer > correct:
            print('DOWN')
        elif answer < correct:
            print('UP')
        elif answer == correct:
            print('정답')
            break
    print(f'{count}번 만에 정답')


game()

리턴은 함수 실행을 멈추고 그 리턴 값을 쓸 수 있다.

break은 그 영역을 멈추게 한다.

 

스택 / 큐, 정렬

•  
• CS(Computer Science) 전반에 자주 등장 하는 자료구조
• 코테 빈출 유형

 

스택

• 한쪽 끝이 막혀 있는 통과 같은 구조
• push : 스택에 저장한다.
• pop: 스택에서 빼낸다.
• peek: 최근 자료를 볼 수 있다.
• 나중에 삽입된 데이터가 먼저 나오는 자료 구조 : 후입선출(last in first out , LIFO)

 

큐

• 양쪽 끝이 뚫려 있는 통과 같은 자료구조
• enqueue : 큐에 저장한다.
• dequeue: 큐에서 빼낸다
• 먼저 삽입된 데이터가 먼저 나오는 자료 구조: 선입선출(first in first out, FIFO)

 

스택/큐의 활용

자료구조/ 알고리즘이 어디에 어떻게 쓰이는지가 중요.

스택

• 데이터를 임시 저장 하고 싶을 때.
• 최근에 임시 저장한 데이터를 가장 먼저 활용해야 할 때
• 쌍을 맞추어 데이터를 임시 저장 하고 싶을 때
• 뒤로 가기 기능을 만들고 싶을 때
• 함수의 실행
• 문자열로 주어진 괄호가 쌍이 맞는지 검사. ( 를 만나면 push. ) 를 만나면 pop. 스택이 마지막에 비어있다면 올바른 괄호.

 

 

큐

• 데이터를 임시 저장하고 싶을 때
• 큐를 버퍼로 활용
• 임시 저장된 데이터를 차례차례 내보내야/꺼내와야 할 때
• 줄을 세우고 싶을 때
• 영화관 예약, 입장 순
• 변형 1: 원형. real가 원형을 돌면서 데이터를 넣는다. front가 real를 뒤따라 돌면서 데이터를 꺼낸다.
• 변형 2: 덱. 양쪽에서 데이터 삽입, 삭제가 가능한 큐
• 변형 3: 우선순위 큐. 순서 상관없이 우선순위를 정하고 그 순위가 높은 데이터가 먼저 나감.

 

정렬의 개념

데이터를 정해진 기준에 따라 재배치 하는 것.

• 다양한 정렬 알고리즘이 존재. 알고리즘 마다 성능이 다름.

sorted() : 배열의 값 자체를 조작하지는 않는다.

sort() : 배열의 값 자체를 조작한다.

• 정렬 알고리즘의 원리를 묻는 코테도 있기 때문에 알아야함.

삽입 정렬

앞에서부터 차례대로 비교하여, 자신의 위치를 찾아 삽입하는 방식

• 시간복잡도 O(n^2)

버블 정렬

• 요소를 쭉 순회
• 인접한 요소와 비교, 정렬이 제대로 되었는지 확인 정렬이 제대로 될 때까지 인접한 요소와 바꿔치기 하는 방법
• 시간복잡도 O(n^2)

선택 정렬

• 요소들 중 최소값 찾아 그 값을 맨 처음 값으로 대체.
• 맨 처음 값을 뺀 나머지 요소들이 정렬될 때 까지 반복.
• 시간복잡도 O(n^2)

퀵 정렬

• 분할 정복 알고리즘의 일종
• 큰 문제를 작은 문제로 분리하여 작은 문제를 해결함으로 큰 문제를 해결
• 이름처럼 빠른 정렬: 시간복잡도O(nlogn)
• 예외적으로 배열이 정렬되어 있는 경우: 시간 복잡도 (O^2)
• 내장 정렬 함수의 대부분의 원리가 되는 알고리즘

임의의 하나의 요소를 고른다. 이를 피벗(기준점) 이라고 한다.

피벗보다 작은 부분집합, 큰부분집합을 선정.

피벗의 좌우를 정렬한다.

피벗의 좌는 작은 부분 집합, 우는 큰 부분 집합

분할 된 두개의 작은 배열에 재귀적으로 이 과정을 반복.

재귀함수는 자기 자신을 호출하는 함수.

 

삽입 정렬, 버블 정렬, 선택 정렬을 실습을 통해 훈련하면 알고리즘 학에 큰 도움이 된다.