코린이형준

링크드리스트(LinkedList)

1.구조

• Hash Table: 키(key)에 데이터(value)를 저장하는 데이터 구조
  • key를 통해 바로 데이터를 받아올 수 있으므로, 속도가 획기적으로 빨라짐
  • 파이썬 딕셔너리 타입이 해시테이블의 예(key를 가지고 바로 데이터(value)를 꺼내옴)
  • 보통 배열로 미리 hash table 사이즈만큼 생성 후에 사용(공간과 탐색 시간을 맞바꾸는 기법 -> 해쉬테이블의 공간을 늘림으로써 충돌로 인한 추가적인 자료구조 알고리즘을 만들지 않기 때문)
  • 단, 파이썬에서는 해쉬를 별도 구현할 이유가 없음 - 딕셔너리 타입을 사용하면 되기 때문

2.알아둘 용어

• 해쉬(hash): 임의 값을 고정 길이로 변환하는것
• 해쉬 테이블: 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조
• 해싱함수: key에 대해 산술 연산을 이용해 데이터 위치를 찾을수 있는 구조
• 해쉬값 또는 해쉬 주소: key를 해싱함수로 연산해서, 해쉬 값을 알아내고, 이를 기반으로 해쉬 테이블에서 해당 key에 대한 데이터 위치를 일관성있게 찾을 수 있음
• 슬롯: 각각의 데이터를 저장할 수 있는 공간
• 저장할 데이터에 대해 key(입력값)를 추출할 수 있는 별도 함수도 존재할 수 있음
• 배열보다 해쉬테이블이 좋은 이유: 검색할 때 배열같은경우는 입력값에 대해 처음부터 확인을 해야하지만 해쉬테이블은 입력값을 통해서 바로 검색을 하여 가져올 수 있기 때문에 더 많이 쓰이게 된다.

3.장단점과 주요 용도

• 장점
  • 데이터 저장/읽기 속도가 빠르다.(ex. 검색 속도)
  • 해쉬는 키에 대한 데이터가 있는지(중복) 확인이 쉽다.
• 단점
  • 일반적으로 저장공간이 좀더 많이 필요하다.
  • 여러 키에 해당하는 주소가 동일할 경우 충돌을 해결하기 위한 별도의 자료구조가 필요하다
• 주요용도
  • 검색이 많이 필요한 경우
  • 저장, 삭제, 읽기가 빈번한 경우
  • 캐시구현시(중복확인이 쉽기 때문)

4.파이썬에서의 해시 테이블의 활용 예 - 딕셔너리(Dictionary)

5.직접 해쉬테이블 구현해보기

hash_table = list([0 for i in range(8)])

def get_key(data): # 전달 받은 데이터를 암호화
    return hash(data)

def hash_function(key): # 특정 고윳값으로 키값 반환
    return key % 8

def save_data(data, value): # hash_function으로 받은 키값으로 데이터 저장
    hash_address = hash_function(get_key(data))
    hash_table[hash_address] = value
    
def read_data(data): # 전달받은 데이터를 기반으로 반환받은 키값을 통해 데이터 출력
    hash_address = hash_function(get_key(data))
    return hash_table[hash_address]

여기서 한가지 의문점이 든다. 그렇다면 전달받은 데이터를 기반으로 키값을 만들어내는데 이때 같은 키값이 나오게 된다면 이를 어떻게 처리하고 저장이 될까? 이때 해쉬테이블의 가장 큰 문제점이 나온다. 바로 충돌(collison)이다. 그래서 해쉬테이블은 따로 충돌알고리즘을 구현해야하는데 대표적으로 2가지 방식이 있다.

-Chaining 기법

• 개방 해슁 또는 Open Hashing 기법 중 하나: 해쉬 테이블 저장공간 외의 공간을 활용하는 기법
• 충돌이 일어나면, 링크드 리스트라는 자료 구조를 사용해서, 링크드 리스트로 데이터를 추가로 뒤에 연결시켜서 저장하는 기법

hash_table = list([0 for i in range(8)])

def get_key(data):
    return hash(data)

def hash_function(key):
    return key % 8

