본문 바로가기

자료구조8

중위표기식을 후위표기식으로 변환하기 (Java) 표기식(expression)* 중위표기식(A+B)-C*D/E 처럼 연산자가 직접 연산하는 피연산자 사이에 위치하는 표기식* 후위표기식AB+CD*E/- 처럼 피연산자 뒤에 연산자가 위치하는 표기식배경지식중위표기식을 후위표기식으로 변환하려면 연산에 대한 '우선순위'를 알아야 한다.우선순위는 다음과 같다.소괄호중괄호대괄호^, *, / __제곱, 곱셈, 나눗셈+, - __ 덧셈, 뺄셈소괄호 안에 있는 식을 계산하고, 다음으로 중괄호 안에 있는 식을 계산하고, 다음으로 대괄호 안에 있는 식을 계산한다.변환 방법피연산자는 바로 출력한다.여는 괄호를 만나면 stack에 push 한다.^, *, / 피연산자를 만나면 stack의 peek가 자신과 같은 우선순위인지 파악하고, 같다면 pop을 한 번 하고, 자신을 pus.. 2025. 4. 12.
백준 11505 - 구간 곱 구하기 (Python3) https://www.acmicpc.net/problem/11505💡 해결방법구간 곱을 다루는 세그먼트 트리를 구현해서 문제 해결👀 풀이세그먼트 트리로 초기화하는 메서드기존 값을 변경해주는 메서드입력된 구간 내의 곱을 반환하는 메서드를 구현하여 정해진 쿼리를 처리한다.특징으로는 기존 값을 원래는 내려가면서 업데이트를 했다면, 이번에는 말단 노드에서 시작해서 루트 노드까지 올라오며 update를 한다.🧾코드import sysinput = sys.stdin.readlinemod_value = 10**9+7N, M, K = map(int, input().split())arr = [int(input()) for _ in range(N)]tree = [0] * (N*4)def init(start, end, .. 2025. 3. 31.
Segment Tree(세그먼트 트리) (Python3) 세그먼트 트리란?세그먼트 트리는 구간의 정보를 알고 싶을 때 사용하는 트리입니다.각 노드는 자식 노드의 정보를 연산한 값을 저장하고 있습니다. 이 특징으로 구간의 사칙연산, 최대·최솟값 등을 구할 때 자주 사용한다고 합니다. 개발자는 배열 혹은 리스트에서 부분의 합 정보를 알고 싶습니다. 그래서 선형 탐색으로 접근을 하고, 구간이 일치한다면 그 정보들을 하나하나 가져옵니다. 이것은 구현이 쉬우나, O(N)의 비용이 발생합니다. 세그먼트 트리의 노드는 부분의 정보를 저장하고 있습니다.말단 노드(leaf node)에 접근하면, 배열의 원소 값과 일치합니다.하지만 말단 노드의 부모 노드 부터는, 자식 노드의 정보를 합한(혹은 빼거나 곱하는 등) 값을 저장하고 있습니다.그래서 필요한 구간의 노드를 찾아내면 원하.. 2025. 3. 29.
Binary Search Tree(이진 탐색 트리) Binary Search Tree는 특정한 규칙을 따르는 이진 트리이다.이진 트리는 부모 노드가 자식 노드를 최대 2개까지 갖는 트리이다.특정한 규칙이란왼쪽 자식 노드는 부모 노드보다 작거나 같다.오른쪽 자식 노드는 부모 노드보다 크다.이진 탐색은 주어진 목표를 향해 전체 크기의 반씩 나누고 비교하여 접근하는 탐색 방법이다.원래는 정렬된 배열에서만 가능했다. 하지만 이진 탐색 트리는 위의 규칙 덕분에 root 노드로부터 찾고자 하는 값을 비교해감으로써 원하는 값에 접근이 쉽다.  ✅ 장점1. 탐색, 삽입, 삭제의 연산이 평균적으로 빠르다.트리의 노드 개수가 n 일때, 탐색, 삽입, 삭제의 평균적인 시간 복잡도는 O(log n) 이다.트리의 높이가 h 일때, 연산을 최대 h번 한다.균형이 잘 갖춰진 트리일.. 2025. 2. 20.
Tree (트리) 트리는 스택, 큐, 연결리스트와는 다르게 비선형적 자료구조이다.트리는 계층 구조로 이루어져 있다.계층 구조로 나타내기 적합한 자료는 가계도, 목차-내용, 폴더-파일 관계 등이 있다. 보통 일반 적인 경우에는 이진 트리를 많이 사용한다.특별한 경우(게임 맵, 웹사이트의 카테고리 등)에서는 삼진 이상의 다진 트리를 이용하기도 한다. 트리는 가지는 특징에 따라서 이진 트리, 완전 이진 트리, B-Tree, AVL트리, 레드 블랙 트리 등등 다양한 이름으로 불린다.마치 이브이같다.이 포스트에서는 트리의 특징에 대해서 설명하고, 트리의 개념을 이해하자.트리는 한 개 이상의 요소(노드)로 이루어진 유한 집합이다. 이들 중에서 특정 한 개의 노드는 root node라고 불리고, 나머지는 subtree(서브 트리)라고.. 2024. 10. 3.
Circular Linked List(원형 연결 리스트) (Java) Circular Linked List는 Singly Linked List(단일 연결 리스트)의 확장된 개념이다. 나는 단일 연결 리스트의 끝 원소(꼬리, tail)를 가장 앞 원소(머리, head)로 이어줌으로써 선형의 리스트가 둥글게 말리는 효과를 얻는다고 이해했다. 그래서 내가 이해한 바를 토대로 오늘 구현을 시작했다. 장점 효율적인 탐색 : 원형 연결 리스트의 어느 부분에서 시작하던, 모든 노드(원소)들을 탐색할 수 있다. 단점 메모리 사용량 : 마지막 노드(원소)가 처음 노드를 가리키기 때문에 약간의 메모리를 더 사용한다. 무한 루프 : 마지막 노드가 처음 노드를 가리키기 때문에 조건 등을 걸지 않고 탐색하면 무한 루프에 빠질 수 있다. 삭제 코드의 복잡성 : head나 tail 노드의 경우, 삭.. 2023. 3. 24.
[S4] 백준 4949 - 균형잡힌 세상 (Python3) https://www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 각 줄은 마침표(".")로 끝난다 www.acmicpc.net 이 문제보다 한 단계 쉬운 문제는 백준 9012번: 괄호라고 생각한다. 이 문제를 풀고나서 이 문제를 푸는 것을 추천한다. 해결방법 스택을 활용하는 문제이다. bracket 이라는 리스트 변수에 여는 괄호("(", "[")를 담고, 닫는 괄호(")", "]")가 나올 때마다 bracket의 원소를 pop 해주는 방식으로 문제를 풀었다. 코드 while (string:=inpu.. 2023. 1. 14.
[Python] 백준 5430 - AC https://www.acmicpc.net/problem/5430 해결방법 문제에 나와있는 대로 따르면 충분히 풀 수 있는 문제이긴 하다. 하지만 곧이곧대로 따르기만 하면 여러 가지 문제로 해결이 불가능하다. 코드 tc = int(input()) for _ in range(tc): command = input() arr_len = int(input()) input_raw_arr = input() raw_arr = list(map(str, input_raw_arr)) raw_arr.pop(0); raw_arr.pop(-1) arr = (''.join(raw_arr)).split(',') error = False # True: 에러 on, False: 정상작동중 head = True # True: 앞부터 읽.. 2022. 5. 29.

티스토리툴바