류나의 작은 DB

27살 류나의 바르고 다르게 살기

Programming 11

우선순위 큐, 힙과 이진 탐색 트리

이번 글에서는 우선순위 큐에 대해 알아봅니다. 이를 구현할 수 있는 두 가지 방법인 힙과 이진 탐색 트리에 대해서도 살펴봅니다. 목차 1. 우선순위 큐, 힙과 이진 탐색 트리 - 우선순위 큐란 - 힙이란 - 이진 탐색 트리란 2. 우선순위 큐의 구현 - 우선순위 큐의 두 가지 구현 - STL의 priority_queue와 multiset 3. 문제풀이: 힙과 이진 탐색 트리 - BOJ 11279번: 최대 힙 (실버 II) - BOJ 1927번: 최소 힙 (실버 II) - BOJ 11286번: 절대값 힙 (실버 I) - BOJ 5639번: 이진 검색 트리 (골드 V) 4. 문제풀이: 우선순위 큐 - BOJ 7662번: 이중 우선순위 큐 (골드 IV) - BOJ 2075번: N번째 큰 수 (실버 I) - B..

BOJ 1654번: 랜선 자르기 문제로 알아보는 "최적화 문제 결정 문제로 바꿔 풀기"

지난 주 코로나19에 걸려 격리를 하면서 매일 근근이 solved.ac [CLASS 2] 문제만 풀고 있었는데, 순서대로 풀다가 맞닥뜨린 "랜선 자르기" 문제에 의외의 중요한 알고리즘 설계 패러다임이 담겨 있다고 생각해 글을 작성하기로 했습니다. 목차 1. 문제 훑어보기 2. 최적화 문제와 결정 문제 3. 이분 탐색과 매개 변수 탐색 4. BOJ 1654번: 랜선 자르기 (실버 III) 참고한 자료 알고리즘 문제 해결 전략, 구종만 https://book.algospot.com/ 알고리즘 문제 해결 전략 프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략, 구종만 지음, 인사이트, ISBN 978-89-6626-054-6 새 소식 책 소개 은 새로운 알고리즘 책입니다. 종이에 적힌 의사코드 book.al..

트리의 개념과 이진 트리의 순회

이번 글에서는 트리 자료구조의 개념과, 가장 간단한 트리의 일종인 이진 트리의 순회에 대해 알아봅니다. 목차 1. 트리의 구현과 순회 - 트리란 - 트리의 표현 - 트리의 순회 2. 이진 트리 - 이진 트리의 개념 - 이진 트리의 순회 3. 문제풀이: 트리 기본 - BOJ 1068번: 트리 (골드 V) - BOJ 15681번: 트리와 쿼리 (골드 V) - BOJ 11725번: 트리의 부모 찾기 (실버 II) - BOJ 15900번: 나무 탈출 (실버 I) 4. 문제풀이: 이진 트리의 순회 - BOJ 1991번: 트리 순회 (실버 I) - BOJ 9934번: 완전 이진 트리 (실버 I) - BOJ 4256번: 트리 (골드 III) - BOJ 2263번: 트리의 순회 (골드 II) 5. 문제풀이: 간선의 가..

배열, 연결 리스트, 스택과 큐 기본 문제

이번 글에서는 지금까지 공부한 자료구조들(배열, 연결 리스트, 스택, 큐)을 활용하는 기본 문제를 풀어봅니다. 목차 1. 동적 배열과 연결 리스트 - 동적 배열: C++ STL의 vector - 연결 리스트: C++ STL의 list - vector vs. list - 문제풀이 2. 스택과 큐, 데크 - C++ STL의 stack, queue - C++ STL의 deque - 문제풀이 참고한 자료 알고리즘 문제 해결 전략, 구종만 https://book.algospot.com/ 알고리즘 문제 해결 전략 프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략, 구종만 지음, 인사이트, ISBN 978-89-6626-054-6 새 소식 책 소개 은 새로운 알고리즘 책입니다. 종이에 적힌 의사코드 book.alg..

연결 리스트의 개념과 클래스 구현

이번 글에서는 연결 리스트(linked list)의 C++ 클래스 구현에 대해 알아보겠습니다. 목차 1. 단순 연결 리스트와 체인 - 개념 - 노드와 체인의 설계 - 템플릿 클래스 체인의 설계와 구현 2. 원형 리스트 - 개념 - 구현 3. 이중 연결 리스트 - 개념 - 구현 참고한 자료 C++ 자료구조론, Horowitz 외 http://www.yes24.com/Product/Goods/2656393 C++ 자료구조론 (2판) - YES24 C++ 언어의 최신 기능을 포함하도록 개정되었다. 예외와 템플릿과 같은 기능들은 제한적이긴 하지만 STL에 사용함으로써 내용전반에 걸쳐 포함되어 있다. 본서는 안전 해싱 알고리즘, 가중치 편 www.yes24.com 단순 연결 리스트와 체인 개념 배열이나 스택, 큐..

