버블(Bubble) 정렬두 개의 인접한 원소를 비교하여 정렬하는 방식이다. 왜 Bubble 이라는 이름이 붙었는지 찾아보니 정렬 과정에서 원소의 이동이 마치 버블이 수면위로 올라오는 것 같다고 해서 버블(Bubble) 이라는 이름이 붙었다고 한다...  정렬 방식 중 가장 쉬우니 일단 버블 정렬에 대한 특징만 짚고 넘어가보자. 버블 정렬은 데이터를 '비교'하면서 찾기 때문에 '비교 정렬'이며 정렬의 대상이 되는 데이터 외에 추가적인 공간을 필요로 하지 않기 때문에 '제자리 정렬(in-place sort)'이기도 하다. 정확히는 데이터를 서로 교환하는 과정(swap)에서 임시 변수를 필요로 하나, 이는 충분히 무시할 만큼 적은 양이기 때문에 제자리 정렬로 보는 것이다. 이는 선택정렬과도 같은 부분이다. 그..

1. 정렬 알고리즘 개요정렬(sorting)이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다. 데이터를 가공할 때 오름차순이나 내림차순 등 대부분 어떤 식으로든 정렬해서 사용하는 경우가 많기에 정렬 알고리즘은 프로그램을 작성할 때 가장 많이 사용되는 알고리즘 중 하나이다.  숫자가 하나씩 적힌 카드가 10장 있다면, 이 카드를 오름차순으로 정렬해보자. 어떻게 이 카드들을 정렬할 수 있을까?보통 인간이라면 카드를 훑은 후 순식간에 숫자를 0부터 10까지 구성된 걸 확인하고 순차적을 나열할 것이다. 하지만 컴퓨터에게는 쉬운 작업이 아니다. 컴퓨터는 인간과 다르게 데이터의 규칙성을 직관적으로 알 수 없으며, 어떻게 정렬을 수행할지에 대한 과정을 소스코드로 작성하여 구체적으로 명시해야 한다. 정..

완전 탐색, 브루트 포스란?Brute Force의 사전적 의미를 보면 다음과 같다. brute: 무식한 +  force: 힘    무식한 힘으로 해석할 수 있다. 즉, 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 가져온다.이 알고리즘의 강력한 점은 예외 없이 100%의 확률로 정답만을 출력한다.  장점알고리즘을 설계하고 구현하기 쉽다.복잡한 알고리즘 없이 빠르게 구현할 수 있다.   단점알고리즘 실행 시간이 매우 오래 걸린다.메모리 효율 쪽으로 매우 비효율적이다.  종류 브루트 포스는 기본 구조는 크게 선형 구조와 비선형 구조로 나눌 수 있다. 선형 구조 : 순차 탐색비선형 구조 : 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)심화 : 백트래킹(재귀)백트래킹과 DFS, BF..

최단 경로(Shortest Path) 알고리즘이란? 가장 짧은 경로를 찾는 알고리즘, '길 찾기' 문제로 불린다. 문제를 그래프로 표현하고 각 지점을 노드, 지점간 연결된 도로는 간선이라 한다. 최단 경로 알고리즘에는 그리디 알고리즘과 다이나믹 프로그래밍이 그대로 적용된다. 다양한 사례가 존재하며, 상황에 맞는 효율적인 알고리즘이 이미 정립되어 있다. 문제 형태가 정형화되어 있기 때문에 구현 부분은 비슷함 문제에 따른 외적인 조건만 챙겨서 풀이 ex) 한 지점에서 다른 특정 지점까지 최단 경로 구하기, 모든 지점에서 다른 모든 지점까지 최단 경로 구하기 등 1) 최단 경로 문제의 종류 단일 출발 (single-source) 최단 경로 어떤 하나의 정점에서 출발하여 나머지 모든 정점 까지의 최단 경로를 찾..

이것이 코딩 테스트다 with 파이썬 정리 및 추가 내용 Greedy Algorithm이란? 그리디 알고리즘(욕심쟁이 알고리즘, Greedy Algorithm)이란 "매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자"라는 모토를 가지는 알고리즘 설계 기법이다. 예를 들어 5개의 도시를 모두 한번씩만 거쳐서 여행하는 경로 중 기름값을 아끼기 위해 가능하면 짧은 경로를 이용하고 싶다고 가정하자. 이 문제를 해결하기 위해 몇 가지 전략을 사용할 수 있다. 가능한 120가지의 조합을 모두 살펴봐서 그중 가장 짧은 경로를 선택하는 것도 하나의 전략이 될 것이다. 그러한 다양한 방법 중, 그리디 알고리즘을 사용한다는 것은 "지금 내가 있는 도시에서 고를 수 있는 도로 중 가장 짧은 도로를..

원문은 해당 페이지로 이동 알고리즘이란? Algorithm is a series of contained steps which you follow in order to achieve some goal, or to produce some output 알고리즘은 어떤 목적을 달성하거나 결과물을 만들어내기 위해 거쳐야 하는 일련의 과정들을 의미합니다. 삼성역에서 택시를 타고 강남역으로 향했는데 30분 걸렸다. 구글에서 알려주는 최단경로로 갔더라면 15분 내에 도착할 것이다. 레스토랑을 예약해서 가는 경우라던지 친구와 약속시간을 잡은 경우 우리에게는 시간은 항상 소중하다. 그래서 우리는 시간을 효율적으로 사용하기 위한 노력을 의식적으로 하고 있다. 컴퓨터 프로그래밍에서도 시간복잡도가 가장 낮은 알고리즘을 채택해 ..