728x90
# GCD
# GCD : Greatest common divisor : 최대공약수
# 유클리드 호제법
# : a,b에 대해 a를 로 나눈 나머지를 r이라 하면
#    a,b의 최대 공약수는  b와 r의 최대 공약수와 같다.
#   a   b
#  192  162
#  162  30
#  30   12
#  12   6   >> 최대 공약수 6


def gcd(a, b):
    print("---" + str(a) + ", " + str(b))
    if a % b == 0:
        return b
    else:
        return gcd(b, a % b)


print(gcd(192, 162))

출처  https://youtu.be/7C9RgOcvkvo

728x90

DFS Depth-first search : 깊이 우선탐색
- 스택(선입후출, 바구니, append, pop), 재귀함수로 구현
1. 탐색 시작 노드를 스택에 삽입하고 방문처리를 한다. 
2. 스택의 최상단 노드에 방문하지 않는 인접한 노드가 하나라도 있으면   
<< 방문기준 문제마다 임의. 작은걸로 임의 정함
그 노드를 스택에 넣고 방문 처리합니다. 
방문하지 않은 인접노드가 없으면 스택에서 최상단 노드를 꺼냅니다. 
3. 더이상 2번의 과정을 수행할수 없을 때까지 반복

그외
- Backtracking : 꼬리잡기 : 한노드의 처음부터 끝까지 탐색하는 과정, 비효율적 어려울때 쓰는 최후의 보루. 
- 트리 운행법
   inorder  : 좌측 가운데 우측
   preorder : 가운데 좌측 우측
   postorder : 좌측 우측 가운데

BFS breadth-first search :너비 우선탐색
큐(선입선출, 터널, append, popleft - from collections import deque 라이브러리 임포트)로 구현
- 인접노드 방문, 주로 최단거리 문제
- 모든 노드 방문안해도 됨. 

1. 탐색 시작 노드를 큐에 삽입하고 방문처리
2. 큐에서 노드를 꺼낸뒤 해당 노드의 인접노드 중에서 방문하지 않는 노드를 모두 큐에 샆입 방문처리
3. 더이상 2번과정 수행없을 때까지 반복

자바: https://www.youtube.com/watch?v=_hxFgg7TLZQ

주로참고 >>>>>>>>>파이썬 : https://youtu.be/7C9RgOcvkvo   

 

 

 



graph = [
[], [2,3,8], [1,7], [1,4,5], [3,5], [3,4], [7], [2,6,8], [1,7] 
]
visited = [False] *9
dfs(graph, 1, visited)
bfs(graph, 1, visited)
GFS BFS
1>2>3 넣었다 꺼냄 >
1>2
1>4>5 넣었따 꺼냄
1>4>6
...

from __future__ import division




def dfs(graph, v, visited):
    visited[v] = True
    print(v,  end=' ')
    for i in graph[v]:
        #print("-- " + str(i))
        #print(visited)
        if not visited[i]:
            dfs(graph, i, visited)



1 넣었다 꺼냄
1 |2 - 3 - 8
1 2 | 3 - 8 - 7
1 2 3 | 8 - 7 -4- 5
..: 간선동일 최단거리 쉬움. 

from __future__ import division
from collections import deque


def bfs(graph, start, visited):
    queue = deque([start])
    visited[start] = True

    while queue:
        v = queue.popleft()
        print(v,  end=' ')
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i]= True

bfs(graph, 1, visited)


 

* breadth :폭, 너비, 브레드  =width   ex) He was surprised at her breadth of reading

* adjacent: 인접한 어제이센트

* queue : 큐 대기행렬, 줄

 

 

파이썬

print(stack[::-1] ) #최 상단 원소 부터 출력

print(stack)  # 최 하단 원소 부터 출력

print(queue) # 먼저 들어온 원소 부터

queue.reverse()

print(queue) # 나중에 들어온 원소 부터

 

 

추가문제 1. 

더보기
# N x M 얼음틀.
# 구멍뚫려 있는 부분 0, 칸마기 1
# 상, 하, 좌, 우 붙어있는경우 서로 붙어있는것으로 간주.
# 생성되는 아이스크림갯수는?
# 1<=N, M<-1000
print("입력하세요")
#5 4
#00110
#00011
#11111
#
00000

n, m = map(int, input().split())
graph = []
for i in range(n):
    graph.append(list(map(int, input())))

print(graph)
graph.pop()
print(graph)

