누런강냉이

해시

완주하지 못한 선수

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
• completion의 길이는 participant의 길이보다 1 작습니다.
• 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
• 참가자 중에는 동명이인이 있을 수 있습니다.

해시란? 해시 테이블이라고 불리우는 저장공간에다 키들이 어느 위치에 있을지 정해 해시 테이블에 값을 저장하는 것.

값들의 위치를 결정하는데에는 hash function이 이용된다. 해시 테이블의 각각의 저장공간을 hash bucket이라고 한다.

코드 구현

def solution(participant, completion):
    d = {}
    for x in participant:
        d[x] = d.get(x,0) +1 #get(x,0) x가 존재하면 키에 해당하는 값을, 존재하지 않으면 0을 return 
    for x in completion:
        d[x] -= 1
    dnf = [k for k, v in d.items() if v > 0]
    answer = dnf[0]
    return answer

시간복잡도 : O(n)

탐욕법

체육복

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.

전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 전체 학생의 수는 2명 이상 30명 이하입니다.
• 체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
• 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

탐욕법이란? 알고리즘의 각 단계에서 그 순간 최적이라고 생각되는 것을 선택

현재의 선택이 마지막 해답의 최적성을 해치지 않을 때 탐욕법 활용 가능

코드 구현

def solution(n, lost, reserve):
    u = [1]*(n+2)
    for i in reserve:
        u[i]+=1
    for i in lost:
        u[i]-=1
        
    for i in range(1, n+1):
        if u[i-1]==0 and u[i]==2:
            u[i-1:i+1]=[1,1]
        elif u[i] == 2 and u[i+1] == 0:
            u[i:i+2]=[1,1]
            
            
    return len([x for x in u[1:-1] if x > 0])

시간복잡도 : O(n)

def solution(n, lost, reserve):
    s = set(lost) & set(reserve)
    l = set(lost) - s
    r = set(reserve) - s
    for x in sorted(r):
        if x-1 in l:
            l.remove(x-1)
        elif x+1 in l:
            l.remove(x+1)
            
    return n-len(l)

시간복잡도 : O(klogk)

정렬

가장 큰 수 

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

제한 사항

• numbers의 길이는 1 이상 100,000 이하입니다.
• numbers의 원소는 0 이상 1,000 이하입니다.
• 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

문제 해결 방법

1. 빈 문자열로 수 초기화
2. 수 목록을 (크게 만드는 것 우선) 정렬
3. 목록에서 하나씩 꺼내 현재 수에 이어 붙인다.
4. 모든 수를 다 사용할 때까지 반복

알고리즘 설계

• 대소 관계 비교를 위한 기준 마련
• 기준을 이용해 주어진 배열 정렬
• 정렬된 배열을 이용해 문자열 표현 완성

코드 구현

def solution(numbers):
    numbers = [str(x) for x in numbers]
    numbers.sort(key=lambda x : (x*4)[:4], reverse=True)
    if numbers[0]=='0':
        answer='0'
    else:
        answer = ''.join(numbers)
    return answer

시간복잡도 : O(nlogn) (정렬하면서..)

탐욕법

큰 수 만들기

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.

예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.

문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

제한 조건

• number는 1자리 이상, 1,000,000자리 이하인 숫자입니다.
• k는 1 이상 number의 자릿수 미만인 자연수입니다.

문제 해결 방법

• 큰 수가 앞 자리에, 작은 수가 뒷 자리에 놓이도록 한다.

알고리즘 설계

• 주어진 숫자로부터 하나씩 꺼내 모은다.
  • 이 때, 이미 모아둔 것 중 지금 등장한 것보다 작은 것들은 빼낸다.
• 모은 숫자들을 자릿수 맞춰 반환한다.
  • 아직 뺄 개수를 채우지 못한 경우를 고려한다.

코드 구현

def solution(number, k):
    collected = []
    for i, num in enumerate(number):
        while len(collected)>0 and collected[-1]<num and k>0: 
            #아직까지 빼낼 게 남아있고 (k>0) 
            #마지막 글자가 현재 글자보다 작고 (collected[-1]<num) 
            #collected의 길이가 0보다 클 때동안 (len(collected)>0)
            collected.pop()
            k-=1
        if k==0:
            collected += list(number[i:])
            break
        collected.append(num)
        
    collected = collected[:-k] if k>0 else collected 
    #만약 k가 0보다 크면 즉, 잘라야 할 문자가 남았다면 맨 뒤부터 남은 문자 갯수만큼 잘라준다.
    return ''.join(collected)

시간복잡도 : O(n)

자료구조와 알고리즘

자료구조란? 데이터가 있고, 그 데이터에 대해 행할 수 있는 연산들로 이루어진 구조

