알고리즘
-
[java] 백준 알고리즘 1094번 막대기 풀이알고리즘/백준 알고리즘 2018. 7. 24. 15:14
반으로 쪼개가면서 계속해서 더하면 되는 문제다. 예제 입력 1의 경우인 23cm은 23cm은 64cm보다 작기 때문에 반으로 쪼갠다. 그럼 32cm, 32cm가 나오는데 32cm보다 23cm가 작기 때문에 32cm 나뭇가지 하나는 버리고 나머지 하나는 반으로 쪼갠다. 그럼 16cm, 16cm가 나온다. 16보단 23이 크기 때문에 16cm 하나는 가지고 있고, 하나는 반으로 쪼갠다. (16cm 하나 킵한다) 8cm, 8cm가 되는데 (가지고 있던 16cm) 나뭇가지에 8cm를 더하면 24cm이므로 다시 8cm 나뭇가지 하나를 쪼개고, 다른 8cm는 버린다. 4cm, 4cm가 나오는데, 가지고 있던 16cm 나뭇가지와 4cm 나뭇가지를 더하면 20cm! 그럼 이것도 킵한다. 남은 4cm를 다시 반으로 쪼갠..
-
[java] 백준 알고리즘 1520번 내리막 길 풀이알고리즘/백준 알고리즘 2018. 7. 23. 09:44
memoization을 활용한 문제다. 동적계획법에 나오는 유형이라는데 memoization이라는 개념은 이 문제를 풀면서 알게 됐다. 재귀개념까지만 알아서 재귀로 푸니 시간초과. 역시 재귀만 해서는 시간이 많이 걸린다. 원래 계산했던 것을 기억해두고 이전에 했던 계산을 다시 꺼내 줌으로써 반복계산을 피하는 방법이 memoization을 사용하는 방법이다. 이 문제는 이전에 방문했는지를 체크해줄 필요가 없다. 내리막길로 이동한 순간, 다시 오르막으로 올 일이 없기 때문에 이전에 방문했던 곳을 다시 방문할 일이 없다. if문에서 현재 값보다 다음 값이 작아야만 이동하게 만들 것이기 때문에. * 풀이 소스 123456789101112131415161718192021222324252627282930313233..
-
[java] 백준 알고리즘 9461번 파도반 수열 풀이알고리즘/백준 알고리즘 2018. 7. 21. 16:41
다이나믹 프로그래밍 문제라는 것을 감안하고 시작! 이 문제는 종이에 몇 번 끄적이다보면 규칙을 찾을 수 있다. P(10) 정도까지 만들어보겠다. P(5)까지는 규칙이 안 보여서 직접 대입했다. 해당 값(파도반 수열 P(?))이 나오는데 어떤 순서의 값들이 더해진걸까를 찾아봤다. 6번째부터는 바로 현재 삼각형의 한 변과 4번째 전에 그려진 삼각형의 한 변을 더 한 길이가 다음 삼각형의 한 변 길이가 됐다. 그럼 현재의 삼각형 길이를 구하기 위해서는 P(i) = P(i-1) + P(i-5)라는 식이 적용할 수 있지 않을까? 앞에서 말했듯이 5번째까지는 규칙이 안 보였으니 6번부터 바로 시작하겠다. P(6) == P(5) + P(1) --> 3 == 2 + 1 P(7) == P(6) + P(2) --> 4 =..
-
[java] 백준 알고리즘 2156번 포도주 시식 풀이알고리즘/백준 알고리즘 2018. 7. 20. 09:44
다이나믹 프로그래밍 문제다. 조건 1이야 마시고 그냥 놔두면 된다라서 알고리즘에서는 별 상관이 없는 것 같고, 조건 2를 만족시키는 것이 중요하다. 앞으로 사용할 변수 명에 대한 설명은 다음과 같다. quantityWine: 각각 포도주 잔의 양 sumQuantityWine: 해당 순서에서 포도주를 마실 수 있는 최대양 연속 3잔을 마실 수 없다는 말은 (4잔 이상 놓여있다는 전제 하에)1. 두 칸 전까지의 포도주를 마실 수 있는 최대양 + 현재의 포도주 잔 마시기 식: sumQauntityWine[현재-2] + qantityWine[현재] 2. 한 칸 전 포도주를 마시고 싶다면 중복을 피하기 위해 현재의 포도주 잔 위치에서 3칸 전까지의 포도주를 마실 수 있는 최대양 식: sumQauntityWine[..
-
[java] 백준 알고리즘 2504번 괄호의 값 풀이알고리즘/백준 알고리즘 2018. 7. 18. 20:48
이 문제는 스택을 활용해서 푸는 문제다. 괄호를 숫자로 변환해서 스택에 담아두고 총합을 구하는 원리로 풀었다. 예제 같은 경우를 푼 방식을 보자면, '(()[[]])([])' 처음 입력된다. 처음 '('가 오면 스택에 '('를 담는다. 다음도 '(' 이므로 다시 스택에 '('를 담아준다. 여기까지 스택의 모양은 '((' 이다. 다음 ')' 가 온다. 닫혔다는 건 괄호 하나가 완성 됐다라는 뜻이다. 그래서 앞에 왔었던 값을 체크해줘야 하는데, 만약, '()'형태로 앞의 문자가 '(' 였다면 바로 2로 변환해주면 된다. 앞의 문자 '('는 pop을 시켜서 없애준다. 다음은 '(()[[]])([])' 중에서 (()[ 까지 왔다. '['이 올 경우도 '('와 똑같이 처리하고 점수만 다르게 해주면 된다. 열리는 ..
-
[java] 백준 알고리즘 1874번 스택 수열 풀이알고리즘/백준 알고리즘 2018. 7. 11. 16:52
사용하는 객체가 많아 메모리, 시간 둘 다 많이 잡아먹는다. ㅠㅠ 내가 짰지만 소스가 그다지 마음에 들지는 않지만, 일단 문제 해결. * 풀이 소스 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667 public class Baekjooon1874{ static StringTokenizer st; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); ..
-
[java] 백준 알고리즘 10828번 스택 풀이알고리즘/백준 알고리즘 2018. 7. 11. 16:30
스택. 스택에 대한 설명: 스택(위키피디아) 스택은 바닥은 깔끔하게 막혀있고, 사각형 모양의 통에 데이터를 넣는다고 생각하면 된다. 그럼 원하는 데이터를 꺼내려면 위에서부터 꺼낼 수 밖에 없다. 데이터를 넣을 때도 퇴적 작용처럼 위에서 하나하나씩 쌓인다. 이를 First In, Last Out이라 한다. 처음 들어간 것이 가장 마지막에 나온다는 뜻이다. 자바에 있는 Stack 클래스를 활용해 쉽게 구현했다. * 풀이 소스 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849 public class Baekjoon10828{ static StringTokenizer st; public static v..
-
[java] 백준 알고리즘 9020번 골드바흐의 추측 풀이알고리즘/백준 알고리즘 2018. 7. 9. 17:10
에라토스테네스의 체를 활용해서 푸는 문제이다. 에라토스테네스는 소수의 배수를 통해서 소수가 아닌 수를 삭제해나가는 것이다. 그리고 삭제되지 않은 수가 소수라는 뜻! 에라토스테네스 체로 먼저 소수를 찾아두고, 입력된 숫자를 반으로 나눈 뒤, 출력될 왼쪽의 수는 -- 하면서 출력될 오른쪽의 수는 ++해준다. 동시에 소수가 나오면 골드바흐의 추측 조건에 만족한다. 그러면 break; * 풀이 소스 12345678910111213141516171819202122232425262728293031323334353637383940414243444546 public class Baekjoon9020{ static StringTokenizer st; public static void main(String[] args) ..