반응형 알고리즘7 [백준 17613] 2019 정올 1차 고등부 "점프" 문제 출처 : https://www.acmicpc.net/problem/17613 17613번: 점프 T개의 줄에 각각 하나의 정수를 출력한다. 각 줄에 출력되는 정수는 구간 [x, y]안의 수들의 점프넘버들 중 최댓값이다. 각 정수는 입력으로 주어지는 구간의 순서에 맞게 출력되어야 한다. 즉, 첫 www.acmicpc.net 이 문제는 2019년 정보올림피아드 1차 고등부 2번 문제 입니다. 점프를 하면서 해당 위치에 갈 수 있는 가장 짧은 점프 횟수를 찾는 문제 입니다. 여기 까지는 쉽지만 범위 안에 있는 모든 짧은 점프 횟수를 찾아 그중 가장 큰 수를 출력해야 합니다. 문제 이해하기 예제 입력에 있는 3번째 경우를 보겠습니다. 12부터 16사이에 가장 큰 점프 횟수를 찾아야 합니다. 먼저 12에 도.. 2024. 2. 29. [백준 28323] 2023 정올 2차 초등부 "불안정한 수열" 문제 출처 : https://www.acmicpc.net/problem/28323 28323번: 불안정한 수열 $N$개의 자연수가 좌우 일렬로 놓여 있다. 왼쪽에서 $i$ ($1 \le i \le N$)번째에 놓여 있는 자연수는 $A_i$다. 여러분은 이 중 몇 개의 자연수를 원하는 만큼 고를 수 있다. 단, 아무 자연수도 고르지 않 www.acmicpc.net 이 문제는 2023년 정보올림피아드 초등부 2차 1번 문제 였습니다. 수열 A에서 이웃한 자연수의 합을 구했을 때 항상 홀수인 수열 B를 구하는 문제 입니다. 문제를 어떻게 풀어야 할지 감이 잘 잡히지 않는다면 조합을 구하고 그 중 답이 있는지 확인하면 됩니다. 그럼 100점은 맞지 못하더라도 부분 점수를 얻을 수 있습니다. 정보 올림피아드는 시.. 2024. 2. 19. [백준 1219] 오민식의 고민 문제 출처 : https://www.acmicpc.net/problem/1219 1219번: 오민식의 고민 첫째 줄에 도착 도시에 도착할 때, 가지고 있는 돈의 액수의 최댓값을 출력한다. 만약 오민식이 도착 도시에 도착하는 것이 불가능할 때는 "gg"를 출력한다. 그리고, 오민식이 도착 도시에 도착 www.acmicpc.net 관련 문제 확인 이 문제는 골목길 문제의 확장판이라고 할 수 있습니다. 골목길에 대한 해설은 아래 링크를 타고 들어가면 확인해 볼 수 있습니다. https://wikidocs.net/225235 03. 골목길[백준 1738] 문제 출처 : [골목길](https://www.acmicpc.net/problem/1738) 민승이가 지나가는 길에 깡패가 있거나 금품이 떨어져 있습니다. 깡.. 2024. 1. 1. 페르마의 소정리 다빈치코딩 알고리즘에 나머지 정리에 대해 설명하다 분배 법칙에 대해 글을 쓰다보니 나눗셈에 대해서는 왜 분배 법칙이 적용이 안되는지를 설명하게 되었습니다. 그러면서 페르마의 소정리를 이용하면 나눗셈도 나머지 연산을 할 수 있다고 하였는데 그것에 대해 설명하려 합니다. 다빈치코딩 알고리즘은 초등학교 고학년에서 중학교 저학년 친구들을 대상으로 하였기 때문에 페르마의 소정리를 다루는 것은 책이 아닌 블로그에 정리하는 것이 맞다고 느껴졌습니다. 페르마의 소정리(Fermat’s little theorem) 페르마의 소정리는 다음과 같이 정의 됩니다. “소수 p와 p의 배수가 아닌 정수 a가 있을 때 a^p를 p로 나눈 나머지와 a를 p로 나눈 나머지는 같다” 입니다. 수학적으로는 아래와 같이 표현 합니다. $$ .. 2023. 8. 28. [백준 7812] 중앙 트리(파이썬) 문제 출처 : https://www.acmicpc.net/problem/7812 7812번: 중앙 트리 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫 줄에는 트리의 정점의 수 n이 주어진다. (1 ≤ n ≤ 10,000) 각 정점은 0번부터 n-1번까지 번호가 붙여져 있다. 다음 n-1개 줄 www.acmicpc.net 트리 DP의 문제 입니다. 트리와 DP를 합친 문제로 복잡하게 느껴질 수 있지만 하나하나 해결해나가면 문제를 풀 수 있습니다. 이 문제를 풀기 위해서는 모든 정점들의 거리를 계산해야 합니다. 중앙 정점이 어디가 될지 모르기 때문입니다. 무작정 문제를 푼다면 다음과 같이 진행 하면 됩니다. 먼저 A를 중앙 정점으로하여 모든 정점까지의 거리를 구해줍니다. A-B =.. 2023. 8. 28. [백준 28326] 2023 정올 고기파티 문제 출처 : https://www.acmicpc.net/problem/28326 28326번: 고기 파티 오늘은 고기 파티가 열리는 날이다. 파티에 걸맞도록, 기다란 그릴 위에 잘 구워진 고기가 총 $N$개 놓여 있다. 그릴을 $10^9$ 의 길이를 가진 선분이라고 하고, 그릴의 왼쪽 끝을 좌표 $0$, 오른쪽 www.acmicpc.net 이 문제는 2023년도 정보 올림피아드 2차 초등부 4번, 중등부 3번 문제 입니다. 문제의 이해 먼저 문제를 이해하도록 해보겠습니다. 첫 번째 예제를 함께 보면서 무엇을 해야하는지 알아보겠습니다. 이와같이 그릴에 고기가 쌓여 있습니다. 여기서 왼쪽 오른쪽에 꼬치를 꽂고 가져갑니다. 가져간 고기들의 맛의 합을 구하는 문제 입니다. 이 때 꼬치 양쪽 모두에 꽂힌 고기만.. 2023. 8. 21. [백준 21762] 2021 정올 공통 부분 수열 확장 문제 출처 : https://www.acmicpc.net/problem/21762 21762번: 공통 부분 수열 확장 어떤 수열에서 0개 이상의 원소를 삭제해서 얻을 수 있는 수열을 그 수열의 부분수열이라 한다. 예를 들어, aab는 $X$ = ababca의 부분수열이지만, $Y$ = cbabba의 부분수열은 아니다. 두 개의 수열이 주 www.acmicpc.net 이 문제는 2021년 정보올림피아드 1차 고등부 문제 입니다. 두 개의 수열 X, Y의 부분수열 W를 확장 가능한지, 불가능한지 확인 하는 프로그램을 작성하는 것입니다. 예제 입력에 있는 X, Y, W를 살펴 보겠습니다. X = ababca Y = cbabba W = baa X, Y에 W는 공통부분수열이기 때문에 무조건 존재합니다. 이 부분수.. 2023. 8. 15. 이전 1 다음 반응형
