[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); } } 루프를 이렇게 처리함으로써..

→2020.12.22

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)일 때, 구간 합은 다음..

→2020.12.22

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) * 최소크기 사각형의 개수인 규칙을 찾을 수 있다. 여기서..

→2020.12.22

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)를 넘지 않는다면 큐에 넣는다. ..

→2020.12.21

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)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의..

→2020.12.21

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)를 넘지 않..

→2020.12.21

Algorithm/Baekjoon Online Judge

[java] 백준 1697 (숨바꼭질) Silver 1

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

→2020.12.21

Algorithm/Baekjoon Online Judge

[java] 백준 14003 (가장 긴 증가하는 부분 수열 5) Gold 1

문제 원문 링크 : https://www.acmicpc.net/problem/14003 14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net Approach 이 문제는 백준 12015번 가장 긴 증가하는 부분 수열 2 과 백준 12738번 가장 긴 증가하는 부분 수열 3 의 문제에 LIS을 추가로 출력해야 하는 문제이다. 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가..

→2020.12.20

Algorithm/Baekjoon Online Judge

[java] 백준 14002 (가장 긴 증가하는 부분 수열 4) Gold 4

문제 원문 링크 : https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net Approach 이 문제는 백준 11053번 가장 긴 증가하는 수열 의 문제에서 가장 긴 부분 수열을 추가로 출력하는 문제이다. 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20,..

→2020.12.20

Algorithm/Programmers

[java] 프로그래머스 (프린터) Level 2

문제 원문 링크 : https://programmers.co.kr/learn/courses/30/lessons/42587 코딩테스트 연습 - 프린터 일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린 programmers.co.kr Approach Baekjoon Online Judge 사이트에 비슷한 문제(프린터 큐 Silver 3)가 있으니 같이 풀어보면 좋을 것이다. 문제의 조건은 이렇다. 1. 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냅니다. 2. 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에..

→2020.12.20

티스토리툴바