🐷전동준(Jeon DongJun)

Go with the flow

[알고리즘 특강]자료구조/알고리즘 특강 요약 1일차

자료구조

자료구조의 개념

  • 자료를 효율적으로 관리하는 방법(요리 전 재료를 다듬는)
  • 컴퓨터 프로그래밍 언어에서 효율적인 자료(데이터)의 형태

자료구조의 종류

  1. 단순 자료구조(정수, 실수, 문자, 문자열)
  2. 선형 자료구조(리스트, 스택, 큐)
  3. 비선형 자료구조(트리, 그래프)
  4. 파일 자료구조(순차 파일, 색인 파일, 직접 파일)

선형 자료구조

1) 선형리스트

선형 리스트란?

  • 맛집이나 마트에서 줄을 서는 것 처럼 데이터를 일정한 순서로 나열한 것

선형 리스트의 개념

  • 데이터를 일정한 순서로 나열한 자료구조
  • 순차 리스트(Ordered List)라고도 함
  • 선형 리스트는 입력 순서대로 저장하는 데이터에 적당

선형 리스트의 예

  • 카톡으로 연락 온 친구를 배열을 이용하여 표현
  • 파이썬의 리스트를 생각하면 안된다. 배열이며 따닥따닥 붙어있다.

선형 리스트 구현

전역변수 선언부

katok = [] # 카톡으로 연락이 많이 온 순서로 배열을 만들기 위해

함수 선언부

  1. 선형 리스트에 데이터를 추가하는 함수(마지막 위치에)
def add_data(friend):
    katok.append(None) # 빈칸 추가
    kLen = len(katok) # 선형리스트의 길이를 구한다.
    katok[kLen-1] = friend # 가장 마지막 위치에 친구를 추가
  1. 원하는 위치에 친구를 추가하는 함수
def insert_data(position, friend):
    katok.append(None) # 빈칸 추가
    kLen = len(katok) # 선형리스트의 길이를 구한다.
    for i in range(kLen-1, position, -1): 
        # 배열의 마지막부터 순차적으로 지정한 위치까지 반복
        katok[i] = katok[i-1] # 뒤쪽으로 데이터를 당겨줌
        katok[i-1] = None # 당겨진 자리에 자리를 비워준다
    katok[position] = friend # 그 자리에 데이터를 추가
  1. 원하는 위치의 데이터를 삭제하는 함수
def delete_data(position):
    katok[position] = None # 지정 위치
    kLen = len(katok) # 리스트의 길이를 구함
    for i in range(position+1, kLen, 1): 
        # position이 3이라면, 4부터 리스트의 끝까지 1씩 증가 반복
        katok[i-1] = katok[i] # 지정한 자리로 뒤에있는 값을 안쪽으로 밀어줌
        katok[i] = None # 옮겨준 뒤 빈 공간을 None으로 
    del(katok[kLen-1]) # 빈 공간이 맨 뒤로 밀려나면 그 때 그것을 삭제

메인 코드부

  1. 소규모 데이터로 직접 자료구조를 만들 때
# 선형리스트에 값들을 추가하는 함수 사용
add_data('다현')
add_data('정연')
add_data('쯔위')
add_data('사나')
add_data('지효')
add_data('모모')

insert_data(3, '미나') # 3 위치에 미나를 추가

delete_data(4) # 4위치에 있는 사나가 지워짐

print(katok)

['다현', '정연', '쯔위', '미나', '지효', '모모']
  1. 함수를 사용해 추가, 삽입, 삭제하는 프로그램 구현
if __name__ == '__main__':
    
    while True:
        
        select = int(input('선택하시오(1: 추가, 2: 삽입, 3: 삭제, 4: 종료) : '))
        
        if select == 1:
            data = input('추가할 데이터 : ')
            add_data(data)
            print(katok)
            
    
        elif select == 2:
            pos = int(input('삽입할 위치 : '))
            data = input('추가할 데이터 : ')
            insert_data(pos, data)
            print(katok)
            
        elif select == 3:
            pos = int(input('삭제할 위치 : '))
            delete_data(pos)
            print(katok)
            
        elif select == 4:
            print(katok)
            break
        else:
            print('잘 못 입력하셨습니다.1~4 의 숫자를 입력하세요.')
            continue