알고리즘이란? 주어진 문제의 해결을 위한 자료구조와 연산 방법에 대한 선택

선형 배열

배열이란? 원소들을 순서대로 늘어놓은 것

원소 삽입

L = [ 1, 3, 5, 7, 9 ]
index 0 1 2 3 4

L.insert(3,6) 적용 시

3번 인덱스의 앞을 우선 찾아내게 되고,

맨 뒤의 수를 오른쪽으로 한 칸 옮기게 된다. (이 과정에서 배열의 크기가 하나 늘어나 크기가 6인 배열이 된다.)
그 후 7을 또 오른쪽으로 한 칸 옮기고
마지막으로 6을 삽입함

결과

L = [ 1, 3, 5, 6, 7, 9 ]
index 0 1 2 3 4 5

원소 삭제

L = [ 1, 3, 5, 6, 7, 9 ]
index 0 1 2 3 4 5

del(L[2]) 적용 시

2번 인덱스에 있던 5를 삭제하고,

오른편에 있던 6과 7과 9를 한 칸씩 옮긴다.

그 후 맨마지막 5번 인덱스에 있던 9를 옮긴다. (이 과정에서 배열의 크기가 하나 줄어 크기가 5인 배열이 된다.)

결과

L = [ 1, 3, 6, 7, 9 ]
index 0 1 2 3 4

del()과 pop()은 비슷한 동작을 시행하지만,

del()은 시행한 후 빠져나간 원소의 값이 반환되지 않고,

pop()은 시행한 후 빠져나간 원소의 값이 반환된다는 차이를 보인다.

원소 삽입과 삭제는 리스트의 길이가 길면 비례해서 연산이 오래걸린다. (선형 시간)

=> O(n)만큼의 시간이 걸린다.

정렬

수 정렬

L = [ 5, 1, 3, 7, 2 ]

sorted(L) 적용 시

L = [ 5, 1, 3, 7, 2 ]

sorted(L)은 리스트 자체에 변화를 주지 않는다.

L.sort() 적용 시

L = [ 1, 2, 3, 5, 7 ]

L.sort()는 L 리스트 자체에 변화를 준다. (바로 적용이 된다.)

L = sorted(L, reverse=True) OR L.sort(reverse=True) 적용 시

L = [ 7, 5, 3, 2, 1]

문자열 정렬

L = [ 'abcd', 'xyz', 'spam']

위 리스트를 그냥 정렬하게 되면 사전순으로 정렬하게 된다.

그렇다면 문자열 길이별로 정렬하려면 어떻게 하여야 할까?

키를 활용한다.

sorted(L, key = lambda x : len(x)) 적용 시

L = [ 'xyz, 'abcd', 'spam' ]

탐색

탐색 알고리즘 (1) - 선형 탐색

리스트에 비례하는 시간 소요

=> O(n)

탐색 알고리즘 (2) - 이진 탐색

한 번 비교할 때마다 리스트를 반씩 줄인다. (divide & conquer)

=> O(log n)

이진 탐색 코드 구현

lower = 0
upper = len(L) - 1
while lower <= upper:
    middle = (lower + upper)//2 #중간 인덱스 찾기
    if L[middle] == target:
    	return middle
    elif L[middle] < target: #중간값이 target값보다 작을 경우
    	lower = middle+1 #중간 인덱스보다 1만큼 큰 값으로 lower값 조정
    else: #중간값이 target값보다 클 경우
    	upper = middle-1 #중간 인덱스보다 1만큼 작은 값으로 upper값 조정

재귀 알고리즘

재귀함수(Recursive function)란? 하나의 함수에서 자신을 다시 호출해 작업을 수행하는 것

재귀함수 설계 시, 종결 조건에 유의하여야 한다.

재귀 알고리즘의 효율

def sum(n):
    if n<=1:
    	return n
    else:
    	return n+sum(n-1)

=> O(n)

vs

def sum(n):
    s = 0
    while n>=0:
    	s+=n
        n-=1
    return s

=> O(n)

vs

def sum(n):
    return n*(n+1)//2

=> O(1)

※ 효율성 측면에 유의하여 알고리즘을 잘 설계해야 한다! 

피보나치 순열

재귀함수를 활용한 경우

def solution(x):
    if x==0:
        return 0
    elif x==1:
        return 1
    else:
        return solution(x-1) + solution(x-2)

반복적 함수를 활용한 경우

def solution(x):
    a, b = 0, 1
    
    if x==0:
        return 0
    
    for i in range(x-1):
        a,b = b, a+b
            
    return b

※ 꼭 재귀라고 효율성이 좋은 것만은 아니다. 문제에 따라 적절한 자료구조를 선택해야 한다는 좋은 본보기가 되어준다.

재귀적 이진 탐색

def binsearch(L, x, lower, upper):
    if l>u:
        return -1
    mid = (lower + upper) // 2
    if x==L[mid]:
        return mid
    elif x<L[mid]:
        return solution(L,x,l,mid-1)
    else:
        return solution(L,x,mid+1,u)

알고리즘의 복잡도

☆ 시간 복잡도란? 문제의 크기와 이를 해결하는 데 걸리는 시간 사이의 관계

• 평균 시간 복잡도 : 임의의 입력 패턴(랜덤한 패턴)을 가정했을 때 소요되는 시간의 평균
• 최악 시간 복잡도 : 가장 긴 시간을 소요하게 만드는 입력에 따라 소요되는 시간 (이를 기준으로 알고리즘의 복잡도를 계산한다.)

공간 복잡도란? 문제의 크기와 이를 해결하는 데 필요한 메모리 공간 사이의 관계

☆ Big-O Notation이란? 점근 표기법의 하나. 알고리즘의 복잡도를 표현할 때 흔히 쓰인다.

• 선형 시간 알고리즘 - O(n)
• 로그 시간 알고리즘 - O(log n)
  • ex) 이진 탐색 알고리즘
