분류 전체보기
-
[알고리즘 문제 풀이][완전탐색] 백준 12784번 - 인하니카 공화국자료구조&알고리즘/알고리즘 - 대회 알고리즘 2022. 2. 13. 16:17
백준 12784번 인하니카 공화국 문제입니다. (완전탐색 - DFS) - 문제 설명: https://www.acmicpc.net/problem/12784 - 문제 풀이: 본 문제는 맨 끝 부분 노드 (리프 노드)와 가장 상위에 존재하는 1번 노드 (루트 노드) 사이의 연결을 끊는 문제입니다. 가장 최소로 다이너마이트 개수를 사용하고 싶다고 했으므로, 자식부터 부모로 올라가면서 자신의 아래 자식 사이 길을 끊는 게 이득인지 자신과 부모 사이 길을 끊는게 이득인지 판단하면 됩니다. 이 문제는 어떤 노드가 자식 노드인지 예제에서 주어지지 않아서 BFS를 하기 위해서는 한 번 for 문을 돌면서 찾아야한다는 귀찮음이 있어 대부분 DFS 로 구현한 코드가 많습니다. - 코드: (1) DFS 코드 (출처) http..
-
[알고리즘 문제 풀이][기하학] 백준 1002번 - 터렛자료구조&알고리즘/알고리즘 - 대회 알고리즘 2022. 2. 12. 20:05
백준 1002번 터렛 문제입니다. (기하학 - 원의 교점의 개수) - 문제 설명: https://www.acmicpc.net/problem/1002 - 문제 풀이: 본 문제는 현재 위치, 적까지의 거리가 주어집니다. 그런데 한 명의 정보가 아니라 2명의 정보가 주어집니다. 문제를 풀기 위해서는 두 명의 정보가 동시에 가리키는 위치를 찾아야합니다. 하나의 거리가 r1 으로 주어졌을 때 가능한 좌표는 r1 만큼 떨어진 모든 곳이므로 원을 하나 그리게 됩니다. 또 다른 한명이 가리키는 거리가 r2 로 주어지면 가능한 좌표는 r2 만큼 떨어진 원형이 됩니다. 두 명이 동시에 가리키는 좌표는 겹치는 한 곳일 수도 있고, 원 두 개가 겹치는 경우를 생각하면 2 곳일 수도 있습니다. 원의 교점의 개수를 구하기 위해 ..
-
[알고리즘 문제 풀이][슬라이딩윈도우] 백준 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..
-
[알고리즘 문제 풀이][DP] 백준 2225번 - 합분해카테고리 없음 2022. 1. 20. 21:58
백준 2225번 합분해 문제입니다. (DP) - 문제 설명: https://www.acmicpc.net/problem/2225 - 문제 풀이: 본 문제는 최종 합을 만들기 위해 분해하는 문제이므로, DP 점화식이 필요합니다. DP 점화식을 도출하는 것이 어려운데, 잘 설명한 글이 있어 참고하였습니다. (https://mygumi.tistory.com/135 또는 https://hongjw1938.tistory.com/63) K 개의 숫자를 이용하여 N 이라는 숫자를 만드는 경우의 수 (DP[K][N]) 를 구하는 문제입니다. N 을 만들기 위해서는 1개의 숫자 A 가 합해졌다면, 나머지 K-1개의 숫자로는 (총 K개의 숫자를 사용해야하므로) N-A 값을 만들어야합니다. 위의 점화식을 구체적으로 보기에 앞..
-
[알고리즘 문제 풀이][조합] 백준 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..