Python/알고리즘11 [python] 백준 2346 - 풍선 터뜨리기 (원형큐 응용) 1. 문제 설명 https://www.acmicpc.net/problem/2346 2346번: 풍선 터뜨리기 1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선 www.acmicpc.net 1-1. 모듈러 연산 ≪cf≫ Division Algorithm : ∀a,b ∈Z, b>0 then ∃! q, r s.t a= b*q +r(0≤r0 and ballons): idx= (idx+(move-1))%len(ballons) elif(move0 and ballons): ballons.rotate(-(move-1)) elif(move 2023. 12. 4. [Python] 큐 유형문제(백준) 1. 11866번 ( 큐 응용 ) https://www.acmicpc.net/problem/11866 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net import sys from collections import deque input = sys.stdin.readline def main(): N, K = map(int, input().split()) que= deque() for i in range(1,N+1): que.append(i) print('',end="") if __name__=="__main__": main() 2. 24511번 ( 큐 & 스택 응용 ) https://www.acmi.. 2023. 11. 30. [python] 스택 응용 : 미로 문제 class Pos(): def __init__(self, row,col): self.row = row self.col= col class Stack(): def __init__(self,size): self.data=[] self.top=-1 self.size=size def push(self, item): self.data.append(item) self.top+=1 def pop(self): self.top-=1 return self.data.pop() def peek(self): return self.data[self.top] def isEmpty(self): return self.top==-1 def isFull(self): return self.top == self.size-1 def Print.. 2023. 11. 20. [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]최소 공통 조상(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. 이전 1 2 다음
