자료구조 & 알고리즘 (5) 썸네일형 리스트형 알고리즘 : 분할정복법 - 이분탐색 알고리즘에서 필요한것 중 하나는 내가 원하는 데이터를 얼마나 빠르게 찾을 수 있는가 입니다.이를 위해 여러가지 탐색방법이 존재하며, 이 중 이분탐색에 대해 알아보도록 하겠습니다. 이분탐색이란?이분탐색은 말 그대로 반씩 탐색하는것을 말합니다.기존의 탐색방법은 하나의 데이터를 찾기 위해 모든 데이터를 확인해야 했고,이 때문에 O(n) 의 시간복잡도를 갖게 되었습니다.하지만, 이분탐색의 경우, 분할정복법을 사용하여 중간지점만을 확인원하는 값이 없는 절반은 제외하는 식으로 계산하기 때문에2n의 꼴, 즉 O(log n)의 시간복잡도를 갖게 되었습니다." data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 이분탐색을 위한 조건이분탐색은 중간값과 탐색값을 비교하여 탐색값보다 작거나 큰 .. 알고리즘 : 정렬 - 버블정렬, 병합정렬, 퀵정렬 정렬이란, 데이터들을 정해진 순서대로 나열하는것입니다.알고리즘을 사용하기 위해서는 원하는 데이터가 어느위치에 있는지 알아야하는데,정렬은 이를 도와주는 과정입니다. 보통 오름차순(점점 커지는 규칙)과 내림차순(점점 줄어드는 규칙)으로 구분하며,원하는 방식을 추가로 정할수도 있습니다. 또한 정렬방식에 따라 시간복잡도를 아낄 수도 있습니다.이번 글에서는 정렬 중,버블정렬(bubble sort)병합정렬(merge sort)퀵정렬(quick sort) 을 알아보도록 하겠습니다. 버블정렬 (bubble sort)버블 정렬이란, 서로 인접한 두 원소를 비교하여 위치를 변경하는 방법입니다.인접한 두 원소를 비교하여 정렬하기 때문에, 한 사이클이 지나면 가장 크거나 작은 값이 맨 뒤로 이동합니다.한 사이클을 유사코.. 자료구조 : 스택, 큐, 리스트 자료구조란, 데이터를 처리하는 추상적인 구조를 말합니다.기본적인 데이터들을 효율적으로 처리하기 위해 필요하며,자료구조 없이는 알고리즘을 수행하는 데 매우 큰 어려움이 따릅니다. 오늘은 기초적인 자료구조인 스택과, 큐, 리스트에 대해 정리해보겠습니다. 데이터들의 배열, 리스트리스트란 말 그대로 데이터를 나열한 구조입니다.크게 ArrayList와 LinkedList, 두가지로 구분합니다. ArrayList배열리스트라고도 하며, 각 데이터마다 자신의 번호(index)를 가지고 있습니다.따라서 번호만 안다면, 해당 데이터를 빠르게 찾을수 있습니다.반면, 배열구조로 되어있기 때문에,데이터를 뺀다면 이후 데이터들의 인덱스를 모두 하나씩 당겨야하고,데이터를 추가한다면 이후 데이터들의 인덱스를 모두 하나씩 뒤로 .. 알고리즘 : 시간복잡도와 공간복잡도 효율적인 알고리즘을 만들려면해당 알고리즘이 얼마나 많은 연산을 하는지, 연산에 필요한 공간이 얼마나 되는지를 알아야 합니다.시간복잡도와 공간복잡도는 이러한 상황으로 인해 생겼습니다. 시간복잡도와 빅-오 표기법시간복잡도란, 해당 알고리즘을 수행하는 데 걸리는 연산의 횟수를 말합니다.한번의 알고리즘동안 입력값과 크기에따라 걸리는 횟수를 시간복잡도라고 합니다.예를 들어, 길이에 상관없이 3번의 계산 이후 출력이 나오는 알고리즘이 있다면,해당 알고리즘의 시간복잡도는 3입니다.만약 입력값의 길이만큼의 계산을 수행하는 알고리즘이 있다면,그 알고리즘의 시간복잡도는 n 입니다. 예시 코드를 보겠습니다.// 시간복잡도 1인 함수function print(number num){ return num;}// 시간복.. 알고리즘 : 알고리즘이란? 개발자로서 원활한 코드를 짜려면, 그리고 코딩테스트를 통과하려면 알고리즘에 대해 알아야 합니다.하지만 알고리즘이 무엇인가를 물어보면 잘 대답하지 못하는 사람들도 있습니다.그렇다면, 알고리즘이란 무엇일까요? 알고리즘이란?알고리즘이란, 말 그대로 문제를 푸는 절차나 방법을 의미합니다.예를들자면, 5-3 이란 수학문제가 있을때,손가락 5개를 펴서 3개를 접는 과정뺄셈을 사용해서 푸는 것이런것들이 알고리즘이라고 할 수 있습니다. 그렇다면, 정확한 알고리즘의 조건은 무엇일까요? 알고리즘의 조건1. 입출력의 존재알고리즘은 문제를 푸는 과정이기 때문에, 문제(입력)와 답(출력)이 반드시 존재해야 합니다.즉, 입력값이 없이 출력만 하는 것, 입력을 받아도 출력값이 없는것들은 알고리즘이라고 할 수 없습니다. .. 이전 1 다음