선택하시오(1: 추가, 2: 삽입, 3: 삭제, 4: 종료) : 1
추가할 데이터 : 동준
['다현', '정연', '쯔위', '미나', '지효', '모모', '동준']
선택하시오(1: 추가, 2: 삽입, 3: 삭제, 4: 종료) : 1
추가할 데이터 : 박진영
['다현', '정연', '쯔위', '미나', '지효', '모모', '동준', '박진영']
선택하시오(1: 추가, 2: 삽입, 3: 삭제, 4: 종료) : 2
삽입할 위치 : 0
추가할 데이터 : 수지
['수지', '다현', '정연', '쯔위', '미나', '지효', '모모', '동준', '박진영']
선택하시오(1: 추가, 2: 삽입, 3: 삭제, 4: 종료) : 3
삭제할 위치 : 7
['수지', '다현', '정연', '쯔위', '미나', '지효', '모모', '박진영']
선택하시오(1: 추가, 2: 삽입, 3: 삭제, 4: 종료) : 4
['수지', '다현', '정연', '쯔위', '미나', '지효', '모모', '박진영']

2) 단순 연결 리스트

단순 연결 리스트란?

  • 방문할 맛집을 지도에 순서대로 연결한 것처럼, 떨어진 곳에 위치한 데이터를 화살표료 연결한 것

단순 연결 리스트의 개념

  • 노드들이 물리적으로 떨어진 곳에 위치
  • 각 노드의 번지도 순차적이지 않음
  • 화살표로 표시된 연결(링크, Link)을 따라가면 선형 리스트의 순서와 같음

단순 연결 리스트의 원리

  • 노드구조
    • 단순 연결 리스트는 다음 데이터를 가리키는 링크가 더 필요
    • 노드(Node)는 데이터와 링크로 구성된 항목
  • 데이터를 삽입/삭제할 때
    • 선형 리스트는 많은 작업이 필요(오버헤드 발생)
    • 단순 연결 리스트는 해당 노드의 앞뒤 링크만 수정하면 되므로 오버헤드가 거의 발생하지 않음
  • head = 가장 첫 노드
  • pre = 현재 작업하고 있는 노드의 바로 직전 노드
  • current = 현재 작업하고 있는 노드

단순 연결 리스트 구현

전역변수 선언부

  1. 노드를 저장할 메모리(연결리스트) 생성
  2. 연산에 필요한 각 노드 None으로 지정
  3. 데이터 배열 생성(데이터는 수백, 수천, 수만가지일 수도 있다.)
memory = []
head, current, pre = None, None, None
dataArray = ['다현','정연','쯔위','사나','지효','동준','JYP']
# dataArray는 현재 정해진 요소 뿐만이 아니라 수백, 수천, 수만가지일 수도 있다.

함수 선언부

  1. 노드를 만드는 함수
class Node():
    def __init__(self): # 초기화
        self.data = None # 노드의 데이터 값
        self.link = None # 노드를 연결해주는 화살표(링크)
  1. 노드들을 출력해주는 함수(단순 연결 리스트 출력)
def printNodes(start):
    current = start # 지정한 노드를 현재 작업 노드로 설정
    print(current.data, end = ' ') # 해당 데이터 값을 출력
    while current.link != None: # 노드의 링크가 None(끝 값)이 아니면
        current = current.link # 노드의 링크노드가 현재노드로 변환
        print(current.data, end= ' ') # 또 다시 해당 데이터값 출력
    print()
  1. 삽입하는 함수
