전체 글
-
백준 20500 (Ezreal 여눈부터 가네 ㅈㅈ)전공/알고리즘 2021. 11. 16. 13:19
https://www.acmicpc.net/problem/20500 20500번: Ezreal 여눈부터 가네 ㅈㅈ 문제의 답을 $1\,000\,000\,007$로 나눈 나머지를 출력한다. www.acmicpc.net 1과 5로만 이루어진 수 중에서 15로 나누어 떨어지는 수가 몇 개있는지 세보자 1자리 1 5 X 2자리 15 O 55 11 51 1가지 이렇게 하다가 알 수 있는 간단한 사실 15 = 3*5 따라서 15의 배수이려면 k*(3*5) 이어야 하고, 5로 나누어 떨어져야 15로 나누어 떨어진다. 그러므로 1의 자리 수가 1이라면 불가능 끝에는 5만 올 수 있다. 여기서부터 조금 막혔다. 근데 10^N은 15로 나누었을때 나머지가 10이며 5*10^N은 15로 나누었을때 나머지가 5였다. 9876..
-
백준 233328 (마을 구하기)전공/알고리즘 2021. 11. 7. 17:29
https://www.acmicpc.net/problem/23328 23328번: 마을 구하기 미소가 사는 마을에는 $N$채의 집이 일렬로 있다. 어느 날 밤, 마을 내 모두가 잠든 사이에 집마다 폭탄 혹은 폭탄 쉴드가 배치되었다. 폭탄과 폭탄 쉴드는 다음과 같은 특징이 있다. 폭탄은 알파 www.acmicpc.net 폭탄을 뭉쳐놓아야 우리가 원하는 문제를 해결 가능 왜냐면 폭탄을 쉴드나 벽으로 감싸서 최대한 마을과 인접한 폭탄이 없도록 만들기 위함이다. 문자열로 받고 폭탄을 방어할 쉴드가 몇개인지 세준다. 2개 이상 1개 0개 간단한 0개부터 가장 좌측 or 가장 우측에 모아두면 0개에서 1개의 마을이 폭파된다. 0개인경우는 마을이 없는 경우 BBBB... -> 1 ....BBBB -> 2 1번은 B보..
-
백준 23327 (리그전 오브 레전드)전공/알고리즘 2021. 11. 4. 00:22
https://www.acmicpc.net/problem/23327 23327번: 리그전 오브 레전드 첫 번째 줄에 참가를 원하는 팀의 수 $N$($2 \le N \le 100 \, 000$), 후보 디비전의 개수 $Q$($1 \le Q \le 200 \, 000$)가 주어진다. 두 번째 줄에 정수 $a_1, a_2, \dots, a_N$이 주어진다. $a_i$는 $i$번째로 잘하는 www.acmicpc.net 어떤 쿼리가 주어질때 그게 만약 연속된 어떤 것을 구하는 거라면 그게 누적합으로 접근 할 수 있겠구나를 느꼈다. 머 사실 N, Q = 10^5이고, 1초인데 O(N*Q)는 불가능하니 O(Q)일텐데 먼가 전처리가 필요하겠구나 싶은 문제이다. 그래서 전처리를 해보자 전처리를 하기 전에 뚝딱 하다보면 ..
-
백준 23324 (어려운 모든 정점 쌍 최단거리)전공/알고리즘 2021. 11. 4. 00:09
https://www.acmicpc.net/problem/23324 23324번: 어려운 모든 정점 쌍 최단 거리 첫 번째 줄에 정점의 개수 $N$($2 \le N \le 100\,000$), 간선의 개수 $M$($1 \le M \le 200\,000$), 정수 $K$($1 \le K \le M$)가 주어진다. 다음 $M$개의 줄에 걸쳐 $u_i$와 $v_i$가 주어진다. 이것은 $i$번째 간선은 $u_i$ www.acmicpc.net 매우 흥미로운 문제였다. 플로이드 와샬이라는 알고리즘을 지문에 제시해두고 그거 안되니깐 다른거로 풀어봐라 이런 것도 좋았고, 가중치 있는 간선이 딱 하나인 것도 좋았다. 물론 여러개의 간선에 가중치가 존재하게 된다면 문제는 완전 다른 문제가 되겠지만 관찰 문제이다. 만약 ..
-
백준 2357(최솟값과 최댓값)전공/알고리즘 2021. 9. 3. 13:51
https://www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 전형적인 세그먼트 트리 개념 문제 웃기게도 알고리즘 시작할 때 공부한 개념이었는데 묻어뒀다가 까먹어서 다시 공부 세그는 최대 N*4의 배열 크기가 필요 N개의 원소들이 주어지면 바텀업이 훨씬 편하다. 요정도? 그리고 최댓값 구할 때나 최솟값 구할 때 빈 공간 잘 찾아주기 그니깐 0으로 초기화 된 공간이 0이어도 괜찮은지 만약 최솟값을 찾는 거라면 0이 무조건 ..
-
SUAPC 2021 Summer 후기대회/기타 2021. 8. 29. 21:51
이번 후기도 그냥 내 시점에서 진행 hwon233, dicohy27과 생수라는 팀으로 대회에 참가하였다. 편의상 효원이랑 재현이로 적겠다. 왜 그런지 몰라도 이번 대회는 잘 보고 싶어서 그런지 정말 오랜만에 긴장을 많이 하고 시작했다. A 처음에 v가 1분에 옮기는 박스 수가 아니라 작업속도로 이해해서 다시 읽고나서야 제대로 이해했다. N이 10^5니깐 모든 케이스 분류로 정렬해서 확인하는 것이 가능하다. 그리고 코포하면서 배운 반올림 방법인데 (K+v-1)/v 하면 된다. A 제출하기 전에 말하고 제출하는데 팀원들이 A 안 풀렸다고 해서 긴장하면서 제출 다행히 정답 퍼솔은 처음이라 아드레날린이 최대치로 나왔던 것 같다. F 다음으로 가장 많이 풀린 문제인 F를 봤는데 긴장이 너무 돼서 문제가 안 읽히길..
-
#737 div2 8/9대회/코드포스 2021. 8. 10. 14:36
https://codeforces.com/contest/1557 Dashboard - Codeforces Round #737 (Div. 2) - Codeforces codeforces.com A 가장 큰 거 따로, 나머지 묶어서 계산 cout.fixed() cout.precision()만 구글링로 찾음 B pair에 값이랑 index 저장해서 정렬, 바로 옆에 있어야 하는 거면 앞에 꺼 인덱스가 뒤에 꺼보다 1작아야함 아니면 cnt++ 계속 변수값 변경해주면서 cnt가 k보다 작거나 같으면 가능 아니면 불가능 C 각 비트별로 따로봐도 된다. 최상위 비트부터 우선순위 적용 근데 어쩌다 보니 &연산이 아닌 not XOR 연산으로 계산해서 계속해서 이상한 사고로 흘러갔다. 4개일때 짝 홀 아무거나 짝 짝 홀 ..
-
#736 div2 8/2 virtual대회/코드포스 2021. 8. 3. 20:20
https://codeforces.com/contest/1549 Dashboard - Codeforces Round #736 (Div. 2) - Codeforces codeforces.com A P mod a = P mod b 인 a,b 구하기 P-1, (P-1)/2 이면 둘다 1로 가능 예시보고 빨리 찾은듯 B 체스 규칙 그대로 폰이 마지막행으로 최대 몇개까지 갈 수 있는지인데 1이 나고 0이 상대인줄 알고 헤맸었다. 그냥 마지막 행에 좌측부터 채워넣으면 된다. 구현문제 C 왜 C번 부터 트리가 나오고 라고 생각하고 딴짓을 했다. 그래도 팀연습을 계속 하면서 집중력이 많이 올라왔고, 다시 생각은 문제로 돌아갈 수 있었다. 동시에 vulnerable 한 귀족들이 제거된다고 해서 뭔가 이거는 하나하나 할 ..