• 이차 시간 알고리즘 - O(n²)
  • ex) 삽입 정렬

삽입 정렬보다 낮은 복잡도를 가지는 정렬 알고리즘

• 병합 정렬
  • 정렬할 데이터를 반씩 나누어 각각 정렬시킨다. - O(log n)
  • 정렬된 데이터를 두 묶음씩 한데 합친다. - O(n)
  • 결과 => O(nlog n)
  • 그림출처 : https://ko.wikipedia.org/wiki/%ED%95%A9%EB%B3%91_%EC%A0%95%EB%A0%AC

연결 리스트 (Linked List)

추상적 자료구조 

• Data
  • 정수, 문자열, 레코드, ...
• A set of operations
  • 삽입, 삭제, 순회, ...
  • 정렬, 탐색, ...

연결 리스트 구현

class Node:

    def __init__(self, item):
        self.data = item
        self.next = None


class LinkedList:

    def __init__(self):
        self.nodeCount = 0
        self.head = None
        self.tail = None


    def getAt(self, pos):
        if pos < 1 or pos > self.nodeCount:
            return None

        i = 1
        curr = self.head
        while i < pos:
            curr = curr.next
            i += 1

        return curr


    def insertAt(self, pos, newNode):
        if pos < 1 or pos > self.nodeCount + 1:
            return False

        if pos == 1:
            newNode.next = self.head
            self.head = newNode

        else:
            if pos == self.nodeCount + 1:
                prev = self.tail
            else:
                prev = self.getAt(pos - 1)
            newNode.next = prev.next
            prev.next = newNode

        if pos == self.nodeCount + 1:
            self.tail = newNode

        self.nodeCount += 1
        return True


    def popAt(self, pos):
        delete_node = self.getAt(pos)

        if pos < 1 or pos > self.nodeCount:  
            raise IndexError 

        if pos == 1:    
            if self.nodeCount == 1:    
                self.head=None
                self.tail=None
                
            else:                          
                self.head = self.head.next
            
        else:                          
            prev = self.getAt(pos - 1)
            prev.next = delete_node.next
            if pos == self.nodeCount:   
                prev.next = None
                self.tail = prev
                
        self.nodeCount -= 1
        return delete_node.data

    def traverse(self):
        result = []
        curr = self.head
        while curr is not None:
            result.append(curr.data)
            curr = curr.next
        return result

조금 변형된 연결 리스트 (Dummy head 추가)

그림 출처 : http://cslabserver2.cs.mtsu.edu/labs/2170/lab10/dummy.html

class Node:

    def __init__(self, item):
        self.data = item
        self.next = None


class LinkedList:

    def __init__(self):
        self.nodeCount = 0
        self.head = Node(None)
        self.tail = None
        self.head.next = self.tail


    def traverse(self):
        result = []
        curr = self.head
        while curr.next:
            curr = curr.next
            result.append(curr.data)
        return result


    def getAt(self, pos):
        if pos < 0 or pos > self.nodeCount:
            return None

        i = 0
        curr = self.head
        while i < pos:
            curr = curr.next
            i += 1

        return curr


    def insertAfter(self, prev, newNode):
        newNode.next = prev.next
        if prev.next is None:
            self.tail = newNode
        prev.next = newNode
        self.nodeCount += 1
        return True


    def insertAt(self, pos, newNode):
        if pos < 1 or pos > self.nodeCount + 1:
            return False

        if pos != 1 and pos == self.nodeCount + 1:
            prev = self.tail
        else:
            prev = self.getAt(pos - 1)
        return self.insertAfter(prev, newNode)


    def popAfter(self, prev):
        curr = prev.next
        
        if prev.next == None:
            return None
        
        if curr.next == None:
            self.tail = prev
        
        prev.next = curr.next
        self.nodeCount-=1 
        
        return curr.data


    def popAt(self, pos):
        if pos < 1 or pos > self.nodeCount :
            raise IndexError
            
        prev = self.getAt(pos-1)
        
        return self.popAfter(prev)
    
    def concat(self, L):
        self.tail.next = L.head.next
        if L.tail:
            self.tail = L.tail
        self.nodeCount+=L.nodeCount