def dfs_ice(x,y):
    if x <= -1 or x >= n -1 or y <= -1 or y >= m-1:
        return False
    elif graph[x][y] == 0:
        graph[x][y] = 1
        dfs_ice(x-1, y)
        dfs_ice(x, y-1)
        dfs_ice(x+1,y)
        dfs_ice(x,y+1)
        return True
    return False

result = 0
for i in range(n):
    for j in range(m):
        if dfs_ice(i, j):
            result +=1
print(result)

 

더보기
# 미로탈출 최소 칸이 갯수
#
"""
5 6
101010
111111
000001
111111
111111

10
"""

from collections import deque

n, m = map(int, input().split())
graph = []
for i in range(n):
    graph.append(list(map(int, input())))

print(graph)

dx = [-1, 1, 0, 0]
dy = [0, 0, -1,1]

def bfs_miro(x,y):
    queue = deque()
    queue.append((x, y))

    while queue:
        x,y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx <0 or nx >= n or ny <0 or ny >= m:
                continue
            elif graph[nx][ny]==0:
                continue
            elif graph[nx][ny] ==1:
                graph[nx][ny]= graph[x][y] +1
                queue.append((nx, ny))

    return graph[n-1][m-1]

print(bfs_miro(0,0))

 

> 자바 버전 참고: https://blog.1028web.com/entry/class

 

728x90

피보나치 수열. _ 재귀함수.

1,1,2,3,4,8

1 + 1 = 2

fibo(1)=1

fibo(2)= 1

fibo(3) =fibo(1)+fibo(2)

fibo(n) = fibo(n-2) + fibo(n-1)

같은 계산을 N^n 반복.

결과를 기록해서 이용. = 메모이제이션  Memoization

문제를 쪼갤수 있는 구조= 겹치는 부분문제 = Overlapping subproblem.

input = 100

# memo 라는 변수에 Fibo(1)과 Fibo(2) 값을 저장해놨습니다!
memo = {
    1: 1,
    2: 1
}
# Top Down 방식.   반대는 바텀업


def fibo_dynamic_programming(n, fibo_memo):
    if n in fibo_memo:
        return fibo_memo[n]

    nth_fibo = fibo_dynamic_programming(n - 1, fibo_memo)+ fibo_dynamic_programming(n - 2, fibo_memo)
    fibo_memo[n] = nth_fibo
    # print(nth_fibo)
    return nth_fibo


print(fibo_dynamic_programming(input, memo))  # 354224848179261915075
728x90

해쉬 테이블 : "키", "데이터"를 저장함으로써 즉각적으로 데이터를 받아오고 업데이트 하고 싶을 때 사용하는 자료구조

해쉬함수 : 임의의 길이를 갖는 메시지를 입력하여 고정된 길이의 해쉬값을 출력하는함수입니다.

해쉬 테이블의 내부 구현은 키를 해쉬 함수를 통해 임의의 값으로 변경한 뒤 배열의 인덱스로 변환하여 해당하는 값에 데이터를 저장합니다.

만약, 해쉬 값 혹은 인덱스가 중복되어 충돌이 일어난다면? 체이닝과 개방주소법으로 해결.

items = [None]*8

hash("가") %86

hash("나")%8

5

items[hash("가") %8]="가위"

items[hash("나") %8]="나비"

결과 :: items[None, None, None, None, None, '나비', '가위', None]

items[hash("나") %8]'나비'

O(N)

인덱스 값이 동일했을때.. "충돌발생"

해결 1) 링크드 리스트 사용.   >> 체이닝

해결 2)  배열의 다음 남는 공간에 넣는것.   >> 개방주소법(Open Addressing)

 

 

 

class LinkedTuple:
    def __init__(self):
        self.items = list()

    def add(self, key, value):
        self.items.append((key,value))

    def get(self, key):
        for k,v in self.items:
            if key == k:
                return v


class LinkedDict:
    def __init__(self):
        self.items = []
        for i in range(8):
            self.items.append(LinkedTuple())

    def put(self,key,value):
        index = hash(key)%len(self.items)
        #LinkedTuple
        self.items[index].add(key,value)

    def get(self,key):
        index = hash(key) % len(self.items)
        return self.items[index].get(key)

#hash("사") %8   >>1
#hash("다") %8   >>1
l = LinkedDict();
a ="바"
b ="자"
print(a,b,(hash(a) %8)==(hash(b) %8))
l.put(a,"사자")
l.put(b,"다리미")
print(l.get(a))
print(l.get(b))
728x90

정렬

데이터를 순서대로 나열하는 방법을 의미합니다.

 

버블정렬

