sdesign416 님의 블로그

[알고리즘] 다익스트라(Dijkstra)알고리즘 - 최단 경로와 동작 원리다익스트라 (Dijkstra) 알고리즘은 시작 정점에서 다른 모든 정점까지의 최단거리를 구하는 알고리즘이다. 예를 들어 지도 어플에서 현재 위치에서 목적지까지 가장 빠른 길을 찾거나네트워크에sdesign416.tistory.com다익스트라는 현재까지 발견한 거리 중 가장 짧은 정점을 선택하면서 최단 거리를 갱신하는 방식이다.하지만 정점이 많아질 경우 매번 가장 가까운 정점을 찾는 과정에서 많은 시간이 필요하다.이를 해결하기 위해 실제 구현에서는우선순위 큐(Priority Queue)와 힙(Heap) 자료구조를 사용한다.1. 우선순위 큐(Priority Queue)우선순위 큐는 일반적인 큐와 다르게먼저 들어온 데이터가 아니라 우선순위..

다익스트라 (Dijkstra) 알고리즘은 시작 정점에서 다른 모든 정점까지의 최단거리를 구하는 알고리즘이다. 예를 들어 지도 어플에서 현재 위치에서 목적지까지 가장 빠른 길을 찾거나네트워크에서 데이터가 이동하는 최적 경로를 찾을 때 사용된다. 다익스트라 알고리즘은 그래프의 가중치를 기준으로 최단 거리를 계산하기 때문에 가중 그래프에서 많이 사용된다. ※ 단, 다익스트라 알고리즘은 음수 가중치가 있는 그래프에서는 사용할 수 없다. 1. 최단 경로 알고리즘(Shortest Path Algorithm) 최단 경로 알고리즘은 그래프에서 특정 정점에서 다른 정점까지 이동할 때 가장 적은 비용이 드는 경로를 찾는 알고리즘이다.그래프의 가중치를 기준으로 최단 경로를 판단하기 때문에거리, 시간, 비용 등 어떤 값을 ..

그래프(Graph)는 정점(Vertex)과 간선(Edge) 으로 이루어진데이터간의 연결 관계를 표현한 자료구조이다. 트리가 계층 구조를 표현하고 있다면그래프는 객체들의 관계를 표현하는데 사용된다. 예를 들어 지하철 노선도, 길찾기 시스템등은 모두 그래프로 표현할 수 있는 예시이다. 즉, 트리는 위에서 아래로 뻗어나가는 구조를 유지해야 하지만그래프는 점과 점이 서로 연결되어 있어트리보다는 좀 더 자유롭게 연결된다라고 생각하면 된다.💡 트리와 그래프의 차이트리는 그래프의 한 종류에 속한다.하지만 트리는 계층 구조를 표현하기 위해 몇가지 제한 조건을 가진 그래프라 생각하면 된다.구분트리그래프구조계층 구조연결 구조방향 부모 → 자식 관계자유로운 연결사이클없음 가능루트 노드존재없을 수 있음예시폴더구조, 조직도지..

그리디(Greedy) 알고리즘은 문제를 해결할 때 현재 시점 기준으로 가장 최선의 선택을 반복적으로 수행하며 결과에 도달하는 알고리즘으로탐욕적인 선택을 한다해서 탐욕 알고리즘이라고도 불린다. 그리디 알고리즘은 각 단계에서 가능한 최선의 선택을 하지만,그 선택이 전체 문제에 대해서 최적해를 보장하는지는 문제별로 다르게 나타난다. 쉽게 말해, 나무만 보고 숲은 보지 못하는 당장의 이익에만 얽매이는 모습이라 생각하면 된다.1. 그리디 알고리즘 동작 흐름그리디 알고리즘은 현재 상황에서 선택할 수 있는 후보들을 확인한 후,후보들 중 가장 좋아보이는 최선의 선택을 한다.선택한 결과를 문제에 반영하여 문제가 해결될 때 까지 반복하는 동작을 한다. 이때 특이한점은한 번 선택한 결과를 다시 되돌아가지 않는다는 점이다. ..

[파이썬 알고리즘] 탐색 알고리즘① - 선형 탐색(Linear), 이진 탐색(Binary)탐색 알고리즘 (Search Algorithms)탐색(Search)은 말 그대로 탐색을 말하는데,여러 데이터 중에서 원하는 값을 찾는 과정을 의미한다. 예를 들어 연락처에서 특정 사람의 전화번호를 찾거나,도서관에sdesign416.tistory.com1. DFS (깊이 우선 탐색)DFS(Depth First Search)는 깊이 우선 탐색이라고도 부르며한 방향으로 끝까지 내려가보는 방식을 말한다. DFS는 한 경로를 끝까지 탐색한 뒤더이상 갈 곳이 없을경우 다시 돌아와 다른 길을 탐색하는 방식이다.깊게 들어갔다가 되돌아오는 탐색이라 생각하면 된다.1_1) DFS 동작 과정시작 정점을 방문한다.현재 정점과 연결된 정점..

