동적계획법 (Dynamic Programming) 처음에 나온 해답을 통해서 그다음 문제의 해답을 구한다. 간단히 말해 '점화식'을 이용하여 문제를 풀어나감 메모이제이션을 하는 것 => 리스트에 저장 메모이제이션 X => 그저 재귀함수 예제 문제를 풀면서 감을 익혀나가는 것이 가장 중요. 예제문제 1. 네트워크 선 자르기 - 1m 선을 자를 때 경우의 수: 1가지 - 2m 선을 자를 때 경우의 수: 2가지 1 + 1 2 - 3m 선을 자를 때 경우의 수: 2 + 1 = 3가지 1) 마지막 선의 길이를 1m로 한다고 하자, 남은 선의 길이는 2m이다. 2m 선을 자르는 경우의 수는 2가지 2) 마지막 선의 길이를 2m로 한다고 하자, 남은 선의 길이는 1m이다. 1m 선을 자르는 경우의 수는 1가지 - 4..

자료구조는 우선순위(priority_queue)를 구현하기 위해 사용하는 자료구조 중 하나다. 우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제한다는 점이 특징인데, 표로 나타내면 다음과 같다. 자료구조추출되는 데이터 스택(stack) 가장 나중에 삽입된 데이터 큐(queue) 가장 먼저 삽입된 데이터 우선순위 큐(priority_queue) 가장 우선순위가 높은 데이터 우선순위 큐를 구현할 때는 내부적으로 최소 힙(min_heap) 혹은 최대 힙(max_heap)을 이용한다. 최소 힙을 이용할때는 값이 가장 낮은 데이터가 먼저 삭제되며, 최대 힙은 값이 큰 데이터가 가장 먼저 삭제됨을 알아두자. 파이썬에서 우선순위 큐 라이브러리를 사용할때는 default값이 최소 최소 힙(min_heap)으..

트리 (Tree) 트리(Tree)는 계층적 데이터를 저장하고 활용하기 위한 자료구조이다. 트리의 특징 트리는 비선형적(none-linear) 구조의 자료구조다. 트리는 연결리스트와 동일하게 노드(Node)를 가지고있다. 각 노드는 엣지(Edge)로 연결되어있다. 각 노드는 부모(Parent) / 자식(Child) 관계를 가진다. 트리 자료구조의 구성 요소: 루트(root)노드: 가장 꼭대기에 있는 도드 잎새(leaf)노드: 트리의 마지막 노드, 즉 자식이 없는 노드 높이(height = Level): 높이는 잎새(leaf) 노트부터의 경로 길이 깊이(depth): 깊이는 루트에서 노드로의 경로 길이 이진 트리(Binary Tree) 그 중, 자식 노드가 최대 2개까지만 붙는 트리를 이진트리(Binary ..

Linked List 연결리스트 배열은 순차적으로 연결된 공간에 연속적으로 데이터를 저장 연결리스트는 떨어진 공간에서도 사용할 수 있다 파이썬에서는 리스트가 연결리스트를 모두 지원 예시 파이썬의 기본 자료구조인 리스트(list) 용어 노드(Node): 데이터의 저장 단위. 데이터와 포인터로 구성 포인터(Pointer): 각 노드 안에서 다음 노드의 주소 정보를 가지고 있는 공간 head: 연결리스트의 맨 앞 노드 tail: 연결리스트의 맨 마지막 노드 장단점 장점 동적으로 메모리 사용 데이터의 재구성 용이 단점 특정 인덱스의 데이터에 접근하기 어려움 즉, 중간 노드의 탐색이 어려움 연결을 위한 포인터와 같은 별도의 공간이 필요함으로 저장 공간 효율이 좋지 않음 배열은 인덱스를 통해 데이터에 접근하므로 시..

이번 포스트에서는 스택, 큐, 재귀함수에 대해 살펴볼 예정이다. 스택 자료구조 먼저 들어온 데이터가 나중에 나가는 형식(선입후출)의 자료구조이다. 입구와 출구가 동일한 형태로 스택을 시각화할 수 있다. ex) 박스 쌓기, 프링글스 통 구조 (LIFO) 마지막에 있는 데이터가 먼저 처리된다. 스택구조를 이용하는 것은 단순한 리스트 삽입구조를 이용하면된다. (시간 복잡도 O(1), 상수시간) stack = [] stack.append(n) stack.pop(n) print(stack[::-1]) #최상단 원소부터 출력 print(stack) #최하단 원소부터 출력 이미지 출처: awesomeo184.log 큐 자료구조 먼저 들어온 데이터가 먼저 나가는 형식(선입선출)의 자료구조이다. 큐는 입구와 출구가 모두..