def insertNode(findData, insertData): # 삽입하는 함수
    global memory, head, current, pre # 전역변수를 불러옴
    
    # 첫 노드 앞에 삽입(헤드를 이용)
    if findData == head.data: # 찾는 함수가 헤드(연결리스트의 첫)
        node = Node() # 새 노드를 생성
        node.data = insertData # 적어준 값을 노드의 값으로
        node.link = head # 기존의 헤드가 생성한 노드의 링크로
        head = node # 생성한 노드가 헤드 노드로
        return
    
    # 두번째 노드 이후 앞에 삽입
    current = head # 찾는 값이 head가 아니므로 현재 작업 노드를 head로
    while current.link != None: # 끝 값이 나올 때 까지
        pre = current # 현재 작업 노드가 이전 작업 노드로
        current = current.link # 링크 노드가 현재 작업 노드로
        if current.data == findData: # 현재 노드의 값이 찾는 값이라면
            node = Node() # 노드를 생성하고
            node.data = insertData # 입력한 값을 데이터로 지정
            node.link = current # 현재 작업 노드를 링크노드로
            pre.link = node # 이전 작업 노드의 링크노드를 생성한 노드로 지정
            return
    
    # 마지막 노드 삽입
    node = Node()
    node.data = insertData
    current.link = node
    return
  1. 삭제하는 함수
def deleteNode(deleteData): # 삭제하는 함수
    global memory, head, current, pre
    
    # 첫 노드를 삭제할 때
    if deleteData == head.data: # 삭제할 값이 첫 노드의 데이터라면
        current = head # 첫 노드를 현재 작업노드로
        head = head.link # 첫 노드의 링크노드를 첫 노드로
        del(current) # 현재 작업 노드 삭제
        return
    
    # 두번째 이후를 삭제
    current = head
    while current.link != None:
        pre = current
        current = current.link
        if current.data == deleteData:
            pre.link = current.link
            del(current)
            return
  1. 단순히 데이터를 찾는 함수
def findNode(findData): # 찾는 함수
    global memory, head, current, pre
    current = head
    if current.data == findData:
        return current # 노드를 통째로 돌려줌
    
    while current.link != None:
        current = current.link
        if current.data == findData:
            return current
    
    return Node()

메인

node = Node()
node.data = dataArray[0]
head = node 
# '다현'이라는 데이터를 가진 첫번째 노드를 head로 지정
memory.append(node)

for data in dataArray[1:] : # 0번은 헤드로이미 지정했기 때문에
    pre = node
    node = Node()
    node.data = data
    pre.link = node
    memory.append(node)

printNodes(head)

다현 정연 쯔위 사나 지효 동준 JYP 

insertNode('다현', '화사') # 헤드 노드인 다현 앞에 화사가 추가되어 화사가 헤드가 된다.
printNodes(head)

화사 다현 정연 쯔위 사나 지효 동준 JYP 

insertNode('사나', '솔라') # 헤드 노드가 아닌 사나 앞에 솔라가 추가
printNodes(head)

화사 다현 정연 쯔위 솔라 사나 지효 동준 JYP 

insertNode('재남', '문별') # 재남이 존재하지 않아서 문별이 마지막에 추가
printNodes(head)

화사 다현 정연 쯔위 솔라 사나 지효 동준 JYP 문별 

deleteNode('화사')
printNodes(head) 
# head였던 화사가 잘 사라짐, 그리고 다현이 head 노드로 변경

다현 정연 쯔위 솔라 사나 지효 동준 JYP 문별 

deleteNode('쯔위')
printNodes(head) # 쯔위가 잘 지워짐

다현 정연 솔라 사나 지효 동준 JYP 문별 

deleteNode('재남')
printNodes(head) # 재남이 원래 없기때문에 변화가 없음.

다현 정연 솔라 사나 지효 동준 JYP 문별 

fNode = findNode('솔라')
print(fNode.data)

솔라

fNode = findNode('쯔위') # 쯔위가 아까 삭제되어 없기때문에 
print(fNode.data) # None을 출력

None

3) 원형 연결 리스트

원형 연결 리스트란?

  • 시작 위치와 다음 위치가 계속 이어진 후 마지막에 다시 시작으로 돌아오는 형태(ex: 전국 일주)

원형 연결 리스트의 개념

  • 단순 연결 리스트와 구조, 구현 코드가 상당히 유사
  • 리스트 형태가 원(Circle) 형태로 구성(계속 회전하면서 사용 가능)
  • 오버헤드가 발생하지 않음

요약