한 쪽으로만 진행이 가능하다는 단점이 있다. 이를 보완한 것이...

양방향 연결 리스트(Doubly Linked Lists)

양방향 연결 리스트란? 앞으로도 뒤로도 즉, 양쪽으로 진행이 가능한 리스트

그림 출처 : https://www.studytonight.com/data-structures/doubly-linked-list

head와 tail에 dummy node를 달아준다.

class Node:

    def __init__(self, item):
        self.data = item
        self.prev = None
        self.next = None


class DoublyLinkedList:

    def __init__(self):
        self.nodeCount = 0
        self.head = Node(None)
        self.tail = Node(None)
        self.head.prev = None
        self.head.next = self.tail
        self.tail.prev = self.head
        self.tail.next = None


    def traverse(self):
        result = []
        curr = self.head
        while curr.next.next:
            curr = curr.next
            result.append(curr.data)
        return result


    def getAt(self, pos):
        if pos < 0 or pos > self.nodeCount:
            return None

        if pos > self.nodeCount // 2:
            i = 0
            curr = self.tail
            while i < self.nodeCount - pos + 1:
                curr = curr.prev
                i += 1
        else:
            i = 0
            curr = self.head
            while i < pos:
                curr = curr.next
                i += 1

        return curr


    def insertAfter(self, prev, newNode):
        next = prev.next
        newNode.prev = prev
        newNode.next = next
        prev.next = newNode
        next.prev = newNode
        self.nodeCount += 1
        return True


    def insertAt(self, pos, newNode):
        if pos < 1 or pos > self.nodeCount + 1:
            return False

        prev = self.getAt(pos - 1)
        return self.insertAfter(prev, newNode)
        
    def insertBefore(self, next, newNode):
        prev = next.prev
        newNode.next = prev.next
        newNode.prev = prev
        prev.next = newNode
        next.prev = newNode
        self.nodeCount+=1
        return True


    def popAfter(self, prev):
        curr = prev.next
        next = curr.next
        prev.next = next
        next.prev = prev
        self.nodeCount-=1
        
        return curr.data


    def popBefore(self, next): #수정필요
        curr = next.prev
        prev = curr.prev
        prev.next = next
        next.prev = prev
        self.nodeCount-=1
        
        return curr.data


    def popAt(self, pos):
        if pos < 1 or pos > self.nodeCount:
            raise IndexError
            
        prev = self.getAt(pos-1)
        next = self.getAt(pos)
        
        return self.popAfter(prev)
        #return self.popBefore(next)
        
    def concat(self, L):
        self.tail.prev.next = L.head.next
        L.head.next.prev = self.tail.prev
        self.tail = L.tail
        self.nodeCount += L.nodeCount

스택

스택이란? 자료를 보관할 수 있는 구조

한 쪽 끝에서 밀어 넣어야 하고 

=> push

같은 쪽에서 뽑아 꺼내야 한다.

=> pop

※ LIFO구조 (Last in First out)

그림 출처 :  https://swexpertacademy.com/

스택 연산

• size() - 현재 스택에 들어 있는 데이터 원소 수
• isEmpty() - 현재 스택이 비어 있는지 판단
• push(x) - 데이터 원소 x를 스택에 추가
• pop() - 스택의 맨 위 저장된 데이터 원소 제거 및 반환
• peek() - 스택의 맨 위 저장된 데이터 원소 반환 (제거하지 않음)

배열을 이용해 구현

class ArrayStack:
    def __init__(self):
        self.data = []
    def size(self):
        return len(self.data)
    def isEmpty(self):
        return self.size() == 0
    def push(self, item):
        self.data.append(item)
    def pop(self):
        return self.data.pop()
    def peek(self):
        return self.data[-1]

연결 리스트를 이용해 구현

from doublylinkedlist import Node
from doublylinkedlist import DoublyLinkedList

class LinkedListStack
    def __init__(self):
        self.data = DoublyLinkedList()
    
    def size(self):
        return self.data.getLength()
        
    def isEmpty(self):
        return self.size()==0
        
    def push(self, item):
        node = Node(item)
        self.data.insertAt(self.size() + 1, node)
        
    def pop(self):
        return self.data.popAt(self.size())
        
    def peek(self):
        return self.data.getAt(self.size()).data