자료구조&알고리즘
-
백준 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 를 최대화하기 (..
-
Python 출력시 앞에 0 채우는 방법자료구조&알고리즘/알고리즘 - 언어 기초 2024. 2. 2. 16:28
문제를 풀 때마다 매번 까먹고 다시 찾아보는 정해진 자릿수만큼 출력하는 방법 ex) 0003 과 같이 항상 4자리로 출력하고 싶을 때 앞에 0 을 채우는 방법 숫자를 출력하는 경우가 가장 많은데, 숫자는 아래 방법으로 사용하면 된다. 1. 숫자 앞에 0 붙이는 방법 print(f"{1:04d}") >>> 0001 python 3.6 이상 사용 가능한 f-string 방식으로 이와 같이 간단하게 쓸 수 있다. f"{출력할숫자:0전체자릿수d}" 순서대로이다. 혹은 이전 버전이라면 아래의 방식을 사용해도 된다. 출력할 숫자가 number 의 자리에 들어가고, '0전체자릿수' 혹은 '{0:0전체자릿수d}' 형식이다. number = 1 a = format(number, '02') b = '{0:04d}'.for..
-
[알고리즘 문제 풀이][그리디] 백준 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 - 문제 풀이: 본 문제는 다른 블로그들의 풀이를 참고하여 풀었기 때문에, 기존 풀이 방식과 동일합니다. 본 문제는 세그먼트 트리를 공부하기 위해 풀게 되었는데, 세그먼트 트리의 기초 개념만 알면 풀 수 있었던 문제들과 달리, 본 문제는 어느 부분에 세그먼트 트리를 적용해야할 지 어려운 문제였습니다. 일반적인 풀이는 들어온 입력들을 정렬을 하고, 쭉 스캔을 하면서 스캔한 범위에 사각형의 일부가 들어있으면 그걸 다 합하는 방식입니다. 이때 스캔한 범위에 사각형 선이 들어있는지 아닌지를 세그먼트 트리로 관리합니다. 들어온 입력을 보면 아래와 같습니다. 사각형 ..