[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)를 비교한 후, 그 때까지의 ..

→2021.01.09

Algorithm/Programmers

[java] 프로그래머스 (타겟 넘버) Level 2

Problem : https://programmers.co.kr/learn/courses/30/lessons/43165 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr Approach BFS나 DFS로 탐색하여 target number에 몇번 도착하는지를 계산하면 된다. 보통 DFS/BFS 는 목적지까지의 최소비용을 구하는데에 사용하지만, 이 문제에서는 최소비용이 아니라 몇번 도착하는지를 구하면 된다. Code public class TargetNumber..

→2021.01.08

Algorithm/Programmers

[java] 프로그래머스 (카펫) Level 2

Problem : https://programmers.co.kr/learn/courses/30/lessons/42842 코딩테스트 연습 - 카펫 Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다. Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 programmers.co.kr Approach 수학적 규칙을 찾는다면 편한 문제이다. 일단 전체 사각형 넓이는 (가로) x (세로) = brown + yellow 이다. 그리고 전체 사각형의 (가로 - 2) x (세로 - 2) = yellow 이다. 이 두 성질을 이용하여 전체 사각형의 넓이를 가질 수 있는 (가로, 세로)의 쌍 중에 (가로 - 2) x (세로 - 2) ..

→2021.01.08

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)의 행렬제곱 문제와 ..

→2021.01.08

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..

→2021.01.08

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번 전체를 ..

→2021.01.08

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개 사용하는게 개수가 더 적다.(주어지는 동전의 가치들이 항상 배수관계이므로 가능함) 다른 테크닉은 필요하지 않는 간..

→2021.01.08

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 한다. 스택의..

→2021.01.08

Algorithm/Baekjoon Online Judge

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

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

→2021.01.08

Algorithm/Baekjoon Online Judge

[java] 백준 1707 (이분 그래프) Gold 4

Problem : https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net Approach 풀이에 시작하기 앞서 주의할 점을 소개한다. 이 문제는 은근히 반례를 찾는 유저들이 많았는데 대부분 다음과 같은 이유로 오답이 생겼을 것이다. 질문 게시판에 있는 djm03178님의 게시글을 인용하겠다. 테스트 케이스마다 초기화를 해야 한다. 똑같은 입력을 주었을 때 다른 출력을 내놓는다면 초기화가 되지 않은 상태일 것이다. 1번 정점에서만 탐색을 하..

→2021.01.07

티스토리툴바