DATA101

문제 문제 원본: https://www.acmicpc.net/problem/12845 12845번: 모두의 마블 영관이는 게임을 좋아한다. 별의별 게임을 다 하지만 그 중에서 제일 좋아하는 게임은 모두의 마블이다. 어김없이 오늘도 영관이는 학교 가는 버스에서 캐릭터 합성 이벤트를 참여했다. 이번 이 www.acmicpc.net 접근법 가장 높은 골드를 획득하는 방법, 간단합니다. 레벨이 가장 높은 카드 1장을 고정하고 나머지 카드와 차례로 덧셈하면 됩니다. 어차피 모든 카드의 레벨과 합산해야 하며, 두 카드의 덧셈이(=획득 골드량) 최대가 되기 위해서는 최상위 레벨의 카드 1장을 고정시키면 되는 것이죠. 소스코드 # 카드 개수 입력받기 n = int(input()) # 카드별 레벨 입력받기 level_l..

문제 문제 원본: https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 접근법 본 문제를 한 줄로 요약하자면, N가지 종류의 동전을 조합해 화폐 가치가 K원을 만들 때 필요한 동전의 최소 개수를 구하는 문제입니다. 본 문제는 그리디 알고리즘의 기초 예제인 거스름돈 문제와 변수 이름이나 표현방식이 다를 뿐 풀이 방법은 매우 흡사합니다. 그래서 저는 다음과 같이 일부 변수명을 거스름돈 문제..

본 포스팅에서는 완전 이진 트리(Complete Binary Tree) 자료구조에 대해 알아봅니다. * 완전 이진 트리(Complete Binary Tree) 자료구조란? 완전 이진 트리란 각 노드가 최대 2개의 자식 노드를 갖는 트리 형태의 자료구조로서 마지막 레벨을 제외한 모든 노드는 완전히 채워져 있어야 합니다. 또한, 최하단 레벨의 노드는 좌측만 노드가 채워져 있거나 좌측과 우측 모두 채워져 있어야 하며, 노드를 삽입할 때는 최하단 좌측 노드부터 차례대로 삽입해야 합니다(그림 1 참고). 그림 1 우측 트리는 노드 12의 자식 노드가 우측에만 삽입되어 있기 때문에 완전 이진트리라고 할 수 없습니다. 포스팅 내용에 오류가 있을 경우 댓글 남겨주시면 감사드리겠습니다. 그럼 오늘도 건강한 하루 보내시길..

본 포스팅에서는 파라메트릭 서치(parametric search)에 대해 알아봅니다. 📚 목차 1. 파라메트릭 서치란? 2. 파라메트릭 서치는 언제 사용하면 좋을까? 3. 파라메트릭 서치와 이진 탐색 간의 차이점 4. 파라메트릭 서치의 동작 과정 4.1. 파라메트릭 서치 예시 4.2. 파라메트릭 서치의 시간 복잡도 1. 파라메트릭 서치란? 파라메트릭 서치는 최적화 문제를 결정 문제로 바꾸어 풀어 나가는 기법입니다. 여기서 결정 문제란 'yes' or 'no', 즉, '예' 또는 '아니오'로 답하는 문제를 말합니다. 파라메트릭 서치는 주로 특정 조건을 만족하면서 동시에 가장 적합한 변숫값을 찾아나가는 문제에서 활용되며, 이진 탐색(Binary Search)을 이용하여 구현합니다. 예를 들어, 특정 조건을 ..

안녕하세요, 오늘은 그래프(graph) 자료구조와 트리(tree) 자료구조의 차이에 대해 알아봅니다. 그래프 자료구조에 대한 자세한 설명은 아래 링크를 참고해 주세요! heytech.tistory.com/66 [자료구조] 그래프 자료구조에 대해 알아보자!(노드, 간선) 안녕하세요, 오늘은 그래프(graph) 자료구조에 대해 알아보겠습니다. 그래프 자료구조의 구성 그래프는 그림 1 과 같이 노드(Node)와 간선(Edge)으로 표현됩니다. 이때 노드는 정점(Vertext)이라고도 heytech.tistory.com 내용이 간단하므로 아래 표 1 과 같이 정리해 볼 수 있을 것 같습니다. 그래프 자료구조 트리 자료구조 방향성(directionality) 무-/방향 그래프 only 방향 그래프 순환성(circ..

본 포스팅에서는 최단경로(길 찾기)알고리즘 중에서도 플로이드-워셜 알고리즘에 대해 알아봅니다. 📚 목차 1. 최단경로(길 찾기) 알고리즘이란? 2. 플로이드-워셜 알고리즘 개념 3. 플로이드-워셜 알고리즘 특징 4. 플로이드 워셜 알고리즘의 동작 과정 5. 플로이드 워셜 알고리즘 구현(Python) 1. 최단경로(길찾기) 알고리즘이란? 최단경로 알고리즘은 길찾기 알고리즘이라고도 불리며, 말 그대로 특정 지점까지 가장 빠르게 도달할 수 있는 경로를 찾는 알고리즘입니다. 이번 포스팅에서는 알고리즘 테스트에서 빈출 최단경로 알고리즘 유형 2가지 중 2번째, 플로이드-워셜 알고리즘에 대해 알아봅니다. 다익스트라 최단경로 알고리즘(Dijkstra Algorithm) 플로이드-워셜 알고리즘(Floyd-Warshal..

📚 목차 1. 최단경로(길찾기) 알고리즘이란? 2. 다익스트라 최단경로 알고리즘이란? 3. 다익스트라 최단경로 알고리즘의 동작 과정 4. 구현 방법1: 일반적인 구현 4.1. 코드 해설 4.2. 전체 코드 4.3. 시간 복잡도 5. 구현 방법2: 시간 복잡도 개선 5.1. 우선순위 큐(Priority Queue) 자료구조 5.2. 힙(Heap) 자료구조 5.3. 우선순위 큐 자료구조 기반의 알고리즘 동작 과정 5.4. 우선순위 큐 자료구조 기반 알고리즘 구현(Python) 1. 최단경로(길찾기) 알고리즘이란? 최단경로 알고리즘은 길찾기 알고리즘이라고도 불리며, 말 그대로 특정 지점까지 가장 빠르게 도달할 수 있는 경로를 찾는 알고리즘입니다. 알고리즘 테스트에서 빈출 최단경로 알고리즘 유형은 아래와 같습니..

📚 목차 1. 힙 자료구조 2. 힙 자료구조는 언제 사용할까? 3. 힙 자료구조의 종류 4. 힙 자료구조의 동작 과정(최소 힙) 4.1. 데이터 삽입 4.2. 데이터 삭제 5. 힙 자료구조 구현(Python) 5.1. heapq 셋업 5.2. 힙 데이터 삽입(heappush) 5.3. 힙 데이터 삭제(heappop) 5.4. 리스트를 힙으로 변경(heapify) 1. 힙 자료구조 힙 자료구조는 가장 높은(혹은 가장 낮은) 우선순위(e.g., 최댓값, 최솟값)를 가지는 노드를 빠르게 찾아내기 위해 고안된 *완전 이진트리(Complete Binary Tree) 기반의 자료구조입니다. 따라서 가장 높은(또는 가장 낮은) 우선순위를 가지는 노드가 항상 루트 노드(root node)에 오는 게 특징입니다. * 완..