본문 바로가기

백준45

[JAVA] 백준 - 검문 2981 (정수론, 유클리드 호제법) https://www.acmicpc.net/problem/2981 2981번: 검문 트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간 www.acmicpc.net 이 문제는 정말 수학문제였습니다. 정답률이 21프로 밖에 안되는데 그 이유는 완전 탐색의 경우 시간초과가 나기 때문입니다. 최악의 경우를 생각해보자. 먼저 M의 범위를 알아야합니다. 결론부터 이야기하면 M은 1보다 큰수이며 주어진 N개의 수 중에서 가장 큰수보다 작은 수입니다. 예를 들어, 주어진 수가 2, 3, 8 ,15 라면 M 의 범위는 2~14 입니다. 왜냐하면 M이 가장 큰 수라고 가정 해보면 주어진 수.. 2022. 3. 29.
[JAVA] 백준 1379 와 세제곱 (백트래킹 , 정수론) https://www.acmicpc.net/problem/2731 2731번: 1379와 세제곱 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 둘째 줄 부터 T개 줄에는 테스트 케이스의 정보가 주어진다. 각 테스트 케이스는 숫자 하나로 이루어져 있고, 이 수는 문제에서 설명한 S이다. S는 www.acmicpc.net 문제 테스트 케이스 및 정답 http://acmgnyr.org/year2005/problems.shtml 2005 ACM Greater New York Regional Collegiate Programming Contest acmgnyr.org 세제곱 해서 1으로 끝나는 숫자는 어떻게 찾을 수 있을까요? 0부터 9까지 다 곱해보는 겁니다. 0*0*0 = 0 1*1*1 = 1 2*2*2 =.. 2022. 3. 19.
[JAVA] 백준 변형 계단수 18244 (다이나믹프로그래밍) https://www.acmicpc.net/problem/18244 18244번: 변형 계단 수 첫째 줄에 정답을 1,000,000,007으로 나눈 나머지를 출력한다. www.acmicpc.net "쉬운 계단수" 문제를 먼저 풀고 나면 좀 더 쉽게 접근 할 수 있습니다. 접근방법이 비슷하기 때문입니다. https://onejunu.tistory.com/143?category=882099 [JAVA] 백준 쉬운 계단 수 10844 (다이나믹 프로그래밍) https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 위 노트를 보면서 간단하게 설명해보겠습니다. 만약 길이가 a.. 2022. 3. 18.
[JAVA] 백준 쉬운 계단 수 10844 (다이나믹 프로그래밍) https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 위 노트를 보면서 간단하게 설명해보겠습니다. 만약 길이가 a 이고 마지막 숫자가 b 인 수가 있습니다. 다음숫자인 c는 어떤 숫자가 와야할까요? c 는 b가 9보다 작다면 b+1이 와야하고 b가 0보다 크다면 b-1이 올 수 있습니다. 예를 들어, b=8인경우를 생각해보겠습니다. 그러면 다음에 올 수 있는 숫자는 7과 9입니다. b=0인 경우를 생각하면 다음에 올 수 있는 숫자는 1 밖에 없습니다. b=9인 경우는 다음에 올 수 있는 숫자는 8 밖에 없습니다. 위 내용을 바탕으로 점화식을 세워 볼겁니다. 먼저 .. 2022. 3. 18.
[JAVA] XOR 연산자 ^ 에 대해 ( feat. 백준 - XOR (12844번)) XOR 연산이란? - XOR 연산이란 쉽게 말해 다르면 참을 반환한다. - 아래 예시를 보자. (1 = 참 , 0 = 거짓) 0 XOR 0 = 0 0 XOR 1 = 1 1 XOR 0 = 1 1 XOR 1 = 0 - 연산자로 표시하면 0^0 = 0 0^1 = 1 1^0 = 1 1^1 = 1 - 이진수의 하나의 비트가 아닌 여러비트로 예시를 들어보자. 십진수 13 과 십진수 8은 각각 이진수로 1101 과 1000 로 나타낼수 있다. 1 1 0 1 1 0 0 0 -------- 0 1 0 1 = 5 따라서 13 ^ 8 = 5 이다. XOR 연산 성질 ko.wikipedia.org/wiki/XOR_%EA%B5%90%EC%B2%B4_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98 XOR 교체 .. 2021. 3. 20.
[JAVA] 세그먼트 트리구현법과 lazy propagation (feat. 백준) www.acmicpc.net/blog/view/26 세그먼트 트리 나중에 업데이트 해야지! 배열 A가 있고, 여기서 다음과 같은 두 연산을 수행해야하는 문제가 있습니다. 10999번 문제: 구간 합 구하기 2 구간 l, r (l ≤ r)이 주어졌을 때, A[l] + A[l+1] + ... + A[r-1] + A[r]을 구해서 출력하기 i번째 www.acmicpc.net 여기서 공부한 내용을 바탕으로 간단하게 정리해보고자 한다. 세그먼트 트리를 공부하면서 분할정복에 대한 감을 좀더 잘 잡을 수 있는거 같다. 세그먼트 트리 구현을 잊어버려도 되지만 감은 계속 붙잡고 있었으면 하는 마음에 본인이 이해한 내용을 그림과 코드로 설명한다. 설명은 위에 백준님이 설명해준 그림을 바탕으로 설명하겠다. 먼저 백준님글을 .. 2021. 3. 12.
[JAVA] 백준 - 캐슬 디펜스 17135 (테케 다 맞는데 틀린다면?) www.acmicpc.net/problem/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 자꾸 틀린다면 꼭 점검해야할 상황을 소개한다. (본인 경험) 1. 궁수 3명을 배치하는 모든 경우를 구했는가? - 문제에서 N+1 번째 칸에 궁수 3명을 배치한다고 하였다. 한 칸에 한명만 올 수 있다. 따라서 M개의 자리에서 3개를 선택하는 모든 경우의수를 구해야한다. Combination 로직을 DFS로 구현해주면 된다. 여기에서 M = 5 일때 3개의 자리를 선택하는 경우의 수는 5C3 이므로 10가지가 나와야한다... 2021. 3. 4.
[JAVA] 위상정렬 (TopologySort) - 위상정렬이란? 순서가 정해져 있는 작업들의 목록들을 가지고 전체 작업 순서를 결정하도록 하는 알고리즘. 이를 위해서는 사이클이 없는 방향그래프에서만 해야한다. 아래 그래프로 예를 들겠다. 1번 작업은 2번보다 먼저 해야한다. 이것을 방향그래프로 나타내었다. 2번은 5번 보다 먼저 해야 한다. 5번은 4번 보다 먼저 해야한다. 만약 위와 같은 작업 스케줄이 있다면 어떻게 진행하면 좋을 것인가? 1 - 2 - 3 - 5 - 4 1 - 3 - 2 - 5 - 4 위 2가지 경우중에서 한가지 선택하여 진행하면 된다. 먼저 차수에 대해 정의하겠다. 한 정점의 차수 = 해당 정점보다 먼저 선행되어야 하는 작업의 수 예를들어, 3번의 차수는 1이다. 1번 작업이 선행되어야 하기 때문이다. 5번의 차수는 2이다. 2.. 2021. 2. 24.
[JAVA] 백준 1707 - 이분 그래프 www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net - 7등에 랭크 되어있는 거 보면 느린코드는 아닌 듯 하다. - 이분 그래프란? 그래프에서 임의의 점을 선택하여 그 점과 이웃하는 다른 점은 선택된 점과 색이 달라야 한다. 그리고 그래프에 칠해진 색은 2종류가 가능할 때 이분 그래프라고 한다. 예를 들어, 아래는 이분 그래프인가? 정답은 이분그래프가 맞다. 왜냐하면 아래처럼 2가지의 색상만을 이용하여 임의의 점을 선택할 시 모든 이웃이 자신과 다른.. 2021. 2. 23.