앞뒤 숫자 비교해서 정렬: 1st 와 2nd, 2nd와 3nd, 3nd와4th 와 비교

input = [10, 4,2]
def bubble_sort(input):
    n = len(input)
    for loop1 in range(n - 1):
        for loop2 in range(n - 1 - loop1):
            print(loop2, loop2 + 1, input)
            if input[loop2] > input[loop2 + 1]:
                input[loop2], input[loop2 + 1] = input[loop2 + 1], input[loop2]

    return input
print(bubble_sort(input))

선택정렬

선택해서 정렬. : 가장 작은 숫자를 맨앞자리 를 교체 해서 인덱스를 늘림.

input = [10, 4, 2]
def selection_sort(input):
    n = len(input)
    for loop1 in range(n - 1):
        min_index = loop1
        for loop2 in range(n-loop1):
            print(min_index + loop2, min_index , input)
            if input[min_index] > input[loop1 + loop2]:
                min_index = loop1 + loop2
        input[loop1], input[min_index] = input[min_index], input[loop1]
    return input
print(selection_sort(input)

삽입정렬

항상 정렬된상태를 유지, 첫번째 루프보다 작은 인덱스의 숫자들 비교.

이미 정렬된 숫자중 가장 큰수보다 크면 더이상진행안해도됨.

시간복잡도가. 최선의 경우 N만큼의 시간복잡도. .

input = [10, 4, 2,3,5,7,]
def insertion_sort(input):
    n = len(input)
    for loop1 in range(n - 1):
        for loop2 in range(loop1):
            #print(loop1, loop2)
            print(loop1-loop2-1 ,loop1-loop2)
            if input[loop1-loop2-1] <input[loop1-loop2]:
                input[loop1-loop2-1],input[loop1-loop2] =input[loop1-loop2],input[loop1-loop2-1]
            else:
                break
    return input
print(insertion_sort(input))

병합정렬

N/2^k = 1

k = log2N

log2N * O(N) → O(NlogN)

array_a = [1, 2, 3, 5]
array_b = [4, 6, 7, 8]
array = [5, 3, 2, 1, 6, 8, 7, 4]

def merge_sort(array):

    if len(array)<=1:
        return array

    mid = len(array)//2
    left_array = merge_sort(array[:mid])
    right_array = merge_sort(array[mid:])

    print(left_array, right_array)
    return merge(left_array, right_array)

def merge(array1, array2):
    array_c =[]

    index_a = 0
    index_b = 0

    for i in range(len(array1)+len(array2)):
        #print(len(array1)+len(array2),i )
        #print(index_a,index_b)
        if len(array1) <= index_a:
            array_c.append(array2[index_b])
            index_b += 1
        elif len(array2) <= index_b:
            array_c.append(array1[index_a])
            index_a += 1
        elif array1[index_a] >= array2[index_b]:
            array_c.append(array2[index_b])
            index_b += 1
        else:
            array_c.append(array1[index_a])
            index_a += 1
    return array_c


print(merge(array_a,array_b))

print(merge_sort(array))

퀵정렬

gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

 

input = [10, 4, 2]
def quick_sort(input):
    data_length = len(input)
    if data_length <=1:
        return input
    pivot = input[data_length//2]
    min = []
    max = []
    for num in range(data_length):
        if input[num] < pivot:
            min.append(input[num])
        elif input[num] > pivot:
            max.append(input[num])
    return quick_sort(min)+[pivot]+ quick_sort(max)
print(quick_sort(input))
728x90

팩토리얼

def factorial(n):
    if n == 1:
        return 1

    ##print(">>", n)
    return factorial(n - 1) * n


print(factorial(5))

회문(palindrome)

은 순서를 거꾸로 읽어도 제대로 읽은 것과 같은 단어와 문장을 말합니다. 한 글자도 회문

ex) 토마토, 오디오

def is_palindrome(string):

    string_len = len(string)
    if string_len <= 1:
        return True
    ##print(string[:1], "|", string[string_len - 1:])
    #if string[:1] != string[string_len - 1:]:
    if string[:1] != string[- 1]:
        return False
    else:
        return is_palindrome(string[1:- 1])


print(is_palindrome("abcba"))
print(is_palindrome("abcㅊㅊㅊba"))

 

더하거나 뺀 모든경우 수

Q. 음이 아닌 정수들로 이루어진 배열이 있다. 이 수를 적절히 더하거나 빼서 특정한 숫자를 만들려고 한다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들기 위해서는 다음 다섯 방법을 쓸 수 있다. -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target_number이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 반환하시오.

# Q. 음이 아닌 정수들로 이루어진 배열이 있다.
# 이 수를 적절히 더하거나 빼서 특정한 숫자를 만들려고 한다.
# 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들기 위해서는 다음 다섯 방법을 쓸 수 있다.

# -1+1+1+1+1 = 3
# +1-1+1+1+1 = 3
# +1+1-1+1+1 = 3
# +1+1+1-1+1 = 3
# +1+1+1+1-1 = 3

# 사용할 수 있는 숫자가 담긴 배열 numbers,
# 타겟 넘버 target_number이 매개변수로 주어질 때 숫자를 적절히
# 더하고 빼서 타겟 넘버를 만드는 방법의 수를 반환하시오.

# 3
# +1 #+1  2
# -1  0
# +1 #+1  2
# -1  0
# 2      4     8
input_array = [1, 1, 1, 1, 1]
target_number = 3
count_number = 0


def get_plus_minus_sum(index, input_array, result_number):
    #print(index,"|",result_number)
    if len(input_array) <= index:
        if result_number == target_number:
            global count_number
            count_number += 1
        return
    get_plus_minus_sum(index + 1, input_array, result_number + input_array[index])
    get_plus_minus_sum(index + 1, input_array, result_number - input_array[index])


get_plus_minus_sum(0, input_array, 0)
print(count_number)

 

728x90

이진 탐색 알고리즘의 장점

  • 선형 탐색과 비교하여 탐색 시간이 빠르다. (선형 탐색의 경우 시간 복잡도는 T(n) = θ(n)이다. ) 이진 탐색 알고리즘의 단점
  • 정렬된 리스트에서만 사용될 수 있다.

순차탐색의 시간복잡도는 O(n)

이진탐색의 시간복잡도는 O(logN)

 

finding_target = 14
finding_numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]

