알고리즘
[알고리즘] 다익스트라
다익스트라 알고리즘 ; DP를 활용한 최단 경로 탐색 알고리즘 - 특정 정점에서 다른 모든 정점으로 가는 최단 경로를 기록 - 해당 정점까지의 최단 거리 저장 & 정점을 방문했는지 저장 알고리즘 순서 1. 최단 거리 값 = 무한대 값으로 초기화 for(int i = 1; i
[알고리즘] DP(Dynamic Programming)
DP (Dynamic Programming) ; 동적 계획법. 한 가지 문제에 대해서, 단 한번만 풀도록 만들어주는 알고리즘 조건 - 작은 문제에서 반복이 일어남 - 같은 문제는 항상 정답이 같음 예시 문제 https://www.acmicpc.net/problem/2133 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net https://www.acmicpc.net/problem/11722 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열..
[알고리즘] 선형 리스트(Stack, Queue, Deque)
Stack ; LIFO(Last In First Out)구조. - 배열을 이용한 데이터 구조이며, 삽입과 삭제가 리스트 한쪽 끝에서만 이루어지는 제한된 리스트구조 - 이용분야 ; 함수 호출 시 복귀주소 저장, 수식 계산(중위 표기법/전위 표기법/후위 표기법) Queue ; FIFO구조, 변수 2개(tail과 head) 사용 - 리스트의 한쪽 끝에서 원소들이 추가(rear)되고, 다른 한쪽 끝에서 삭제(front)되는 선형리스트 - - 시스템에서, 프로세스의 순차처리와 보조기억장치를 이용한 spool처리 등에 이용 # Spool 처리 ; CPU에서 I/O장치로 보낼 때 임시로 보조기억장치에 저장하는것 무빙 큐 ; 데이터 삭제 시 데이터를 한칸 왼쪽으로 이동시킴 -> 많은 시간적 손실 초래 원형 큐 ; 배열..
[알고리즘] 해시
해시 ; 다양한 길이를 가진 데이터를 고정된 길이의 데이터로 매핑한 값 - 내부적으로 배열을 사용하여 데이터를 저장하기 때문에 빠른 검색 속도 가짐 - 해시 알고리즘을 통해 고유한 인덱스를 얻음 - 적은 자원으로 많은 데이터를 효율적으로 관리하기 위해 사용 해시 함수 ; 데이터를 효율적으로 관리하기 위해, 임의의 길이의 데이터를 수학적 연산을 통해 고정된 길이의 데이터로 매핑하는 함수 해시 테이블 ; 키와 값을 매핑해둔 데이터 구조 충돌 해결법 1. 개방 주소법 ; 해시 충돌이 발생하면 해시 함수로 얻은 주소가 아닌, 다른 주소 공간에 데이터를 저장하는 방식 2. 폐쇄 주소법 ; 인덱스로 인해서 충돌이 발생하면 그 인덱스가 가리키고 있는 연결 리스트에 노드를 추가
[알고리즘] 해싱(자료구조 기말고사 공부 정리)
해싱 ; 해시 함수에 의하여 계산된 키 값의 주소로 직접 접근하는 것 - 해싱 = 'key to address transformation', 즉 특정 규칙에 따라 주어진 키 값을 주소로 변환하여 해시 테이블이라는 기억공간에 키의 레코드를 저장 - 해시 함수를 이용하여 필요한 레코드의 주소를 산출함으로서 검색작업을 수행 해시 테이블 ; 해시 함수에 의해 산출된 주소에 각 레코드를 기억시킨 테이블 - 버킷들로 구성되어 있으며, 각각의 버킷은 슬롯으로 구성 해시 함수 ; 입력된 키 값을 해시 테이블의 주소로 변환시켜주는 함수 - 중간 제곱함수 ; 키 값을 제곱한 후 그 수의 중간에 정해진 자리 수만큼을 취해서 해시 테이블의 버킷주소로 만듬 - 나누기 함수 ; 키 값을 해시 테이블의 크기로 나누어서 그 나머지를..
[알고리즘] 탐색
탐색 ; 컴퓨터 기억공간에 저장되어 있는 데이터들로부터 필요한 데이터를 찾아내느 ㄴ것 - 순서화되지 않은 레코드를 탐색하는 방법 ; 순차 탐색, 선형 탐색 선형 탐색(linear search) ; 순서대로 인덱스 사용하여 탐색 이진 탐색(binary search) ; 키 값에 따라 두 부분으로 나누어지고 찾고자 하는 키와 중앙 부분의 키를 비교하여 같으면 탐색 종료, 두 부분 중 크기에 따라 한 쪽 부분을 선택하고 .. 반복 - 탐색 효율이 가장 좋은 방법 #include using namespace std; #define MAX 5 int arr[5]={10,20,30,40,50}; main(){ int l=0,h=MAX-1,m,data; scanf("%d",&data); while(1){ m=(l+h..
[알고리즘] 그래프
이번에 알아볼 알고리즘 중 자료구조는 그래프입니다! 그래프는 노드와 그 노드를 연결하는 간선을 하나로 모아 놓은 자료구조입니다. 그 예시로 지도, 지하철 노선도의 최단 경로, 전기 회로의 소자들 등이 있습니다. 그래프 순회(임의의 한 정점에서 시작하여 모든 정점을 한 번씩 방문)에는 DFS와 BFS 등이 있습니다. 자료구조는 선형구조와 비선형 구조로 나뉘는데, 그래프는 그 중에서 비선형 구조입니다. 선형 구조 ; 자료를 구성하고 있는 데이터들을 순차적으로 나열 시킨 형태 ex) 큐, 스택, 데큐 - 자료를 저장하고 꺼내는 것에 초점 비선형 구조 ; 데이터가 계층적으로 구성된 형태 - 표현에 초점 ex) 트리, 그래프 / 컴퓨터의 폴더(폴더 속 폴더..) 그래프 용어 - 정점(=노드) ; 위치라는 개념 -..
