road to DS

다들 백준 문제 풀다가 이런 상황 겪어보셨을 겁니다. 이는 백준에서 문제를 채점할 때 시간제한을 두기 때문인데요, 코드를 비효율적으로 작성하면 그만큼 실행하는 데 시간이 더 오래 걸리게 되겠죠? 이를 방지하기 위해 코드의 실행 시간이 얼마나 걸릴지 파악하는 것이 좋은데요, 이를 위해 사용하는 방법이 코드의 '시간 복잡도'를 파악하는 것입니다. 이는 정확한 실행 시간을 구하는 방법이 아니고, 알고리즘이 얼마만큼의 시간을 사용할지 근사적으로 알려주는 방법입니다. 시간복잡도는 Big-O Notation을 이용해 표기합니다. O(n)과 같이 작성하며, 괄호 안에는 알고리즘이 사용할 시간과 관련된 식이 들어갑니다. 시간복잡도를 작성하는 규칙이 몇 가지 있는데요, 이에 대해 알아보도록 하겠습니다. 1. 기본적인 작..

재귀란, 함수 내부에서 자기 자신을 호출하는 방법입니다. 가장 대표적인 예제인 팩토리얼을 통해 작동하는 원리를 알아봅시다. 먼저, 반복문으로도 팩토리얼을 계산할 수 있습니다. def factorial(n): value = 1 for i in range(1, n+1): value *= i return value 이를 재귀를 이용해 구현하면 다음과 같습니다. def factorial(n): if n==1: return 1 else: return n * factorial(n-1) 위 코드를 보면, n이 1보다 클 경우 factorial(n-1)이라는 코드에서 자기 자신을 호출하는 것을 확인할 수 있습니다. 이를 '함수를 재귀적으로 호출한다'라고 표현합니다. 위 코드는 다음과 같이 작동할 것입니다. n부터 시작..

이분 탐색은 내부 원소들이 정렬되어 있는 배열에서 특정 원소를 빠르게 찾을 수 있는 탐색 방법이다. 탐색 범위를 절반씩 줄여나간다는 특징이 있는데, 이 때문에 시간복잡도가 O(log n)으로, 순차 탐색보다 효율적이다. 예를 들면, 아래의 배열에서 숫자 3을 탐색하는 과정은 다음과 같다. 이분 탐색(Binary Search) 헷갈리지 않게 구현하기 개요 이분 탐색은 off-by-one error가 발생하기 쉬워서 늘 헷갈립니다. 이분 탐색 문제를 풀다보면 탈출 조건으로 lo k 를 만족하는 mid를 탐색할 수 있을 것이다. P.S. 12015번은 풀지 않는 것을 추천한다. DP를 쓰면 이분 탐색으로 풀 수 있지만 시간초과가 많이 난다고 하며, LIS(가장 긴 증가하는 부분 수열) 알고리즘을 사용하는 것이..

5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 이 문제에서 숫자 입력을 배열 형태의 텍스트로 받기 때문에, 여기서 숫자를 분리해야 한다. [1,2,3,4] -> 숫자 1,2,3,4 분리 string str, word; vector words; str.erase(location);// location = str.begin() + (제거할 위치 - 1) stringstream ss(str); while(getline(ss, word, )){ words.push_back(word);// str을 ',' 기준으로 토큰화 -> 하나씩 words에 저장 } ..

1. Stack : LIFO(Last In First Out) 구조. 가장 최근에 스택에 삽입된 자료의 위치를 top이라 한다. 스택이 비어있을 때 stack.pop 시도 -> stack underflow 발생 스택의 크기가 비어있을 때 stack.push 시도 -> stack overflow 발생 데이터 삽입, 삭제의 시간 복잡도는 O(1) 데이터를 저장하는 버퍼를 1차원 배열 형태로 관리함 -> 메모리 추가로 할당할 경우 기존 메모리 영역의 2배만큼 메모리 추가로 할당하고 기존의 요소 복사 - 데이터 접근, 삽입, 삭제가 빠르다. - top 위치 이외의 데이터에 접근할 수 없어서 탐색 불가능. 탐색하려면 모든 데이터 꺼내면서 진행해야 됨 #include vector v; v.at(idx..