본문 바로가기

분류 전체보기

 (97)
[알고개념] 2. Lowest Common Ancestor LCA는 스터디 발표 자료로 블로그 글을 대신합니다.
[알고개념] 1. Segment Tree 1. 알고리즘 개념 세그먼트 트리: 각 노드가 구간 정보를 가지고 있는 트리를 의미한다. 루트 노드는 전체 구간을 가지고, 리프 노드는 길이가 1인 구간들을 가진다. 리프 노드를 제외한 다른 모든 노드는 항상 2개의 자식을 가진다. -> 완전 이진 트리 꼴 리프 노드가 $N$개인 완전 이진 트리의 전체 노드의 개수는 $2N-1$이고, 높이는 $\lceil log\ N \rceil$ 이다. $N$이 2의 제곱꼴이 아닐 경우에는 남는 구간을 기본값으로 채워서 사용한다. 2. 알고리즘 구현 start == end : 리프 노드는 구간 길이가 1이므로 바로 값을 대입한다. node의 왼쪽 자식은 node*2이고, 오른쪽 자식은 node*2+1이다. node에 저장된 구간이 [start,end]라면, 왼쪽 자식은..
[알고연] (2주차-3) 1285B. Just Eat It! 1285B. Just Eat It! Today, Yasser and Adel are at the shop buying cupcakes. There are nn cupcake types, arranged from 11 to nn on the shelf, and there are infinitely many of each type. The tastiness of a cupcake of type ii is an integer aiai. There are both tasty and nasty cupcakes, so the tastiness can be positive, zero or negative. Yasser, of course, wants to try them all, so he will buy exact..
[알고연] (2주차-2) 466C. Number of Ways 466C. Number of Ways You've got array a[1], a[2], ..., a[n], consisting of n integers. Count the number of ways to split all the elements of the array into three contiguous parts so that the sum of elements in each part is the same. More formally, you need to find the number of such pairs of indices i, j (2 ≤ i ≤ j ≤ n - 1), that (아래식 참고). 배열을 3등분하는 구간이 몇 개인지 찾는 문제인데, 누적합의 3의 배수로 파악해야 한다는 점에서 약간..
[알고연] (2주차-1) 1003C. Intense Heat 1003C. Intense Heat The heat during the last few days has been really intense. Scientists from all over the Berland study how the temperatures and weather change, and they claim that this summer is abnormally hot. But any scientific claim sounds a lot more reasonable if there are some numbers involved, so they have decided to actually calculate some value which would represent how high the tempe..
[PS] 백준 #2798. 블랙잭 문제 정보 난이도: 브론즈 II 문제 주소: https://www.acmicpc.net/problem/2798 이 문제를 푼 이유: 알고리즘 스터디 - 브루트포스와 그리디 문제 카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다. 한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다. 김정인 버전의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 외친다. 이제 플레이어는 제한된 시간 안에 N장의 카드 중에서 3장의 카드를 골라..
[모프] 1. Kotlin 개요 1. 데이터 타입 코틀린에서는 문장의 끝에 세미콜론 (;) 을 붙이지 않는다! 코틀린에서는 모든 것이 객체이다. 기본 타입: Byte, Short, Int, Long, Float, Double, Char, Boolean, Array, String Char: 자바와 다르게 숫자형이 아니여서 'a' 대신 65와 같이 사용이 불가능하다. 숫자 값을 저장할 때 underscores (_)를 사용하여 보기 편하게 나타낼 수 있다. ex) $1\_000\_000$ 작은 타입에서 큰 타입으로 대입이 안된다. 명시적 형변환이 필요하다! 산술 연산에서는 묵시적 형변환이 이루어진다. 문자열의 비교 시 "==" 으로 사용 가능하다. 2. 변수 및 상수 변수: var / 상수: val 로 정의해서 사용한다. var a: In..
[알고개념] 알고리즘 개념 목차 (이 게시판에는 2022년 3~4월간 알고리즘 초급, 중급 스터디에서 공부한 내용을 업로드할 예정입니다.) 초급 알고리즘 목차 Brute-Force Greedy DP (Dynamic Programming) Math Data Structure Back Tracking DFS & BFS 고급 알고리즘 목차 Segment Tree LCA (Lowest Common Ancester) SCC (Strongly Connected Component) kmp Lazy Propagation 2-SAT Network Flow - Dinic Algorithm Bipartite Matching

티스토리툴바