큐 자료구조의 개요와 구현

이번 글에서는 큐가 어떤 자료구조인지 알아보고, C++로 구현해 봅니다. 목차 1. 큐란 2. 큐의 기본 연산 구현 3. 데크의 구현 작성하면서 참고한 자료 C++ 자료구조론, Horowitz 외 http://www.yes24.com/Product/Goods/2656393 C++ 자료구조론 (2판) - YES24 C++ 언어의 최신 기능을 포함하도록 개정되었다. 예외와 템플릿과 같은 기능들은 제한적이긴 하지만 STL에 사용함으로써 내용전반에 걸쳐 포함되어 있다. 본서는 안전 해싱 알고리즘, 가중치 편 www.yes24.com 큐란 큐(queue)는 리어(rear)라고 하는 한쪽 끝에서 삽입이 일어나고 프런트(front)라고 하는 반대쪽 끝에서 삭제가 일어나는 순서 리스트입니다. 제일 먼저 삽입되는 원소가..

스택 자료구조의 개요와 구현

이번 글에서는 스택이 어떤 자료구조인지 알아보고, C++로 구현해 봅니다. 목차 1. 스택이란 2. 스택의 기본 연산 구현 3. 스택의 추가 연산 구현 작성하면서 참고한 자료 C++ 자료구조론, Horowitz 외 http://www.yes24.com/Product/Goods/2656393 C++ 자료구조론 (2판) - YES24 C++ 언어의 최신 기능을 포함하도록 개정되었다. 예외와 템플릿과 같은 기능들은 제한적이긴 하지만 STL에 사용함으로써 내용전반에 걸쳐 포함되어 있다. 본서는 안전 해싱 알고리즘, 가중치 편 www.yes24.com 스택이란 스택(stack)은 톱(top)이라고 하는 한쪽 끝에서 모든 삽입(push)과 삭제(pop)가 일어나는 순서 리스트입니다. 제일 마지막으로 삽입된 원소가 ..

[LeetCode] 1. Two Sum (Python)

LeetCode를 문제 번호 순서대로 풀지는 않지만, 1번 문제는 나름의 상징성이 있다고 생각해서 풀이를 남겨봅니다. leetcode.com/problems/two-sum/ Two Sum - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 풀이 1. Brute Force from typing import List def twoSum(nums: List[int], target: int) -> List[int]: for i in range(len(nums)): for..

포덕의 파이썬: 1-2. 문자열 다루기

프로그래밍을 하다 보면 어쩌면 숫자보다도 더 다뤄야 할 일이 많고 더 복잡한 것이 문자열일 겁니다. 이번 시간에는 파이썬에서 문자열을 다루는 방법에 대해 살펴볼 것입니다. 문자열 만들기 큰따옴표 또는 작은따옴표를 사용해서 문자열(string)을 만들 수 있습니다. >>> "Pokemon" 'Pokemon' >>> 'Pokemon' 'Pokemon' 보다시피 파이썬에서는 큰따옴표와 작은따옴표를 똑같이 처리합니다. 큰따옴표와 작은따옴표 두 가지로 문자열을 만들 수 있는 이유는 따옴표가 포함된 문자열을 만들 필요가 있기 때문입니다. 다음과 같은 경우들 때문이죠. >>> "Ryuna's Database" "Ryuna's Database" >>> 'Ryuna "Database"' 'Ryuna "Database"'..

포덕의 파이썬: 1-1. 숫자 사용하기

프로그래밍 언어를 처음 배울 때는 숫자를 사용하는 법, 그리고 사칙연산부터 다루곤 합니다. 그래서 파이썬에 대해 가장 먼저 다룰 주제는 숫자입니다. 파이썬의 숫자 살펴보기 파이썬에서 사용할 수 있는 숫자에는 크게 두 가지가 있습니다. 정수(Integer) – int 실수(부동소수점수, Floating-point number) – float 정수는 말 그대로 자연수와 음의 정수, 0을 포함하는 개념이고, 실수는 소수점이 포함된 숫자를 이야기합니다. 수학적으로는 정수도 실수의 일부이지만, 컴퓨터에서는 정수와 실수를 구분해 두는 경우가 많고 파이썬도 그러합니다. 파이썬을 계산기로 사용해 볼까요? >>> 5 + 3 8 >>> 6 - 2 4 >>> 7 * 4 28 간단한 덧셈, 뺄셈, 곱셈의 예시입니다. >>> ..