공부(Archive)/BOJ
-
BOJ 20530: 양분공부(Archive)/BOJ 2021. 1. 7. 15:54
www.acmicpc.net/problem/20530 20530번: 양분 첫째 줄에 두 자연수 $N$, $Q$가 주어진다. 주어지는 그래프의 정점과 간선의 개수가 $N$개이며 쿼리가 $Q$개 주어진다는 것을 의미한다. 둘째 줄부터 $N$개의 줄에는 $i$번 간선이 연결하는 두 정점 www.acmicpc.net 풀이 자체는 굉장히 쉽게 떠올렸는데 구현하는데 제법 애를 먹어 글로 남겨놓는다. 문제를 간단하게 요약하자면 $N$개의 정점으로 이루어진 트리에 간선이 하나 추가된 그래프가 주어지고, $q$개의 쿼리가 주어진다. 쿼리는 $u,\ v$의 형태로 주어지며 두 정점 사이의 단순 경로의 개수를 구하는 문제이다. 가장 간단한 접근 방법은 주어진 두 정점 $u,\ v$가 주어질 때마다 탐색을 하여 경로의 개수를..
-
BOJ 1168: 요세푸스 문제 2공부(Archive)/BOJ 2020. 12. 20. 19:45
www.acmicpc.net/problem/1168 1168번: 요세푸스 문제 2 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 100,000) www.acmicpc.net $N$, $K$가 주어졌을 때 요세푸스 순열을 순서대로 출력하는 문제이다. 순열을 간단히 요약하자면 $K$칸씩 건너뛰면서 해당 위치에 있는 번호를 제거하는 순열이다. 단 중간에 빠진 사람을 카운트해서는 안된다. 즉 어떤 구간의 합이 $K$인지를 파악하고 딱 그만큼이 되는 부분으로 이동할 수 있게끔 만드는 것이 핵심이라 생각했기 때문에 segment tree를 이용하여 $K$ 번째 수를 구하는 문제와 유사하다고 생각하여 접근하였다. Seg tree를 이용하여 $K$ 번째 수를 구하는 것은 이분 탐..
-
BOJ 3025: 돌 던지기 (미해결)공부(Archive)/BOJ 2020. 5. 13. 14:50
https://www.acmicpc.net/problem/3025 3025번: 돌 던지기 문제 이 모든 사건의 시작은 2주 전이었다. 그 날 상근이는 복도에 누워서 잠을 자고 있었다. 커다란 돌을 들고 그 옆을 지나가던 민혁이는 복도에서 잠을 자는 사람을 처음봐서 신기하게 쳐다보 www.acmicpc.net 최근 구현능력이 많이 떨어지는 것을 느껴 시뮬레이션/구현 문제를 풀던 중 재밌는 문제를 찾았다. 간단하게 요약하자면 위에서 돌을 떨어뜨렸을 때 돌을 적절히 굴려주고 최종 결과를 출력해주는 문제이다. 사실 처음 어떻게 접근할까 고민하던중 최근 set을 이용하여 해결했던 문제가 있어 set을 이용하여 아래와 같은 방법으로 구현하였다. 각 set에는 가장 처음 벽의 위치를 저장한다. 벽의 위치를 저장후 맨..
-
BOJ 1509: 팰린드롬 분할공부(Archive)/BOJ 2020. 5. 6. 20:54
https://www.acmicpc.net/problem/1509 1509번: 팰린드롬 분할 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하는 프로그램을 작성하시오. www.acmicpc.net 문제를 간단히 요약하자면 주어진 문자열을 부분 문자열들로 나누는데 모든 부분 문자열이 팰린드롬이어야 한다. 이때 부분 문자열의 최소 개수를 구하는 문제이다. 가장 처음 시도한 방법은 모든 구간 $[l, r]$에 대하여 팰린드롬인가를 확인할 수 있는 배열 $chk[l][r]$을 만들었다. 이후 행렬 곱셈 순..
-
BOJ 3079: 입국심사공부(Archive)/BOJ 2020. 5. 6. 16:50
https://www.acmicpc.net/problem/3079 3079번: 입국심사 문제 상근이와 친구들은 오스트레일리아로 여행을 떠났다. 상근이와 친구들은 총 M명이고, 지금 공항에서 한 줄로 서서 입국심사를 기다리고 있다. 입국심사대는 총 N개가 있다. 각 입국심사관이 심사를 하는데 걸리는 시간은 사람마다 모두 다르다. k번 심사대에 앉아있는 심사관이 한 명을 심사를 하는데 드는 시간은 Tk이다. 가장 처음에 모든 심사대는 비어있고, 심사를 할 준비를 모두 끝냈다. 상근이와 친구들은 비행기 하나를 전세내고 놀러갔기 때문에, 지금 심사 www.acmicpc.net 최근 실패했던 문제들을 다시금 도전해보고 있던 도중 "이 문제가 왜 실패한 문제에 있지?"싶었던 문제가 하나 있었다. 문제의 대략적인 풀..
-
BOJ 10775: 공항공부(Archive)/BOJ 2020. 5. 6. 15:15
https://www.acmicpc.net/problem/10775 10775번: 공항 문제 오늘은 신승원의 생일이다. 박승원은 생일을 맞아 신승원에게 인천국제공항을 선물로 줬다. 공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다. 공항에는 P개의 비행기가 순서대로 도착할 예정이며, 당신은 i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다. 비행기가 도킹된 게이트에는 다른 비행기가 도착할 수 없다. 이러한 사고가 일어나면 공항이 폐쇄되고, 이후 어떤 비행기도 도착할 www.acmicpc.net 요즘 공부를 너무 게을리했기에 간만에 감을 찾고자 BOJ를 켰다. 딱히 눈에 띄는 문제가 없어 단계별로 풀어보기나 차례대로 풀고자 하여 찾..
-
BOJ 2613: 숫자구슬공부(Archive)/BOJ 2020. 2. 20. 15:32
https://www.acmicpc.net/problem/2613 2613번: 숫자구슬 첫째 줄에 구슬의 개수 N과 그룹의 수 M이 주어진다. 둘째 줄에는 각 구슬이 적혀진 숫자가 왼쪽부터 차례로 주어진다. N은 300 이하의 자연수, M은 N이하의 자연수이며, 구슬에 적혀진 숫자는 100 이하의 자연수이다. www.acmicpc.net 처음 문제를 보고 이분 탐색을 이용한다면 문제를 쉽게 해결할 수 있으리라 생각하고 구현한 후 제출하였다. 그 방법은 먼저 최댓값의 최솟값을 결정한 후, 해당 값을 이용하여 배열을 돌며 구간의 합이 해당 값보다 작게 그룹을 만들어서 그 그룹의 수와 주어진 m을 비교하는 방법을 이용하였다. 오랜만에 문제를 풀어서 그런지 테스트 케이스 이외의 다른 케이스들을 고려하지 않고 그..
-
BOJ 11439: 이항 계수 5공부(Archive)/BOJ 2019. 7. 10. 18:54
올해들어 알고리즘 공부를 뜸하게 하다가 최근 일주일에 몇 문제씩은 풀게되었다. 이항 계수 4 문제까지는 구글링을 통해 다양한 공식과 정리들을 알게되어 쉽게 해결하였지만 최근 도전했던 이항 계수 5는 도저히 어떠한 공식도 정리도 찾을수가 없었다. 내가 이 문제를 풀기 위해 어떤 방식으로 접근했는지와 결국 풀이를 떠올리고 풀어낸 방법을 소개하고자 한다. 1. 먼저 N제한이 400만이기 때문에 DP를 사용하기에는 너무나도 큰 메모리 공간이 필요하기 때문에, 아마 메모리 공간이 부족하지 않더라도 너무나도 긴 시간이 걸릴 것이기 때문에 불가능하다고 생각했다. 2. 이항 계수 4를 풀기 위해 사용했던 Lucas Theorem을 사용해보고자 했지만 나누는 수가 소수인 경우에만 사용할 수 있으므로 포기했다. 3. 그렇..