def save_data(data, value):
    index_key = get_key(data)
    hash_address = hash_function(index_key)
    if hash_table[hash_address] != 0: # 저장할 공간에 이미 데이터가 존재할때
        for index in range(len(hash_table[hash_address])):
            if hash_table[hash_address][index][0] == index_key:
                hash_table[hash_address][index][1] = value
                return
        hash_table[hash_address].append([index_key, value])
    else:
        hash_table[hash_address] = [[index_key, value]]
    
def read_data(data):
    index_key = get_key(data)
    hash_address = hash_function(index_key)

    if hash_table[hash_address] != 0:
        for index in range(len(hash_table[hash_address])):
            if hash_table[hash_address][index][0] == index_key:
                return hash_table[hash_address][index][1]
        return None
    else:
        return None

-Linear Probing 기법

• 폐쇄 해슁 또는 Close Hashing 기법 중 하나: 해쉬 테이블 저장공간 안에서 충돌 문제를 해결하는 기법
• 충돌이 일어나면, 해당 hash address의 다음 address부터 맨 처음 나오는 빈공간에 저장하는 기법
  • 저장공간 활용도를 높이기 위한 기법

hash_table = list([0 for i in range(8)])

def get_key(data):
    return hash(data)

def hash_function(key):
    return key % 8

def save_data(data, value):
    index_key = get_key(data)
    hash_address = hash_function(index_key)
    if hash_table[hash_address] != 0:
        for index in range(hash_address, len(hash_table)):
            if hash_table[index] == 0:
                hash_table[index] = [index_key, value]
                return
            elif hash_table[index][0] == index_key:
                hash_table[index][1] = value
                return
    else:
        hash_table[hash_address] = [index_key, value]

def read_data(data):
    index_key = get_key(data)
    hash_address = hash_function(index_key)
    
    if hash_table[hash_address] != 0:
        for index in range(hash_address, len(hash_table)):
            if hash_table[index] == 0:
                return None
            elif hash_table[index][0] == index_key:
                return hash_table[index][1]
    else:
        return None

+) 위와 같은 해결기법을 통해 해결가능하지만 근본적으로 빈번한 충돌을 방지하기 위해서는 해쉬테이블의 저장공간을 애초에 많이 생성해주면 된다!

사실 이번 코딩테스트 준비 파트를 기초부터 들어가게 된 원인이 된 녀석이다... 면접때 코딩테스트 당시 풀었던 코드에대해 시간복잡도를 여쭤보셨는데 이부분에대한 정의가 안되어있어서 대답조차 못했기때문...ㅎ... 그리어렵진 않다.

알고리즘 복잡도 표현방법

1.알고리즘 복잡도 계산이 필요한 이유

하나의 문제를 푸는 알고리즘은 다양함

• 정수의 절대값 구하기(1,-1)
  • 방법1:정수값을 제곱한 값에 다시 루트 씌우기
  • 방법2:정수가 음수 인지 확인해서, 음수일 때만 -1을 곱하기
  • 즉, 다양한 알고리즘 중 어느 알고리즘이 더좋은지를 분석하기 위해, 복잡도를 정의하고 계산함

2.알고리즘 복잡도 계산항목

• 시간 복잡도: 알고리즘 실행속도
• 공간 복잡도: 알고리즘이 사용하는 메모리 사이즈
• 가장 중요한 시간 복잡도를 이해하고 계산할 수 있어야함 -> 공간복잡도는 아무래도 비중이적음

알고리즘 시간 복잡도의 주요 요소는 반복문이다. -> 입력의 크기가 커지면 커질수록 알고리즘 수행시간이 증가함

알고리즘 성능 표기법

• Big O (빅-오) 표기법: O(N)
  • 알고리즘 최악의 실행 시간
  • 가장 많이/일반적으로 사용
  • 아무리 최악의 상황이라도, 이정도의 성능을 보장한다는 의미
• Ω (오메가) 표기법: Ω(N)
  • 오메가 표기법은 알고리즘 최상의 실행 시간
• Θ (세타) 표기법: Θ(N)
  • 세타 표기법은 알고리즘 평균 실행시간을 표기
• 시간 복잡도 계산은 반복문이 핵심 요소이며, 계산 표기는 최상, 평균, 최악 중, 최악의 시간인 Big-O표기법을 중심으로 익히면 됨

