본문 바로가기

Computer Science/Algorithm48

[이코테] 15강. 최소 공통 조상 알고리즘 Ⅰ. 최소 공통 조상 : 기초 https://www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net N(2 ≤ N ≤ 50,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다. 두 노드의 쌍 M( 1 ≤ M ≤ 10,000 )개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다. 이 문제는 어떻게 해결할 수 있을까? O ( NM )로 풀 수 있는 문제이기도 하다. 1... 2022. 6. 1.
[이코테] 14강. 자료구조: 바이너리 인덱스 트리 먼저 아래 문제부터 보자. 1. 데이터 업데이트가 가능한 상황에서 구간 합 (Interval Sum) 문제 BOJ '구간 합 구하기' 문제: https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 어떤 N 개의 수가 주어져 있다. 그런데 중간에 수의 변경이 번번히 일어나고 그 중간에 어떤 부분의 합을 구하려 한다. 만약에 1, 2, 3, 4, 5라는 수가 있고, 3번째 수를 6으로 바꾸고 2번.. 2022. 6. 1.
[이코테 7강] 최단 경로 알고리즘 목차 [1] 가장 빠른 길 찾기 1. 가장 빠르게 도달하는 방법 2. 다익스트라 최단 경로 알고리즘 방법1. 간단한 다익스트라 알고리즘 방법2. 개선된 다익스트라 알고리즘 개선된 다익스트라 알고리즘의 시간 복잡도 3. 플로이드 워셜 알고리즘 [2] 예시1 - 미래 도시 [3] 예시2 - 전보 최단 경로 특정 지점까지 가장 빠르게 도달하는 방법을 찾는 알고리즘 [1] 가장 빠른 길 찾기 1. 가장 빠르게 도달하는 방법 ​ 한 지점에서 다른 특정 지점까지 최단 경로를 구해야 하는 경우 → 다익스트라 최단 경로 알고리즘 (그리디) 모든 지점에서 다른 모든 지점까지의 최단 경로를모두 구해야 하는 경우 → 플로이드 워셜 알고리즘 (다이나믹) 벨만 포드 알고리즘 노드를 연결하는 간선으로 그래프 표현 코딩 테스트 :.. 2022. 5. 26.
[이코테 3강] BFS & DFS 1주차 - BFS & DFS 참고 원본 - DFS & BFS 목차 [1] 배우기 전 알아야 할 기초 개념 1. 스택 2. 큐 3. 재귀함수 [2] 탐색 알고리즘 DFS / BFS 1. DFS 2. BFS [3] 예제 1. 음료수 얼려먹기 2. 미로탈출 [1] 배우기 전 알아야 할 기초 개념 탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말한다. 대표적인 그래프 탐색 알고리즘으로는 DFS와 BFS가 있다. DFS/ BFS는 코딩 테스트에서 매우 자주 등장하는 유형이므로 반드시 숙지하자 1. 스택 먼저 들어온 데이터가 나중에 나가는 형식(선입후출)의 자료구조 입구와 출구가 동일한 형태로 스택을 시각화 할 수 있음 박스 쌓기 예시 삽입과 삭제 연산이 사용 리스트 자료형을 이용하여 append(.. 2022. 5. 19.
[파이썬] DAY12 자료구조 복습 문제 자료구조 62 문제 빈칸, 이론 입학식 코딩 테스트 문제 리뷰 - openCV - Numpy - 파이프라인?? 통신과 thread ROS로 그래프 보는 기초 다짐.. 2022. 2. 4.
[파이썬] DAY11 검색 검색 탐색 키: 자료를 구별하여 인식할 수 있는 키 삽입 / 삭제 작업에서의 검색: 원소를 삽입하거나 삭제할 위치를 찾기 위해 검색 1. 수행 위치에 따른 분류 내부 검색: 메모리에 있는 자료에 대해 검색 수행 외부 검색: 보조기억장치에 있는 자료에 대해 검색 수행 2. 검색 방식에 따른 분류 1) 비교 검색 검색 대상의 키를 비교하여 검색하는 방법 순차 검색, 이진검색, 트리 검색 2) 계산 검색★ (도서관의 책 위치 찾는 방식) 계수적인 성질을 이용한 계산으로 검색 하는 방법 값을 입력하자마자 계산값을 준다. 해싱 (가장 중요) 네이버 해싱 테이블 손 코딩으로 면접 본다. 자료 구조의 형태(큐, 스택 등등)와 자료의 배열 상태(정렬 되었느냐 안되었느냐)에 따라 최적의 검색 방법 선택 1. 순차 검색 .. 2022. 1. 28.
[파이썬] DAY11 트리 코드 리뷰 계층적 연결구조라는 점에서 이중 연결리스트와는 다르다. class Node: def __init__(self,item,left=None, right=None): self.item = item self.left = left self.right = right class BinaryTree: def __init__(self): self.root =None def preorder(self,n): if n!=None: print(str(n.item),'',end='') if n.left: self.preorder(n.left) if n.right: self.preorder(n.right) def inorder(self,n): if n!=None: if n.left: self.inorder(n.left) print.. 2022. 1. 28.
[파이썬] DAY11 그래프 복습 & 정렬 설날 과제는 정리용 문제 안 낼 거래.. 그래프 코드 주석 달아놓기 넓이 우선 순위 그래프 탐색에서 우선순위 큐(늦게 들어왔더라도 우선순위 가중치를 매겨서 먼저 내보내는 큐 방식)랑 dequeue enqueue랑 헷갈리지 말것. 자료구조 스택과 스택 영역은 같다.(메모리 구조는 스택이다.) 자료구조 힙 과 힙 메모리 영역은 다르다.... 즉 힙 영역은 자료구조 힙을 쓰지 않는다. 동음이의어 같은 관계 참고로 C에서는 힙이라는 언어를 메모리에서 쓰지 않는다. API 문서 안에 라이브러리가 있다. 파이튜터는 3.6 버전을 쓴다. 코딩테스트 리스트를 주로 쓴다. 큐 스택을 직접 구현하지 않는다. 동적 프로그래밍 dp(dynamic programming) 큰 문제를 소분해서 프로그래밍함으로써.. 2022. 1. 28.
[파이썬] DAY10 그래프 1. 그래프 요소 다대다 관계 대다수의 데이터들은 다대다 관계이다. 그래프는 추가적으로 따로 공부하자 중요하다 1. 그래프란 정점(V)들의 집합 간선(E)들의 집합 2. 무방향 그래프: (Vi, Vj) = (Vj, Vi) 파이썬에서는 딕셔너리나 리스트의 특정 형식으로 그래프를 구현한다. 3. 방향 그래프 : ≠ Vi 는 머리, Vj 는 꼬리를 의미한다. 4. 완전 그래프 각 정점에서 다른 모든 정점을 연결하여 가능한 최대의 간선 수를 가진 그래프 최대 간선수 방향 그래프는 무방향 그래프의 2배이다. 5. 부분 그래프 일부 정점이나 간선 제외하여 만든 그래프 6. 가중 그래프, 네트워크 간선마다 가중치(weight)를 할당한 그래프 간선에 정점과 정점이 얼마 만큼 떨어져있는지 표기해준다. 2. 용어 정리 .. 2022. 1. 27.

티스토리툴바