본문 바로가기

알고리즘/기초

(5)
빅오 표기법(Big O notation) 빅오 표기법은 알고리즘이 얼마나 빠른지 표시하는 특별한 방법입니다. 예를 들어, 리스트의 크기가 n이라고 가정해 봅시다. 단순 탐색은 원소를 하나씩 확인하기 때문에 n번을 연산해야 합니다. 그래서 빅오 표기법에 따른 실행 시간은 O(n)입니다. 빅오 표기법은 속도를 시간 단위로 세지 않습니다. 빅오 표기법은 연산 횟수를 비교하기 위한 것입니다. 빅오 표기법을 사용하면 수행해야 할 일이 많아질 때 알고리즘에 걸리는 시간이 어떤 식으로 증가하는지를 알 수 있습니다. 다른 예를 들어보자면, 이진 탐색은 크기가 n인 리스트를 확인하기 위해 log n번의 연산이 필요합니다. 빅오 표기법으로는 O(log n)입니다. 빅오 표기법은 알고리즘이 동작하기 위해 필요한 연산 횟수를 나타냅니다. 이 연산 횟수 앞에 커다란(..
알고리즘이란? 알고리즘은 프로그램보다 훨씬 오래 전부터 있던 개념입니다. 프로그램은 컴퓨터가 나온 이후, 즉 세계 최초의 기계식 컴퓨터가 발명된 19세기 중반부터 나온 것이지만, 알고리즘은 무려 기원전부터 존재했던 개념입니다. 알고리즘은 '문제를 풀기 위한 절차'입니다. 알고리즘을 영어사전에서 찾아보면 '산법'이라고 나오기도 하는데, 이는 '어떤 문제를 해결하기 위해 입력된 자료를 토대로 원하는 출력을 유도하는 규칙의 집합'을 뜻합니다. 알고리즘을 '문제를 풀기 위한 절차'라고 한다면 요리 레시피도 알고리즘의 하나라고 말할 수 있습니다. 요리 레시피에는 필요한 재료나 사용할 분량, 구체적인 요리 절차가 있습니다. 예를 들어 카레라이스 레시피대로 요리하면 누가 만들어도 비슷한 카레라이스가 완성됩니다. 올바른 알고리즘을 ..
BFS / DFS 그래프의 탐색은 하나의 정점에서 시작하여 그래프의 모든 정점들을 한 번씩 방문(탐색)하는 것이 목적입니다. 그래프의 데이터는 배열처럼 정렬이 되어 있지 않습니다. 그래서 원하는 자료를 찾으려면, 하나씩 모두 방문하여 찾아야 합니다. 지하철 노선도를 보여주는 애플리케이션에서 경로를 탐색할 때에는, 최단 경로나 최소 환승 등 하나의 목적에도 여러가지 방법이 있습니다. 이처럼 그래프의 모든 정점 탐색 방법에도 여러 가지가 있습니다. 그중에서 가장 대표적인 두 가지 방법, DFS와 BFS를 소개합니다. 이 둘은 데이터를 탐색하는 순서만 다를 뿐, 모든 자료를 하나씩 확인해 본다는 점은 같습니다. BFS (Breadth-First Search), 너비 우선 탐색 가까운 정점부터 탐색합니다. 그리고 더는 탐색할 정..
자료구조 기초 자료구조란? 여러 데이터들의 묶음을 저장하고, 사용하는 방법을 정의한 것입니다. 자료구조를 설명하기에 앞서, 데이터(data)는 무엇일까요? 데이터는 문자, 숫자, 소리, 그림, 영상 등 실생활을 구성하고 있는 모든 값입니다. 우리의 이름, 나이, 키, 집 주소, 목소리 혹은 유전자 DNA까지 데이터로 분류할 수 있습니다. 하지만 데이터는 그 자체만으로 어떤 정보를 가지기 힘듭니다. 예를 들어 나이라는 데이터만 알고 있다면, 이 나이가 사람의 나이인지, 고양이의 나이인지, 나무의 나이인지 알 수 없습니다. 이처럼 데이터는 분석하고 정리하여 활용해야만 의미를 가질 수 있습니다. 그 뿐만 아니라, 데이터를 사용하려는 목적에 따라 형태를 구분하고, 분류하여 사용합니다. 필요에 따라 데이터의 특징을 잘 파악(분..
재귀 재귀란? 엘레베이터 거울처럼 거울 속의 거울 속의 거울처럼 자기자신을 반복하는 것입니다. 그리고 재귀 호출은 실행과정 중에 자기 자신을 호출하는 것입니다. https://youtu.be/RPSVXjcFbvA 재귀는 언제 사용해야 하나요? 재귀는 다음과 같은 상황에서 아주 적합합니다. 1. 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우 2. 중첩된 반복문이 많거나 반복문의 중첩 횟수(number of loops)를 예측하기 어려운 경우 재귀적 사고 연습하기 1. 재귀 함수의 입력값과 출력값 정의하기 (재귀적 사고) 💭 이 문제는 재귀로 풀 수 있을 것 같아! 재귀 함수를 통해 풀고자 하는 문제, 즉 도달하고자 하는 목표를 정의하는 데 도움이 됩니다. 재귀적으로 사고하는데에 가장 먼저 해야..

반응형