Computer Science

✨그래프(Graph) 그래프(graph)는 vertex와 edge로 구성된 한정된 자료구조를 의미한다. vertex: 정점 edge: 정점과 정점을 연결하는 간선 ✨그래프(Graph)종류 무방향그래프 그래프를 연결하는 간선에 방향이없다. 방향그래프 그래프를 연결하는 간선에 방향이있다. 가중치 그래프 그래프를 연결하는 간선에 코스트가있다. 완전그래프 그래프의 모든 정점이 간선으로 연결되있다. ✨그래프(Graph)구현 인접행렬 그래프의 정점을 2차원 배열로 표현 연결됨:1 (가중치 그래프일 경우 가중치로 표현) 연결안됨:0 O(n^2) 시간 복잡도 인접리스트 그래프의 노드를 리스트로 표현 각정점에 대한 인접정점을 순차적으로 표시 O(n) 시간 복잡도 🎈참고자료 https://80000coding.oopy.i..

모델링 특징 추상화: 일정한 형식에 맞춰 표현 단순화: 제한된 표기법이나 언어로 표현 명확성: 이해하기 쉽게 표현하기 위해 애매모호함 제거 유의점 중복 : 중복되는 정보 최소화 비유연성: 데이터 정의와 데이터 사용 프로세스 분리 비일관성: 데이터들간 상호연관 관계에 대한 명확한 정의 스키마 외부스키마:각 사용자 단계의 DB 스키마. (사용자 관점)(개개인 사용자) 개념스키마:조직 전체의 DB 스키마. (설계자 관점)(모든 사용자) 내부스키마:물리적으로 데이터가 저장되는 스키마. (개발자 관점) (물리적 저장 구조) 모델링 3단계 개념적 데이터 모델링: 추상화 논리적 데이터 모델링: 속성,관계표현,속성 물리적 데이터 모델링:성능, 저장 등 물리적인 성격 데이터 독립성 논리적 독립성:개념 스키마가 변경되도 ..

✨우선순위 큐(Priority Queue) 평범한 큐나 스택과 비슷한 축약 자료형이다. 각 원소들은 우선순위를 갖고 있다. 높은 우선순위를 가진 원소는 낮은 우선순위를 가진 원소보다 먼저 처리된다. 자료구조 힙을 통하여 구현된다 ✨힙(Heap) 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리 부모노드의 키값이 자식노드의 키 값보다 항상 큰 힙을 '최대 힙' 부모노드의 키 값이 자식노드의 키 값보다 항상 작은 힙을 '최소 힙' ✨Python PriorityQueue from queue import PriorityQueue q=PriorityQueue() q.put(5) q.put(3) q.put(4) print(q.get()) #출력: 3 (우선순위,값)튜플 형태 추가 from q..

✨ 그리디 알고리즘(Greedy algorithm)최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식    ex)백준 1715번https://www.acmicpc.net/problem/1715 import sysimport heapqsum=0hq=[]for i in range(int(sys.stdin.readline().rstrip())): heapq.heappush(hq,int(sys.stdin.readline().rstrip())) sum=0if(len(hq)==1):print(0)else: while hq: a=heapq.heappop(hq) b=heapq.heap..

✨누적 합(Prefix sum) 주어진 배열에서 각 위치까지의 합을 미리 계산하여 배열에 저장해 놓는 알고리즘 빠른응답속도 추가 메모리 사용 ex) 백준 11659번 구간 합 구하기 4 https://www.acmicpc.net/problem/11659 import sys N,M=map(int,sys.stdin.readline().rstrip().split(" ")) li=list(map(int,sys.stdin.readline().rstrip().split(" "))) li2=[0] sm=0 for i in li: sm+=i li2.append(sm) for i in range(M): a,b=map(int,sys.stdin.readline().rstrip().split(" ")) sys.stdout.w..

✨동적 계획법(dynamic programming) 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다. 재귀,메모이제이션을 이용한다. ✨메모이제이션(Memoization) ‘중복 계산'을 피하기 위한 기법 이전에 계산한 값을 메모리에 저장한다. ✨탑다운방식 재귀적으로 호출함 큰문제를 작은문제로 나눔 ✨바텀업방식 반복문을 사용함 작은 문제로 큰문제를 해결함 예시) 백준 알고리즘 수업 - 피보나치 수 1 https://www.acmicpc.net/problem/24416 제귀함수로 작성한 피보나치 def fib(n): if(n

✨백트래킹(backtracking) 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법 주요 개념은 해를 얻을 때까지 모든 가능성을 시도 트리를 검사하기 위해 깊이 우선 탐색을 사용 ✨ 예시문제) 백준 N과 M(1) https://www.acmicpc.net/problem/15649 끝나는 조건:리스트의 길이가 M이 되었을때 -> 정답목록에 해당 리스트를 추가, 종료 수열의 조건: 방문했던 숫자에 다시 방문하면안됨 ->방문 리스트 V를 만들어서 체크 전체 코드 import sys def back(n,li): if(n==M): answer.append(li) #종료조건 return for j in range(1,N+1,1): if(V[j]==0): V[j]=1 back(n+1,li+..

✨ 합병정렬(merge sort) 합병 정렬은 O(n log n) 비교 기반 정렬 알고리즘이다. 일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬에 속하며, 분할 정복 알고리즘의 하나이다. (분할정복:그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법) ✨ 과정(2-way 합병 정렬) 길이가 1이하임을 확인(1이하인경우 정렬완료상태) 분할: 리스트를 절반으로 나눈다. 정복:각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬 결합:두 부분 리스트를 다시 하나의 정렬된 리스트로 합병( 임시배열에 저장 ) 복사:임시 배열에 저장된 결과를 원래 배열에 복사 def merge_sort(arr): #길이 1이하확인 if(arr