[240108] 알고리즘 특강 01.자료 구조 & 파이썬 숙제

[알고리즘 특강 with 분석가 by 임정 튜터]

 

0. 자료 구조 (Data Structures)

- 자료의 효율적 접근과 수정을 가능하게 하는 구조.

- 각 자료형 특징에 맞춰 그릇에 담는 것이 필수적임

 

1. 배열 (Array)

- 연속된 데이터를 저장하는 자료 구조로 가장 직관적임. python의 list 개념과 유사

- 인덱스와 대응하는 데이터를 저장해 첫번째부터 상대적인 위치를 표현

- 검색 연산은 빠르지만, 데이터 추가/삭제 연산은 느림 

 

1) O(1): 검색 연산. 자료를 단 번에 찾음

2) O(N): 추가/삭제. 최악의 경우 자료를 찾기 위해 자료의 길이 만큼 시간 소요 

 

(cf) 효율적인 알고리즘 = 코딩을 잘 구현했다 = ① 시간 단축 ② 사용 메모리 감소 

 └ ① 자료형 길이 및 크기에 따라 시간복잡도가 높아짐  

 └ ① ② 자료형 마다 속도/메모리 등이 모두 상이 

    (ex. Numpy array 자료형: 1가지 타입 자료형만 받아서 속도가 빠름 / 숫자, 문자 섞여 있다면 문자로 통일)

 

2. 연결리스트(Linked List)

- 배열과 같이 연속된 데이터를 저장하기 위한 자료 구조

- 배열의 단점을 해결하기 위해 고안(배열보다 좋은 것은 아님)

- 배열과 반대로, 데이터 추가/삭제 연산은 빠르지만 검색 연산은 느림 

 

1) O(N): 검색 연산 (ex. 음악 플레이리스트에서 다음곡이나 이전곡 누르면서 찾는 거랑 비슷한 이치)

2) O(1): 추가/삭제 연산 

 

3. 큐와 스택

- 큐와 스택은 배열과 비슷한 자료형

- 일상에 적용되는 예가 많아서 개념 자체는 쉬움. 문제 난이도는 스택 > 큐 

- 큐(Queue)는 먼저 들어온 값이 먼저 나가는 것 (ex.줄서기)

- 스택(Stack)은 먼저 들어온 값이 나중에 나가는 것. 들어오는 게 push, 빼는 게 pop (ex.프링글스)

- 스택 문제 예시 

 

4. 해시 테이블(Hash Table)

- Key, Value 형태의 데이터를 검색이 쉬운 형태로 저장하는 자료 구조 
- 해시 함수를 통해 임의 길이를 가진 데이터를 고정된 크기로 인덱싱

- Key, Value로 이루어진 사전형 '자료형'으로 파이썬의 딕셔너리 형과 동일

- Hash Function을 활용해 하기와 같은 직관적인 형식의 자료 구조가 가능해짐
- Key가 주어지면, O(1) 시간만에 매칭되는 Value가 저장된 곳을 알려줌 (빠름!)

└ 검색 속도가 자료형 길이에 상관없이 매우 빠르게 진행됨 

- SQL 최적화 방법인 옵티마이저에도 해시 개념이 나옴

└ 옵티마이저는? SQL문 결과 도출 시, 최적의 실행 방법을 결정하는 역할을 하는 DBMS의 두뇌

- 기본 자료형별 시간복잡도 

└ 파이썬 기능별 시간복잡도 정보는 링크 참조 https://wiki.python.org/moin/TimeComplexity

구분	배열(Array)	큐(Queue)	스택(Stack)	해시 테이블(Hash Table)
데이터 검색	O(N)	O(N)	-	O(1)
데이터 추가	O(N)	O(1)	O(1)	O(1)
데이터 삭제	O(N)	O(1)	O(1)	O(1)
인덱스 접근	O(1)	-	-	-

(cf) 코드 작성 시 우선순위 

① (검색) 라이브러리 찾기

② (적용) 어떤 함수 혹은 메소드 사용할지 찾기

③ (생성) 자주 사용할 것 같으면 사용자 정의 함수로 만들기

④ (최적화) 대용량 데이터가 필요하다면 성능을 고려한 코드를 작성 or 요청하기

 

5. 트리(Tree)

- 계층적 구조를 갖는 데이터를 표현하는 자료 구조

- 루트(계층 최상위)를 기준으로 재귀적이고 비선형적인 구조 (그래프의 일종임)

- 주요 용어

 └ Node: 트리의 구성 요소

 └ Root: 트리의 최상위 Node

 └ Leaf Node: 트리의 최하위(가장 마지막) Node

 └ Level: 트리의 깊이 단계(마지막 레벨은 Depth)

 └ Subtree: 임의의 Node를 Root로 하는 트리 

- 트리의 종류: 일반트리, 이진트리, 이진 탐색 트리(Binary Search Tree), 힙(Heap) 등

- 트리의 연산: 추가/삭제, 순회(Trabersal, 탐색) 등

- 트리의 활용: 컴퓨터 OS 디렉토리 구조, 조직의 계측도, 결정트리, DB데이터 검색 등

 

6. 그래프(Graph)

- 연결 관계를 표현하는 자료 구조. 비선형적 구조

- 어떤 자료를 표현하는 정점(Vertex)들의 집합 V와 이를 연결하는 간선(Edge)들의 집합 E로 구성된 자료 구조

 