: 단순 연결 리스트에서 맨 끝 노드의 링크가 head인 경우로 생각하면 된다.

4) 스택(Stack)

스택 구조란?

  • 아이스크림 콘에 여러가지 맛을 쌓을 때, 가장 먼저 넣은 맛을 가장 나중에 먹을 수 있는 구조

스택 개념

  • 스택 자료구조는 한쪽 끝이 막힌 형태
  • 입구가 하나이기 때문에 먼저 들어간 것이 가장 나중에 나오는 구조
  • 선입후출(FILO), 후입선출(LIFO)

스택 원리

  • 스택 기본 구조
    • 스택에 데이터를 삽입하는 작동 : push
    • 스택에 데이터를 추출하는 작동 : pop
    • 스택에 들어 있는 가장 위의 데이터 : top

스택 구현

전역 변수 선언부

SIZE = 5
stack = [None for _ in range(SIZE)] # 스택의 크기를 SIZE로 지정
top = -1 # 스택이 비어있는 상태(바닥 상태라 생각하자)

함수 선언부

  1. 스택이 꽉 찼는지 확인하는 함수
def isStackFull():
    global SIZE, stack, top # 전역변수를 불러온다.
    if (top >= SIZE-1): # 내용물의 머리가 통과 같거나 크다면
        return True # 스택은 꽉찬거다(진실)
    else:
        return False # 아니라면 빈 공간이 있다.(거짓)
  1. 스택이 비어있는지 확인하는 함수
def isStackEmpty(): # 스택이 비었는지 확인하는 함수
    global SIZE, stack, top # 전역 변수 불러옴
    if (top <= -1): # 만약, 내용물의 머리가 바닥과 같거나 작다면
        return True # 스택은 텅텅 비어있다.
    else:
        return False
  1. 스택에 데이터(내용물)을 넣어주는 함수
def push(data): # 스택에 데이터를 넣어주는 함수
    global SIZE, stack, top # 전역 변수 호출
    if isStackFull(): # 만약 스택이 꽉찼다면
        print('스택이 가득찼습니다.')
        return # 아무일도 없다.
    top += 1 # 꽉차지 않았다면 내용물의 머리의 높이가 1 높아짐
    stack[top] = data # 해당 위치에 데이터 값을 넣어줌
  1. 스택에서 데이터 꺼내기(추출하기)
def pop():
    global SIZE, stack, top
    if isStackEmpty(): # 스택이 비었다면,
        print('스택이 텅텅 비었습니다.')
        return # 아무일도 없다.
    data = stack[top] # 맨 위의 내용물을 추출
    stack[top] = None # 추출한 자리 비우기
    top -= 1 # 내용물의 머리의 높이가 1 낮아짐
    return data # 추출 데이터 반환
  1. 가장 위의 내용물이 무엇인지(추출 예정인 데이터)를 알아보는 함수
def peek(): # 맨 위에 뭐있는 확인하는 함수
    global SIZE, stack, top
    if isStackEmpty():
        print('스택이 텅텅 비었어유')
        return
    return stack[top]

메인

1) push
push('커피1')
push('커피2')
push('커피3')
push('커피4')
push('커피5')
print(stack)
push('커피6') # SIZE가 5이기 때문에 커피 5까지만 들어감.

['커피1', '커피2', '커피3', '커피4', '커피5']
스택이 가득찼습니다.
2) pop
returnData = pop()
print('팝 --->', returnData)
returnData = pop()
print('팝 --->', returnData)
returnData = pop()
print('팝 --->', returnData)

print(stack)


팝 ---> 커피5
팝 ---> 커피4
팝 ---> 커피3
['커피1', '커피2', None, None, None]
3) peek
print('다음에 빠질 것은?',peek())

다음에 빠질 것은? 커피2

5) 큐(Queue)

큐란?

  • 기차가 터널에 들어가는 순서대로 터널을 빠져나오고, ATM기에서 줄을 선 순서대로 예금을 인출하는 것처럼 큐는 먼저 들어간 것이 먼저 나오는 구조를 의미

큐의 개념

  • 큐(Queue) 자료 구조는 입구와 출구가 따로 있는 원통 형태
  • 스택(Stack)은 선입후출(FILO), 큐는 선입선출(FIFO)