def is_existing_target_number_Sequential(target, array):
    find_count = 0
    for idx in range(len(finding_numbers)):
        find_count += 1
        if finding_numbers[idx] == finding_target:
            print(find_count)
            return True
    return False


def is_existing_target_number_binary(target, array):
    current_min = 0
    current_max = len(array) - 1
    current_guess = (current_min + current_max) // 2

    find_count = 0
    while current_min <= current_max:
        find_count += 1
        if array[current_guess] == target:
            print(find_count)
            return True
        elif array[current_guess] < target:
            current_min = current_guess + 1
        else:
            current_max = current_guess - 1
        current_guess = (current_max + current_min) // 2

    return False


print(is_existing_target_number_Sequential(finding_target, finding_numbers))
print(is_existing_target_number_binary(finding_target, finding_numbers))
728x90

트리

계층형 비선형 자료구조.(큐, 스택 : 선형구조)

Node : 트리에서 데이터를 저장하는 기본요소

Root Node : 트리 맨 위에 있는 노드

Level: 최상위 노드를 Level 0으로 하였을때 하위 B 브렌치로 연결된 노드의 깊이

Parent Node: 어떤 노드의 하위 레벨에 연결된노드

Child Node : 어떤 노드의 상위 레벨에 연결된 노드

Leaf Node(Terminal Node) Child Node가 하나도 없는 노드

Sibling : 동일한 Parent Node를 가진노드    *자매 형제 시빌링

Depth: 트리에서 Node가 가질 수 있는 최대 Level

이진트리, 이진 탐색트리, 균형트리(AVL, red-black), 이진힙(최대힙, 최소힙)

이진트리

노드가 최대 두 개의 자식을 가진다.

하위 노드가 4~5가 될수 없고 무조건 0, 1, 2 개만 가능

완전이진트리

Complete Binary Tree

: 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입해야 한다.

> 완전이진 트리만 배열로 표현 가능.

8             [None, 8]

6  3          [None, 8, 6, 3]

4  2  5       [None, 8, 6, 3, 4, 2, 5]

현재 인덱스 * 2 >>왼쪽자식의 인덱스

현재 인덱스 *2+1 >> 오른쪽 자식의 인덱스

현재 인덱스 //2 부모의 인덱스

8의 왼쪽자식은.  1*2  6, 오른쪽자식은 3

완전 이진 트리의 높이 : 각 레벨의 꽉 차있을떄  Level k >> 2^k개,   1+ 2^1+2^2+2^h ...

최대 노드 개수 N>> 2^h - 1

높이는 : h = log2(N+1), O(log(N))

데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진트리

