자료구조&알고리즘
-
[알고리즘 문제 풀이][슬라이딩윈도우] 백준 16440번 - 제이크와 케이크자료구조&알고리즘/알고리즘 - 대회 알고리즘 2022. 1. 28. 14:28
백준 16440번 제이크와 케이크 문제입니다. (슬라이딩 윈도우) - 문제 설명: https://www.acmicpc.net/problem/16440 - 문제 풀이: 본 문제는 Necklace splitting problem 이라고 치면 나오는 위상 수학의 유명한 문제와 같습니다. 두 도둑이 하나의 목걸이를 반으로 나눠 가지려고 하는데 목걸이에 있는 보석들을 종류마다 똑같은 개수로 나눠갖도록 하는 것입니다. 그때 자르는 횟수를 최소한으로 해야합니다. 이 문제는 위상 수학의 보르수크-울람 정리 (Borsuk-Ulam theorem) 으로 증명이 되었는데, 위상 수학에 대해 이해할 수 있다면 아래 동영상으로 증명 과정을 따라가 볼 수 있습니다. https://www.youtube.com/watch?v=yuV..
-
[알고리즘 문제 풀이][조합] 백준 17205번 - 진우의 비밀번호자료구조&알고리즘/알고리즘 - 대회 알고리즘 2022. 1. 19. 00:10
백준 17205번 진우의 비밀번호 문제입니다. (조합론) - 문제 설명: https://www.acmicpc.net/problem/17205 - 문제 풀이: 가능한 비밀번호가 최대 3자리라면 a, aa, aaa, aab, aac, ..., azy, azz, b, ba 이런 식으로 나타나게 됩니다. 그러면 매 자리마다 가능한 경우의 수를 합해주면 됩니다. a b ... z ===> 여기가 총 26개 a a a b a c a ... a z ====> 여기는 a~z * a~z 를 생각하면 총 26 * 26개 a a a a a b a a c a a ... a a z ======> 여기는 a~z * a~z * a~z 를 생각하면 총 26 * 26 * 26개가 됩니다. 그렇다면 만일 최대 길이가 3이고, 문제에서 ..
-
[알고리즘 문제 풀이][슬라이딩 윈도우] 백준 15961번 - 회전 초밥자료구조&알고리즘/알고리즘 - 대회 알고리즘 2022. 1. 5. 00:02
백준 15961번 회전 초밥 문제입니다. (투 포인터 & 슬라이딩 윈도우) - 문제 설명: https://www.acmicpc.net/problem/15961 - 문제 풀이: 회전 초밥 접시들을 연속해서 k 개씩 먹고, c 라는 초밥을 하나 먹을 수 있는 쿠폰이 있을 때, 최대의 가짓수를 찾아야합니다. 최대의 가짓수를 위해서는 일반적으로 k 개 먹은 초밥 중에 같은 번호의 초밥이 하나도 없어야합니다. 또한 c 쿠폰을 사용할 수 있도록 c 라는 번호의 초밥도 없어야합니다. sliding window 라는 방법으로, k 개 범위를 한칸씩 이동하면서 해당 범위 안에 초밥 가짓수가 줄어들었는지, 증가했는지를 체크합니다. - 코드: N, d, k, c = map(int, input().split()) dish =..
-
[알고리즘 연습] 2021년도 11월 첫째주 학습 (D번 문제 풀이)자료구조&알고리즘 2021. 12. 6. 23:26
AtCoder Beginner Contest 227 (D번 문제): 이분탐색 Codeforces Round #753 (Div.3) (D번 문제): 그리디 대회를 진행할 때 D번 문제에서 대부분 막혀서, 풀지 못한 D번 문제들을 기록해두고자 한다. 1. AtCoder Beginner Contest 227 (D번 문제) 문제 https://atcoder.jp/contests/abc227/tasks/abc227_d N 개의 부서에 Ai명의 직원들이 있는데, K 개의 다른 부서에서 K 명을 뽑아오려고 한다. 이렇게 뽑았을 때 만들 수 있는 project의 최대 개수를 구해야한다. 입력 3 3 2 3 4 정답 2 풀이 https://atcoder.jp/contests/abc227/editorial/2919 이분 ..
-
[알고리즘 연습] 2021년도 10월 넷째주 학습 (D번 문제 풀이)자료구조&알고리즘 2021. 12. 6. 23:08
AtCoder Beginner Contest 223 (D번 문제): topological sort 응용 AtCoder Beginner Contest 223 (F번 문제): segment tree 응용 AtCoder 를 풀다가 공부해두고 싶은 문제가 생겨서 정리해두었다. 1. AtCoder Beginner Contest 223 (D번 문제) https://atcoder.jp/contests/abc223/tasks/abc223_d 풀이 Indegree 를 활용하는 일반적인 topological sort 코드에 heap push, heap pop 을 추가하기만 하면 된다! 코드 출처: https://atcoder.jp/contests/abc223/submissions/26656807 from heapq imp..
-
[알고리즘 문제 풀이][탐욕] 백준 2109번 - 순회강연자료구조&알고리즘/알고리즘 - 대회 알고리즘 2021. 12. 6. 22:54
백준 2109번 순회강연 문제입니다. (탐욕 알고리즘 or 우선순위 큐) - 문제 설명: https://www.acmicpc.net/problem/2109 - 문제 풀이: 본 문제는 탐욕 알고리즘 혹은 우선순위 큐로 풀이 가능합니다. (시간이 2초이고, 입력 크기가 10,000 이므로 N^2 알고리즘 가능) 탐욕 알고리즘을 쓰는 경우에는 pay 가 큰 값부터 작은 값으로 정렬해주고 (d일 이내에 와야한다는 조건 때문에 오름차순이 아닌 내림차순으로 풀이하게 됩니다), pay 가 큰 값부터 우선적으로 day 에 지정해줍니다. 그런데, day 값을 그 기간 안에 오기만 하면 되는 것이기 때문에 1일차부터 주어진 day 까지 다 확인하면서 지정해줍니다. (자세한 설명: https://steady-coding.t..
-
-