본문 바로가기

전체 글365

[12주차] 분할정복법과 탐욕적기법 4월 9일 자 학습 내용 정리입니다. ✅ 분할정복법 분할정복법은 아래와 같다. 문제를 소문제로 분할한다. 각각의 소문제를 해결한다. 소문제의 해결 결과를 이용해 전체 문제를 해결한다. 분할정복법의 대표적인 예로는 합병정렬과 이분탐색이 있다. ✔️ 합병정렬 합병정렬(Merge Sort)은 흔히 하향식 2-way 방법으로 쓰이는데 이는 다음과 같이 작동한다. 리스트의 길이가 1 이하이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는 아래 과정을 거친다. 분할(divide) : 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다. 정복(conquer) : 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다. 결합(combine) : 두 부분 리스트를 다시 하나의 정렬된 리스트로.. 2022. 4. 9.
[12주차] 재귀호출 4월 8일 자 학습 내용 정리입니다. ✅ 재귀호출 재귀호출(recursive call)은 함수가 자기 자신을 호출하는 것이다. 이러한 재귀 호출은 자기가 자신을 계속해서 호출하므로, 끝없이 반복되게 된다. 따라서 함수 내에 재귀 호출을 중단하도록 조건이 변경될 명령문을 반드시 포함해야 한다. 재귀호출의 예로는 팩토리얼이 있다. 팩토리얼(factorial)은 n이 하나의 자연수일 때, 1에서 n까지의 모든 자연수의 곱을 n에 상대하여 이르는 말이다. 이를 코드로 구현하면 다음과 같다. def Factorial(n): if n == 0: return 1 else: return n * Factorial(n-1) Factorial 함수의 구현에는 재귀호출이 포함되어있다. n = 5 일 때, Factorial 함.. 2022. 4. 9.
[12주차] 우선순위 큐와 힙 4월 6일 자 학습 내용 정리입니다. ✅ 우선순위 큐 우선순위 큐는 우선순위가 높은 원소가 먼저 출력되는 추상적 자료형이다. 우선순위 큐를 단순히 배열로 구현할 경우 입력은 O(1)이지만 출력은 O(n)이다. 우선순위가 가장 높은 원소를 찾는 과정과 그 원소를 제거하는 과정이 비효율적이라고 할 수 있다. ✅ 힙 힙(Heap)은 최솟값 또는 최댓값을 빠르게 찾기 위해 고안된 완전 이진 트리이다. 힙은 최대 힙과 최소 힙의 두 가지 종류로 나뉜다. 최대 힙(Max Heap)은 부모 노드가 항상 자식 노드보다 큰 값을 가지고 있다는 특징이 있다. 반대로 최소 힙(Min Heap)은 부모 노드가 항상 자식 노드보다 작은 값을 가지고 있다는 특징이 있다. 파이썬에서는 heapq 모듈로 최소 힙을 사용할 수 있다... 2022. 4. 7.
[12주차] 트리의 표현과 트리 순회 4월 6일 자 학습 내용 정리입니다. ✅ 트리의 표현 방법 이진 트리의 각 노드는 왼쪽 또는 오른쪽 자식을 갖고 있으므로 다음 코드와 같이 표현할 수 있다. class TreeNode : def __init__(self) : self.left = None self.right = None 완전 이진 트리는 배열을 이용해 간단하게 구현할 수 있다. 루트 노드부터 깊이를 더해가며 각 정점에 번호를 붙였을 때 어쩐 정점의 번호가 n이라면 왼쪽 자식은 2n, 오른쪽 자식은 2n+1의 인덱스를 가진다. 따라서 이를 배열로 표현하면 아래와 같다. ✅ 트리 순회 트리 순회란 트리의 모든 노드를 방문하는 순서이다. 트리는 비선형 구조로 자료 사이에 정해진 순서가 없기 때문에 각 노드를 방문하고 값을 가져오기 위해 트리 .. 2022. 4. 7.
[12주차] 트리의 개념 4월 6일 자 학습 내용 정리입니다. ✅ 비선형 구조 앞서 포스팅에서 스택과 큐를 배우며 선형 구조와 비선형 구조에 대해 언급했었다. 선형 구조는 자료들이 순서를 가지고 연속된 자료구조를 의미하며 비선형 구조는 자료를 일렬로 나열하기 힘들고 자료의 순서가 불규칙해 연결 관계가 복잡한 구조를 의미한다. 바로 이 비선형 구조의 대표적인 예가 트리(Tree)와 그래프(Graph)이다. ✅ 그래프 트리는 사실 그래프의 특수한 형태 중 하나이다. 따라서 트리를 이해하기 위해서는 그래프의 정의부터 알 필요가 있다. 그래프(Graph)는 정점(vertex)과 간선(edge)으로 이루어져 있는 자료구조이다. 정점(vertex)은 자료, 상태 등 값을 담고있는 것을 의미하며 노드라고 부르기도 한다. 간선(edge)은 정.. 2022. 4. 7.
[백준 10825번] 국영수 문제 링크 >> https://www.acmicpc.net/problem/10825 📋 문제 도현이네 반 학생 N명의 이름과 국어, 영어, 수학 점수가 주어진다. 이때, 다음과 같은 조건으로 학생의 성적을 정렬하는 프로그램을 작성하시오. 국어 점수가 감소하는 순서로 국어 점수가 같으면 영어 점수가 증가하는 순서로 국어 점수와 영어 점수가 같으면 수학 점수가 감소하는 순서로 모든 점수가 같으면 이름이 사전 순으로 증가하는 순서로 (단, 아스키 코드에서 대문자는 소문자보다 작으므로 사전순으로 앞에 온다.) 👉 입력 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보.. 2022. 4. 6.
[백준 10814번] 나이순 정렬 문제 링크 >> https://www.acmicpc.net/problem/10814 📋 문제 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오. 👉 입력 첫째 줄에 온라인 저지 회원의 수 N이 주어진다. (1 ≤ N ≤ 100,000) 둘째 줄부터 N개의 줄에는 각 회원의 나이와 이름이 공백으로 구분되어 주어진다. 나이는 1보다 크거나 같으며, 200보다 작거나 같은 정수이고, 이름은 알파벳 대소문자로 이루어져 있고, 길이가 100보다 작거나 같은 문자열이다. 입력은 가입한 순서로 주어진다. 👈출력 첫째 줄부터 총 N개의 줄에 걸쳐 온라인 저지 회원을 나이 순,.. 2022. 4. 6.
[백준 1343번] 폴리오미노 문제 링크 >> https://www.acmicpc.net/problem/1343 📋 문제 민식이는 AAAA와 BB의 폴리오미노 2개를 무한개만큼 가지고 있다. 이제 '.'와 'X'로 이루어진 보드판이 주어졌을 때, 민식이는 겹침없이 'X'를 모두 폴리오미노로 덮으려고 한다. 이때, '.'는 폴리오미노로 덮으면 안 된다. 폴리오미노로 모두 덮은 보드판을 출력하는 프로그램을 작성하시오. 👉 입력 첫째 줄에 보드판이 주어진다. 보드판의 크기는 최대 50이다. 👈출력 첫째 줄에 사전순으로 가장 앞서는 답을 출력한다. 만약 덮을 수 없으면 -1을 출력한다. 📝 풀이 board = input() arr = board.split('.') def poly(arr): string = "" for item in arr:.. 2022. 4. 5.
[백준 11508번] 2+1 세일 문제 링크 >> https://www.acmicpc.net/problem/11508 📋 문제 KSG 편의점에서는 과일우유, 드링킹요구르트 등의 유제품을 '2+1 세일'하는 행사를 하고 있습니다. KSG 편의점에서 유제품 3개를 한 번에 산다면 그중에서 가장 싼 것은 무료로 지불하고 나머지 두 개의 제품 가격만 지불하면 됩니다. 한 번에 3개의 유제품을 사지 않는다면 할인 없이 정가를 지불해야 합니다. 예를 들어, 7개의 유제품이 있어서 각 제품의 가격이 10, 9, 4, 2, 6, 4, 3이고 재현이가 (10, 3, 2), (4, 6, 4), (9)로 총 3번에 걸쳐서 물건을 산다면 첫 번째 꾸러미에서는 13원을, 두 번째 꾸러미에서는 10원을, 세 번째 꾸러미에서는 9원을 지불해야 합니다. 재현이는 K.. 2022. 4. 5.

티스토리툴바