큐의 원리

  • 구조와 용어
    • 큐에 데이터를 삽입하는 작동 : enQueue(인큐)
    • 데이터를 추출하는 작동 : deQueue(데큐)
    • 저장된 데이터 중 첫 번째 데이터 : front(머리)
    • 저장된 데이터 중 마지막 데이터 : rear(꼬리)
  • 꼬리로 들어가서 머리로 나옴
  • front와 rear의 값이 같으면 빈 큐

큐 생성

  • 배열 크기를 지정한 후 해당 크기의 빈 큐 생성

큐 구현

전역 변수 선언부

: 스택과 비슷함. 다만 top이 아닌 front와 rear가 있음

SIZE = 5
queue = [None for _ in range(SIZE)] # list_comprehension으로 queue  생성
front = rear = -1

함수 선언부

  1. 큐가 꽉 찼는지 확인하는 함수
def isQueueFull(): # 큐가 꽉찼는지 확인하는 함수
    global SIZE, queue, front, rear
    if (rear == SIZE -1): # 꼬리(입구쪽)가 큐의 크기와 같다면
        return True
    else:
        return False
  1. 큐가 비었는지 확인하는 함수
def isQueueEmpty(): # 큐가 비었는지 확인하는 함수
    global SIZE, queue, front, rear
    if (rear == front):
        return True
    else:
        return False
  1. 큐에 데이터를 넣는 함수
def enQueue(data): # 큐에 데이터를 넣는 함수
    global SIZE, queue, front, rear
    if (isQueueFull()):
        print('큐가 꽉 찼습니다.')
        return
    rear += 1 # 꼬리가 입구쪽으로 증가한다.
    queue[rear] = data
  1. 큐에서 데이터를 빼는 함수
def deQueue(): # 큐에서 데이터를 빼는 함수
    global SIZE, queue, front, rear
    if isQueueEmpty():
        print('큐가 비었습니다.')
        return None
    front += 1 # 머리가 출구에서 입구쪽으로 증가
    data = queue[front]
    queue[front] = None
    return data
  1. 다음 나올 데이터를 알려주는 함수
def peek(): # 다음 나올 데이터를 알려주는 함수
    global SIZE, queue, front, rear
    if isQueueEmpty():
        print('큐가 비었습니다.')
        return None
    return queue[front+1]

메인

enQueue(삽입)
enQueue('화사')
enQueue('솔라')
enQueue('문별')
enQueue('선미')
enQueue('동준')
print('출구<-----',queue,'<-----입구')
enQueue('아이유') # 큐의 SIZE가 5이므로 더이상 들어갈 자리가 없다.
print('출구<-----',queue,'<-----입구')

출구<----- ['화사', '솔라', '문별', '선미', '동준'] <-----입구
큐가 꽉 찼습니다.
출구<----- ['화사', '솔라', '문별', '선미', '동준'] <-----입구
deQueue(추출)
print('밥 손님 : ', deQueue())
print('밥 손님 : ', deQueue())
print('밥 손님 : ', deQueue())
print('출구<-----',queue,'<-----입구')
print('밥 손님 : ', deQueue())
print('다음 손님.. 준비 ', peek())
print('밥 손님 : ', deQueue())
print('출구<-----',queue,'<-----입구')


밥 손님 :  화사
밥 손님 :  솔라
밥 손님 :  문별
출구<----- [None, None, None, '선미', '동준'] <-----입구
밥 손님 :  선미
다음 손님.. 준비  동준
밥 손님 :  동준
출구<----- [None, None, None, None, None] <-----입구

2022

[web]jQuery 복습 3

2 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]jQuery 복습 2

11 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]jQuery 복습 1

16 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]JavaScript 정리4

6 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]JavaScript 정리3

6 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]JavaScript 정리2

6 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]JavaScript 정리1

7 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]CSS 기초 정리

9 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]HTML 기초 정리

2 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[Pandas]pandas 연습

3 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

맨 위로 이동 ↑

2021

[Python기초]module

1 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

맨 위로 이동 ↑