road to DS

DataFrame에 대해 알아보기에 앞서, Series 자료형에 대해 먼저 알아보겠습니다. DataFrame이 matrix와 같다면, Series는 한 열과 같습니다. 딕셔너리와 매우 유사한데, 딕셔너리가 key-value로 이루어져 있듯이 Series는 index-value로 구성됩니다. import pandas as pd s = pd.Series({'상민':'컴공', '휘주':'화학', '도헌':'기계', '혜진':'생명'}) print(s) 더보기 리스트를 이용해 Series 객체를 만들 수도 있습니다. 딕셔너리의 경우에는 key가 index에 대응했던 반면, 리스트의 경우에는 index에 정수형 위치 인덱스, 즉 리스트의 인덱스가 Series에서 index가 됩니다. s = pd..

다들 백준 문제 풀다가 이런 상황 겪어보셨을 겁니다. 이는 백준에서 문제를 채점할 때 시간제한을 두기 때문인데요, 코드를 비효율적으로 작성하면 그만큼 실행하는 데 시간이 더 오래 걸리게 되겠죠? 이를 방지하기 위해 코드의 실행 시간이 얼마나 걸릴지 파악하는 것이 좋은데요, 이를 위해 사용하는 방법이 코드의 '시간 복잡도'를 파악하는 것입니다. 이는 정확한 실행 시간을 구하는 방법이 아니고, 알고리즘이 얼마만큼의 시간을 사용할지 근사적으로 알려주는 방법입니다. 시간복잡도는 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부터 시작..

프로그래밍에 앞서, '함수'라는 말을 수학에서 먼저 떠올릴 텐데요, 수학에서 다루는 함수는 두 집합의 대응 관계를 나타냅니다. 프로그래밍에서 다루는 함수도 이와 비슷한데요, 마찬가지로 입력값(x)에 따라 출력값(y)이 변하게 됩니다. 다만, 프로그래밍에서는 '반복적으로 사용되는 부분'을 간단하게 작성하기 위해 사용하는 데 초첨을 더 둡니다. (사실 함수를 사용하지 않아도 코드를 짤 수는 있지만, 함수를 사용하면 코딩이 엄청 편해집니다) 파이썬 함수의 구조는 다음과 같습니다. def 함수명(매개변수): 수행할 코드 return 리턴값 매개변수는 함수에 입력으로 전달되는 값을 받는 변수입니다. 함수를 사용하는 것을 '함수를 호출한다'라고 표현하는데, 코드에서 함수를 호출하면 1) 매개변수를 받고 2) 함수의..

집합 자료형은, 말 그대로 집합(set)에 관련된 것을 쉽게 처리하기 위한 자료형입니다. 다음과 같이 집합 자료형을 선언할 수 있습니다. >>> s1 = set([1,2,3]) >>> s1 {1,2,3} >>> s2 = set("Hello") >>> s2 {'e', 'H', 'l', 'o'} 얼핏 보면 집합 자료형은 이전에 다루었던 리스트와 비슷해 보이지만, 2가지 차이점을 가집니다. - 중복을 허용하지 않는다. - 순서가 없다. 리스트는 요소의 순서가 있기 때문에 인덱스를 통해 값에 접근할 수 있지만, 집합은 순서가 없기 때문에 인덱스 등을 통해 요소에 접근하는 것이 불가능합니다. 만약 set에 저장된 값을 인덱싱으로 접근하고 싶다면, 다음과 같이 리스트로 변환한 후에 해야 합니다. s1 = set([..

반복문이란, 프로그램 내에서 똑같은 명령을 일정 횟수만큼 반복하여 수행하도록 제어하는 명령문입니다. 파이썬에서는 크게 2종류의 반복문이 존재하는데요, 바로 while문과 for문 입니다. 1. while문 while문의 기본 구조는 다음과 같습니다. while 조건문: 실행문... 실행문... 종료 만일 조건식이 거짓이라면 실행문의 코드가 실행되지 않고 while문을 빠져나갑니다. 반면 조건식이 참이라면 실행문의 코드가 실행된 후에 다시 조건식으로 돌아가 조건식의 참/거짓 여부를 판단합니다. 이때, 실행문 내부에서 조건식의 참/거짓 여부에 영향을 미칠 수 있는데요, 다음 예시를 보도록 하겠습니다. a = 0 while a < 5: a += 1 print(a) print('while문 종료') 더보기 [출..

이분 탐색은 내부 원소들이 정렬되어 있는 배열에서 특정 원소를 빠르게 찾을 수 있는 탐색 방법이다. 탐색 범위를 절반씩 줄여나간다는 특징이 있는데, 이 때문에 시간복잡도가 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..