JIN's.log

최단 경로 [플로이드] 📌 플로이드 워셜 알고리즘 플로이드 워셜 알고리즘은 모든 정점에서 모든 정점으로의 최단 경로구하고 싶을때 사용합니다. 다익스트라 알고리즘은 가장 적은 비용을 하나씩 선택해야 했다면 플로이드는 기본적으로 거쳐가는 정점을 기준으로 알고리즘을 수행한다는 점이 특징입니다. 플로이드 알고리즘의 핵심 아이디어는 거쳐가는 정점을 기준으로 최단 거리를 구하는 것이다. 특징 D_ab = min(D_ab, D_ak + D_kb) a->b로 가는 최소 비용과 (a에서 노드k로 가는 비용 + 노드K에서 b로가는 비용)이 두 값중에 최소값으로 갱신합니다. 자기자신으로 가는 비용은 0 직접 연결되어있지 않은 경로는 무한대 입력 데이터N이 500이하로 들어올 때만 사용가능하다. 플로이드 알고리즘은 O(N^3..

최단 경로 📌 다익스트라(Dijkstra) 다익스트라 알고리즘은 다이내믹 프로그래밍을 활용한 대표적인 최단 경로(Shortest Path) 탐색 알고리즘입니다. 흔히 인공위성 GPS 소프트웨어 등에서 가장 많이 사용됩니다. 다익스트라 알고리즘은 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려줍니다. 다익스트라 알고리즘이 다이나믹 프로그래밍 문제인 이유는 최단 거리는 여러 개의 최단 거리로 이루어져 있기 때문입니다. 기본적으로 다익스트라는 하나의 최단 거리를 구할 때 이전까지 구했던 최단 거리 정보를 그대로 사용한다는 특징이 있습니다. 📌 그림 설명 한 번 다음 경우를 고려해봅시다. 1부터 다른 모든 노드로 가는 최단 경로를 구해야 합니다. 예를 들어 1에서 3까지 가는 최소 비용은 6입..

이진탐색 📌 이진탐색 1 ~ 50까지 오름차순 정렬된 카드 더미에서 28번 카드를 찾는 문제를 예시로 이분 탐색을 알아보겠습니다. 편의상 첫 번째 카드부터 i번째 카드는 v[i], 28은 val로 표기하겠습니다. 이 경우 결정 문제를 "v[i] >= val인가?"로 잡으면 결정 문제의 답은 i가 증가함에 따라 F, F, ..., F, T, T, ..., T와 같이 분포함을 알 수 있습니다. 이때 우리가 찾고자 하는 값은 처음으로 v[i] >= val인 지점, 즉 조건문이 처음 True가 되는 i값입니다. 정렬 등과 함께 가장 기초인 알고리즘으로 꼽히는 문제. 검색 범위를 줄여 나가면서 원하는 데이터를 검색하는 알고리즘이다. BigO : O(log N) 정렬된 자료를 반으로 나누어 탐색하는 방법 주의점 :..

DFS & BFS & 백트래킹 1. 그래프의 표현방법 👉 이런 그래프라는 개념을 컴퓨터에서 표현하는 방법은 두 가지 방법이 있습니다! 1) 인접 행렬(Adjacency Matrix): 2차원 배열로 그래프의 연결 관계를 표현 2) 인접 리스트(Adjacnecy List): 링크드 리스트로 그래프의 연결 관계를 표현 인접 리스트로 많이 쓴다. 하지만 인접한 요소가 너무 많아서 검색하는데 O(n)이 걸릴 수 있다. 이런 경우 인접 행렬을 이용하면 O(1)의 복잡도로 검색할 수 있다. 📌 DFS 👉 DFS는 Depth First Search라고 한다.! 갈 수 있는 만큼 계속해서 탐색하다가 갈 수 없게 되면 다른 방향으로 다시 탐색하는 구조입니다. 이 말만 들어서는 방법이 안 떠오르니까, 한 번 구체적으로 실..

정렬 알고리즘 버블 정렬 (bubble Sort) 버블 정렬은 뒤에서부터 앞으로 정렬을 진행하는 구조를 가지고 있다. 오름차순 정렬 기준으로 배열의 맨 뒷공간에 가장 높은 값을 보내고, 그 앞에 두 번째로 큰 값을 보낸다. 그래서 배열 내 값들을 앞뒤로 서로 비교하며 자리를 바꾸는 작업르 반복한다. 버블 정령은 큰 값들을 뒤에서부터 앞으로 하나씩 쌓아 나가기 때문에 원소가 자리를 잡을 때마다 정렬의 범위가 하니씩 줄어들게 도니다. 제일 작은 값을 찾아 맨 앞에 위치시키는 선택정렬과는 반대의 정렬 방향을 갖는다. 다른 정렬 알고리즘에 비하여 값의 swap이 비번하게 일어난다. O(n^2)의 시간 복잡도를 갖는다. 루프문을 통해 모든 인덱스에 방문해야 하므로 O(N)의 시간이 소모되고 또 인접한 원소와 대소..

해시 테이블에 대해서 알아보자 해시 테이블 (Hash tables / Hash map)이란? 📍 해시 테이블의 개념 해시테이블 또는 해시 맵은 키를 값에 매핑할 수 있는 구조인, 연관 배열 추상 자료형(ADT)를 구현하는 자료구조다. 📍 해시 테이블의 특징 해시테이블의 가장 큰 특징은 대부분의 연산이 분할 상환 분석에 따른 시간 복잡도가 O(1)이라는 점이다. 덕분에 데이터 양에 관계없이 빠른 성능을 기대할 수 있다는 장점이 있다. 해시 테이블의 핵심은 해시 함수다. 해시 함수란 임의 크기 데이터를 고정 크기 값으로 매핑하는 데 사용할 수 있는 함수를 말한다. 해시 테이블을 인덱싱하기 위해 이처럼 해시 함수를 사용하는 것이 해싱(Hashing)이라 하며, 해싱은 정보를 가능한 빠르게 저장하고 검색하기 위..

스택(Stack) 큐(Queue)에 대해서 알아보자 스택(Stack)이란? 📍 스택의 개념 스택이란 쌓아 올린다는 것을 의미한다. 따라서 차곡차곡 쌓아 올린 형태의 자료구조를 말한다. 📍 스택의 특징 스택은 위의 사진처럼 같은 구조와 크기의 자료를 정해진 방향으로만 쌓을 수 있고, top으로 정한 곳을 통해서만 접근할 수 있다. 스택에서 top을 통해 삽입하는 연산을 'push' , top을 통한 삭제하는 연산을 'pop'이라고 한다. 따라서 스택은 시간 순서에 따라 자료가 쌓여서 가장 마지막에 삽입된 자료가 가장 먼저 삭제된다는 구조적 특징을 가지게 된다. 이러한 스택의 구조를 후입선출(LIFO, Last-In-First-Out) 구조이라고 한다. 📍 스택의 활용 예시 스택의 특징인 후입선출(LIFO)..