정렬이란? 섞여 있는 데이터를 순서대로 나열하는 것 정렬 알고리즘은 시간 복잡도에 따라 성능을 좌우되며 성능이 좋을수록 구현 방법이 어려워진다. 대표적인 정렬의 종류 O(n²)의 시간 복잡도 (정렬할 자료의 수가 늘어나면 제곱에 비례해서 증가) 버블 정렬(Bubble Sort) 선택 정렬(Selection Sort) 삽입 정렬(Insertion Sort) O(n log n)의 시간 복잡도 병합 정렬(Merge Sort) 퀵 정렬(Quick Sort) 1. 거품 정렬 (Bubble Sort) 정렬 중에서도 가장 직관적인 정렬 방식이다. 거품 정렬은 인접한 두 수를 비교하고, 가장 큰 값을 뒤로 보낸다. 알고리즘 동작이 각 순회의 가장 큰 요소가 맨 뒤로 이동(Bubble Up) 하는 방식이기 때문에 지어진..

문제 해결이란? 초기 상태에서 목표상태에 도달하는 과정이다. 8-Puzzle 타일을 1부터 8까지 순서대로 배치하는 게임 • 상태(state): Location of tiles: 8개의 타일의 각각의 위치와 빈칸의 위치 • 동작(action): Move blank Left, Right, up, down: 빈칸으로 왼쪽, 오른쪽, 위, 아래 이동 • 목표 도달 확인(goal test): 주어진 목표상태에 도달하였는지 확인 • 경로 비용(path cost): 한번 action할 때마다 1씩 증가 (경로의 수) 상태공간 그래프 인공지능에서는 최적의 해를 찾기 위해, 각 동작에 따른 상태 변화를 그래프로 나타내어 해결한다. 이러한 문제 해결과정에 있어서 우리는 다음과 같은 탐색 방법을 찾아볼 수 있다. 그래프 ..

해시법 해시법(hashing) '데이터를 저장할 위치 = 인덱스'를 간단한 연산으로 구하는 것을 말한다. 이 방법은 원소의 검색뿐 아니라 추가 · 삭제도 효율적으로 수행할 수 있다. 배열의 키(원소의 값)를 원소 갯수인 7로 나눈 나머지를 해시값(hash value)라고 한다. 해시값은 데이터에 접근할 때 기준이 된다. 11을 7로 나눈 나머지는 4이므로 x[4]에 바로 저장한다. 이렇게 키를 해시값으로 변환하는 과정을 해시 함수(hash function)라고 한다. 또한 일반적으로 해시 함수는 나머지를 구하는 연산 또는 그 연산을 응용할 때 주로 사용한다. 해시 테이블에서 만들어진 원소를 버킷(bucket)이라고 한다. 해시 충돌 앞에서 만든 해시 테이블에 18을 추가하면 7로 나눈 나머지는 4이므로 ..

검색 알고리즘이란? 정렬은 흩어져있는 데이터를 키 값(주민등록번호, 학번 등)을 이용하여 순서대로 열거하는 알고리즘이다. 검색은 데이터(정렬이 안된 데이터 , 정렬이 된 데이터)에서 키 값에 해당되는 데이터를 찾는 알고리즘이다. 검색(Search) : n 개의 데이터를 검색한다. 가장 간단한 검색 알고리즘은 선형 검색(Sequential Search) 알고리즘이다. n개의 데이터를 놓고 한 개씩 검색하는 방법이다. 데이터가 정렬이 된 상태에서는 이진 검색(Binary Search) 방법이 더 효율적이다. 이진 검색은 전체 데이터의 중간에 있는 데이터를 비교하면서 찾는 데이터가 앞/뒤 중 어디 있는지 알 수 있다. 선형 검색 선형 검색 알고리즘은 직선 모양으로 늘어선 요소의 배열에서 앞부터 순차적으로 검색..

그래프 탐색 알고리즘 DFS & BFS 탐욕(Search)이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정이다. 대표적인 그래프 탐색 알고리즘으로는 DFS와 BFS가 있다. * 코딩테스트에서 자주 등장하는 유형 이번 포스트에서는 DFS, BFS에 대해 살펴볼 예정이다. DFS (Depth-First Search) DFS는 깊이 우선 탐색이라고도 부르며, 그래프의 깊은 부분을 우선적으로 탐색하는 알고리즘이다 DFS는 스택 자료구조(또는 재귀 함수)를 이용한다 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다 더 이상 2번의 과정을 ..

그리디 알고리즘이란 그리디 알고리즘(탐욕법)은 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미합니다. 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구합니다. 그리디 해법은 그 정당성 분석이 중요합니다. 단순히 가장 좋아보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토합니다. [문제 상황] 루트 노드부터 시작하여 거쳐 가는 노드 값의 합을 최대로 만들고 싶음 Q. 최적의 해는 무엇인가? 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많음 하지만 코딩 테스트에서 대부분의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서 이를 추론할 수 있어야 풀리도록 출제됨 탐욕 알고리즘 문제를 해결하는 방법 선택 절차(..