전체 글

전체 글

    [java] 백준 10844 (쉬운 계단 수) Silver 1
    Algorithm/Baekjoon Online Judge

    [java] 백준 10844 (쉬운 계단 수) Silver 1

    문제 원문 링크 : https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net Approach DP로 풀 수 있는 문제이다. 문제 풀이에 앞서, 밑의 조건을 알고 가면 편하다. ​ 1. 0으로 시작하는 N자리 수는 없다. ​ 2. 1자리 수는 모두 계단수이다. ​ 3. DP에 저장할 때에 1,000,000,000으로 나눈 나머지를 저장해야 한다. N자리 수를 봤을 때, 10의 자리 수가 0이면 1의 자리 수가 1이어야 한다. 10의 자리 수가 1~8이면 1의 자리 수는 10의 자리 수의 +1한 수 이거나 -1한 수 여야만 한다. 10의 자리수가 9이면 1의 자리 수는 ..

    [java] 백준 1932 (정수 삼각형) Silver 1
    Algorithm/Baekjoon Online Judge

    [java] 백준 1932 (정수 삼각형) Silver 1

    문제 원문 링크 : https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net Approach DP 문제이다. 문제에서는 이등변 삼각형처럼 보이지만, 실제로는 정사각형 배열의 반만 쓰면 된다. 크기가 N인 정수 삼각형이고, i는 위에서부터 층의 높이, j는 삼각형의 열일 때, ​ DP[i][j] = DP[i - 1][0] (j == 0) ​ DP[i][j] = DP[i - 1][j - 1] (j == N) ​ DP[i][j] = DP[i - 1][j - 1] + DP[i - 1][j] (j == 1...N-1) 위의 식을 도출..

    [java] 프로그래머스 (기능개발) Level 2
    Algorithm/Programmers

    [java] 프로그래머스 (기능개발) Level 2

    문제 원문 링크 : https://programmers.co.kr/learn/courses/30/lessons/42586 코딩테스트 연습 - 기능개발 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 programmers.co.kr Approach 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다. progresses speeds return [93, 30, ..

    [java] 백준 2580 (스도쿠) Gold 4
    Algorithm/Baekjoon Online Judge

    [java] 백준 2580 (스도쿠) Gold 4

    문제 원문 링크 : https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net Approach 이 문제 또한 대표적인 BruteForce, Backtracking 문제이다. N-Queens 문제와 접근법은 동일하다. 놓을 수 있는지 없는지 검사 후, 다음 단계로 넘어가며, 놓을 수 없다면 다시 뒤로 돌아가 똑같이 다음 수를 검사하는 것이다. 나는 1차원 배열을 사용하였으며, 배열에서 i번째 요소는 N x N 행렬에서 (i / N)행 (i % N)열이다. ..

    [java] 백준 9663 (N-Queen) Gold 5
    Algorithm/Baekjoon Online Judge

    [java] 백준 9663 (N-Queen) Gold 5

    문제 원문 링크 : https://www.acmicpc.net/problem/9663 Approach 대표적인 BruteForce, Backtracking 알고리즘 문제이다. 첫번째 열부터 숫자를 하나씩 놓으면서 그 다음 열에 놓을 수 없는지를 검사하여 놓을 수 있는 총 개수를 구하는 문제다. 퀸을 놓으려면 가로, 세로, 대각선에 퀸을 놓아서는 안된다. arr[] 배열은 몇 번째 열, 몇번째 행에 퀸을 놓은지를 기록한 것이다. 예를 들어, arr[i] = j 라 할 때, i번째 열에 j번째 행에 퀸이 놓아져 있다는 뜻이다. for(int i = 0; i < n; i++){ arr[lv] = i; if (isPossible(lv)){ backtracking(lv + 1); } } 루프를 이렇게 처리함으로써..

    [java] 백준 11660 (구간 합 구하기 5) Silver 1
    Algorithm/Baekjoon Online Judge

    [java] 백준 11660 (구간 합 구하기 5) Silver 1

    문제 원문 링크 : https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net Approach DP를 활용하여 풀 수 있는 문제이다. DP[i][j] = (0, 0)부터 (i, j) 까지의 직사각형을 이루는 요소들의 합이다. 이 때, (0, 0)과 (i, j)는 직사각형의 좌상, 우하의 꼭짓점이다. 위의 DP배열을 이용하여, 좌상 꼭짓점이 (x1, y1)이고, 우하 꼭짓점이 (x2, y2)일 때, 구간 합은 다음..

    [java] 프로그래머스 (멀쩡한 사각형) Level 2
    Algorithm/Programmers

    [java] 프로그래머스 (멀쩡한 사각형) Level 2

    문제 원문 링크 : https://programmers.co.kr/learn/courses/30/lessons/62048 코딩테스트 연습 - 멀쩡한 사각형 가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 programmers.co.kr Approach 임의의 꼭짓점 (x1, y1) -> (x2, y2) 으로 가는 최소크기로 나누어서 계산한 후, 최소크기의 개수만큼 곱해주는 식으로 풀면 쉽다. 최소크기로 나누었을 때, 선분이 거치는 사각형의 개수 = (최소크기 사각형의 가로 + 세로 - 1) * 최소크기 사각형의 개수인 규칙을 찾을 수 있다. 여기서..

    [java] 백준 13913 (숨바꼭질 4) Gold 4
    Algorithm/Baekjoon Online Judge

    [java] 백준 13913 (숨바꼭질 4) Gold 4

    문제 원문 링크 : https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net Approach 대표적인 BFS문제로, 최단시간을 이루는 경로 또한 구해야 하는 문제이다. 현재 위치가 X 일 때, 1초 후에 X - 1 또는 X + 1 또는 2 * X 위치로 갈 수 있다. 처음 큐에 N을 넣은 후 하나씩 뺀다. 뺀 수에 +1, -1, *2를 하여 범위(0 ~ 100,000)를 넘지 않는다면 큐에 넣는다. ..

    [java] 백준 13549 (숨바꼭질 3) Gold 5
    Algorithm/Baekjoon Online Judge

    [java] 백준 13549 (숨바꼭질 3) Gold 5

    문제 원문 링크 : https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net Approach 대표적인 BFS문제로 백준 1679번 숨바꼭질 문제와 단 한개의 조건을 제외하고 똑같은 문제이다. 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의..

    [java] 백준 12851 (숨바꼭질 2) Gold 5
    Algorithm/Baekjoon Online Judge

    [java] 백준 12851 (숨바꼭질 2) Gold 5

    문제 원문 링크 : https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net Approach 대표적인 BFS 문제로, N to K의 최단시간과 최단시간으로 가는 방법을 구하는 문제이다. 현재 위치가 X 일 때, 1초 후에 X - 1 또는 X + 1 또는 2 * X 위치로 갈 수 있다. 처음 큐에 N을 넣은 후 하나씩 뺀다. 뺀 수에 +1, -1, *2를 하여 범위(0 ~ 100,000)를 넘지 않..

티스토리툴바