알고리즘/백준 알고리즘
-
[java] 백준 알고리즘 10866번 덱 풀이알고리즘/백준 알고리즘 2018. 8. 6. 14:22
덱은 스택과 큐의 특징을 골고루 가지고 있다. First In, First Out도 가능하고, First In, Last Out도 가능하다. 양방향으로 이동이 가능하다. 자바에서 덱을 제공해준다. 덱을 활용해 문제 해결. * 풀이 소스 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677 public class Baekjoon10866{ static StringTokenizer st; public static void main(String[] args) throws IOException { Buffe..
-
[java] 백준 알고리즘 1158번 조세퍼스 문제 풀이알고리즘/백준 알고리즘 2018. 7. 27. 14:26
풀이 방법은 백준 알고리즘 11866번 문제와 같다. 풀이 방법 보러가기 : Click 내 풀이 방법은 input 값이 올라갈수록 시간이 오래 걸리는 알고리즘이다.(그다지 좋은 알고리즘을 만들어내지 못했다.) 여기 올린 풀이소스는 나 혼자 힘으로 풀어냈던 코드를 올린 것이고, 더 효율적인 알고리즘은 나머지 연산자(%)를 활용해 푼 알고리즘이 메모리면에서나 시간면에서나 더 좋다. * 풀이 소스 12345678910111213141516171819202122232425262728293031323334353637383940414243 public class Baekjoon1158 { static StringTokenizer st; public static void main(String[] args) throw..
-
[java] 백준 알고리즘 11866번 조세퍼스 문제 0 풀이알고리즘/백준 알고리즘 2018. 7. 27. 13:45
List의 원리를 잘 이해하면 풀 수 있는 문제다. LinkedList는 index에 대해 자유로운 편이기 때문에 index 중간에 삽입하고 삭제하기가 쉽다. arrayList는 index 기반이라 list 중간 index가 빠지면 다른 index의 데이터까지 복사해야하는 불상사가 생긴다. 그에 비하면 LinkedList는 index가 아닌 노드와 다음 노드 값만 연결하고 있어서 list 내의 값에 대한 복사가 없다. LinkedList로 넣은 값에 순서에 맞는 index만 계속해서 삭제해주면 된다. ** arrayList를 사용하면 안되는 건 아니다. index 기준이므로 상관없지만, 개념적으로 값의 삽입과 삭제가 빠른 건 LinkedList로 배웠기 때문이다. 원하는 삭제 index보다 배열의 크기가..
-
[java] 백준 알고리즘 10845번 큐 풀이알고리즘/백준 알고리즘 2018. 7. 25. 14:37
큐의 개념을 공부하기 위한 문제이다. 큐는 스택과 반대되는 개념으로 FIFO(First In, First Out)이다. 먼저 들어간 녀석이 먼저 나오는 것이다. 예를 들어 급식을 받는다고 일렬로 줄을 서있으면 먼저 배식을 받는 사람이 먼저 배식 줄을 나오는 것과 같은 원리! 아래는 이해를 돕기위한 발 그림... 자바에서 라이브러리를 통해 큐를 사용할 수 있지만, 배열을 통해 직접 한 번 만들어보고 싶었다. 일반 배열을 큐처럼 만들기 위해 사이즈(dynamicSize)와 0번째 순서(bottom)를 동적으로 만들었다. 큐에서 pop이 되면 0번째 순서의 다음 순서로 +1로 올라가게 만들고, 사이즈는 -1로 줄어들게 했다. 반대로 push를 하면 사이즈는 +1로 만들었다. 제약조건 중 정수가 들지 않았을 경..
-
[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[..