BOJ

    [java] 백준 1915 (가장 큰 정사각형) Gold 5
    Algorithm/Baekjoon Online Judge

    [java] 백준 1915 (가장 큰 정사각형) Gold 5

    Problem : https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net Approach DP로 풀 수 있는 문제로, DP[i][j] 는 (i, j) 위치에서 좌상으로 진행했을 때 만들수 있는 가장 큰 정사각형의 한 변의 길이이다. 따라서 주어진 board[i][j] 가 1이라면 일단 최소 1x1 정사각형을 만들 수 있으므로 dp[i][j] = 1을 저장한다. 그리고 board[i][j - 1], board[i - 1][j], board[i - 1][j - 1]이 모두 1이라면 DP[i][j]에 min(DP[i][j - ..

    [java] 백준 11780 (플로이드 2) Gold 3
    Algorithm/Baekjoon Online Judge

    [java] 백준 11780 (플로이드 2) Gold 3

    Problem : https://www.acmicpc.net/problem/11780 11780번: 플로이드 2 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net Approach 플로이드와샬 알고리즘을 사용한 최단경로비용 구하기 + 최단경로를 구하는 문제이다. dist[i][j] = i부터 j까지 가는 최소비용이고, (i == j 일 경우거나, 도달할 수 없는 경우는 0) next[i][j] = j도착 직전 도시를 저장해놓은 배열이다. (i == j 일 경우거나, 도달할 수 없는 경우는 -1) 입력으로 그래프를 먼저 구성하고, 플로이드..

    [java] 백준 9019 (DSLR) Gold 5
    Algorithm/Baekjoon Online Judge

    [java] 백준 9019 (DSLR) Gold 5

    Problem : https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net Approach BFS + DP + Tracing 을 사용하여 풀이한 문제이다. 필자는 위의 과정보다 숫자를 만드는 작업이 더 어려웠다.(어렵다기보다 생각할 조건들이 많아서 귀찮았다.) D: D 는 n을 두 배로 바꾼다. 결과 값이 9999 보다 큰 경우에는 10000 으로 나눈 나머지를 취한다. 그 결과 값(2n mod 10000)을 레지스터에 저장한다. S: S ..

    [java] 백준 9252 (LCS 2) Gold 5
    Algorithm/Baekjoon Online Judge

    [java] 백준 9252 (LCS 2) Gold 5

    Problem : https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net Approach LCS(Longest Common Subsequence) 문제로 DP로 풀이가 가능한 문제이다. 배열은 DP[s1.length + 1][s2.length + 1] 으로 선언하여 두 문자열을 각각 한 문자씩 비교해 나간다. DP[i][j] 는 s1.charAt(i)와 s2.charAt(j)를 비교한 후, 그 때까지의 ..

    [java] 백준 11444 (피보나치 수 6) Gold 3
    Algorithm/Baekjoon Online Judge

    [java] 백준 11444 (피보나치 수 6) Gold 3

    Problem : https://www.acmicpc.net/problem/11444 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net Approach 유명한 피보나치 수열의 n번째 수를 구하는 문제이다. 이 문제는 백준 2749 피보나치 수 3 문제와 나머지 연산 부분만 다르고 아예 똑같은 문제이다. 문제풀이 개수 늘리기 좋다. 하지만 n이 1,000,000,000,000,000,000 이하의 숫자이므로 오랜시간이 걸릴 것이다. 따라서 아래와 같이 피보나치의 행렬적 규칙을 이용하여 계산하여야 한다. (long 자료형을 사용하여) 아래 규칙만 알고 있다면 O(log n)의 행렬제곱 문제와 ..

    [java] 백준 1629 (곱셈) Silver 1
    Algorithm/Baekjoon Online Judge

    [java] 백준 1629 (곱셈) Silver 1

    Problem : https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net Approach 수학적 지식이 있어야 하는 분할정복(Divide & Conquer)문제이다. A^4 % C = ((A^2 % C) * (A^2 % C)) % C A^5 % C = ((((A^2 % C) * (A^2 % C)) % C) * A) % C 위의 규칙을 이용하여 구현하면 된다. Code import java.io.*; /** * no.1629 : 곱셈 * hint : A^2 % C = ((A % C) * (A % C)) % C */ p..

    [java] 백준 1992 (쿼드트리) Silver 1
    Algorithm/Baekjoon Online Judge

    [java] 백준 1992 (쿼드트리) Silver 1

    Problem : https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net Approach 전형적인 분할정복(Divide & Conquer)문제이다. 다음과 같은 과정을 반복하면 답을 도출할 수 있다. 현재 영역의 제일 좌상 요소를 기억한 후, 모든 영역을 검사한다. 기억한 요소와 모든 영역이 같다면, 기억한 요소를 반환한다. 다르다면, 정확히 4등분한다. (나누기 전 괄호로 감싼다.) 나눠진 영역의 크기가 1x1이 될 때까지 1번 전체를 ..

    [java] 백준 11047 (동전 0) Silver 1
    Algorithm/Baekjoon Online Judge

    [java] 백준 11047 (동전 0) Silver 1

    Problem : https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net Approach 주어지는 동전의 가치가 항상 배수관계이므로, 동전의 개수가 최소가 되게끔 동전을 사용하려면 동전의 가치가 큰 것부터 동전을 구성해나가면 된다. 예를들어, 500원 2개보단 1000원 1개 사용하는게 개수가 더 적다.(주어지는 동전의 가치들이 항상 배수관계이므로 가능함) 다른 테크닉은 필요하지 않는 간..

    [java] 백준 17298 (오큰수) Gold 4
    Algorithm/Baekjoon Online Judge

    [java] 백준 17298 (오큰수) Gold 4

    Problem : https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net Approach 배열에서 자신 기준 오른쪽에 있는 큰 값들 중 가장 가까운 값을 찾는 문제이다. 간단하게 생각할 수 있는 naive한 방법은 자신보다 큰 값이 나올 때까지 자신 기준 오른쪽 요소들을 모두 탐색하는 것이다. 하지만 이런 접근법은 최대 O(n^2)의 시간복잡도를 가지므로 효율성이 떨어진다. 다른 풀이법으로는 스택을 이용한 풀이법이 있다. 처음 시작점을 스택에 push 한다. 스택의..

    [java] 백준 2629 (양팔저울) Gold 2
    Algorithm/Baekjoon Online Judge

    [java] 백준 2629 (양팔저울) Gold 2

    Problem : https://www.acmicpc.net/problem/2629 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무 www.acmicpc.net Approach 주어진 추들의 무게로 구슬의 무게를 확인할 수 있는지를 판단하는 문제였다. 구슬을 목적지라고 가정한다면, 목적지를 갈 수 있는지를 판단하는 문제다. 따라서 필자는 깊이우선탐색을 이용하여 풀이를 하였다. 일단, 탐색 진행 방법에는 3가지 방법이 있다. 무게를 확인할 구슬은 항상 저울의 왼쪽에 놓는다고 가정하였을 때, 다음 구슬을 저울의 오른쪽에 올리는 경우(w + w..

티스토리툴바