큰 값이 항상 상위레벨, 작은값이 항상 하위레벨  (Max Heap)or 반대(Min Heap)로  구현되야 함.

8

63

421

> 4보다 3이 크지만. 부모가 아니라 상관없음. 부모 자식 관계만보면됨

Max heap 에 원소 추가.

Min heap 에 원소 추가.

1. 원소를 맨 마지막에 넣습니다.

2. 부모노드와 비교합니다. 대소관계가 맞지 않으면 자리를 바꿉니다.

3. 2번을 반복합니다.

Max heap, Min Heap 원소 삭제 ==루트노드를 삭제

  1. 루트 노드와 맨 끝에 있는 원소를 교체
  2. 맨뒤에 있는원소(원래 루트노드)를 삭제한다.
  3. 변경된 노드와 자식노드를 비교한다.  대소관계가 맞지 않으면 자리를 바꿈
  4. 자식 노드 둘 보다 부모 도드가 크거나 가장 바닥에 도달하지 않을때까지 3 반복
  5. 2에서 제거한 원래 루트 노드를 반환합니다.
728x90

그래프

연결되어 있는 정점과 정점간의 관계를 표현할수 있는 자료구조.

선형구조는 자료저장,  꺼내는것, 비선현구조는 표현에 초점.

그래프는 연결관계에 초점.

그래프는 유방향(Directed Grape)과  무방향(undirected Grape) 그래프 두가지가 있음.

 

 

1) 인접행렬(Adjacency Matrix)

2차원 배열로 그래프의 연결 관계를 표현

0 1 2 3

0xOxx

1OxOx

2xOxO

3xxOx

graph = [

[false, true , false, false]

[true, false, true, false]

[false, true, false, true]

[false, false, true, false]

]

 

 

2) 인접리스트(Adjacency List)

링크드 리스트로 그래프의 연결관계를 표현

0->1

1->0->2

2->1>3

3->2

graph = {

0: [1],

1:[0,2],

2:[1,3],

3:[2]

}

시간 vs 공간

인접행렬은 즉각적으로 0과 1일 연결되었는지 바로 알수있음.

O(노드^2) 공간사용

인접리스트 즉각적으로연결되었는지 알수없고 리스트를 검토.

O(간선) 시간 사용.

O(간선 +노드 ) 공간사용

'Algorithm' 카테고리의 다른 글

[1028알고리즘 16]이진탐색 vs 순차탐색  (0) 2021.04.10
[1028알고리즘 15]트리, 힙  (0) 2021.04.10
[1028알고리즘 14]그래프  (0) 2021.04.10
[1028알고리즘 13]탑송신  (0) 2021.04.10
[1028알고리즘]Queue - JAVA  (0) 2021.04.10
[1028알고리즘 12] 큐 구현  (0) 2021.04.10
728x90
#[6, 9, 5, 7, 4]   →[0, 0, 2, 2, 4]
# 4 는 4번째에서 수신
# 7은 2번째에서 수신
# 5는 두번째에서 수신
# 9는 수신안됨
# 6은 수신안됨

top_heights = [6, 9, 5, 7, 4]


def get_resive_top_order(heights):
    result = [0]* len(heights)
    while heights:
        height = heights.pop()
        for idx in range(len(heights)-1,0,-1):
            print(idx)
            if heights[idx] > height:
                result[len(heights)] = idx +1
                break
    return result

print(get_resive_top_order(top_heights))

'Algorithm' 카테고리의 다른 글

[1028알고리즘 15]트리, 힙  (0) 2021.04.10
[1028알고리즘 14]그래프  (0) 2021.04.10
[1028알고리즘 13]탑송신  (0) 2021.04.10
[1028알고리즘]Queue - JAVA  (0) 2021.04.10
[1028알고리즘 12] 큐 구현  (0) 2021.04.10
[1028알고리즘 11] 스택구현  (0) 2021.04.10
728x90
import java.util.HashMap;
import java.util.Map;
 Map<Integer,Integer> wants_dic = new HashMap<>();
 wants_dic.put(1, 1);
 System.out.println(wants_dic.get(1)+1);
 
import java.util.LinkedList;
import java.util.Queue;
 Queue<Integer> queue = new LinkedList<>();
 		 System.out.println(queue.add(1));
         System.out.println(queue.peek());
		 System.out.println(queue.poll());
		 System.out.println(queue.add(1));
		 System.out.println(queue.add(2));
		 System.out.println(queue.remove());
		 queue.clear();
         

'Algorithm' 카테고리의 다른 글