3.Big-O 표기법

• 빅 오 표기법, Big-O 표기법 이라고도 부름
• O(입력값)   
• 입력 n에 따라 결정되는 시간 복잡도 함수
• O(1), O( 𝑙𝑜𝑔𝑛 ), O(n), O(n 𝑙𝑜𝑔𝑛 ), O( 𝑛2 ), O( 2𝑛 ), O(n!)등으로 표기함
• 입력 n 의 크기에 따라 기하급수적으로 시간 복잡도가 늘어날 수 있음
• O(1) < O( 𝑙𝑜𝑔𝑛 ) < O(n) < O(n 𝑙𝑜𝑔𝑛 ) < O( 𝑛2 ) < O( 2𝑛 ) < O(n!)
• 참고: log n 의 베이스는 2 -  𝑙𝑜𝑔2𝑛 
• 단순하게 입력 n에 따라, 몇번 실행이 되는지를 계산
• 표현식에 가장 큰 영향을 미치는 n 의 단위로 표기 -> 상수회 무시
• 예시

-무조건 2회(상수회)실행: O(1)

if n>10:
	print(n)

-n에따라, n번, n+10번 또는 10n+10번등 실행: O(n)

variable = 1
for num in range(3):
	for index in range(n):
		print(index)
# 따져보면 2n+2회이지만 결국 시간복잡도는 2n

-n에 따라, 𝑛2번 , 𝑛2+1000번,  𝑛2+1번실행한다: O(𝑛2)

variable = 1
for i in range(300):
	for num in range(n):
		for index in range(n):
			print(index)

• 성능 판단 예시: 1부터 n까지의 합을 구하는 알고리즘

# 입력값 n을 정렬하여 모두 합
def sum_all(n):
    total = 0
    for num in range(1, n + 1):
        total += num
    return total
#시간복잡도: n

# 덧셈 알고리즘 이용
def sum_all(n):
    return int(n * (n + 1) / 2)
#시간복잡도: 1

같은 문제이더라도 어떤 알고리즘을 이용하냐에 따라 시간 복잡도가 다르게 나옴 즉, 시간복잡도가 1인 2번째 알고리즘의 성능이 더욱 좋다.

링크드리스트(LinkedList)

1.구조

• 연결리스트라고도 함
• 배열은 순차적으로 연결된 공간에 데이터를 나열하는 데이터 구조
• 링크드 리스트는 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조
• 링크드 리스트 기본 구조와 용어
  • 노드(Node): 데이터 저장 단위(데이터, 포인터)로 구성
  • 포인터(Pointer): 각 노드 안에서, 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간
• 배열은 미리 특정한 공간을 예약해두고 그공간을 쓰는구조이지만, 이에반해 링크드 리스트는 미리 예약을 해두지 않고 필요할때마다 그공간을 추가할수 있는 구조이다.
• 보통 파이썬에서 링크드 리스트를 구현시, 파이썬 클래스를 활용 -> 파이썬 객체지향 문법의 이해가 필요함

2.장단점

• 장점
  • 미리 데이터 공간을 할당하지 않아도됨 -> 배열은 미리 데이터 공간을 할당 해야함
• 단점
  • 연결을 위한 별도 데이터 공간이 필요하므로, 저장공간 효율이 높지 않음
  • 연결정보를 찾는 시간이 필요하므로 접근 속도가 느림
  • 중간 데이터 삭제시, 앞뒤 데이터 연결을 재구성해야 하는 부가적인 작업이 필요

3.직접 링크드 리스트 구현해보기

class Node:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next
    
class NodeMgmt:
    def __init__(self, data):
        self.head = Node(data)
        
    def add(self, data):
        if self.head == '':
            self.head = Node(data)
        else:
            node = self.head
            while node.next:
                node = node.next
            node.next = Node(data)
        
    def desc(self):
        node = self.head
        while node:
            print (node.data)
            node = node.next
    
    def delete(self, data):
        if self.head == '': 
            print ("해당 값을 가진 노드가 없습니다.")
            return
        
        if self.head.data == data: # 삭제하는 데이터가 헤드일경우
            temp = self.head
            self.head = self.head.next
            del temp
        else: # 삭제하는 데이터가 중간,맨뒤일 경우
            node = self.head
            while node.next:
                if node.next.data == data:
                    temp = node.next
                    node.next = node.next.next
                    del temp
                    return
                else:
                    node = node.next

