개발(합니다)/컴퓨터 일반&CS (25) 썸네일형 리스트형 [알고리즘]그래프(최소신장트리, 다익스트라) 최소 신장 트리란그래프의 속성을 가지고 있으며 간선에 가중치를 추가 한 그래프의 하위 개념인 트리최소한의 비용으로 모든 도시를 연결하는 도로를 설계하는 문제를 풀기 적합한 알고리즘간선의 가중치를 기준으로 사이클을 제거하여 필요한 정보만 가지는 방식 가중치를 가진 트리 / B를 시작으로가중치에 따라 사이클을 제거하고 빠른 길을 찾은 트리 최소 신장 트리 알고리즘가장 작은 가중치를 가지는 트리를 만드는 알고리즘 - 프림(Prim) 알고리즘 : 정점에 연결 된 간선의 가중치 중 가장 작은 가중치의 간선을 연결해 나가는 방식- 크루스칼(kruskal) 알고리즘 : 모든 간선의 가중치를 조사하고 정렬 후 순서대로 연결해 나가는 방식-> 최소 신장 트리에서 발생하는 사이클은 깊이 우선 탐색 방법으로 해결할 수 있지.. [알고리즘]그래프(인접리스트, 깊이우선탐색, 너비우선탐색) 그래프란7개의 다리를 한번씩 건너서 온 동네를 돌아다닐수 있는 방법을 찾다가 위대한 수학자 오일러가 고안 그래프의 정의- 정점 : 하나의 위치를 가진 점- 간선 : 하나의 길, 가중치, 방향을 가진 선- 인접 : 점과 점이 간선으로 이웃되어 있는 경우- 경로 : 하나의 점에서 다른 점을 간선을 따라 이동하는 길- 사이클 : 하나의 점이 경로를 따라 2번 이상 거치는 경우ex) A->B->C->A- 연결성 : 무방향 그래프에서 두 정점 사이에 경로가 존재하는 경우 그래프 표현정점끼리 인접 여부를 빠르게 알아야 한다면 인접 행렬정점과 인선의 입력이 자주 발생한다면 인접 리스트 - 인접 행렬 그래프 : 모든 정보 저장장점 : 직관적이고 구현이 쉬움단점 : 불필요한 정보 저장으로 메모리 낭비와 NxN으로 메모리.. [알고리즘]해시 테이블(Hash Table) 해시란해시는 입력 받은 데이터를 완전히 다른 형태의 데이터로 바꾸는 작업 사용처- 해시 테이블- 암호화- 데이터 축약 해시 테이블이란공간을 소비해서 속도를 올린 알고리즘.테이블을 만들어 해시 값을 참고하여 데이터를 찾는 방식 데이터는 해시 함수를 거쳐서 해시 테이블의 주소로 변환되고 이를 참고 하는 방식 해시 함수란데이터를 가공하여 해시 테이블내의 주소 값으로 저장하는 함수 해싱 함수 종류- 나눗셈법 : 입력 값을 테이블 크기(소수 선호)로 나누고, 나머지를 테이블 주소로 사용ex ) 입력 % 테이블 크기 = 주소 - 자릿수 접기 : 입력 값을 아스키 코드화 하여 총합을 주소로 사용 해싱 충돌해싱 함수를 통해 서로 다른 데이터의 주소가 같은 주소를 가지게 되는 충돌하는 경우 해싱 충돌 해결 방법- 개방 .. [알고리즘]우선순위 큐와 힙 우선 순위 큐란일반 큐와 다른 점은 데이터의 우선순위 존재하며 우선순위에 따라 출력 우선순위에서의 힙이란우선 순위 큐를 구현하기 위한, 자유 저장소와 다른 힙이며 힙 순서 속성을 가진 완전 이진트리가장 우선순위가 높은 데이터를 루트 노드를 가지는 완전 이진 트리가장 마지막 노드를 찾기 위해서는 배열로 구현하는 방법을 선호 우선순위 힙에서의 삽입 후 '후처리'1. 가장 마지막 위치에 새로운 노드를 추가2. 부모 노드와 비교 후 우선순위가 높다면 변경3. 루트 노드까지 비교하여 후처리 우선순위 힙에서의 제거 후 '후처리'1. 가장 우선 순위가 높은 데이터 루트 데이터를 삭제2. 가장 마지막 위치의 노드를 루트 노드로 이동3. 왼쪽 자식과 아래쪽 자식을 우선 순위 비교하여 우선 순위가 높은 쪽과 위치 변경4... [알고리즘]탐색/검색(순차, 자기 구성, 이진 탐색, 레드블랙트리) 탐색/검색이란 무엇인가를 찾는 의미이며 컴퓨터에서는 데이터를 찾는 의미 순차 탐색맞는 짝이 나올 때까지 처음부터 차례대로 비교하는 방법한쪽 방향으로 탐색을 수행한다고 하여 선형 탐색이라고 부르기도 함 '처음부터 끝까지 모든 데이터를 확인'하여 효율이 좋지 않은 방법정렬 되지 않은 데이터에서는 원하는 데이터를 찾을 수 있는 유일한 방법 자기 구성 순차 탐색특정 데이터를 선택 하고 해당 데이터를 자주 사용하는 항목, 즐겨찾기와 같은 기능에 사용 되는 방법 - 전진 이동법- 전위법- 빈도 계수법 전진 이동법특정 데이터가 한번 탐색 되면 해당 데이터를 가장 처음으로 위치를 변경ex) 3번 선택 시1 2 3 4 5 : 3 1 2 4 5 ↑전위법특정 데이터가 한번 탐색 되면 이전 데이터와 위치를 변경ex) 3을 선.. [알고리즘]정렬 알고리즘(버블, 삽입, 퀵) 정렬 알고리즘이란잘 찾기 위해 하는 정리.탐색을 위한 정렬.데이터를 빠르고 쉽게 찾을 수 있게 하는 목적. 버블 정렬데이터를 정렬하는 과정이 물 속 깊은 곳에서 일어난 거품이 수면을 향해 올라오는 모습이라 붙여진 명칭집합 내의 이웃 되는 데이터를 순회하면서 비교 및 교환으로 정렬을 수행 사용을 지양해야 하는 정렬 알고리즘.O(n^2) 삽입 정렬뒤죽박죽 되어있는 트럼프 카드를 순서대로 정리하는 모습데이터를 순회 하면서 필요한 값을 뽑아내어 필요한 위치에 삽입하여 정렬을 수행 사용을 지양해야 하는 정렬 알고리즘O(n^2) 퀵 정렬빨라서 이름이 퀵인 정렬분할 정복을 기반한 알고리즘 : 적군를 싸우기 보다는 잘게 나누어 싸우는 전법기준 값의 왼쪽에는 작은 수들을 놓고 오른쪽은 큰 수들 배치하여 정렬을 수행 사용.. [자료구조]트리(Tree) 트리란나무 뿌리 형태의 자료 구조.조직도, 수식, 집합, 데이터 탐색에 사용 되는 자료구조. 트리의 용어단말 : 더 이상 뻗어나가지 않는 마지막 단위관계 : 부도, 형제, 자식의 계층깊이 : 루트 노드에서 해당 노드까지의 경로의 길이레벨 : 깊이가 같은 노드의 집합높이 : 가장 말단 노드까지의 깊이차수노드의 차수 : 해당 노드의 자식 노드 개수트리의 차수 : 트래 내 노드들 중 자식 노드가 가장 많은 노드 트리의 표현 - 중첩 된 괄호 - 중첩 된 집합 - 들여쓰기 1. 중첩 된 괄호 (A(B(C)(D(E)(F)))(G(H))(I(J(K)))2. 중첩 된 집합 3. 들여 쓰기 노드의 표현노드의 표현이란 부모와 자식, 형테 노드를 연결 하는 방법N-링크는 자식 노드의 수가 노드마다 달라지는 트리에 적용하기.. [자료구조]큐(Queue) 큐란선입 선출(First-In First-Out) 형태의 자료 구조.큐는 먼저 들어간 데이터가 먼저 나오는 자료 구조.버퍼의 역할로 입력 데이터가 폭주 할 때 임시로 줄을 세워 모아두었다가 내보내는 구조. 삽입과 제거가 주요입니다.스택과 같은 삽입과 제거의 용어가 헷갈리지 않도록 구분합니다.스택은 push, pop입니다.큐는 enqueue, dequeue 입니다. 큐는 순환(배열)과 링크드 리스트로 구현 할 수 있습니다. 순환 큐와 링크드 큐의 성능 비교 순환 큐는 동적 할당을 하지 않아 성능 측에서 우수합니다.큐의 크기를 예측 할 수 있고 고성능이 필요한 버퍼가 필요한 상황이라면 순환 큐가 적절합니다. 큐의 기본 구조 데이터 삽입 과정 데이터 제거 과정 순환(배열) 큐에서 주의 할 점순환 큐는 전단과 .. 이전 1 2 3 4 다음
