목록algorithm/CodingTest (27)
on my way
06. 스택 06-1. 스택 개념 스택은 어원에서 짐작할 수 있듯이 먼저 입력한 데이터를 제일 나중에 꺼낼 수 있는 자료구조이다. 이렇게 먼저 들어간 것이 마지막에 나오는 규칙을 선입후출 또는 FILO(First In Last Out)라고 한다. 이때 스택에 삽입하는 연산을 푸시push, 꺼내는 연산을 팝pop이라고 한다. 06-2 스택의 정의 ADT는 우리말로 추상 자료형abstract data type으로, 추상 자료형이란 인터페이스만 있고 실제로 구현은 되지 않은 자료형이다. 일종의 자료형의 설계도라고 생각하면 된다. 그렇다면 스택은 어떤 정의가 필요한 자료구조인가? 언어에 따라 표준 라이브러리에서 스택 제공 여부는 다르다. 파이썬의 경우 스택을 제공하진 않지만 대안으로 리스트 메서드인 append..
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