컴공생의 다이어리

다익스트라(Dijkstra) 다이나믹 프로그래밍을 활용한 대표적인 최단 경로 탐색 알고리즘 특정한 노드에서 출발해 연결되어 있는 다른 모든 노드로 가는 최단 경로를 구하기 위한 알고리즘 0보다 작은 값을 가지는 음의 간선이 없어야 정상적으로 동작 보통 우선 순위 큐를 구현하기 위해 사용되는 heapq 라이브러리를 활용해서 구현 GPS 소프트웨어의 기본 알고리즘으로 채택 과정 출발 노드를 설정 출발 노드를 기준으로 각 노드의 최소 비용을 저장 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소 비용을 갱신 위의 3번 ~ 4번 과정을 반복 동작 단계에 대한 예시는 아래 게시물이 잘 정리되어 있으니 참고하면 좋을 것 같다! [알고리즘] 다익스트..

계수 정렬(Counting Sort) 계수 정렬은 특정한 조건이 부합될 때만 사용할 수 있지만 데이터 수가 많더라도 중복된 값이 많이 분포돼있는 배열을 정렬할 때 효과적이고 빠른 정렬 알고리즘이다. 최대, 최소 값 차이가 100만 이하일 경우 효과적이다. 카운팅 정렬이라고 하기도 한다. 선택, 삽입, 퀵 정렬처럼 데이터를 비교하며 위치를 변경하는 비교 기반의 정렬 알고리즘이 아니다. 계수 정렬의 조건은 아래와 같다. 데이터의 크기 범위가 제한된 경우 ex) 0 ~ 100 까지의 점수를 정렬하는 경우 데이터가 양의 정수인 경우 데이터가 실수인 경우 무한의 범위를 가질 수 있으므로 1번 조건에 부합하지 못함 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000(백만)을 넘지 않는 경우 필수적인 조건..

선형 탐색(Linear Search) 선형 탐색은 일렬로 된 자료를 왼쪽부터 오른쪽으로 차례대로 탐색하는 알고리즘이다. 순차 탐색(Sequential Search)이라고도 한다. 파이썬 코드 def linear_search(arr, search): # for문 사용 for i in range(len(arr)): if arr[i] == search: return True return False linear_search([3, 110, 8, 13, 2], 5) # False 반환 linear_search([3, 110, 8, 13, 2], 13) # True 반환 혹은 def linear_search(arr, search): # while문 사용 i = 0 while i < len(arr): if arr[i..

이진 탐색(Binary Search) 이진 탐색은 정렬된 리스트에 적용할 수 있는 간단한 고속 탐색 기법이며 이분 탐색이라고도 불린다. 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다. 사람들이 숫자를 맞춰가는 업다운 게임과 같은 방식이다. 참고 : 업다운 게임 - 무한도전 니가 가라 하와이편 탐색 과정 이진 탐색은 데이터가 정렬되어있는 상태에서 진행된다. 시작점과 끝점 사이에 중간점을 정함 (만일, 중간점이 실수라면 소수점 이하를 버림) 중간점에 해당하는 값과 찾고자 하는 값을 비교 찾고자 하는 값이 중간점에 해당하는 값보다 작다면 중간점을 기준으로 왼쪽 부분을, 찾고자 하는 값이 중간점에 해당하는 값보다 크다면 중간점을 기준으로 오른쪽 부분에 해당하는 데이터 범위를 가..

병합 정렬(Merge Sort) 병합 정렬은 분할 정복 알고리즘의 하나로 합병 정렬이라고도 한다. 불안정 정렬인 퀵 정렬과 달리, 병합 정렬은 안정 정렬에 속한다. 전체 데이터를 가장 작은 단위로 분할한 후 분할한 데이터를 다시 병합하면서 정렬하는 재귀용법을 활용한 정렬 알고리즘이다. 퀵 정렬과 비교했을 때, 차이점은 아래와 같다. 퀵 정렬 - 각 요소를 피벗과 비교하여 요소를 정렬 - 피벗을 통해 정렬(partition) → 영역을 쪼갬(quick sort) 병합 정렬 - 배열을 하나의 요소가 남을 때까지 두 개의 하위 배열 (n / 2)로 반복하여 나눔 - 영역을 쪼갤 수 있을 만큼 쪼갬(merge sort) → 정렬(merge) 정렬 과정 분할(Divide) 단계 리스트를 절반으로 나누어 비슷한 크..

