JAVA - 백준 [BAEK JOON]
[백준] 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로 풀이하는 방법을 모르신다면 아래 링크의 포스팅을 한 번 읽어보고 오는 것을 ..
[백준] 2748번 : 피보나치 수 2 - JAVA [자바]
[백준] 2748번 : 피보나치 수 2 - JAVA [자바]
2020.07.21www.acmicpc.net/problem/2748 2748번: 피보나치 수 2 문제 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n>=2)�� www.acmicpc.net 문제 동적 계획법 1의 첫 문제다. 확인한바 동적계획법에서 사라졌다. (2021.01.02) 이 전 재귀 문제에서도 피보나치 수 문제를 올려둔 것이 있으니 한 번 아래 포스팅을 참고해보시는 것도 좋을 것 같다. st-lab.tistory.com/94 [백준] 10870번 : 피보나치 수 5 - JAVA [자바] st-lab.tistory.com 알고리즘 [접근 방법] 피..
[백준] 14889번 : 스타트와 링크 - JAVA [자바]
[백준] 14889번 : 스타트와 링크 - JAVA [자바]
2020.07.15www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 문제 저번 연산자 끼워넣기에 이어 이번 문제도 백준에서 제공하는 삼성 SW 역량 테스트 기출문제 중 하나다. 이 문제의 포인트는 두 팀으로 나누는데, 각 팀의 능력치 차이를 최소화 한다는 것이다. 한마디로 팀의 전력차가 적게 나도록 팀을 짜면 된다. 그렇게 어려운 문제는 아니니 천천히 풀어보자. 알고리즘 [접근 방법] 앞서 말했듯 두 팀으로 나누면 된다. 위 문제의 예시로 보자. 위와 같이 4명의 사람이 있을 때 두 팀으로 나눌 수..
[백준] 14888번 : 연산자 끼워넣기 - JAVA [자바]
[백준] 14888번 : 연산자 끼워넣기 - JAVA [자바]
2020.07.14www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, �� www.acmicpc.net 문제 백준에서 제공한느 삼성 SW 역량 테스트 기출 문제 중 하나다. (참고로 덧붙이자면 삼성 SW 역량 테스트의 경우 dp와 탐색 정도의 기본적인 알고리즘 풀이 능력은 갖추는 것을 추천한다. 자료구조는 뭐.. 당연 기초 중의 기초다.) 알고리즘 [접근 방법] 이번 문제 또한 그동안 백트래킹을 통해 문제를 풀어보고 정확하게 이해했다면 정말 쉽게 접근 ..
[백준] 2580번 : 스도쿠 - JAVA [자바]
[백준] 2580번 : 스도쿠 - JAVA [자바]
2020.07.09www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 문제 N-Queen 문제를 풀었다면 이 문제 또한 접근 방법만 잘 이해한다면 매우 쉽게 풀 수 있는 문제다. 알고리즘 [접근 방법] 스도쿠를 한 번쯤은 모두 접해보셨을 것이라 생각한다. 같은 행과 열에 겹치지 않으면서 3×3 행렬 안에서도 겹치면 안된다. 즉, 이 규칙을 토대로 조건문을 만들어야 한다는 것은 누구나 알 것이다. 이전 문제처럼 재귀호출부와 조건 검사 함수, 이렇게 두 개를 구성하도록 하자. 최대한..