본문 바로가기

Algorithm/Study

Algorithm/Study 2021. 9. 17. 그래프 탐색 알고리즘 : DFS (Python) DFS - 개념 : 그래프에서 깊은 부분을 우선적으로 탐색하는 깊이 우선 탐색 알고리즘이다. - 스택 자료구조 이용 (= 파이썬 리스트. 재귀 함수를 이용했을 때 구현이 간결) - 시간 복잡도 : O(N) - 인접리스트로 구현시 - 장점 : 1) BFS에 비해 저장공간의 필요성이 적다. 2) 찾아야 하는 노드가 깊은 단계에 있을 수록, 그 노드가 왼쪽에 있을 수록 BFS보다 유리하다. - 단점 : 1) 목표 노드가 없는 경로에 깊이 빠질 수 있다. 2) 최단 경로가 보장되지 않는다. - 사용예 : 위상정렬, 사이클 탐지 - 구현 # DFS def dfs(graph, v, visited): visited[v] = True # 현재 노드와 연결된 다른 노드를 재귀적으로 방문 for i in graph[v]:..
Algorithm/Study 2021. 9. 17. 그래프 탐색 알고리즘 : 인접 행렬과 인접 리스트 (Python) 인접 행렬 - 개념 : 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식 - 모든 관계를 저장하므로 노드의 개수가 많을 수록 메모리가 낭비된다. - 특정한 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 빠르다. - 구현 INF = 999999999 # 9 자리수 # 2차원 리스트를 이용해 인접 행렬 표현 graph = [ ''' [노드0과 노드0 간선 비용, 노드0과 노드1 간선 비용, 노드0과 노드2 간선 비용] [노드1과 노드0 간선 비용, 노드1과 노드1 간선 비용, 노드1과 노드2 간선 비용] [노드2와 노드0 간선 비용, 노드2와 노드1 간선 비용, 노드2와 노드2 간선 비용] ''' [0, 7, 5], [7, 0, INF], [5, INF, 0] ] print(graph) 인접 리스..
Algorithm/Study 2021. 9. 17. 그리디 알고리즘 (Python) 그리디 알고리즘 위 그림처럼 그리디 알고리즘을 이용하면 매 순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 특정 문제를 만났을 때 단순히 현재 상황에서 가장 좋아보이는 것만을 선택해도 문제를 풀 수 있느지를 파악할 수 있어야 한다. 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 제시할 때 대체로 그리디 알고리즘과 정렬 알고리즘을 함께 사용할 수 있다. 거스름돈 문제 500원, 100원, 50원, 10원짜리 동전히 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수를 구하라. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다. 1) 아이디어 : 가장 큰 화폐 단위부터 돈을 거슬러 ..
Algorithm/Study 2021. 9. 17. 정렬 알고리즘 : 계수 정렬 (Python) 계수 정렬 개념 - 특정한 조건이 부합될 때만 사용할 수 있지만 데이터 수가 많더라도 매우 빠른 정렬 알고리즘이다. - 특정한 조건 : 최대, 최소 값 차이가 100만 이하일 경우 효과적이다. ex. 0 이상 100 이하인 성적 데이터를 정렬 - 이유 : 모든 데이터 범위를 담을 수 있는 리스트를 선언 - 비교 기반의 정렬 알고리즘 X (선택, 삽입, 퀵 정렬 처럼 데이터를 비교하며 위치를 변경하지 않음) 소스코드 # 모든 원소의 값이 0보다 크거나 같다고 가정 array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2] # 모든 범위를 포함하는 리스트 선언 및 0으로 초기화 # ex. 최댓값이 9일 경우, 0 ~ 9 므로 9 +1 = 10 count = [0] * (..
Algorithm/Study 2021. 9. 15. 정렬 알고리즘 : 버블 정렬 (Python) 버블 정렬 개념 선택 정렬과 유사한 알고리즘으로 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘이다. 배열 끝에서부터 반대 끝까지 두 요소를 선택하여 비교한다. 만약 더 작은 요소가 뒤에 있다면 자리를 바꾼다. 1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동한다. 2회전에서는 맨 끝에 있는 원소는 정렬에서 제외한다. 장점은 구현이 간단하고 소스 코드가 직관적이다. 또한 정렬하고자 하는 배열 안에서 교환하는 방식이므로 다른 메모리 공간을 필요로 하지 않는다. 단점은 시간 복잡도가 최악, 최선, 평균 모두 비효율적이며, 정렬되어있지 않은 원소가 정렬될 자리로 가기 위해 SWAP 연산이 많이 일어나게 된다. 소스 코드 def bubble_sort_1(arra..
Algorithm/Study 2021. 9. 8. 정렬 알고리즘 : 퀵 정렬 (Python) 퀵 정렬 개념 '기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾼다.' 퀵 정렬은 기준(피벗)을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작한다. 피벗을 고르는 기준은 가장 대표적으로 호어 분할(리스트에서 첫 번쨰 데이터를 피벗으로 정한다.)이 있다. 피벗을 설정한 뒤에는 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다. 그다음 큰 데이터와 자긍ㄴ 데이터의 위치를 서로 교환해준다. 1) 로직 : 분할 - 정복 - 결합 2) 상세 로직 소스 코드 array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] def quick_sort(array): # 리스트가 하나 이하의 원소만을 담고 있다면 종료 i..
Algorithm/Study 2021. 9. 8. 정렬 알고리즘 : 삽입 정렬 (Python) 삽입 정렬 개념 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다. 즉 정렬되어 있는 데이터 리스트에서 적절한 위치를 찾은 뒤에, 그 위치에 삽입된다. 삽입 정렬은 두 번째 데이터부터 시작한다. (첫 번째 데이터는 그 자체로 정렬되어 있다고 판단하기 때문이다.) 두 번째 요소 1은 3의 왼쪽이나 오른쪽으로 들어가는 2가지 경우가 있다. 오름차순이므로 3의 왼쪽에 1을 삽입합한다. 2는 1의 왼쪽, 1과 3의 사이, 3의 오른쪽에 들어갈 수 있다. 2의 바로 왼쪽에 있는 3과 비교했을 때 작으므로 왼쪽으로 이동하고, 1보다 크기 때문에 이동을 멈추고 삽입된다. 즉, 자신보다 작은 숫자가 나타나거나 왼쪽 끝에 도착할 때 까지 반복한다. 이런 식으로 마지막 요소 4까지 ..
Algorithm/Study 2021. 9. 8. 정렬 알고리즘 : 선택 정렬 (Python) 스터디 목표 설정 | 2021.09.08 부터 '이것이 취업을 위한 코딩테스트다.' 책을 기반으로 공부한 알고리즘을 블로그에 기록하고 프로그래머스 및 백준 사이트에서 알고리즘 문제를 풀이합니다. 이 과정을 통해 상황에 가장 적절한 알고리즘을 선택하여 문제를 빠르고 정확하게 해결하는 소양을 갖추려고 합니다. 선택 정렬 개념 데이터가 무작위로 여러 개 있을 때, 이중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두 번쨰와 데이터와 바꾸는 과정을 반복하는 정렬 방법이다. 소스 코드 array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(len(array)): min_index = i for j in range(i+1..

티스토리툴바