알고리즘 풀이/백준 (48) 썸네일형 리스트형 [백준] 10986번: 나머지 합 - JAVA 🔗 문제 링크 BOJ 10986번: 나머지 합 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 📝 풀이 과정 연속된 구간의 합이기 때문에 누적합 방법으로 문제를 풀이해야 한다. 배열의 연속 구간의 합은 $sum[j] - sum[i]$로 구할 수 있는데, 이 합의 M으로 나눈 나머지가 0인 순서쌍을 구해야 한다. $(sum[j] - sum[i]) \% M = 0$이 되고, 모듈러 연산은 분배가 가능하기 때문에 $sum[j]\%M - sum[i]\%M = 0$ 따라서.. [백준] 1072번: 게임 - JAVA 🔗 문제 링크 BOJ 1072번: 게임 1072번: 게임 김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시 www.acmicpc.net 1️⃣ 이분 탐색 📝 풀이 과정 새로운 게임을 하게 되면 계산되는 확률은 $((y+횟수) \times 100) / (x + 횟수)$ 따라서 해당되는 횟수가 최소로 증가할 때 확률의 값이 변하는 경우를 찾으면 된다. 주어진 게임의 2배만큼 진행했는데도 확률이 변하지 않았다면 더이상 변하지 않기 때문에, 0부터 최고 1,000,000,000번 진행했을 때까지 이분탐색을 통해 값을 찾을 수 있다. 💡 부동소수점 오차 변수.. [백준] 11779번: 최소비용 구하기 2 - JAVA 🔗 문제 링크 BOJ 11779번: 최소비용 구하기 2 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 📝 풀이 과정 다익스트라로 + 경로를 구하는 문제이다. 다익스트라는 dist 배열을 통해 현재 노드에서부터 다음 노드로 이동하는 비용이 최소 비용이 될 때 갱신하는 방법을 사용하는데, 이 때 거리를 갱신하면서 현재 노드의 위치를 함께 저장하면 경로를 구할 수 있다. 만약, 1번에서 3번으로 이동했다면 3번 전에 1번 노드를 방문했다는 의미가 되고, prev[3] = 1가 되는 .. [백준] 10830번: 행렬 제곱 - JAVA 🔗 문제 링크 BOJ 10830번: 행렬 제곱 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 📝 풀이 과정 [백준] 1629번: 곱셈 - JAVA에서 확장된 문제다. 거듭제곱을 분할 정복으로 계산하는 같은 방식의 문제이지만, 행렬이라는 조건이 추가되었다. 행렬의 곱셈에서 A x B의 (i, j)의 값을 구하기 위해서는 A의 i열의 곱과 B의 j행의 곱을 순차적으로 더해 구해야 한다는 것을 이용해 곱셈하는 함수인 multipleMatrix(m1, m2)를 만들어 주었다. 기존 거듭제곱 문제에서는 거듭 제곱값으로 주어진 값이 .. [백준] 1629번: 곱셈 - JAVA 🔗 문제 링크 BOJ 1629번: 곱셈 📝 풀이 과정 주어진 숫자를 제곱해야 하는데 단순하게 반복문으로 제곱수를 구하게 되면 시간복잡도는 B의 크기만큼 소요되게 되고 B의 최대 크기는 $2^{31}-1$로 시간 제한을 초과하게 된다. 따라서 정해진 제곱을 분할하는 방식을 사용해 시간을 줄여야 한다. $$ A^{10} = A^{5 + 5} = A^5 \times A^5 $$ 먼저 제곱은 위의 식처럼 분할이 가능하다. 따라서 제곱을 순차적으로 하나씩 곱하면서 구하지 않고, $A^5$를 구한 뒤 그 수를 제곱하면 $A^{10}$을 쉽게 구할 수 있는 것이다. 만약 제곱수가 11(홀수)이라면 $A^5$(절반)를 제곱한 뒤 그 수에 $A$를 곱하면 되기 때문에 빠르게 답을 구할 수 있게 된다! static lon.. [백준] 18119번: 단어 암기 - JAVA 🔗 문제 링크 BOJ 18119번: 단어 암기 18119번: 단어 암기 준석이는 영어 단어를 외우려고 한다. 사전에는 N가지 단어가 적혀 있다. 모든 단어는 소문자이다. 단어 안에 있는 모든 알파벳을 알 때, 그 단어를 완전히 안다고 한다. 다음과 같은 쿼리들이 주 www.acmicpc.net 📝 풀이 과정 단어가 알고있는 알파벳으로 구성되어 있을 때 아는 단어라고 한다. 따라서 단어를 알파벳을 기준으로 보고 단어에 포함되는 알파벳을 비트마스킹을 통해 처리하려고 하였고, 현재 알고 있는 알파벳도 비트연산을 통해 계속 누적하였다. 알파벳은 총 26자리로 이루어져있으며 처음에는 모든 알파벳을 알고있기 때문에 (1 = word) cnt++; 이후, for문으로 단어마다 기억하고 있는 알파벳과 &연산을 통해 비.. [백준] 15663번: N과 M (9) - JAVA 🔗 문제 링크 BOJ 15663번: N과 M (9) 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 📝 풀이 과정 permutation을 활용해 수열을 구하는 문제이다. 사전순으로 출력하기 위해 Arrays.sort를 활용해 입력이 들어온 숫자들을 오름차순 정렬해주었고, visit배열을 통해 같은 숫자가 수열에 포함되지 않도록 했다. input 3 1 4 4 2 -------- output 2 4 이전의 N과 M 문제들과 다른 점은 중복되는 수열이 출력되면 안된다는 점이다. 모든 수열을 구하게 되면 2,4,4.. [백준] 1800번: 인터넷 설치 - JAVA 🔗 문제 링크 BOJ 1800번: 인터넷 설치 1800번: 인터넷 설치 첫 번째 줄에 N(1 ≤ N ≤ 1,000), 케이블선의 개수 P(1 ≤ P ≤ 10,000), 공짜로 제공하는 케이블선의 개수 K(0 ≤ K < N)이 주어진다. 다음 P개의 줄에는 케이블이 연결하는 두 컴퓨터 번호와 그 가격이 차 www.acmicpc.net 📝 풀이 과정 처음에는 방문할 때마다 가격을 저장하고 해당 가격순으로 정렬하여 K개만큼 제외하는 등의 작업이 굉장히 오래걸렸기 때문에 당연하게도 시간초과가 발생했다... 계속 고민하며 아이디어가 떠오르지 않아 고생하던 중 한가지 힌트를 보게 되었다. 최소값을 미리 정한 뒤 탐색을 하라는 것이었다. 최소값을 x로 두고 가격이 x이하인 선은 그냥 연결을 하고, x이상인 선은 K개.. 이전 1 2 3 4 ··· 6 다음
