Algorithm

Stack (스택)

Stack (스택) Stack 이란 ? - LIFO (Last In First Out) 방식의 자료구조이다. 나중에 들어온것이 먼저 나가는 형태이다. 대표적으로 우리가 흔히 사용하는 인터넷 브라우저의 뒤로가기 기능이 비슷하다. 뒤로 가기 하면 할 수록 우리가 직전에 봤던 페이지를 볼 수 있다. 또한, 프링글스 통을 생각하면 아주 똑같다. 기능 - Push : 값을 Stack 으로 넣는 동작 - Pop : Stack에서 값을 하나 꺼내는 동작 - Peek : Stack의 현재 맨위의 값을 확인 - isEmpty : Stack이 비어있는지 확인하는 동작 JAVA 에는 이러한 Stack이 JDK에 구현되어있다. 선언을 Stack으로 하고 구현체 또한 Stack이다. import java.util.Stack; ..

[BOJ] 17298번 : 오큰수 (JAVA/자바)

문제 알고리즘 고민 해당 문제는 n번째 숫자를 n+1 번부터 n번째 숫자 보다 큰 숫자중에 가장 왼쪽에 있는 숫자를 출력하는 문제이다. 처음에는 투포인터 방식으로 right가 큰숫자를 찾고 left를 진행하고 도달하면 right가 큰숫자를 찾고 left를 다시 진행하고 하는 방식을 생각했다. 하지만, 하나 문제가 있었는데 만약 left를 진행하면서 right 숫자를 써주던 중에 left숫자가 left+1 숫자보다 크다면 right가 갱신될 가능성이 있다는 것이다. 예제 입력 중 2번을 통해 확인할 수 있다. 4 9 5 4 8 먼저, 4개의 숫자 9, 5, 4, 8을 입력받게 된다. 이후 left = 0, right = 0 에서 시작하고 left == right 이므로 right를 진행시킨다. 하지만 현재..

[BOJ] 2981번 : 검문 (JAVA/자바)

문제 알고리즘 고민 처음에는 단순하게 모든 숫자를 다 나눠보면서 나머지가 같은 숫자들을 나열하는 방식으로 하려했으나 당연스럽게도 시간초과로 인해 실패했다. 그 이후에 여러가지 방법을 시도하다가 실패하고 https://st-lab.tistory.com/155 사이트의 풀이를 참고하여 풀었다. (정말 잘푸시는거 같다...) 먼저, 수학적인 수식으로 접근을 해서 공통적인걸 뽑아내는 과정을 거쳤다. 특정한 숫자로 나눴을때 모든 숫자가 나머지가 같아야 하는 문제의 조건에 식을 맞춰서 작성한다면 다음과 같이 수식을 만들 수 있다. 최대 공약수를 M 이라고 하고 n번째의 숫자를 N, 나머지를 r 이라고 하였다. $N_1 = M * n_1 + r$ $N_2 = M * n_2 + r$ $N_3 = M * n_3 + r$..

[BOJ] 1541번 : 잃어버린 괄호 (JAVA/자바)

문제 알고리즘 고민 맨 처음에 문제를 잘못 이해해서 괄호를 단 한번 열고 닫을 수 있는줄 알고 DP 방식으로 풀으려고 했다... (문제를 꼼꼼히 읽는 습관을 기르자..) 괄호를 칠 수 있는 개수의 제한이 없다는 것을 확인하고 나서는 문제가 쉽게 풀렸다. 식을 진행하면서 ( - )연산자가 나온다면 그 이후부터는 모든 숫자를 음수로 생각하면 되기에 그렇게 문제를 풀었다. 입력을 받는 방식에서 람다를 이용해서 한번 받아보겠다고 이거저거 시도를 해보았다. 또한, 숫자만 뽑아내거나 연산자만 뽑아내는 방식 이것저것 해보면서 정규식에 대한 내용을 조금 공부했다. JAVA Code import java.io.BufferedReader; import java.io.IOException; import java.io.Inp..