java
[백준] 11053번 : 가장 긴 증가하는 부분 수열 - JAVA [자바]
[백준] 11053번 : 가장 긴 증가하는 부분 수열 - JAVA [자바]
2020.09.02www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net (제목이 꽤 길다...) 문제 이전 포도주 시식 또는 계단오르기 문제를 해결했다면 오히려 쉽게 접근 할 수 있는 문제다. 알고리즘 [접근 방법] 앞서 말했듯 포도주 시식, 계단오르기 같은 문제랑 같은 계열의 문제다. 보통 이런 문제를 최장 증가 부분 수열(LIS)라고 한다. 말 그대로 주어진 수열에서 오름차순으로 구성 가능한 원소들을..
[백준] 2156번 : 포도주 시식 - JAVA [자바]
[백준] 2156번 : 포도주 시식 - JAVA [자바]
2020.08.31www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 문제 만약 백준 카테고리에서 동적계획법을 차례대로 풀어왔다면 쉽게 풀 수 있는 문제다. 알고리즘 [접근 방법] 아마 동적계획법1 카테고리 문제를 차례대로 풀어왔다면 2579번 문제인 '계단 오르기'랑 매우 유사하다는 것을 느끼셨을 것이다. 이 문제를 풀기에 앞서 혹여 기억이 안나거나 아직 풀어보지 못한 분은 계단 오르기 문제를 보고 오시는 것을 추천드린다. 필자도 이에 대해 포스팅 했으니 아래 포스팅을 참고하시면..
[백준] 10844번 : 쉬운 계단 수 - JAVA [자바]
[백준] 10844번 : 쉬운 계단 수 - JAVA [자바]
2020.08.29www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 저번 문제인 1로 만들기보다 쉬운 편이다. 몇가지 규칙만 알면 되니 한 번 같이 알아보도록 하자. 알고리즘 [접근 방법] 문제를 설명하기 전에 자릿수 개념에 대해 헷갈려 하는 분들이 있어 먼저 한 번 정리하려고 한다. 그래야 필자가 설명하기도 편할 듯 하다. N번째 자릿수라 하면 보통 길이가 N인 자연수에서 가장 왼쪽에 있는 수가 N번째 자리가 N번째가 된다. 만약 123456이라는 수가 있다고 하면 6번째 자릿수 자릿값은 1, 5번째 자릿수의 자릿값은 2, ⋯ , 첫번째 자릿수의 자릿값은 6이 된다. 소수의 경우 왼쪽..
[백준] 1463번 : 1로 만들기 - JAVA [자바]
[백준] 1463번 : 1로 만들기 - JAVA [자바]
2020.08.28www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 알고리즘 [접근 방법] 생각보다 어렵지 않게 풀 수 있는 문제다. 이번 문제는 재귀로 풀이해볼 것이다. 크게 세 가지 경우의 수로 나눌 수 있는데, 3으로 나누는 경우, 2로 나누는 경우, 1을 빼는 경우가 있다. 여기서 1로 만들기 위한 최소 연산 횟수를 찾아내야 한다. 여기서 함정이 하나 있다. "무조건 큰 수로 나눈다고 해결되진 않는다." 위 이미지의 힌트에서 볼 수 있듯이 10을 큰 수부터 나눠보기 시작하면 10 -> 5 -> 4 -> 2 -> 1 이렇게 4번의 연산이 필요하다. 하지만 정답은 10 -> 9 ->..
[백준] 2579번 : 계단 오르기 - JAVA [자바]
[백준] 2579번 : 계단 오르기 - JAVA [자바]
2020.08.27www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 문제 생각보다 많은 분들이 틀렸던 문제다. 특히 문제 조건을 제대로 이해하지 못하거나 동적계획법을 제대로 이해하지 못해 틀리는 경우가 대다수였던 것 같다. 조건들을 유의하면서 풀어야 하니 차근차근 알아보자. 알고리즘 [접근 방법] 문제는 어렵지 않다. 문제에서 나온 것처럼 크게 다음과 같은 세 가지 조건을 만족해야한다. 1. 계단을 오를 때 한 계단, 또는 두 계단을 오를 수 있다. 2. 연속된 3개의 계단을 밟으면 안된다..
[백준] 1932번 : 정수 삼각형 - JAVA [자바]
[백준] 1932번 : 정수 삼각형 - JAVA [자바]
2020.08.26www.acmicpc.net/problem/1932 1932번: 정수 삼각형 문제 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최� www.acmicpc.net 문제 조금만 살펴보면 쉽게 풀 수 있는 문제다. 다만 가끔 위에서 아래로 내려오면서 최댓값 경로만 찾아서 하는 경우가 있는데 그렇게 하면 100% 오답이 난다. 또한 DP에 한 번 탐색한 값을 재활용(Memoization)하지 않고 불필요하게 재귀호출을 다 해주면 시간초과가 나니 이 점 유의하도록 하자. 알고리즘 [접근 방법] 정답률이 높은 것을 보아 아마 다들 쉽게 풀 수 있..
[백준] 1149번 : RGB거리 - JAVA[자바]
[백준] 1149번 : RGB거리 - JAVA[자바]
2020.08.11www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 문제 이번 문제는 조금은 생각해 볼 필요가 있는 문제인 것 같다. 대표적으로 풀이방법이 2가지가 있는데, 재귀(Top-Down)방법과 반복문(Bottom-Up)을 이용한 방법. 이렇게 두 가지로 나뉜다. 여타 다른 문제처럼 먼저 재귀를 이용한 풀이를 보여주고, 마지막에 반복문을 사용한 풀이 방법을 알려주겠다. 알고리즘 [접근 방법] 먼저 문제에 대한 이해가 필요하다. 풀이 조건이 조금은 어..
[백준] 9461번 : 파도반 수열 - JAVA [자바]
[백준] 9461번 : 파도반 수열 - JAVA [자바]
2020.08.05www.acmicpc.net/problem/9461 9461번: 파도반 수열 문제 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 � www.acmicpc.net 문제 그동안 배웠던 동적계획법을 응용하여 써보려 한다. 정석적인 방법과 단순 반복문으로 풀이하는 방법 모두 보여줄 것이다. 알고리즘 [접근 방법] 그동안의 동적계획법 문제는 테스트 케이스가 1개뿐으로 해당 값에 대한 재귀 또는 반복문으로 풀었었다. 이번 문제는 테스트 케이스가 여러개이므로 각 케이스마다 동적계획법을 쓰려 한다. 예로들어 Func() 함수가 있다고 가정하자. 이 함수는 Fucn(N) = Func(N..
[백준] 1904번 : 01타일 - JAVA [자바]
[백준] 1904번 : 01타일 - JAVA [자바]
2020.07.24www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이�� www.acmicpc.net 문제 문제의 이해 자체는 어렵지 않을 것이다. 타일은 두 종류가 있는데 1타일과 0이 두 개 이어 붙여진 00타일이 있는 것이다. 즉 1타일과 00타일을 조합할 때, 00타일은 분해할 수 없다는 의미다. 막상 풀어보면 그렇게 어렵지 않으니 한 번 같이 문제를 들여다보도록 하자 알고리즘 [접근 방법] 이 문제는 만약 N=1 부터 경우의 수를 쭉 나열해보았다면 매우 쉽게 풀 수 있다. 일단 한 번 나열해보도록하자. ..
[백준] 1003번 : 피보나치 함수 - JAVA [자바]
[백준] 1003번 : 피보나치 함수 - JAVA [자바]
2020.07.22www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 문제 이전의 피보나치 수를 풀어보셨다면 쉽게 풀 수 있는 문제다. 이 문제는 피보나치 수를 구할 때, fibonacci(0)과 fibonacci(1)이 각각 몇 번 호출되는지를 묻는 문제다. 알고리즘 [접근 방법] 이 문제 또한 풀이방법은 여러가지다. 대표적으로 정석적인 방법인 재귀(Top-Down)를 이용하여 풀이하는 방법이 있고, 다른 하나는 반복문(Bottom-Up)을 사용하여 계산하는 방법이 있다. 혹여 피보나치 수를 DP로 풀이하는 방법을 모르신다면 아래 링크의 포스팅을 한 번 읽어보고 오는 것을 ..