[1028알고리즘 14]그래프  (0) 2021.04.10
[1028알고리즘 13]탑송신  (0) 2021.04.10
[1028알고리즘]Queue - JAVA  (0) 2021.04.10
[1028알고리즘 12] 큐 구현  (0) 2021.04.10
[1028알고리즘 11] 스택구현  (0) 2021.04.10
[1028알고리즘 10]스택 vs 큐  (0) 2021.04.10
728x90
  • 노드구현
  • 큐 의 초기화 구현 * head, tail
  • 큐의 enqueue data 마지막에넣음
  • 큐의 dequeue 처음에서뺌
  • 큐의 peek
  • 큐의 isEmpty()
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class Queue:
    def __init__(self):
        self.head = None
        self.tail = None

    def isEmpty(self):
        return self.head is None

    def enqueue(self,data):
        new_node = Node(data)
        if self.isEmpty():
            self.head = new_node
            self.tail = new_node
            return

        self.tail.next = new_node
        self.tail = new_node

    def dequeue(self):
        if self.isEmpty():
            print("비었음")
            return
        delete_head = self.head
        self.head = delete_head.next
        return delete_head

    def peek(self):
        if self.isEmpty():
            print("비었음")
            return
        return self.head.data


q = Queue()
q.enqueue(3)
print(q.peek())
q.enqueue(4)
print(q.peek())
print(q.dequeue().data)
print(q.peek())

'Algorithm' 카테고리의 다른 글

[1028알고리즘 13]탑송신  (0) 2021.04.10
[1028알고리즘]Queue - JAVA  (0) 2021.04.10
[1028알고리즘 12] 큐 구현  (0) 2021.04.10
[1028알고리즘 11] 스택구현  (0) 2021.04.10
[1028알고리즘 10]스택 vs 큐  (0) 2021.04.10
[1028알고리즘 09]링크드리스트 구현  (0) 2021.04.10
728x90
  • 노드생성
  • 스택의 push _입력
  • 스택의 pop _ 빼내기._head
  • 스택의 peek_맨앞데이터 보기
  • 스택의 isEmpty() 스택이 비어있는지 여부.
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class Stack:
    def __init__(self):
        self.head = None

    def push(self, value):
        next_node = self.head
        self.head = Node(value)
        self.head.next = next_node

    def pop(self):
        return_node = self.head
        if self.is_empty():
            print("비었음")
            return
        self.head = return_node.next
        return return_node

    def peek(self):
        if self.is_empty():
            print("비었음")
            return
        return self.head.data

    def isEmpty(self):
        if self.head is None:
            return True
        return False


s = Stack()
s.push("b")
s.push("c")
print(s.peek())
print(s.pop().data)
print(s.peek())
print(s.isEmpty())
print(s.pop().data)
print(s.isEmpty())
728x90

스택

: Last in First out : 한쪽 끝으로만 자료를 넣고 뺼 수 있는 자료구조. 했떤 행동 순서기억할때 유리.

push : 맨 위에 데이터 넣기

pop 맨위의 데이터 뽑기

peek 맨위의 데이터 보기.

isEmpty 스택이 비어있는지 여부 반환.

stack = [] # 빈 스택 초기화 stack.append(4) # 스택 push(4) stack.append(3) # 스택 push(3) top = stack.pop() # 스택 pop print(top) # 3!

 

스택구현

First in First out

enqueue(data) 맨 뒤에 데이터 추가.   : tail 에 추가.

dequeue() 맨앞에 데이터 뽑기          :  head 에 서 뺌

peek() 맨앞의 데이터 보기

isEmpty()큐가 비었는지, 안비었는지 여부 반환

 

큐구현

탑문제

 

728x90
  • node 구현 _ data, next
  • 링크드리스트 init _head
  • 링크드리스트 append
  • 링크드리스트 프린트 all
  • 링크드리스트 get Node_index
  • 링크드리스트 add Node index value
  • 링크드리스트 delete Node index
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedList:
    def __init__(self, value):
        self.head = Node(value)
        
    def __len__(self):
        cur = self.head
        list_len = 1
        while cur.next is not None:
            list_len += 1
            cur = cur.next
        return list_len

    def append(self, value):
        current_node = self.head
        while current_node.next is not None:
            current_node = current_node.next
        current_node.next = Node(value)

    def print_all(self):
        current_node = self.head
        print_text = current_node.data
        while current_node.next is not None:
            current_node = current_node.next
            print_text += ", " + current_node.data
        print(print_text)

    def get_node(self, index):
        current_node = self.head
        for i in range(0, index):
            if current_node.next is None:
                print("데이터가 존재하지 않습니다.")
                return None
            current_node = current_node.next
        return current_node

    def add_node(self, index, value):
        new_node = Node(value)
        if index == 0:
            new_node.next = self.head
            self.head = new_node
            return

        before_node = self.get_node(index - 1)
        if before_node is None:
            print("추가할수가 없습니다.")
            return
        new_node.next = before_node.next
        before_node.next = new_node

    def delete_node(self, index):

        if index == 0:
            self.head = self.head.next
            return
        before_node = self.get_node(index - 1)
        if before_node is None:
            print("삭제할수가 없습니다.")
            return
        before_node.next = before_node.next.next