• head의 경우, 리스트의 첫시작을 알기위해 임의로 지정한 것
• 링크드리스트를 다시금 학습하며 개념을 파악할수 있었다. 그리고 생각보다 구현하는데 애를먹어 객체지향적 프로그래밍에 대한 학습또한 할수 있었던 파트다.

큐(Queue)

1.구조

• 가장먼저 넣은 데이터를 가장먼저 꺼낼수 있는 구조
  • 음식점에서 가장먼저 줄을 선 사람이 가장 먼저 음식점에 입장하는것
  • FIFO(First In, First Out)또는 LILO(Last-In, Last-Out)방식으로 스택과 꺼내는 순서가 반대

2.알아둘 용어

• FIFO
• Enqueue: 큐에 데이터를 넣는 용어
• Dequeue: 큐에서 데이터를 꺼내는 용어

3.파이썬 queue 라이브러리 활용해서 큐 자료 구조 사용하기

#일반적인 큐 사용(fifo)
import queue

data_queue = queue.Queue()
data_queue.put("func")
data_queue.put(1)
data_queue.get() # func 출력
data_queue.get() # 1 출력
#들어간 순서대로 출력됨 FIFO

#LifoQueue(Lifo(Lastin,Firstout)) 
import queue
data_queue = queue.LifoQueue()
data_queue.put(123)
data_queue.put(456)
data_queue.get() # 456출력
data_queue.get() # 123출력
#나중에 들어간 456출력 LIFO


#PriorityQueue(우선순위에 따라추출중요!!)
import queue
data_queue = queue.PriorityQueue()
data_queue.put((10,"korea"))
data_queue.put((5,32))
data_queue.put((7,"china"))
data_queue.get() # 32출력
#가장 우선순위가 높은 32가 출력됨

4.직접 dequeue, inqueue구현해보기

#dequeue, inqueue 구현
queue_list = list()

def enqueue(data):
    queue_list.append(data)
    
def dequeue():
    data = queue_list[0]
    del queue_list[0]
    return data

스택(stack)

1.구조

• 스택은 LIFO(Last In, First Out) 또는 FILO(First In, Last Out) 데이터관리 방식을 따름
  • LIFO: 마지막에 넣은 데이터를 가장 먼저 추출하는 데이터 관리 정책
  • FILO: 처음에 넣은 데이터를 가장 마지막에 추출하는 데이터 관리 정책
• 대표적인 스택의 활용
  • 컴퓨터 내부의 프로세스 구조의 함수 동작 방식

  • def recursive(data):
        if data < 0:
            print("ended")
        else:
            print(data)
            recursive(data-1)
            print('returned',data)
    recursive(3)
    
    #결과
    # 3
    # 2
    # 1
    # 0
    # ended
    # returned 0
    # returned 1
    # returned 2
    # returned 3
    
    # recursive(data-1)의 종결과 같은 ended가 출력된이후 
    # 쌓여있는 returned 출력문을 가장 늦게 들어왔지만 0부터 출력해냄

2.알아둘 용어

• push():데이터를 스택에 넣기
• pop():데이터를 스택에서 꺼내기

3.스택의 장단점

• 장점
  • 구조가 단순해서 구현이 쉽다.
  • 데이터 저장/읽기 속도가 빠르다.
• 단점
  • 데이터 최대 갯수를 미리 정해야 한다.(파이썬의 경우 재귀함수는 1000번까지 호출가능)
  • 저장공간의 낭비가 발생할 수 있다.(미리 최대 개수만큼 저장 공간을 확보해야함)
• 스택은 단순하고 빠른 성능을 위해 사용되므로, 보통 배열 구조를 활용해서 구현하는것이 일반적임.

4. 파이선 리스트 기능에서 제공하는 메서드 스택

• append(push), pop

• data_stack = list()
  data_stack.append(1)
  data_stack.append(2) # [1,2]
  data_stack.pop() # 2 출력 [1]

5.직접 push, pop 구현해보기

