When will you grow up?

다이나믹 프로그래밍 - 다이나믹 프로그래밍은 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법입니다. - 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 합니다. (메모이제이션) - 다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식(top-down, bottom-up)으로 구성됩니다. 또한, 다이나믹 프로그래밍은 동적 계획법이라고 부르며, 일반적인 프로그래밍 분야에서의 자료구조에서 동적 할당(Dynamic Allocation)은 '프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법'이라는 의미를 가지며 다이나믹 프로그래밍에 동적(Dynamic)은 별다른 의미 없이 사용된 단어라 헷갈리면 안된다. 다이나믹 프로그래밍은 문제가 다음의 ..

이진탐색 순차 탐색(sequential search) : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법 이진 탐색(binary search) : 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 이진 탐색은 시작점, 끝점, 중간점이 존재 ex) 정렬되어 있는 리스트가 있다고 가정하고 4인 원소를 찾는 예시 [0, 2, 4, 6, 8, 12, 14, 16, 18] 시작점 0(index) 끝점 9 중간점 4 으로 설정하고, 중간점과 찾고자하는 원소값이 작다면 오른쪽 범위는 볼 필요가 없다. [0, 2, 4, 6] 이렇게 탐색범위는 총 4개 줄어드는데, 시작점은 0 중간점은 1 끝점은 3이 된다. 이렇게 해도 원하는 4를 못찾았는데 이번에는 중..

