본문 바로가기

전체 글

 (57)
그리디 알고리즘 1.그리디 알고리즘이란? 그리디 알고리즘(탐욕법)은 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구 그리디 해법은 그 정당성 분석이 중요 => 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토 해야함. 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많음. 하지만 코딩 테스트에서의 대부분의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론할 수 있어야 풀리도록 출제됩니다. 2. 그리디 알고리즘 문제예시 *거스름돈 : 해결 아이디어 최적의 해를 빠르게 구하기 위해서는 가장 큰 화폐 단위부터 돈을 거스러 주면 됨 N원을 거슬러 줘..
DFS와 BFS 1. DFS(Depth-First Search)의 개념 DFS는 깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 DFS는 스택 자료구조(혹은 재귀 함수)를 이용하며, 구체적인 동작 과정은 다음과 같음 탐색 시작 노드를 스택에 삽입하고 방문 처리함 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리함. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복. 2. DFS 동작 예시 [Step 1] 그래프를 준비 (시작노드 : 1) [Step 2] 시작 노드인 '1'을 스택에 삽입하고 방문 처리 [Step 3] 스택의 최상단 노드인 '1'에 방문하지 않은 인접 노드 ..
동적 프로그래밍(Dynamic Programming) - DP 1. 동적 계획법 (Dynamic Programming)이란? 큰 문제를 작은 문제로 나누어 푸는 문제를 일컫는 말 하나의 문제는 단 한번만 풀도록 하는 알고리즘 2. 분할 정복과 차이점 * 분할 정복 - 큰 문제를 해결하기 어려워 단지 작은 문제로 나누어 푸는 방법 - 작은 문제에서 반복이 일어나는 부분이 없음 * 동적 프로그래밍 - 작은 부분 문제들이 반복되는것을 이용해 풀어나감 3. Dynamic Programming 방법 - 모든 작은 문제들을 한번만 풀어야 한다. - 푼 작은 문제의 정답을 어딘가에 메모해 놓음 - 다시 그보다 큰 문제를 풀어나갈 때 똑같은 작은 문제가 나타나면 앞서 메모한 작은 문제의 결과값을 이용 * 조건 작은 문제가 반복이 일어나는 경우 같은 문제는 구할 때마다 정답이 같음..
9. 우선 순위 큐 (Heap) 1. 우선 순위 큐 (Priority queue) 가장 우선 순위가 높은 원소가 가장 먼저 제거되는 큐 ex) 병원 응급실 * 우선 순위 큐의 연산 - 추가 (Push) 큐에 새로운 원소를 삽입함 새로운 원소의 위치는 그 중요도(priority)에 따라서 결정됨 - 제거 (Pop) 큐에서 가장 우선 순위가 높은 원소를 삭제함 - 탑 (Top) 큐에서 가장 우선 순위가 높은 원소를 찾음(삭제하지는 않음) * 정렬된 리스트를 이용한 우선 순위 큐의 구현의 성능 추가 (Push) : O(n) 제거 (Pop) : O(n) 탑 (Top) : O(1) * 추가와 제거의 성능을 향상시킬 수 있는 방법은? 이진 트리를 이용!! (heap) 2. 정의 * Heap 이진 트리를 기반으로 구현된 우선 순위 큐 완전 이진 트..
8. 이진 탐색 트리 (binary search tree) 1. 이진 탐색 (binary search) 복습 - 배열의 중앙값을 찾아서 배열을 반으로 분할하는 과정을 재귀적으로 반복하면서 key 값을 검색 *이진 트리와의 유사성 배열이 2개의 부분 배열로 재귀적으로 분할 분할 구조 - 배열 : (왼쪽 부분 배열) + 중앙 + (오른쪽 부분 배열) - 이진 트리 : (왼쪽 부분 트리) + 부모 노드 + (오른쪽 부분 트리) 재귀적인 구조 - 각 부분 배열이 또 분할됨 , 각 부분 트리가 또 분할됨 2. 이진 탐색 트리 정의 * 이진 탐색 과정에서 분할되는 배열을 이진 트리에 대응시킨 구조 이진 트리 모든 노드는 서로 다른 하나의 값(key)을 저장 왼쪽 부분 트리의 모든 값들은 루트 노드의 값보다 더 작음 오른쪽 부분 트리의 모든 값들은 루트 노드의 값보다 더 큼..
7. 트리(tree) 1. 개요 *배열 , 연결 리스트 , 스택, 큐의 공통점? 리스트형 자료구조 선형 자료구조 모든 원소는 인덱스에 대응 2개 이상의 관계를 표현하는데 한계 존재 - ex) 족보 , 파일 구조 , 의사 결정 => 계층 구조 * 계층 구조의 공통점? 하나의 근원(root)으로부터 파생됨 한 노드가 여러 개의 노드로 전파됨 순환하는 경로가 없음 2. 트리의 정의 루트(root)라는 특별한 노드가 하나 있음 모든 노드는 부모 자식 관계라는 1:1관계에 재귀적으로 연결되어 있음 3. 용어 Root node : 트리의 최상위 노드 , 부모 노드가 없는 노드 Leaf node : 자식 노드가 없는 노드 Internal node : Leaf node가 아닌 모든 노드 Parent node : 연결된 한 쌍의 노드들 중에..
6. 정렬 (sorting) 1. 정렬의 소개 *리스트 연산 리스트에 원소를 추가 또는 제거하고 원하는 원소를 검색 제약점 -> 정렬된 리스트만을 요구함 정렬되지 않은 리스트라면? -> 정렬 * 정렬 (sorting) 데이터를 정해진 키에 따라서 크기 순으로 배열하는 것 오름차순 (ascending order) 내림차순 (descending order) *정렬 알고리즘의 성능 정렬할 데이터의 개수 : n O(f(n))으로 표시 O(n^2)정렬 알고리즘 - 버블정렬, 삽입 정렬, 선택 정렬, .... O(nlogn) 정렬 알고리즘 - 합병 정렬, 쾌속 정렬, .... 2. O(n^2) 정렬 - 정렬 알고리즘의 성능은 정렬하고자 하는 원소의 수 (n)의 제곱인 (n^2)에 비례함. 이동에 기반한 정렬 : 삽입 정렬 교환에 기반한 정렬 ..
4. 연결 리스트 (linked list) 1. 연결리스트 개념 원소들이 메모리에서 임의의 위치에 배치되어 있음 한 원소는 다음 원소를 가리키는 link를 가지고 있음 (포인터 기반) 2. 배열과 연결 리스트 비교 배열 : 원소들이 메모리에서 일정한 간격으로 나열되어 있음 연결 리스트 : 원소들이 메모리에 임의의 위치에 배치되어 있음 배열 연결 리스트 메모리 공간 연속된 메모리 주소 이산된 메모리 주소 공간 할당 정적 할당 / 동적 할당 동적 할당 접근 경로 첫 번째 원소의 주소 첫 번째 원소의 주소 접근 방법 인덱스 포인터 접근 방식 Random access Sequential access 3. 연결 리스트 정의 node = data + link node는 메모리의 임의의 위치에 배치됨 각 node는 다음 node를 가리키는 link를 포함하고..

티스토리툴바