stack_list =list()
def push(data):
    stack_list.append(data)
    
def pop():
    data = stack_list[-1]
    del stack_list[-1]
    return data

1.자료구조란?

• 용어: 자료구조, 데이터구조, datastructure
• 대량의 데이터를 효율적으로 관리할 수 있는 데이터의 구조를 의미
• 코드상에서 효율적으로 데이터를 처리하기 위해, 데이터 특성에 따라, 체계적으로 데이터를 구조화해야함
  • 어떤 데이터 구조를 사용하느냐에 따라 코드 효율이 달라짐
• 효율적으로 데이터를 관리하는 예
  • 우편번호: 5자리 우편번호로 국가의 기초구역을 제공
  • 학생관리: 학년, 반, 번호를 학생에게 부여해서, 학생부를 관리
• 대표적인 자료구조
  • 배열, 스택, 큐, 링크드 리스트, 해쉬 테이블, 힙등

2.알고리즘이란?

• 용어: 알고리즘, algorithm
• 어떤 문제를 풀기위한 절차/방법
• 어떤 문제에 대해 특정한 '입력'을 넣으면, 원하는 '출력'을 얻을 수 있도록 만드는 프로그래밍
• 좋은 알고리즘의 요소: 시간복잡도, 데이터 효율성등

3.자료구조와 알고리즘이 중요한 이유

어떤 자료구조와 알고리즘을 쓰느냐에 따라 성능이 전지차다 --> 결국 프로그래밍을 잘 할수 있는 기술과 역량을 익히고, 검증할 수 있음

코딩테스트 문제를 마구잡이식으로 풀다 보니 아무래도 자료구조/ 알고리즘 관련 면접에서 막힌 경험이 생겼다.. 그리하여 남는 시간동안 자료구조/알고리즘 이론을 좀더 튼튼히 준비한후 동시에 코딩테스트 문제를 풀어보려한다.

4군데의 기업에서코딩테스트를 봤는데 2군데 합격, 2군데 불합격이떳다ㅎ... 대부분 유형은 프로그래머스, 백준과 같은 알려진 사이트에서의 문제, sql문제, restapi문제였고 경험은 없지만 지원하는 회사가 사용하는 프레임워크로 시험을 치는 회사가 있다고 했다. 약 2개월동안 좀 빡쌔게 기본을 다시 복습한뒤 이후부턴 여러 회사에 지원해보며 코딩테스트에 모두합격할수 있도록 대비해야겠다.

공부 환경은 유명한 아나콘다 환경에서 준비할예정!

배열의 크기 N, 숫자가 더해지는 횟수 M, 똑같은 수가 더해지는 최대의 수 K라 할때 입력받은 N중에서 가장M번을 더하여 가장 큰 숫자가 나올수 있는 경우의 수를 구하라.(각자연수는 공백으로 구분한다.)

n,p,k=map(int, input().split())
number = list(map(int, input().split()))

number.sort()
number.reverse()
first=number[0]
second=number[1]
result=0

while True:
	for i in range(k):
    	if m==0:
        	break
        result += first
        m-=1
    if m==0:
    	break
    result+=second
    m-=0
    
print(result)

여기서 중요한 함수는 자료형을 입력받는 map함수와 입력받은 수를 정렬하는 sort함수이다.

map(자료형, 입력받는 방식)으로 입력하면 여러 변수를 내가 설정한 자료형과 방식으로 변경하여 입력받을 수 있고 sort함수를 통해 무작위로 입력받은 값들은 오름차순으로 정렬할수 있다. 그 이후부터는 while반복문을 통해 무한반복으로 설정한 조건에 따라 break문으로 반복문을 종료시킴으로써 원하는 값을 얻을수 있다.

당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수를 구하라. 단, 거슬러 줘야할 돈 N은 항상 10의 배수이다.

n = 2860
count = 0
coin_type = [500,100,50,10]
for coin in coin_type:
	count += int(n/coin)
	n %= coin
print(count)

여기서 알아야 할점은 int() 이다. int는 정수형으로 정수만을 출력할수 있는데 처음 애먹었던 부분이 count에 동전의 개수를 저장해야하는데 처음 500원의 몫은 소수까지 나와서 어려웠다. 답은10이 출력되었다.