오늘은무엇을만들까

이진 탐색

이진 탐색이란 순차 탐색: 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법. 이진 탐색: 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법. 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정한다.시간 복잡도 단계마다 탐색 범위 = 탐색 범위 / 2이므로 연산 횟수는 log2(N)에 비례한다. 다시 말해 이진 탐색은 탐색 범위를 절반씩 줄이며, 시간 복잡도 O(logN)을 보장한다.

퀵 정렬, 계수 정렬

퀵 정렬 기준 데이터를 설정, 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법이다. 일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나이다. 병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘이다. (e.g. C, Java, Python) 가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(Pivot)으로 설정한다. 동작 방식 빠른 이유 시간 복잡도 퀵 정렬은 평균의 경우 O(NlogN)의 시간 복잡도를 가진다. 하지만 최악의 경우, O(N^2)의 시간 복잡도를 가진다. 계수 정렬 특정한 조건이 부합할 때만 사용할 수 있지만, 매우 빠르게 동작하는 정렬 알고리즘이다. 계수 정렬은 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 ..

선택 정렬, 삽입 정렬

정렬(Sorting) 데이터를 특정한 기준에 따라 순서대로 나열하는 것 선택 정렬 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택, 맨 앞에 있는 데이터와 바꾸는 것을 반복한다.시간 복잡도 선택 정렬은 N번만큼 가장 작은 수를 찾아 맨 앞으로 보내야 한다. 구현 오차를 무시하면 이는 (N^2 + N - 2) / 2, 즉 O(N^2)으로 표기된다. 삽입 정렬 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입한다. 선택 정렬에 비해 구현 난이도가 높은 편이지만 일반적으로 더 효율적으로 동작한다.

DFS / BFS

탐색(Search)이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말한다. 대표적인 그래프 탐색 탐색 알고리즘이 바로 오늘 다룰 DFS, BFS이다. 이 둘은 코딩 테스트에서 매우 자주 등장하는 유형이므로, 반드시 숙지하는 것이 좋다. 이러한 알고리즘들을 사용하기 위해서는, 우선 몇 가지 자료구조를 알아야 한다. 선행되는 자료구조 스택 (Stack) 먼저 들어온 데이터가 나중에 나가는 형식(선입후출, First-In-Last-Out, FILO)의 자료구조 입구와 출구가 동일한 형태로 스택을 시각화할 수 있다. (예: 프링글스 통) 큐 (Queue) 먼저 들어온 데이터가 먼저 나가는 형식(선입선출, First-In-First-Out, FIFO)의 자료구조 큐는 입구와 출구가 모두 뚫려 있는 형태..

구현 유형

구현 유형 구현이란, 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다. 이에 따르면, 사실상 모든 알고리즘 문제를 구현 문제라고 할 수 있겠다. 그래서 어떠한 문제를 구현 문제라고 부르면, 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 지칭한다. 예시 알고리즘은 간단하나, 코드가 지나치게 길어지는 문제 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제 문자열을 특정한 기준에 따라 끊어 처리해야 하는 문제 적절한 라이브러리를 찾아 사용해야 하는 문제 구현 문제에서의 행렬 구현 문제에서는 2차원 배열 형태로써 행렬을 사용하는 경우가 많다. 특히 시뮬레이션, 완전 탐색 문제에서는, 배열을 통해 2차원 공간에서의 방향 벡터가 자주 활용된다. 예시 문제 위의 문제가 동, 북, 서, ..

그리디 알고리즘

최근 알고리즘 공부를 대학교 동아리 스터디에서 진행하게 되었다. 스터디의 진행 방식은 유튜브를 통해 나동빈님의 알고리즘 강의를 보고, 내용을 정리, 주어진 문제를 파이썬으로 푸는 방식이다. 이때 정리한 내용을 동아리 Notion 페이지에 올리게 되는데, 추후 따로 다시 공부하거나, 또 훗날 누군가 이 velog 글을 보며 공부할 때를 위해 알고리즘을 정리한 글을 velog에 남기려 한다. 이제 시작해 보자. 참고한 강의는 아래의 강의이다. https://youtu.be/5OYlS2QQMPA?si=77wCe6SQRnNbqIA7 그리디 알고리즘 그리디 알고리즘이란 그리디 알고리즘이란 Greedy(탐욕적인)라는 이름답게, 단순히 현재의 주어진 상황에서 가장 나은 선택지를 구하는 것, 즉 최적해를 구하는 것이다..