전체 글

🚀 Union_Find(서로소 집합 자료구조) Union_Find 자료구조는 스택의 pop, push처럼 Union(합집합), Find(찾기) 연산으로 구성된다. Union 연산을 확인하여, 서로 연결된 두 노드 A,B를 확인한다. - A와 B의 루트 노드 A`, B`를 각각 찾는다. - A`를 B`의 부모 노드로 설정한다.(B`가 A`를 가리키도록 한다.) 모든 Union 연산을 처리할 때까지 1번 과정을 반복한다. 실제로 구현 할 때는 A`와 B`중에서 더 번호가 작은 원소가 부모노드가 되도록 구현하는 경우가 많다. 초기 단계에서 각자 자기 자신을 부모로 가지도록 초기화 한다. Union 1,4 - 현재 각각 루트 노드가 1과 4이기 때문에 둘 중 더 큰 번호에 해당하는 루트 노드 4의 부모를 1로 ..

이 문제는 어려워서 정리 한다기 보다 인접리스트로 그래프를 만드는 것을 처음 접해서 기록 및 정리를 위해 작성한다. https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 처음 인접리스트를 배열로 구현한 코드 from sys import stdin as s s = open('input.txt','rt') n = int(s.readline()) graph = [[] for _ in range(n+1)] def preorder(num): if ..

📔 트리 구조 노드와 가지로 구성되고 각 노드는 가지를 통해 다른 노드와 연결된다. 트리에는 루트, 리프, 비단말 노드 , 자식, 부모, 형제, 레벨, 차수, 높이 등등의 용어들이 있다. 가장 위쪽에 있는 노드를 루트 가장 아래쪽에 있는 노드를 리프 루트에서 얼마나 멀리 떨어져 있는지 나타내는 레벨 각 노드가 갖는 자식의 수를 차수 루트에서 가장 먼 리프까지의 거리가 높이 📔 이진 트리의 검색 너비 우선 검색 낮은 레벨부터 왼쪽에서 오른쪽으로 검색하고, 한 레벨에서 검색을 마치면 다음 레벨로 내려가는 방법 깊이 우선 검색 깊이 우선 검색은 리프에 도달 할 때까지 아래쪽으로 내려가면서 검색하는 것을 우선으로 한다. 깊이 우선 검색의 세가지 종류의 스캔 방법 더보기 노드 방문 -> 왼쪽 자식 -> 오른쪽 자..

https://www.acmicpc.net/problem/16120 16120번: PPAP 첫 번째 줄에 문자열이 주어진다. 문자열은 대문자 알파벳 P와 A로만 이루어져 있으며, 문자열의 길이는 1 이상 1,000,000 이하이다. www.acmicpc.net 처음에 리스트 말고 collections의 deque를 사용해서 문제를 풀려고 했는데 리스트와는 다르게 deque에서는 슬라이싱하는 방법을 찾지 못해서 다시 리스트로 풀게 되었다. 간단하게 입력받은 문자를 슬라이싱해서 하나씩 스택에 넣어주면서 스택에 4개이상 쌓였을 때, 4개를 빼고 해당 문자가 PPAP이면 P를 다시 스택에 넣어주고 마지막에 스택에 남은 문자가 P이거나 P P A P가 남아있으면 PPAP 문자열이고 나머지 문자는 전부 NP 이다...

https://www.acmicpc.net/problem/5904 5904번: Moo 게임 Moo는 술자리에서 즐겁게 할 수 있는 게임이다. 이 게임은 Moo수열을 각 사람이 하나씩 순서대로 외치면 되는 게임이다. Moo 수열은 길이가 무한대이며, 다음과 같이 생겼다. m o o m o o o m o o m o o o www.acmicpc.net 이 문제는 분할 정복으로 풀어야 하는 문제 중 하나이다. 처음 접근을 할때 10**9의 문자열 길이까지 가능하기 때문에 문자열을 직접 만들면서 실행하면 시간초과나 메모리 초과가 날 것을 알았지만 그래도 한번 해봤었고 역시나 메모리 초과가 나왔다. 메모리 초과를 해결하기 위해서는 각각 단계를 분할해서 문제를 해결해야 한다. moo는 기본적으로 - S(n-1) + ..

스택 문제 - G3-2812-크게 만들기 나의 풀이 법 (스택의 갯수와 남은 숫자의 갯수를 비교해서 계산) from sys import stdin as s from collections import deque s = open('input.txt') N, K = list(map(int,s.readline().split())) arr = list(map(str.rstrip,s.readline())) a = deque() a.append(int(arr[0])) for i in range(1,N): while len(a) + N-i-1 >= N-K: # 스택 개수 + 남아있는 숫자 개수 >= 마지막에 필요한 개수 if len(a)-1 >=0 and int(arr[i]) > a[len(a)-1]: # 스택의 크기..