본문 바로가기

Python17

[Python] 스택 응용 : 후위 표기법 이용한 수식 계산 2023.09.15 - [C/알고리즘] - 스택 응용(수식 계산) 스택 응용(수식 계산) 1. 수식표기법 (1) 중위표기법(infix notation) : 연산자를 피연산자의 가운데 표기하는 방법 => 우리가 사용하는 방식 ex) A+B (2) 후위표기법(postfix notation) : 연산자를 피연산자 뒤에 표기하는 방법 => 컴 growingupis.tistory.com => 수식 계산 알고리즘의 자세한 동작 과정은 위의 글에 상세히 적어두었다 1. 중위 표기 => 후위 표기 변환 연습 class ArrayStack: def __init__(self): self.data = [] def size(self): return len(self.data) def isEmpty(self): return se.. 2023. 11. 15.
[python] dummy node 활용한 Linked List #맨 앞에 dummy node를 추가한 형태 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 =[] cur= self.head.next while(cur is not None): result.append(cur.data) cur=cur.next return result def getAt(self, pos): if pos self.nodeCount: return N.. 2023. 11. 14.
[Python]최소 공통 조상(Lowest Common Ancestor) 1. 최소 공통 조상: 두 노드의 가장 가까운 공통 조상 노드를 구하는 것 1-1. 단순 LCA 알고리즘 1-1-1. 알고리즘 동작 과정모든 노드에 대한 깊이 계산최소 공통 조상을 찾을 두 노드 확인 - 두 노드의 깊이가 동일하도록 함 - 두 노드의 부모가 같아질때까지 반복적으로 두 노드의 부모 방향으로 거슬러 올라감 (1) 깊이 계산: BFS(너비 우선 탐색 이용) => 깊이 계산 동작 과정 아래 그림처럼 단순예제로 표현from collections import deque def BFS(start): queue = deque() queue.append(start) visited[start]=True while(queue): now = queue.popleft() for node in graph[now].. 2023. 10. 12.
[Python]바이너리 인덱스 트리(Binary Indexed Tree) : 2진법 인덱스 구조를 통해 구간 합 문제 효과적으로 해결가능한 자료구조 (1) 정수에 따른 2진수 표기 7 => 00000000 00000000 00000000 00000111 -7 => 111111111 111111111 111111111 11111001 7 & (-7) = 1 : 7의 마지막 1의 위치=> 특정 수 K의 마지막 1의 위치 (2) 트리 구조 만들기 : 마지막 1의 위치 = 내가 저장하고 있는 값들의 갯수 ex) 16의 0이 아닌 마지막 비트 = 16 : 1~16까지의 모든 데이터들의 합을 담겠다 (3) 특정 값 변경하기 (처음에 데이터 값 설정할때도 포함) : 0이 아닌 마지막 비트만큼 더하면서 구간들의 값 변경(4) 합 구하기 (1부터 N번째까지의 합 구하기) : 0이 아닌 마지막.. 2023. 10. 10.
[Python]기타 알고리즘 1. 소수 판별 알고리즘(1) 제곱근 이용한 소수판별: 하나의 수에 대해 소수인지 아닌지 판별 : O(N^1/2) import math def Is_Prime(num): sqrt_num = int(math.sqrt(num)) for i in range(2,sqrt_num+1): if(num%i==0): return False return True def main(): num = int(input("소수판별한 숫자를 입력하시오 ")) if(Is_Prime(num)): print("소수입니다") else: print("소수가 아닙니다") if __name__=="__main__": main()(2) 에라토스테네스의 체: 특정한 수의 범위 안에 존재하는 모든 소수를 찾는 경우 이용 : O(NloglogN) 1.. 2023. 10. 6.
[Python]최단 경로 알고리즘 : Dijkstra Algorithm, Floyd Washall 1. 다익스트라 알고리즘 1-1. 순차탐색을 이용한 다익스트라 INF = int(1e9) def get_min_distance(res, visited): min_val = INF idx=0 for i in range(1,len(res)): if(visited[i]==0 and min_val>res[i]): min_val = res[i] idx = i return idx def dijkstra(graph, E,V, start, res): visited = [0]*(V+1) #초기화 res[start]=0 for j in range(1,V+1): for i in range(1,V+1): now= get_min_distance(res,visited) visited[now]=1 for now_to, distan.. 2023. 9. 26.

티스토리툴바