linked_list = LinkedList("a")
print(linked_list.head.data)
linked_list.append("b")
linked_list.print_all()
print(linked_list.get_node(1).data)
linked_list.add_node(0, "first")
linked_list.print_all()
linked_list.add_node(1, "2th")
linked_list.add_node(2, "3th")
linked_list.add_node(3, "4th")
linked_list.add_node(3, "4th")
linked_list.print_all()
linked_list.add_node(10, "4th")
linked_list.delete_node(10)
linked_list.delete_node(0)
linked_list.print_all()
linked_list.delete_node(3)
linked_list.print_all()
728x90
  배열 링크드리스트특징 배열 링크드리스트
정의 같은 종류의 데이터들이 순차적으로 저장되는 자료구조 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다
특정원소 조회 원소에 즉시 접근 0부터 시작하는 인덱스 존재O(1) 리스트 특정원소 접근시 연결고리를 따라 탐색 O(N)
원소를 삽입/삭제 O(n) O(1)의 시간복잡도 앞뒤 포인터만 변경
원소 새로 추가 모든 공간 다 차면 새로운 공간 할당 모든 공간 다 차도 맨 뒤에 노드만 동적추가
특징 크기가 정해진 데이터 공간, 변경 불가,데이터 접근하는 경우가 빈번하면 Array 리스트는 크기가 정해지지 않은 데이터 공간삽입 삭제 빈번하면 LinkedList

python 배열은 list 라고 부름 append 를 함 >> 파이썬 list는 array 로 구현

append시 내부적으로 동적배열을 사용하여 배열의 길이가 늘어나도 O(1) 시간복잡도 되도록 설계

파이썬의 경우 배열은 링크드리스트로 쓸수 있고, 배열로도 쓸수있게 만든 효율적 자료구조

 

링크드 리스트 구현 

 

728x90
#Q. 0과 1로만 이루어진 문자열이 주어졌을 때, 이 문자열에 있는 모든 숫자를 전부 같게 만들려고 한다. 할 수 있는 행동은 문자열에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다.
# 예를 들어 S=0001100 일 때,전체를 뒤집으면 1110011이 된다.
# 4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어서 2번 만에 모두 같은 숫자로 만들 수 있다.
# 하지만, 처음부터 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 한 번에 0000000이 되어서 1번 만에 모두 같은 숫자로 만들 수 있다.
# 주어진 문자열을 모두 0 혹은 모두 1로 같게 만드는 최소 횟수를 반환하시오.

input="01110"


def find_count_to_turn_out_to_all_zero_or_all_one(input):
    number_sum = 0
    for num in input:
        if num == "1":
            number_sum += 1
    #print(len(input)//2 , number_sum)
    if len(input)//2 >= number_sum:
        return number_sum
    else:
        return len(input) - number_sum



print(find_count_to_turn_out_to_all_zero_or_all_one(input))
728x90

제곱근 이하만 계산하면된다  : 18의 약수 3*6, 6*3 도 됨.. 제곱근 이하만 확인하면 OK

설명 참고 >> www.it-note.kr/308

# 005 정수입력시 그이하 소수 출력
number = 20


# 소수 : 약수가 1과 자기자신밖에 없는것.
# N이 N의 제곱근보다 크지 않은 어떤소수로도 나눠지지 않는다.

def find_prime_list_under_number(number):
    prime_list = []
    count = 0
    for n in range(2, number + 1):
        for i in prime_list:
            count += 1
            if n % i == 0 and i * i <= n:
                break
        else:  # 브레이크가 한번도 실행안되었을때
            prime_list.append(n)
    print("최종:", count)
    return prime_list


def find_prime_list_under_number1(number):
    prime_list = []
    count = 0
    for n in range(2, number + 1):
        for i in range(2, n):
            count += 1
            if n % i == 0:
                break
        else:
            prime_list.append(n)
    print("1:", count)
    return prime_list