용어	설명
정점(Vertex)	그래프의 구성 요소(= Node)
간선(Edge)	정점(Vertex) 간 연결 관계
가중(Weight)	간선(Edge)의 크기가 있는 경우, 가중치값

 

- 그래프의 활용: 도로정보(최단 경로 탐색), 소셜 네트워크 관계망(인간관계 분석), 인터넷 네트워크망(전송 속도) 등  

 

 

#01. 배열 문제 

나누어 떨어지는 숫자 배열 https://school.programmers.co.kr/learn/courses/30/lessons/12910

#내 풀이
def solution(arr, divisor):
    answer = []
    for num in arr:
        if num % divisor == 0:
            answer.append(num)
        else:                       #pass는 생략해도 되는듯
            pass   
    if not answer:
        answer.append(-1)
    else:                           #역시 pass는 생략해도 되는듯  
        pass 
    answer = sorted(answer)      #sort는 return none, sorted는 return 
    return answer

#튜터님 풀이
def solution(arr, divisor):
    answer = []
    #1. for문으로 나누어 떨어지는 것(%==0) 계산
    for num in arr:
    	if num%divisor == 0: 
    	answer.append(num)
    #2.오름차순으로 정렬
    answer.sort
    
    # 3. element 없을 경우
    if len(answer) == 0:
    	answer.append(-1)
    return answer

 

(cf) 정렬방법: list.sort()와 sorted(list)의 차이점 

- list.sort() : list의 메소드로, list.sort() 형식으로 사용 가능. 리스트 원본 값을 직접 정렬하나 Return은 None. 쪼끔 빠름 

##sort 
a1 = [6, 3, 9]
a2 = a1.sort() #a2에 sort 정렬 
-----정렬 후-----
print(a1)  #[3, 6, 9] #원본 변경
print(a2)  #None      #반환 안함 
		   
#sort 출력 예시
#O
answer.sort() 
print(answer)  
#X #none으로 나옴 
print(answer.sort())

 

- sorted(list): literable 객체*를 파라미터로 받는 메서드(내장함수). 리스트 원본 값은 그대로 두고 정렬값을 Retrun 해줌 

* 반복 가능한 객체로, 대표적인 iterable 타입은 list, dict, set, str, bytes, tuple, range 등

##sorted
b1 = [6, 3, 9]
b2 = sorted(b1) #b2dp sorted 정렬 
-----정렬 후-----
print(b1) #[6, 3, 9] #원본유지
print(b2) #[3, 6, 9] #새로운 객체에 정렬 

#sorted 출력 예시
#O
answer = sorted(answer)
answer                   
#O
print(sorted(answer))

 

 

#02. 큐 문제

같은 숫자는 싫어 https://school.programmers.co.kr/learn/courses/30/lessons/12906

def solution(arr):
    answer = []
    answer.append(arr[0])    #무조건 포함되는 리스트의 맨 첫 숫자 먼저 넣기
    for num in arr[1:]:      #첫 번째 숫자를 이미 answer에 넣어두었으니 두 번째부터 반복문 시작
        if answer[-1] == num:  #새로 들어온 게 마지막 순서니까[-1]! num과 answer 끝수랑 비교 
            pass
        else:                  #answer에 포함된 마지막 숫자와 겹치지 않을 때만 변수 추가 
            answer.append(num)
    return answer

 

 

#03. 스택 문제 

올바른 괄호 https://school.programmers.co.kr/learn/courses/30/lessons/12909

#내 풀이 
def solution(s):
    answer = True
    bracket = []
    for c in s:
        if c == "(":           #Start! 열린 괄호 리스트에 추가
            bracket.append(c)
        elif not bracket:      #리스트가 미었다면(열린괄호 안 들어왔는데 다른게 들어왔다?) 
            return False       #혹시 닫힌 괄호가 먼저? 저리가 False
        else:                  #열린+닫힌 괄호 매칭되면 리스트에서 제외 
            bracket.pop()
    if not bracket:            #괄호 짝 맞추기 완료 후 리스트 비었으면 True
        return True
    else:                      #리스트에 짝 없는 괄호가 남았다면 False
        return False
    return answer

 

---

[파이썬 개인과제 & 알고리즘 특강 문제]

1) 어떤 문제가 있었나

파이썬 쿼리 작성시 함수를 적용하면 결과 값이 안 나오고, 함수를 빼면 값이 제대로 찍히는 문제가 반복됨 

2) 내가 시도해본 건 무엇인가

들여쓰기 위치 및 retrurn, print 등을 여러 위치에서 시행해보고, 함수를 다 빼고 줄줄이 작동 여부를 모두 체크도 해봄 

3) 어떻게 해결했나

튜터님께 문의를 통해, def로 함수 선언만 했지 실행 명령을 내리기 위해서는 마지막에 함수명을 출력해야 함을 알게 됨

4) 무엇을 새롭게 알았나

- 파이썬 문법을 고민하는 것도 중요하지만, 기본적으로 변수를 선언하고 최종 반환 및 출력해야 결과 값이 제대로 나옴 

- for문, if문 등을 활용해 문제 풀이 할 때 변수를 상수, 리스트 등 상황에 맞게 유연하게 활용 필요

└ 변수라면 계산식, 리스트라면 append(), remove() 등 합수와 합쳐서 쓰는 경우가 많은 듯