본문 바로가기

algorithm68

[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] 2021 카카오문제 - 메뉴 리뉴얼 https://programmers.co.kr/learn/courses/30/lessons/72411 코딩테스트 연습 - 메뉴 리뉴얼 레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 programmers.co.kr 💡 개요 문제는 보고 오셨다고 생각하고 바로 풀이 하겠습니다. dfs 재귀를 통한 완전탐색 하셔도 되지만 저는 비트마스킹을 통한 완전탐색을 선택했습니다. 그 이유는 단어의 특징때문입니다. 하나의 주문에 들어가는 메뉴는 중복되는 알파벳이 없다는 점 때문입니다. 알파벳은 아래처럼 각각 하나의 숫자에 대응됩니다. 'A' - 1 'B' - 1 2022. 3. 15.
[JAVA] 백준 K번째 최단경로 찾기 1854 (다익스트라) 만약 다익스트라 알고리즘이 어떤거였는지 다시 상기해보려면 아래 링크 참고해주시기 바랍니다. 이번 문제는 다익스트라 개념을 응용한 쉽지 않은 문제였습니다. 메모리 제한과 더불어 속도제약이 까다로웠습니다. https://onejunu.tistory.com/87 [JAVA] 백준 최단 경로 1753 ( 다익스트라 알고리즘) www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는.. onejunu.tistory.com 그래도 다익스트라에 대해 간단히 언급해보겠습니다. 우선순위 큐를 이용한 다익스트라 알고리즘을 설명하기 .. 2022. 3. 12.
[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] 백준 - 스위치 1395 (세그먼트트리 + lazy propagation) www.acmicpc.net/problem/1395 1395번: 스위치 첫 줄에는 스위치의 개수 N(2 ≤ N ≤ 100,000)과 처리할 일의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에 대해 각 줄에 처리할 일에 대한 정보가 담겨진 세 개의 정수 O, Si, Ti가 입력된다. O www.acmicpc.net 세그먼트트리를 풀기위한 기본 템플릿은 onejunu.tistory.com/119 [JAVA] 세그먼트 트리구현법과 lazy propagation (feat. 백준) www.acmicpc.net/blog/view/26 세그먼트 트리 나중에 업데이트 해야지! 배열 A가 있고, 여기서 다음과 같은 두 연산을 수행해야하는 문제가 있습니다. 10999번 문제: 구간 합 구하기 2 .. 2021. 3. 14.
[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.

티스토리툴바