def find_prime_list_under_number2(number):
    prime_list = []
    count = 0
    for n in range(2, number + 1):
        for i in prime_list:  # 2~ n-1 중에서 소수인 친구들만
            count += 1
            if n % i == 0:
                break
        else:  # 브레이크가 한번도 실행안되었을때
            prime_list.append(n)
    print("2", count)
    return prime_list


print(find_prime_list_under_number1(number))

print(find_prime_list_under_number2(number))

print("최종: ", find_prime_list_under_number(number))
728x90
# Q. 다음과 같이 영어로 되어 있는 문자열이 있을 때, 이 문자열에서 반복되지 않는 첫번째 문자를 반환하시오. 만약 그런 문자가 없다면 _ 를 반환하시오.
# "abadabac" # 반복되지 않는 문자는 d, c 가 있지만 "첫번째" 문자니까 d를 반환해주면 됩니다!
import re

#input = "abadabac"
input = "abab"

def find_not_repeating_first_character(input):
    ascii_a = ord("a")
    ascii_z = ord("z")
    occured_alphabet = [0] * (ascii_z - ascii_a + 1)
    # print(ord("z")-ord("a")+1)
    input_param = input.lower()
    input_param = re.sub("[^a-z]", "", input_param)
    for text in input_param:
        occured_alphabet[ord(text)-ascii_a] += 1
    #print("occured_alphabet: ",occured_alphabet)

    for text in input_param:
        if occured_alphabet[ord(text) - ascii_a] == 1:
            return text
    return "_"


print(find_not_repeating_first_character(input))

728x90
#Q. 다음과 같이 0 혹은 양의 정수로만 이루어진 배열이 있을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 '✕' 혹은 '+' 연산자를 넣어 결과적으로 가장 큰 수를 구하는 프로그램을 작성하시오.
#단, '+' 보다 '✕' 를 먼저 계산하는 일반적인 방식과는 달리, 모든 연산은 왼쪽에서 순서대로 이루어진다.
input = [0, 3, 5, 6, 1, 2, 4]

# 1이하는 더하고 크면 곱한다.

def find_max_plus_or_multiply(input):

    result = input[0]

    for idx in range(1,len(input)):
        if input[idx] >= 1 :
            result += input[idx]
        else:
            result *= input[idx]

    return result

print(find_max_plus_or_multiply(input))
728x90
# 002 최빈값 찾기, 최빈값==가장많은 빈도
import re

input = "I'm Going To Live Every Minute Of It."


# 정규 표현식(正規表現式, 영어: regular expression, 간단히 regexp[1] 또는 regex, rational expression)

def find_max_occured_alphabet(input):
    ascii_a = ord("a")
    ascii_z = ord("z")
    occured_alphabet = [0] * (ascii_z - ascii_a + 1)
    # print(ord("z")-ord("a")+1)
    input_param = input.lower()
    input_param = re.sub("[^a-z]", "", input_param)
    for text in input_param:
        occured_alphabet[ord(text)-ascii_a] += 1

    #print("occured_alphabet: ",occured_alphabet)

    max_occured_idx = 0
    max_occured_idx_value = occured_alphabet[0]
    for idx in range(len(occured_alphabet)):
        if max_occured_idx_value < occured_alphabet[idx]:
            max_occured_idx_value = occured_alphabet[idx]
            max_occured_idx = idx

    return chr(max_occured_idx + ascii_a)


print(find_max_occured_alphabet(input))
728x90
# 001 최대값을 찾아라

input = [1, 2, 4, 6, 7, 8, 9]


def find_max_num(input):
    max_num = input[0]
    for idx in range(1,len(input)):
        if max_num < input[idx]:
            max_num = input[idx]
    return max_num

print(find_max_num(input))
728x90

 

알고리즘

어떤 문제의 해결을 위하여 입력된 자료를 토대로 하여 원하는 출력을 유도해내는 규칙의 집합

시간복잡도

입력한 값과 해결한 시간과 상관관계

공간복잡도

입력한 값과 해결한 공간과 상관관계

cf) 알고리즘의 성능은 시간보다 공간 희생이 더 좋은방법

점근표기법

asymptotic notation

어떤 함수의 증가양산을 다른 함수와 비교로 표현하는 추론과 해석의 방법

빅오

Big-O

O(n) 최악의 성능

빅오메가

Big-Ω

Ω(n) 최선의 성능

+ Recent posts