본문 바로가기
반응형

알고리즘

 (8)
알고리즘 [shortest path] 최단 경로 - 다익스트라, 플로이드 워셜 최단 경로 알고리즘이란? 최단 경로라는 말 그대로 가장 짧은 경로를 찾는 알고리즘입니다. 최단 경로의 알고리즘은 여러가지 있지만 그 중 다익스트라 최단 경로 알고리즘과, 플로이드 워셜 알고리즘을 기반으로 설명하겠습니다. 다익스트라 최단 경로 알고리즘 다익스트라 최단 경로 알고리즘은 그래프에서 여러 개의 노드가 있을 때 특정 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘입니다. 따라서 매 순간 가장 짧은 거리를 선택하므로 그리디 알고리즘이라고 생각하면 됩니다. 그리고 중요한 점은 0보다 작은 음의 간선이 있을 경우 정상적으로 동작하지 않을 수 있습니다. 알고리즘 흐름도 1. 출발 노드를 설정합니다. 2. 최단 거리 테이블을 초기화합니다. 3. 방문하지 않은 노드 중에서 최단 거리..
알고리즘 다이나믹 프로그래밍 DP 컴퓨터에서 연산 속도에 한계가 있고 메모리 공간도 있어 데이터 개수에 따른 한정적이라는 문제점이 있습니다. 다만 메모리 공간을 더 사용해 연산 속도를 크게 올릴 수 있는데 알고리즘이 하나로 다이나믹 프로그래밍을 많이 사용합니다. 다이나믹 프로그래밍이란? 어떤 문제를 풀기 위해 그 문제를 더 작은 문제의 연장선으로 생각하고, 과거에 구한 해를 활용하는 방식의 알고리즘입니다. 쉽게 이전의 해를 기억하면서 문제를 해결하는 방법입니다. 다이나믹 프로그래밍 조건 부분 반복 문제(Overlapping Subproblem) 최적 부분 구조(Optimal Substructure) 부분 반복 문제(Overlapping Subproblem) 동일한 작은 문제들이 반복해서 이용될 때 사용가능합니다. 쉽게 이전 해를 리스트나..
알고리즘 이진 탐색 알고리즘 이진 탐색을 알기 전에 먼저 순차탐색의 개념을 이해해야합니다. 순차 탐색은 순서대로 특정데이터를 찾기 위해 앞에서 부터 확인하는 방법입니다. 순차 탐색 코드 예제 data = ["apple","graph","tomato","pear"] find = "tomato" def Seq(da,fi): for i in range(len(da)): if da[i] == fi: return i+1 print(Seq(data,find)) 해당하는 과일의 인덱스를 순서대로 비교해 찾은 후 반환하는 순차탐색의 예제입니다. 이 처럼 순차탐색은 가장 앞에 있는 원소부터 하나씩 확인해야 한다는 특징이 있습니다. 이진탐색 이진 탐색은 시작점, 끝점, 그리고 중간점을 기준으로 데이터를 반으로 쪼개면서 탐색하는 알고리즘입니다. 이진 ..
알고리즘 정렬 알고리즘 - 선택정렬, 삽입정렬, 퀵정렬, 계수정렬(카운트정렬) 정렬이란? 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말합니다. 작은 숫자순으로 정렬하는 것을 내림차순 큰 숫자순으로 정렬하는 것을 오름차순 정렬이라고 합니다. 정렬알고리즘은 다양하지만 이번 포스트에서 선택정렬, 삽입정렬, 퀵정렬, 계수 정렬에 대해 설명하겠습니다. 선택정렬 선택 정렬은 말 그대로 선택한 값과 선택되지 않은 값 중 가장 작은 데이터와 바꾸는 정렬입니다. 예를 들어 1,3,2,4,5,0 이라는 리스트가 존재할 때 1. 가장 처음 자리 숫자인 1을 선택하고 선택되지 않은 값 중 가장 작은 값인 0과 자리를 바꿔줍니다. 0,3,2,4,5,1 2. 두번 째 자리 숫자인 3을 선택하고 선택되지 않은 값 중 가장 작은 값인 1과 자리를 바꿔줍니다. 0,1,2,4,5,3 3. 세번 째 자리..
알고리즘 [DFS / BFS ] 깊이 우선 탐색, 너비 우선탐색 그래프의 구조를 이해하고 탐색 알고리즘인 DFS와 BFS를 적용하는 내용입니다. 그래프란? 노드와 노드 사이를 간선으로 연결하는 자료 구조 형태입니다. 예를 들어 노드는 도시 간선은 도로라고 생각하면 이해하기 쉽습니다. 그래프의 종류는 다양하게 있습니다. 방향이 있는 그래프와 방향이 없는 그래프, 가중치를 구하는 그래프, 모든 노드가 서로 연결되어 있는 그래프 등등 이 있지만 이것을 코드로 표현하고 해결하기 위해 어떤 방식으로 표현하는 지 설명하겠습니다. 인접 행렬 - 2차원 배열로 그래프의 연결 관계를 표현하는 방식 인접 리스트 - 리스트러 그래프의 연결 관계를 표현하는 방식 아래에 그래프를 인접 행렬로 구현했을 때 인접 리스트로 구현했을 때를 설명하겠습니다. 인접행렬 인접행렬에서 중요한 점은 연결이 ..
알고리즘 [재귀 함수] recursive function 재귀함수란? 재귀 함수란 함수 안에서 자기 자신의 함수를 다시 호출하는 것을 말합니다. 재귀 함수는 함수를 계속 호출했을 때 가장 마지막에 호출한 함수가 먼저 끝나야 그 앞의 함수를 종료하는 구조이기 때문에 스택 구조입니다. 반복문으로도 구현가능한데 굳이 재귀함수를 쓰는 이유는 뭘까요? 왜냐하면 재귀함수로 구현했을 때 직관적이기 때문에 이해하는데 쉽기 때문입니다. 파이썬에서는 재귀함수의 최대 깊이가 존재합니다. 따라서 계속 호출하는 경우 인터프리터에서 재귀함수 깊이 오류를 발생시킵니다. def recursive_fuc(): print("재귀함수 호출") recursive_fuc() recursive_fuc() 재귀함수 구현해보기 - 파보나치 수열 # Fibonacci (순환): O(2^n) def fib..
알고리즘 [자료구조] 스택 , 큐, 데크 파이썬 자료구조 사전적의미로는 데이터를 체계적으로 저장하고 효율적인 접근 및 수정을 가능케 하는 자료의 조직, 관리를 의미합니다. 자료 구조의 종류로는 스택, 큐, 그래프, 트리 등 다양한 구조가 있지만 이중에서 스택과 큐에대해 설명하겠습니다. 스택 큐 핵심 데이터를 삽입 하고 삭제하는 기능이 핵심 기능입니다. 자료 구조에 더이상 삽입할 수 없으면 오버플로우 삭제 할 수 없으면 언더플로우가 발생합니다. 스택 선입후출(First In Last Out) 이라는 먼저 들어온 데이터가 가장 마지막으로 꺼낼 수 있는 구조입니다. 스택은 프링글스 통을 생각하면 스택에 구조 이해에 쉽습니다. 왜냐하면 프링글스 통에서 맨 아래의 과자를 꺼낸다고 생각할 때 포장과정에서는 가장 먼저 들어가지만 우리가 먹기 위해서는 가장 마지막으..
알고리즘 [탐욕법] 당장 좋은 것만 선택하는 그리디 그리디 알고리즘이란 그리디 알고리즘이란 한국어로 번역하면 탐욕적인이라는 뜻으로 현재 상황에서 지금 당장 좋은 것만 고르는 알고리즘입니다. 그 뜻은 해당하는 구간에서 가장 좋은 것만 선택하고 다음 구간을 고려하지 않는다는 뜻입니다. 아래에 거스름 돈에서 그리디를 사용할 떄와 사용하면 안될 때를 설명하겠습니다. 거스름 돈 코드 # 그리디 알고리즘 코인선택 def greed_coin(N,coins): count = 0 for coin in coins: count+= N//coin N %=coin print("최소 동전 " , count) N = 1310 coins = [500,100,50,10] greed_coin(N,coins) 1310원의 돈을 그리디 알고리즘으로 해결하는 코드입니다. 몫은 코인에서 남은 ..

티스토리툴바