퀵 정렬(Quick Sort) 퀵 정렬은 분할 정복 알고리즘의 하나로 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 알고리즘이다. 합병 정렬(Merge Sort)과 달리 퀵 정렬은 리스트를 비균등하게 분할한다. 퀵 정렬은 불안정 정렬에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교정렬에 속한다. 하나의 리스트를 피벗(pivot)을 기준으로 피벗보다 작은 데이터와 큰 데이터를 두 개의 부분 리스트로 나눈 다음, 각 부분 리스트에 대해 다시 재귀적으로 수행하여 정렬하는 방법이다. 정렬 과정 배열 가운데서 하나의 원소를 선택(→ 이 원소가 피벗) 피벗을 기준으로 피벗보다 작은 원소들은 피벗 앞(왼쪽)으로 오고, 피벗보다 큰 원소들은 피벗 뒤(오른쪽)로 이동 피벗을 제외하고 나뉘게 된 두 배열은 앞 ..

삽입 정렬(Insertion Sort) 삽입 정렬은 손안의 카드를 정렬하는 방법(새로운 카드를 기존의 정렬된 카드 사이에 올바른 위치에 삽입)과 유사하다. 또한 삽입 정렬은 선택 정렬과 유사하지만, 좀 더 효율적인 정렬 알고리즘이다. 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다. 정렬 과정 2번째 위치(index)의 값부터 정렬을 시작한다. 해당 인덱스(key 값) 앞에 있는 데이터(B)부터 비교해서 key 값이 더 작으면, B값을 뒤 인덱스로 복사 이를 key 값이 더 큰 데이터를 만날 때까지 반복 큰 데이터를 만난 위치 바로 뒤에 key 값을 이동 파이썬 코드 def insertion_sort(arr): ..

선택 정렬(Selection Sort) 선택 정렬은 버블 정렬(Bubble Sort)과 유사한 알고리즘이다. 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘이다. 정렬 과정 1. 우선, 위치(index)를 선택한다. 2. i+1번째 원소부터 선택한 위치(index)의 값과 비교를 시작 3. 오름차순이므로 현재 선택한 자리에 있는 값보다 순회하고 있는 값이 작다면, 위치(index)를 갱신 4. 2번 반복문이 끝난 뒤에는 min_index에 1번에서 선택한 위치(index)에 들어가야 하는 값의 위치(index)를 갖고 있으므로 서로 교환(swap) 파이썬 코드 def selection_sort(arr): for i in range(len(arr)-1): min_i..

인공지능(AI, Artificial Intelligence)이란? 인공지능은 인간의 지적능력을 인공적으로 구현하여 컴퓨터가 인간의 지능적인 행동과 사고를 모방할 수 있도록 하는 소프트웨어이다. 인공지능의 지능 수준에 따른 분류 수준 내용 사례 수준1 단순 제어 프로그램 에어컨, 청소기, 세탁기 수준2 고전적인 인공지능(탐색, 추론, 지식) 전문가 시스템 수준3 기계학습 인공지능 온라인 쇼핑몰의 추천 시스템 수준4 딥러닝 인공지능(특징 표현 학습) 자연어 처리, 영상인식 기계학습 기계학습은 인공지능으 분야 중 하나로, 인간의 학습 능력과 같은 기능을 컴퓨터에서 실현하고자 하는 기술 환경과의 상호작용에 기반한 경험적인 데이터로부터 스스로 성능을 향상시키는 시스템을 연구하는 기술 기계학습에 대한 분류 분류 설..

현민이는 게임캐릭터가 맵 안에서 움직이는 시스템을 개발중이다. 캐릭터가 있는 장소는 1 * 1 크기의 정사각형으로 이뤄진 N * M 크기의 직사각형으로, 각각의 칸은 육지 또는 바다이다. 캐릭터는 동서남북 중 한 곳을 바라본다. 맵의 각칸은 (A, B)로 나타낼 수 있고, A는 북쪽으로부터 떨어진 칸의 갯수, B는 서쪽으로부터 떨어진 칸의 개수이다. 캐릭터는 상하좌우로 움직일 수 있고, 바다로 되어 있는 공간에는 갈 수 없다. 캐릭터의 움직임을 설정하기 위해 정해놓은 매뉴얼은 이러하다. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향(반시계 방향으로 90도 회전한 방향)부터 차례대로 갈 곳을 정한다. 캐릭터의 바로 왼쪽 방향에 아직 가보지 않은 칸이 존재한다면, 왼쪽 방향으로 회전한 다음 왼쪽으로 한 칸을..