순서대로 나열되어 있는 배열이 있습니다. 이 배열에서 target 값을 찾으려 하는데, 배열 요소가 100만개라 모두 비교하면 시간이 많이 걸립니다. 이때 더 빠르게 target 값을 찾을 순 없을까요? 이 필요성을 채워주는 것이 이분 탐색 알고리즘입니다. 📌 이분 탐색 정의 이분 탐색은 정렬된 배열을 1/2씩 줄여서 타겟 값을 찾아나가는 알고리즘입니다. 이분 탐색의 프로세스는 다음과 같습니다. (1) 배열의 중간 값을 찾는다. (2) target 값과 중간 값을 비교하여 (low, same, high)큰지, 작은지, 같은지를 판단한다. (3) target이 작다면 중간 값 이전의 배열을, 크다면 중간 값 이후의 배열을 대상으로 다시 이분 탐색을 진행한다. (4) 만약 같다면, 중간 값이 바로 targe..

이번 포스팅에서 다룰 알고리즘은 '분할 정복'이다. Divide and Conquer 이 알고리즘은 문자 그대로, 분해해서 해결하는 것을 메인 흐름으로 가져간다. 밑의 그림을 보면 이해될 것이다. * 실습 환경은 windows 10/ vscode에서 이뤄졌습니다. 📍 정의 한 번에 해결하기 어려운 문제(시간문제, 공간문제 등)를 잘게 쪼개고 각개 격파한 후, 하나의 답을 도출하는 알고리즘. 분할 정복 알고리즘은 다음 세 개의 프로세스를 가진다. 📍 Process (1) Divide : 문제를 정의하고, 잘게 쪼개는 과정이다. 이 단계에서 문제를 잘 쪼개야 손쉽게 문제를 해결할 수 있다. (2) Conquer : 잘게 쪼개진 문제를 해결할 시간이다. 분할 알고리즘의 문제는 쪼개도 사실상 같은 문제들이다. ..

동적계획법 Dynamic Programming 이번 포스팅에선 동적계획법 알고리즘을 살펴보겠다. 동적계획법은 "한 번 계산한 문제는 다시 계산하지 않는다"라는 신념을 가진 녀석이다. 메모리를 조금 써서 속도를 비약적으로 상승시키는 것이 핵심이다. Let's Go 동적계획법이 아니라면? 보통은 단순 재귀. 동적계획법의 성능을 확인할 수 있는 문제가 있다. 바로 피보나치 수열이다. 피보나치 수열을 동적계획법이 아닌 단순 재귀를 사용하여 구현하면 다음과 같다. def fibo(x): if x == 1 or x ==2: return 1 else: return fibo(x-1) + fibo(x-2) 위의 코드로 피보나치 수열을 구한다고 생각해보자. --- fibo(5)를 구하기 위해선, fibo(4)와 fibo(..

이번 포스팅에선 큐(Queue)의 개념과 코드 구현을 할 것이다. 만약 스택(Stack) 개념을 알지 못한다면 이전 포스팅을 보고 오자. [이전 포스팅 URL: https://mengu.tistory.com/29] [자료구조] 스택(Stack) 개념 및 코드 구현 자료구조 중 하나인 스택(Stack)에 대해 알아보고, 직접 코드로 구현해보자. 배열 구현과 연결 리스트 구현 모두 해볼 것이다. 들어가자. 스택(Stack) 개념 가장 나중에 넣은 데이터를 가장 먼저 빼 mengu.tistory.com 들어가보자! 큐(Queue) 개념 큐(Queue)는 FIFO(First In First Out) 방식의 자료구조이다. 먼저 들어온 요소가 가장 먼저 나간다. 큐(Queue)의 제일 앞 요소를 front, 제일 ..

자료구조 중 하나인 스택(Stack)에 대해 알아보고, 직접 코드로 구현해보자. 배열 구현과 연결 리스트 구현 모두 해볼 것이다. 들어가자. 스택(Stack) 개념 가장 나중에 넣은 데이터를 가장 먼저 빼내는 데이터 구조. LIFO(Last In First Out) 방식. 스택의 가장 위 요소를 Top이라 한다. 활용 재귀적으로 함수를 호출해야 하는 작업에서, 임시 데이터를 스택에 쌓아두고 이전 단계로 돌아갈 때 데이터를 다시 꺼내오는 등으로 쓰인다. 기능 1. push() : 스택의 원소를 추가한다. 2. top() : 스택의 가장 위 원소를 가져온다. 3. pop() : 스택의 가장 위 원소를 뽑아낸다. 4. isEmpty() : 스택의 empty 여부를 확인한다. 스택(Stack) 구현 배열 구현 ..

'알고리즘을 효율적을 짠다 = 시간과 공간을 최소화한다' 알고리즘의 효율성을 판단할 때, 시간 복잡도(Time complexity)와 공간 복잡도(Space complexity)를 따진다. 백준, 프로그래머스에서도 알고리즘을 평가할 때 시간과 메모리 제한을 두는 것도 다 이런 이유에서다. 시간 복잡도(Time complexity) 개념와 예시 '입력값의 증가에 대한 연산 횟수 증가분' 시간 복잡도는 그저 실행 시간을 측정하는 것이 아니다. 실행 시간은 측정을 위한 프로그램이 필요할뿐더러 수행 환경에 따라 실행 시간이 달라질 수 있다. 이에 따라 입력값이 증가함에 따라 연산 횟수가 어떤 비율로 증가하는가에 초점을 두고 시간 복잡도를 측정한다. 시간 복잡도는 Worst Case, 즉 가장 최악으로 시간이 걸..