자료구조&알고리즘/알고리즘 - 대회 알고리즘
-
백준 2545 팬케익 먹기 증명 (라그랑주 승수법)자료구조&알고리즘/알고리즘 - 대회 알고리즘 2024. 4. 4. 23:06
수학 무지렁이의 증명 노트 2024.04.14 1) 문제 백준 2545번 팬케익 먹기 문제 https://www.acmicpc.net/problem/2545 2545번: 팬케익 먹기 두 번째 테스트 케이스를 보자. 왜 정답이 64일까? 가장 먼저 4 * 5 변에 맞춰서 2번 팬케익을 자르면 남은 팬케익은 4*5*4가 된다. 그 다음에 4 * 4 변에 맞추어 팬케익을 자르면 4*4*4가 된다. 따라서 6 www.acmicpc.net 박스 모양의 팬케익의 가로 세로 높이가 각각 A cm, B cm, C cm 일 때 D번 자르고 남은 부피를 최대화 하는 방법 A, B, C 를 각각 어떻게 값을 줄여야 A*B*C 가 최대가 되는지 찾는 문제 요약하면, x+y+z = c 로 일정할 때 x*y*z 를 최대화하기 (..
-
[알고리즘 문제 풀이][그리디] 백준 3211번 - kino자료구조&알고리즘/알고리즘 - 대회 알고리즘 2024. 2. 1. 16:25
백준 3211 kino 문제의 풀이 방법을 정리한 내용입니다. - 문제 설명: https://www.acmicpc.net/problem/3211 3211번: kino In the first row there is an integer N, 2 ≤ N ≤ 10 000, number of friends. In the next N rows there is one integer per row Zi, 1 ≤ Zi < N. That numbers represent requests of all Mirko’s friends, that is, minimal number of people they are willing to www.acmicpc.net 미르코 (Mirko) 는 친구들을 영화관에 데려가려고 합니다. 각 친구들..
-
[알고리즘 문제 풀이][기하학] 백준 16483번 - 접시 안의 원자료구조&알고리즘/알고리즘 - 대회 알고리즘 2023. 2. 11. 19:16
백준 16483 접시 안의 원 문제를 푼 방법을 개인적으로 정리한 내용입니다. - 문제 설명: https://www.acmicpc.net/problem/16483 - 문제 풀이: 문제에 따라 안쪽에 있는 원의 접선을 그리면 아래와 같습니다. 그리고 문제에서 접선과 바깥 원이 만나서 생기는 두 점 사이 거리를 T 로 준다고 하였으니 T 도 함께 표현하면 아래와 같습니다. 원의 테두리는 반지름들이 모여 이루어진 것이기 때문에 접선이 지나는 점 또한 중심으로부터 거리가 반지름과 같을 수밖에 없습니다. 따라서 바깥 원의 반지름인 a 와 안쪽 원의 반지름인 b 를 표현하면 아래와 같습니다. 원의 중심으로부터 접선까지 선을 그으면 직교하기 때문에 피타고라스 정리에 따라 a^2 - b^2 = (T/2) ^ 2 이 됩..
-
[알고리즘 문제 풀이][기하학] 백준 14264번 - 정육각형과 삼각형자료구조&알고리즘/알고리즘 - 대회 알고리즘 2022. 8. 27. 17:18
백준 14264 정육각형과 삼각형 문제를 푼 방법을 개인적으로 정리한 내용입니다. (증명에 부족한 점이 있는데, 어떻게 보완할 수 있을지 확인하게 되면 추후 업데이트할 예정입니다.) - 문제 설명: https://www.acmicpc.net/problem/14264 - 문제 풀이: 정육각형은 겹치지 않는 3개의 선을 이용하여 4개의 삼각형으로 나눠야한다. 직접 그려보니 총 3가지 경우가 확인되었다. 가장 작은 삼각형의 크기는 항상 일정하였다. 따라서 저 삼각형의 크기 S 를 구하였다. 문제에서는 S의 넓이를 최대화하라는 것이었지만, 항상 일정하기 때문에 최대화는 의미가 없는 것 같다. 아래와 같이 삼각형을 잘라보면 각도의 관계를 알 수 있다. 이것만으로 바로 각도를 알아내지는 못하였고, 아래 (2) 의 ..
-
[알고리즘 문제 풀이][유니온파인드] 백준 20040번 - 사이클 게임자료구조&알고리즘/알고리즘 - 대회 알고리즘 2022. 7. 8. 21:07
백준 20040번 사이클 게임입니다. (Union Find 혹은 Disjoint Set) - 문제 설명: https://www.acmicpc.net/problem/20040 - 문제 풀이: 본 문제는 일반적으로 유니온 파인드를 이용하는 문제입니다. 각 정점마다 연결된 부모를 관리해주는데, 서로 다른 그룹에 속한 정점을 합치게 되면 (Union) 각 그룹의 최상위 부모를 찾아서 (Find) 두 부모 중 하나를 부모로 만들어줍니다. 유니온 파인드 개념에 대해 알지 못한다면 아래 개념을 참고하시거나, 간단한 유니온 파인드 기초문제부터 풀어보시는 것을 추천드립니다. * 유니온 파인드란? https://gmlwjd9405.github.io/2018/08/31/algorithm-union-find.html * 유니..
-
[알고리즘 문제 풀이][재귀] 백준 11729번 - 하노이 탑 이동 순서 / 1914 번 - 하노이 탑자료구조&알고리즘/알고리즘 - 대회 알고리즘 2022. 3. 1. 15:48
백준 11729번 하노이 탑 이동 순서 / 1914번 하노이 탑 문제입니다. (재귀) - 문제 설명: https://www.acmicpc.net/problem/11729 - 문제 풀이: 백준 단계별로 풀어보기의 '재귀' 연습 문제입니다. (https://www.acmicpc.net/step/19) 하노이 탑은 시작점에 있는 원판들을 도착점으로 옮기는 것인데, 직접 이동시켜보면 최소 이동 횟수가 2^n - 1 개가 나오는 것을 알 수 있습니다. 왜 그렇게 나오는지 재귀적으로 생각해보면 다음과 같습니다. 원판이 3개 있는 경우를 살펴보겠습니다. 그러면 맨 마지막 3번째 칸이 맨 끝 도착지점에 가기 위해서는 반드시 위의 2개의 원판이 가운데 지점에 놓여야합니다. 그래야 3번째 원판을 도착 지점에 먼저 깔고 작..
-
[알고리즘 문제 풀이][세그먼트트리] 백준 3392번 - 화성 지도자료구조&알고리즘/알고리즘 - 대회 알고리즘 2022. 2. 28. 17:40
백준 3392번 화성 지도 문제입니다. (세그먼트 트리 & 스위핑) - 문제 설명: https://www.acmicpc.net/problem/3392 - 문제 풀이: 본 문제는 다른 블로그들의 풀이를 참고하여 풀었기 때문에, 기존 풀이 방식과 동일합니다. 본 문제는 세그먼트 트리를 공부하기 위해 풀게 되었는데, 세그먼트 트리의 기초 개념만 알면 풀 수 있었던 문제들과 달리, 본 문제는 어느 부분에 세그먼트 트리를 적용해야할 지 어려운 문제였습니다. 일반적인 풀이는 들어온 입력들을 정렬을 하고, 쭉 스캔을 하면서 스캔한 범위에 사각형의 일부가 들어있으면 그걸 다 합하는 방식입니다. 이때 스캔한 범위에 사각형 선이 들어있는지 아닌지를 세그먼트 트리로 관리합니다. 들어온 입력을 보면 아래와 같습니다. 사각형 ..
-
[알고리즘 문제 풀이][DP] Leetcode 264번 - Ugly Number II자료구조&알고리즘/알고리즘 - 대회 알고리즘 2022. 2. 19. 19:46
릿코드 264번 Ugly Number 2 문제입니다. (DP) - 문제 설명: https://leetcode.com/problems/ugly-number-ii/ - 문제 풀이: 본 문제는 대부분의 풀이가 DP 로 나오지만, Heap 자료구조를 이용해서도 풀 수 있습니다. (1) Heap 을 이용한 풀이 min Heap 을 이용하면 현재 숫자 중에 가장 작은 숫자를 매번 꺼낼 때마다 알 수 있기 때문에, 여기에 *2, *3, *5 한 값을 다시 Heap 자료구조 안에 넣어서 꺼내주면 됩니다. (2) DP 풀이 DP 풀이를 보기 위해 문제의 예제를 보면 아래와 같습니다. 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 처음에는 1로 시작합니다. 그 다음에 1에서 2 곱한 값은 2, 3 곱한 값은 3,..