정렬 알고리즘 정렬(Sorting)이란 데이터를 특정한 기준에 따라 순서대로 나열하는 것을 말합니다. 일반적으로 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용된다. 아래 리스트를 어떻게 정렬할까 ? [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] 1. 선택 정렬(selection sort) - 처리되지 않은 데이터 중 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복 : [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] 가장 작은 0을 선택해 7와 바꾼다. : [0, 5, 9, 7, 3, 1, 6, 2, 4, 8] 다음 작은 1를 선택해 5와 바꾼다. : [0, 1, 9, 7, 3, 5, 6, 2, 4, 8] 다음 작은 2을 선택해 9와 바꾼다. : [0, 1, ..

그래프 탐색 알고리즘 : DFS / BFS 탐색(search)이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말합니다. 대표적인 그래프 탐색 알고리즘으로는 DFS와 BFS가 있습니다. DFS / BFS는 코딩 테스트에서 매우 자주 등장하는 유형이므로 반드시 숙지해야 합니다. DFS 와 BFS 알고리즘을 알아보기 전에 반드시 숙지해야할 두가지 자료구조와 재귀 함수가 있다. 1. 스택(stack) 자료구조 - 먼저 들어온 데이터가 나중에 나가는 형식(선입후출)의 자료구조입니다. - 간단하게 삽입(insert), 삭제(delete) 연산이 있는데 삽입하면 제일 끝에 쌓이고, 삭제하면 제일 뒤에 있는 데이터부터 삭제된다. python으로는 간단하게 리스트를 이용하면 된다. stack = [] stac..

그리디 알고리즘 (Greedy Algorithm) - 그리디 알고리즘(탐욕법)은 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미 - 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디얼르 떠올릴 수 있는 능력을 요구 - 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는 검토하여 문제를 풀어야 한다 (모든 경우 지금 당장 좋은 것만 고르는 방법이 최고의 방법이 아니므로) 대표적으로 동전 거스름돈 문제가 있다. 500원 / 100원 / 50원 / 10원 짜리 동전이 무한히 존재하는데 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러줘야 할 동전의 최소 개수를 구하라. 단, 돈 N은 항상 10의 배수이다. N이 1,280원이라면? 500 - 2 100 - 2 50 - ..

그래프(graph)는 여러 노드(node or vertex)들이 간선(edge)으로 연결된 추상 네트워크를 말한다. 즉, 그래프는 노드+간선의 집합으로 정의된다. 수식 - G=(V,E) V: vertex의 유한 집합, E: 간선 집합 그래프 방향 그래프는 방향이 있는 그래프(directed)와 방향이 없는 그래프(undirected)가 있다. 방향이 있는 그래프는 간선에 방향이 지정되어 있지 않아, 서로 인접(adjacent)해 있으며, 이웃(neighbor)이라고 한다. 부분 그래프 부분 그래프(subgraph)는 그래프 G에서 V와 E로 주성된 그래프의 일부이다. 완전 그래프 완전 그래프(complete graph)는 그래프의 모든 노드가 서로 인접한 그래프를 말한다. 차수 차수(degree)는 한 ..

객체지향설계, 파이썬 고급주제는 향 후 시간이 남을때 한번 정리하기로 하고, 이제 알고리즘 세상 속으로 들어가보자. 추상 데이터 타입(abstract data type)은 유사한 동작을 가진 자료구조의 클래스에 대한 수학적 모델을 가르키며, 각기 크래스는 다르지만, 기능적으로 동일하게 구현된 자료구조를 가질 수 있다. 먼저 알고리즘을 이해하기전 자료구조에 대해 알아보자. 자료구조는 크게 배열 기반 연속방식과 포인터 기반의 연결 방식으로 분류한다. 스택(stack) 큐(queue) 데크(deque) 우선순위 큐(priority queue) 힙(heap) 연결 리스트(linked list) 해시 테이블(hash table) 스택(stack) - 배열의 끝에서만 데이터를 접근할 수 있는 선형 자료구조형식이며,..

- 모듈 파이썬에서 모듈(module)은 def를 사용하여 정의한다. def가 실행되면, 객체와 참조가 같이 생성되는데, 반환값을 정의하지 않으면 None을 반환한다. 이처럼 반환하지 않는 함수는 프로시저(procedure)라고 부른다. - 스택과 활성화 레코드 함수가 호출될 때마다 활성화 레코드(activation record)가 생성되는데, 활성화 레코드에는 함수의 정보(반환값, 매개변수, 지역변수, 반환값, 반환 주소 등)가 기록되며 이 정보는 스택(stack)에 저장에 저장한다. - 모듈의 기본값 모듈을 생성할 때, 함수 또는 메소드에서 가변 객체를 기본값으로 사용해선 안된다. bad ex) def bad_append(number, number_list=[]): number_list.append(..

스퀀스(sequence) 자료구조는 데이터를 슬라이싱이 하거나 정렬했는데, 컬렉션(collection) 자료구조는 데이터를 서로 연관시키지(relating) 않고 모아두는 컨테이너(container)다. 속성 : 멤버십 연산자(in), 크기 함수(len(seq)), 반복성 위 세가지 속성을 지니고 있으며, 파이썬 내장 컬렉션 데이터 타입에는 Set, Dictionary가 있다. - 셋(Set) : 반복 가능하고, 가변적이며, 중복 요소가 없고, 정렬되지 않은 컬렉션 데이터 타입이다. 일반적으로 멤버십 테스트나 중복 항목 제거에 사용된다. dir(set()) 을 통해 속성을 확인할 수 있다. Set 메소드 A.add(x) - set A에 x가 없는 경우 x 추가 company = {'네이버', '카카오',..

알고리즘 문제를 풀 때 자주 사용되는 내장시퀀스데이터타입에 대해서 알아보자. python의 시퀀스(sequence) 데이터 타입은 다음과 같은 속성을 가진다. - 맴버십(membership)연산 : in 키워드 이용 - 크기(size) 메소드 : len(seq) - 슬라이싱(slicing) 속성 : seq[0:-1] - 반복성(iterability) : 반복문에 있는 데이터 순회 파이썬에는 문자열, 튜플, 리스트, 바이트 배열, 바이트 등 5개의 내장 시퀀스 타입이 있다. #list bin_list = [] print(type(bin_list)) # class 'list' #string bin_str = '' print(type(bin_str)) # class 'str' #tuple bin_tuple =..