CodingGom

[Algorithm]기본 탐색 알고리즘

이 글은 이전에 운영하던 깃 블로그에서 옮겨온 글입니다. 서론 지난 글 [Algorithm] 기본 정렬 알고리즘에 이어, 역시나 코딩 테스트 문제의 단골인 기본 탐색 알고리즘에 대해 다뤄보려 합니다. 정렬은 데이터를 '정리'하는 게 중심이었다면, 탐색은 데이터를 '검색'하는 게 중심이 되겠네요. 단골 문제이다 보니 예시 코드는 좋은 것들이 많이 돌아다녀 이번 글에서 코드는 굳이 포함하지 않겠습니다.(설명이 길어 글 길이가 길어진 이유도 있습니다.) 선형 탐색 가장 기본적이고 쉬운 탐색 알고리즘이 아닐까 생각합니다. 순서대로 쭉… 찾는 거니까... 다른 이름으로 순차 탐색이라고도 함 데이터의 집합(배열, 리스트)등의 처음부터 끝까지 순서대로 비교하며 탐색하는 방식 데이터의 양이 늘어나면 수행 시간이 기하급..

2022.04.10

[Algorithm]기본 정렬 알고리즘

이 글은 이전에 운영하던 깃 블로그에서 옮겨온 글입니다. 서론 예전에 취업준비를 하면서 코딩 테스트 연습을 한 적이 있습니다. 코딩 테스트 출제 문제는 수학적 사고가 필요한 Dynamic programming이나 트리 같은 자료구조 등 다양 하지만 데이터의 정렬과 탐색이 꽤나 많았던 걸로 기억합니다. 이번 글에서는 기본적인 정렬 알고리즘 몇가지를 다뤄 보려 합니다. 다루는 주 내용은, 알고리즘의 특징과 시간 복잡도 그리고 간단한 코드 예시 입니다. 선택정렬 시간 복잡도 : O(n^2) 공간 복잡도 : O(n) 현재 위치에 들어갈 자리를 선택해 정렬하는 방식 로직 제일 앞에서 부터, 배열값 중 가장 작은 값을 찾음 찾은 가장 작은값을 현재 인덱스와 교체 위 과정 반복 코드 예시 void selectionS..

2022.04.10