on my way

05. 배열 05-1. 배열 개념 배열은 인덱스와 값을 일대일 대응해 관리하는 자료구조입니다. 데이터를 저장할 수 있는 모든 공간은 인덱스와 일대일 대응하므로 어떤 위치에 있는 데이터든 한 번에 접근할 수 있습니다. 배열 선언 # 일반적인 방법 arr = [0, 0, 0, 0, 0, 0] arr = [0] * 6 # 리스트 생성자 사용 arr = list(range(6)) # [0, 1, 2, 3, 4, 5] # 리스트 comprehension 사용 arr = [0 for _ in range(6)] # [0, 0, 0, 0, 0, 0] 선언한 배열은 위 사진처럼 저장된다. 파이썬의 리스트는 동적으로 크기를 조절할 수 있도록 구현되어 있습니다. 파 이썬의 리스트는 다른 언어의 배열 기능을 그대로 사용할 수..

03. 알고리즘의 효율 분석 시간복잡도 시간 복잡도(time complexity)란, 알고리즘의 성능을 나타내는 지표로 입력 크기에 대한 연산 횟수의 상한을 의미한다. "내가 구현한 알고리즘 성능이 제한 시간내 결과값을 낼수 있는지"를 위해 필요하다. 알고리즘 수행 시간을 측정하는 방법 시간 복잡도를 측정하는 법 입력 크기에 따른 연산 횟수의 추이를 활용해서 성능을 가늠하게끔 시간 복잡도를 표현하는 방법을 점근적 표기법이라고 합니다 가장 많이 사용하는 점근적 표기법은 상한선을 활용하는 방법입니다. 그리고 이 표기법을 빅오 표기법(big-O notation)이라고 합니다. 빅오 표기법은 어렵지 않습니다. 어떤 프로그램의 연산 횟수가 f(x)라고 할 때 함수의 최고차항을 남기고 차수를 지워 O(...)와 같..

I. 다이나믹 프로그래밍 다이나믹 프로그래밍은 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법이다. 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다는 것이 핵심이다. 즉, 하나의 문제는 단 한 번만 풀도록 하는 알고리즘이다. (우리가 평소에 문제를 풀이할 때 효율적인 방법으로 고안할 필요가 있다.) 다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식(탑다운-하향식, 바텀업-상향식)으로 구성된다. 매우 비효율적인 문제더라도 다이나믹으로 획기적으로 시간을 줄일 수 있다. 다이나믹 프로그래밍은 동적 계획법이라고도 부른다. 일반적인 프로그래밍 분야에서는 동적이란 프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법을 의미하지만, 다이나..

완전 탐색(Brute-Force) 완전히 탐색, 즉 가능한 경우의 수를 모두 조사하는 방법이다. 예시) 번호 자물쇠 (경우의 수 0000~9999). 최악의 경우 10000*1초 = 대략 166분 그러나 컴퓨터 연산속도는 1초에 1억(=10^8) 백만(1,000,000)은 10^6 완전 탐색의 장단점 장점: 답을 무조건 찾을 수 있다. 단점: 답을 찾는데 시간이 많이 걸린다. 따라서, 탐색할 요소가 많을 때는 다른 방법을 사용하는 것이 현명하겠지만 탐색할 요소가 적거나, N제한이 작은 경우에는 완전 탐색만큼 정확한 탐색 방법은 없다. 또한 완전 탐색 문제를 풀 때에는 시간 제한을 체크하는 것이 중요하다. 재귀함수 어떤 함수에서 자기 자신을 호출하는 함수이다. (인셉션에서의 꿈 개념과 동일하다) 재귀함수에..

스택은 후입선출 (LIFO : Last In First Out) 큐 선입선출 (FIFO : First In First Out) 즉, 스택과 큐는 서로 반대되는 개념이다. 스택(Stack) 가장 마지막에 들어온 데이터가 가장 먼저 처리가 되는 자료구조이다. 입구와 출구가 하나 밖에 없는 상태이다. 스택 사용 방법 1. 스택 직접 구현 #include using namespace std; const int MX = 1000005; int dat[MX]; int pos = 0; void push(int x){ dat[pos++] = x; } void pop(){ pos--; } int top(){ return dat[pos-1]; } void test(){ push(5); push(4); push(3); cout

Sorting Algorithm 정렬 알고리즘 Big O는 알고리즘의 퍼포먼스를 이해하기 쉽고 효율적으로 작성하는 방법이다. 그러나 Big O가 모든 알고리즘을 완벽하게 설명하는 것은 아니다. 알고리즘이 같은 Big O지만 각 퍼포먼스가 다르기 때문이다. 정렬이란 무엇을 정리하는 것이다. 이진 검색에서 빠른 알고리즘을 사용하려면 배열 정렬을 해야한다. 1. Bubble Sorting 버블 정렬 버블은 그렇게 좋은 알고리즘은 아니다. 그러나 이해하기 쉬운 알고리즘이다. 정렬의 입문으로 좋은 토픽이다. 배열의 2개의 아이템을 선택하고, 비교한다. 왼쪽이 오른쪽보다 크면 swap하며 바꾸는 방식이다. 비교하고 swap하며 반복하고, 값이 큰 아이템이 끝까지 bubble로 이동하는 것이다. # include #..