코딩은 삽질이다

지난 포스팅에서 버블 정렬(Bubble Sort)와 선택 정렬(Selection Sort)를 포스팅 해보았습니다. 오늘은 지난 포스팅과 더불어 시간복잡도 O(N2)을 갖는 기초적인 정렬 중 하나인 삽입 정렬(Insertion Sort)에 대해 알아보겠습니다. 삽입 정렬(Insertion Sort) 삽입 정렬(揷入整列, Insertion Sort)은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다. *위키백과 참조 위키백과의 설명이 조금은 이해가 가지 않을 수 있기 때문에, 아래 그림을 통해 이해를 돕도록 하겠습니다. 정렬이 안된 초기상태의 배열이 있습니다. 삽입정렬에서는 가장 첫번째 원소는 정렬이 된 상태라고 가..

지난 포스팅에서는 버블 정렬(Bubble Sort) 에 대해 포스팅 해보았습니다. 이번에는 버블 정렬과 함께 기초적인 정렬 방법인 선택 정렬(Selection Sort) 에 대해 알아보도록 하겠습니다. 선택 정렬(Selection Sort) 선택 정렬(Selection Sort)은 제자리 정렬(in-place sorting) 알고리즘 중 하나로 주어진 리스트의 최소값을 찾아 그 값을 맨 앞으로 교체하며 정렬하는 방법입니다. 시간복잡도가 O(N2)으로 상당히 느리지만, 알고리즘이 단순하며 메모리가 제한적인 경우에 사용시 성능 상의 이점이 있습니다. *위키백과 참조 선택 정렬(Selection Sort)은 정렬을 구현할 때 알고리즘을 모르더라도 가장 일반적인 접근방법 중 한가지라고 생각합니다. 그림을 통해 ..

알고리즘을 처음 시작하는 단계라면 가장 자주 접할 수 있는 문제 중 하나가 "정렬(Sort)" 일 것입니다. 왜 정렬이 자주 나오고 질문되는 것일까요 ? 그 이유는 정렬을 하는 방법이 매우 다양하고, 이를 비교하여 알고리즘의 효율성 차이를 잘 나타내 줄 수 있기 때문입니다. 빈번하게 나오는 몇몇 정렬 알고리즘에 대한 비교를 순차적으로 포스팅 하도록 하겠습니다. 그럼 가장 첫번째로 알아볼 버블 정렬(Bubble Sort)의 기본 개념부터 다루도록 하죠 버블 정렬(Bubble Sort) 버블 정렬(Bubble Sort)은 두 인접한 원소를 검사하여 정렬하는 방법이다. 시간 복잡도가 O(n2)로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용된다. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기..

제목이 제일 고민 많이했.. 지난 포스팅에서 재귀함수에 대해 간단한 예제인 팩토리얼을 통해 알아보았습니다. 혹시나 재귀에 대해 처음 접근하신다면, 우선 팩토리얼 포스팅부터 보고 오시는 것을 추천합니다. 이번 포스팅에서는 재귀함수의 또 다른 대표예제인 피보나치(Fibonacci)수열을 통해 알아보도록 하겠습니다. 피보나치(Fibonacci)란? 피보나치를 *위키백과를 참조 해보면 다음과 같다. 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열 이다. 처음 여섯 항은 각각 1, 1, 2, 3, 5, 8이다. 편의상 0번째 항을 0으로 두기도 한다. 다음과 같은 그림을 보여준 이유는 실제로 문제에서 적용될 수 있는 타일 문제를 이해하기 좋다. 즉 피보나치 수열이 1,1,2,3,5,8,..

오늘은 신입 면접시 자주가끔???(?) 나오는 재귀 함수에 대한 포스팅을 해보도록 하겠습니다. 더불어 재귀함수와 자주 비교되는 반복문에 대해서도 같이 작성하도록 하겠습니다. 재귀함수란? 하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 방식으로 문제를 해결하는 방법 반복문은 while문이나 for문의 사용을 통해 익숙할 것입니다. 하지만 재귀함수는 비슷한 기능임에도 조금은 낯설다고 생각합니다. (고수분들 제외) 재귀함수에서 가장 쉬운 문제인 Factorial을 사용하여 이해를 돕도록 하죠. 팩토리얼은 예를들면 5! [5 팩토리얼] 이라고 하면 5x4x3x2x1 = 120 의 결과를 얻는 것입니다. 이러한 문제에 직면했을 때 쉽게 생각하는 방법 중 하나가 반복문을 이용하는 것이죠 재귀 함수에 앞서서, ..

이번 포스팅에서는 자료구조와 알고리즘의 특징을 알아보기 전에 왜 배워야 하는가 ? 많은 기업들은 왜 자료구조와 알고리즘 해결능력을 보려고 하는가 ? 에 대해서 포스팅 해보면서 우리가 배워야 하는 이유에 대해 개인적인 생각을 말해보도록 하겠습니다. 유튜브 "알고리즘" 이 날 여기로 인도했다. ( 해적왕?... ) 요즘 알고리즘이라는 단어는 많이들 알고 계실거라고 생각한다. 사실 내가 학교를 다닐때만 해도 알고리즘이란 단어는 그저 학과수업의 제목일 뿐이였는데... ( 이건 나만 해당 ) 이제는 알고리즘이란 단어가 많이 친숙해졌으며, 특히 컴퓨터 안에서 알고리즘에 대해서 개발자가 아닌 사람들도 어느 정도의 이해를 하고 있다. 근데 자료구조라는 단어는 익숙하지 않을 거라고 생각한다. 특히 자료구조의 경우는 왜 ..