탐색 알고리즘 (Search Algorithms)탐색(Search)은 말 그대로 탐색을 말하는데,여러 데이터 중에서 원하는 값을 찾는 과정을 의미한다. 예를 들어 연락처에서 특정 사람의 전화번호를 찾거나,도서관에서 책 이름 검색하기, 인터넷에서 원하는 정보를 검색하는것들 모두 탐색에 해당된다. ❓ 탐색 알고리즘, 중요할까?탐색 알고리즘은 데이터의 집합에서 원하는 데이터를 효율적으로 찾기 위한 알고리즘이다.데이터의 양이 많을수록 원하는 정보를 찾는데에 많은 시간이 소요되는데이때 탐색 알고리즘을 사용하여 데이터를 빠르게 찾아 시간을 절약할 수 있으며시스템 성능 개선과 함께 대용량 데이터를 효율적으로 처리할 수 있는 장점이 있기 때문에 탐색 알고리즘을 사용해야 한다.1. 선형 탐색 (Linear Search)..

[알고리즘] 정렬 알고리즘 - 버블정렬(Bubble), 선택정렬(Selection), 삽입정렬(Insertion)[파이썬 자료구조와 알고리즘] 시간 복잡도, 빅오 표기법(자료구조, 정렬 알고리즘의 시간 복잡프로그램을 개발할때에는 같은 결과를 만들어 내는 코드라도 실행 속도는 천차만별이다. 예를 들sdesign416.tistory.com 이 전 글에선 정렬중에서도 안정 정렬에 해당하는 삽입 정렬, 버블 정렬, 병합 정렬을 보았다.이번 글에서는 안정 정렬인 병합정렬과, 불안정 정렬인 퀵 정렬에 대해 살펴 볼 예정이다. 💡 안정 정렬(Stable Sort) 이란?정렬 후에도 값이 같은 원소들의 순서가 그대로 유지되는 정렬 방식이다.※ 원래 순서 : 정렬 전의 상대적인 위치1. 재귀 함수(Recursive F..

[Python MySQL] MySQL을 활용한 단어장 프로그램 만들기[Python MySQL] Python에서 MySQL 연결하고 데이터 조회하기Python 설치부터 VSCode, Jupyter, venv설정까지파이썬을 시작하기 앞서가장 중요한 것은 개발환경 설정이다. Python 설치, VSCode 확장 프로그램, venv 가sdesign416.tistory.com단어장 프로그램을 수업시간에 만들고 복습을 하다보니데이터 저장 클래스가 왜 필요한지에 대해 의문점이 들었다.# 단어장 프로그램에서 사용된 클래스명class Word: def __init__(self, eng, kor, lev=1): self.eng = eng self.kor = kor self.l..

[파이썬 자료구조와 알고리즘] 시간 복잡도, 빅오 표기법(자료구조, 정렬 알고리즘의 시간 복잡프로그램을 개발할때에는 같은 결과를 만들어 내는 코드라도 실행 속도는 천차만별이다. 예를 들어 특정 데이터를 찾을 때처음부터 끝까지 순서대로 하나씩 확인하는 방법이 있고,정렬된 데이sdesign416.tistory.com정렬 알고리즘(Sorting Algorithm)이란?정렬 알고리즘은 무작위로 나열되어 있는 데이터를특정 기준(오름차순 또는 내림차순)에 따라 순서대로 재배열하는 알고리즘을 말한다.정렬 알고리즘을 사용하여데이터를 효율적으로 탐색하고 관리할 수 있다. 정렬 알고리즘엔 버블 정렬, 선택 정렬, 삽입 정렬, 합병 정렬, 퀵 정렬, 힙 정렬이 있고이는 비교 정렬에 포함되며, 비교하지 않는 정렬에는 계수 정..

[Python MySQL] Python에서 MySQL 연결하고 데이터 조회, 추가하기Python 설치부터 VSCode, Jupyter, venv설정까지파이썬을 시작하기 앞서가장 중요한 것은 개발환경 설정이다. Python 설치, VSCode 확장 프로그램, venv 가상환경까지 한 번에 등장하다보니각 역할이 무엇인sdesign416.tistory.com 프로그램을 만들 기 전,SQL 데이터베이스에 voca테이블을 만들고 시작한다.create table voca( eng varchar(50) primary key, kor varchar(50) not null, lev int default 1);프로그램 설명프로그램 전체 코드는 MySQL을 활용한 단어장_최종.iptnb 파일을 확인!아래 실..