와구와구

https://www.acmicpc.net/problem/13334아이디어각 사람들의 집과 사무실에 상관 없이 선분 상 왼쪽에 있는 곳을 튜플의 왼쪽에 둔다. (x, y) -> x 스위핑 방식 : 사람들 case를 정렬한 후, 각 case마다 오른쪽 점을 기준으로 한 철로를 옮기면서 철로 별 case가 얼마나 있는지 계산한다.case 정렬철로 안에 있는지 판별을 오른쪽 점인 y를 기준으로 판별하므로, y값을 기준으로 오름차순으로 정렬한다.철로 좌표 = (start, end)우선순위큐 사용 철로 안에 case가 있으면, 해당 case를 queue에 push한다.철로 안에 없는 new case 차례라면 철로를 옮겨야 한다.철로를 new case의 end값을 기준으로 설치한다고 가정이 때, 새 철로 start..

https://www.acmicpc.net/problem/2170아이디어start와 end는 각각 이어지는 긴 선분의 처음과 끝 부분이다.튜플 (x, y)에서 x가 end보다 큰 경우, 새로운 선분임으로 취급한다.이 때, 새 선분 이전까지의 선분 길이를 정답에 더한다.이후 start와 end를 갱신한다.일부만 포함된 경우, end값만 y로 갱신한다.완전히 포함된 경우 선분 길이에 영향이 없으므로 아무 행동을 취하지 않는다.# https://www.acmicpc.net/problem/2170# sweepingimport sysN = int(input())lines = [0] * Nfor idx in range(N) : x, y = map(int, sys.stdin.readline().split()) ..

https://www.youtube.com/watch?v=FeAowtZB80w Neo4j그래프 데이터베이스 DBMS, Cypher라는 그래프 쿼리 언어를 통해 그래프 데이터를 다룸 Cypher그래프 데이터베이스에 접근하기 위해 사용되는 그래프 쿼리 언어MATCH (n1)-[r]->[n2] RETURN r, n1, n2 LIMIT 25MATCH : 어떤 노드와 어떤 관계를 표현할 건지 검색할 노드와 릴레이션을 표현하는 구문RETURN : 위에서 표현된 노드와 릴레이션들 중 어떤 값을 반환할 건지에 대한 설명을 RETURN 구문에 작성LIMIT : 어떤 노드와 릴레이션들이 조회가 되었다면, 그 조회된 값들 중 25개만 리턴하고 싶으면 LIMIT 25WHERE 등의 조건문도 사용 가능Neo4j Sandbox..

https://www.acmicpc.net/problem/11725 입력으로 주어지는 것들이, '처음에 나오는 것이 부모다'라는 말이 없어서 undirectional graph로 트리를 생성했다.노드 1이 항상 루트이므로, 노드 1에서부터 BFS를 수행하며 노드의 부모를 찾는 것을 목표로 했다. # https://www.acmicpc.net/problem/11725# Tree, BFSimport sysfrom collections import defaultdict, dequeN = int(input())tree = defaultdict(list)for _ in range(N-1) : a, b = map(int, sys.stdin.readline().split()) tree[a].append(b..

참고https://www.youtube.com/watch?v=Vj-xOhIMkZE 구글 코랩에서 진행했다. 필요 패키지를 설치한다.!pip install neo4j-graphrag!pip install openai openai API KEY를 설정한다.json으로 API KEY를 저장하여, json을 불러왔다.import jsonimport oswith open('./drive/MyDrive/실습/251010_GraphRAG/openai_api_key.json') as j : json_file = json.load(j) j.close()os.environ["OPENAI_API_KEY"] = json_file['OPENAI_API_KEY'] neo4j ERExtraction 템플릿은 다음과 같..

https://www.acmicpc.net/problem/14725 # https://www.acmicpc.net/problem/14725# Tree, DFSimport sysfrom collections import defaultdictsys.setrecursionlimit(10**8)N = int(input())tree = defaultdict(list)start = set([])for _ in range(N) : path = sys.stdin.readline().split() num_rooms = int(path[0]) rooms = path[1:] path_name = '' for idx in range(num_rooms) : if idx == 0 : ..

https://www.acmicpc.net/problem/15681 임의의 루트가 있는 트리가 에서, 입력 U를 루트로 하는 서브트리의 노드 개수를 구하는 문제이다. 아이디어DFS recursion으로 leaf에 도달했을 때, leaf node의 서브 트리의 노드개수는 1그리고 leaf의 부모 노드로 돌아가면 자식 노드들 개수를 본인 노드 개수와 합친다. # https://www.acmicpc.net/problem/15681# Tree, DPimport sysfrom collections import defaultdict, dequesys.setrecursionlimit(10**6)N, R, Q = map(int, sys.stdin.readline().split())tree = defaultdict(li..

참고https://www.youtube.com/watch?v=mlsZIThxQcQ https://arxiv.org/abs/2404.16130 From Local to Global: A Graph RAG Approach to Query-Focused SummarizationThe use of retrieval-augmented generation (RAG) to retrieve relevant information from an external knowledge source enables large language models (LLMs) to answer questions over private and/or previously unseen document collections. However, RAG f..

https://www.acmicpc.net/problem/2533 인생 첫 트리에서의 다이나믹 프로그래밍... 이어서 고민을 제법 많이 했다. 먼저 트리에서 다이나믹 프로그래밍을 어떻게 하지? 했는데 DFS를 활용하는 듯했다.https://orijeje.tistory.com/40 [알고리즘] 트리에서의 다이나믹 프로그래밍(Tree DP)tree dp 이전에 일반적인 dp에 대해 살짝 이야기하고 tree dp로 넘어가려 한다. 먼저 어떤 문제를 dp로 풀기 위해서는 다음 3가지 조건을 만족해야 한다. 1) 큰 문제를 작은 문제로 나눌 수 있다. 2) 충orijeje.tistory.com위 블로그에서 DFS를 기반으로한 DP 코드를 간단하게 적어두어 이를 참고했다.void dfs(int cur){ if..

https://www.acmicpc.net/problem/7569 3차원 배열에서의 BFS문제 기존에 defaultdict을 활용한 Graph를 중심으로 탐색을 진행했었는데, 이번엔 메모리 초과 문제로 사용을 포기했다.대신 BOX와 visited를 적극 활용하여 defaultdict을 대신했다.토마토가 다 익는데 필요한 시간은 visited에 적어 최대한 메모리 사용을 줄였다. 조건이 몇 개 있다. 토마토가 모두 익지 못하는 경우, 애초에 토마토가 모두 익어 있는 경우에 다른 수를 출력해야 한다.이를 위해 green_tomatos라는 변수를 둬서 BFS 중 익을 경우 요소를 제거하는 방식으로 안 익은 토마토를 바로 확인할 수 있도록 했다.또한 처음 BFS를 시작하기 전 green_tomatos의 요소 갯..