본문 바로가기

자료구조

 (6)
[자료구조] 트라이 트라이문자열을 효율적으로 탐색하는 자료구조로 O(n) 시간복잡도로 해당 문자열이 존재하는지 확인 할 수 있는 자료구조 이다.삽입, 검색, 삭제, 업데이트 : O(n) 시간이 걸린다.Node 트리구조 기반의 자료구조를 활용한다.만약 “abc123” 과 “abc12” 라는 문자열이 존재한다면 “abc12”는 같은 노드를 공유한다.삽입 :루트노드에서 자식 노드로 방문해가면서 자식노드가 존재하지 않으면 자식노드를 만들어준다.마지막 노드에 도착하면 노드에 값을 넣어준다. ( 마지막 노드인것을 판별하기위한 플래그 )삭제 :삽입과 다르게 for문이 아닌 재귀 방식으로 구현하였다.재귀방식으로 구현할경우 자식노드를 지워가면서 자식노드의 길이가 0이면 부모노드도 삭제 할 수 있다.검색 :삽입과 마찬가지로 자식노드를 방문하..
[백준] 14725번 : 개미굴 14725번: 개미굴 14725번: 개미굴 첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N (1 ≤ N ≤ 1000)개가 주어진다. 두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이 정 www.acmicpc.net 🤔 문제분석 입력값을 알파벳 순으로 정렬을 하고, 정렬한 데이터를 순회하면서 경로를 기준으로 방문처리를 하여 문제를 해결하였습니다. 이미 방문한 경로가 있다면 그 경로는 무시 하도록 하면 됩니다. 💻 코드 import sys input = sys.stdin.readline visited = set() N = int(input()) ants_route = [] for _ in range(N): temp = list(map(st..
[백준] 6198번 : 옥상 정원 꾸미기 6198번: 옥상 정원 꾸미기 6198번: 옥상 정원 꾸미기 문제 도시에는 N개의 빌딩이 있다. 빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다. i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으 www.acmicpc.net 🤔 문제분석 스택 자료구조를 활용하여 문제를 해결한다. 스택은 해당위치에서 자기자신보다 낮은 건물이 나올때까지 꺼낸다. 스택에 담긴 자료는 해당 건물포함해서 그 뒤에 볼 수 있는 건물을 담는다. 자기자신보다 큰 건물이기때문에 해당 건물을 포함한 그 뒤에있는 건물 또한 볼 수 있기때문이다. 💻 코드 import sys input = sys.stdin.readline N = int(input()) buildings = list(..
[백준] 6549번 : 히스토그램에서 가장 큰 직사각형 [백준] 6549번 : 히스토그램에서 가장 큰 직사각형 6549번: 히스토그램에서 가장 큰 직사각형 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net 🤔 문제분석 이틀공안 고민하다가, 결국 해결하지 못하여, 풀이법을 참조하였습니다. 😂 해당 문제를 해결하는 방법은 스택을 활용하여 푸는 방법과, 분할정복, 세그먼트 트리를 활용하여 푸는 방법이 있습니다. 분할정복, 세그먼트 트리 최소 높이를 찾아서, 그 지점을 기준으로 양쪽을 분할한다. 해당 구간에서 최대 ..
느리게 갱신되는 세그먼트 트리 (Segment Tree Lazy Propagation) 개념 최대한 늦게 세그먼트 트리를 갱신시키는 방법으로, Lazy Value 값을 노드에 저장시켜놓은뒤, 노드의 방문을 필요때마다, 업데이트를 시켜준다. 쿼리나, 다른 업데이트가 필요할때, 그때 노드를 방문함으로서, 업데이트를 최대한 미루는 방식이다. Lazy Value 대상은 자식노드들이 모두 업데이트가 필요할 경우이다. 모든 자식노드가 업데이트가 필요할경우 해당 부모노드에서 자식노드까지의 방문을 멈추고, 해당 부모노드에 Lazy Value 값을 갱신시킨다. 추후 나중에 필요할때 Lazy Value 값을 적용 자식들에게 가중치를 전파한다. 가령, 원소는 (0, 9)가 존재한다고 하고, (3, 7)구간을 업데이트 한다고 가정한다. 빨간색과, 흰색을 제외한 부분은 다 업데이트를 해야하는 부분이며, 하늘색 부..
[백준] 5639번 : 이진 검색 트리 https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net Node의 자료구조를 만들어 문제를 해결 하였습니다. InsertNode함수는 현재 루트 노드로부터 해당 노드를 인서트 합니다. 재귀 함수를 사용하여 preOrder 함수는 전위순회로 출력하고 postOrder 함수는 후위순회로 출력합니다. import sys sys.setrecursionlimit(10**6) class Node(object): def __init__(self,dat..

티스토리툴바