본문 바로가기

분류 전체보기215

백준 10828: 스택(java) 문제 풀이스택을 구현하면 끝나는 문제다자바에서는 Stack 클래스를 기본적으로 지원하므로 이를 사용해도 될 것 같지만, 이번에는 스택을 직접 구현해 보았다.자바 스택 참고 Stack (Java SE 21 & JDK 21)Type Parameters: E - Type of component elements All Implemented Interfaces: Serializable, Cloneable, Iterable , Collection , List , RandomAccess, SequencedCollection public class Stack extends Vector The Stack class represents a last-in-first-out (LIFO) stdocs.oracle.com 자료구.. 2024. 7. 12.
스택의 응용: 미로 문제 미로의 출구를 찾는 가장 기본적인 방법은 시행착오 방법으로서, 하나의 경로를 선택하여 한 번 시도해 보고 안 되면 다시 다른 경로를 시도하는 것이다. 문제는 현재의 경로가 출구로 이어지지 않을 때 다른 경로를 선택해야 한다는 것으로, 이를 위해 다른 경로들이 어딘가에 저장되어 있어야 한다. 현재 위치에서 가능한 경로 중 가장 가까운 경로를 쉽게 추출해야 하므로, 스택을 사용하는 것이 적합하다.  현재 위치에서 갈 수 있는 방들의 좌표를 스택에 기억하였다가 막다른 길을 만나면 아직 가보지 않은 방들 중 가장 가까운 방으로 돌아가 새로운 경로를 찾아보는 것이다. 또, 한번 지나간 방을 다시 지나가면 안 되므로 각 방들을 지나갈 때마다 방문했다는 사실을 저장해야 한다. 문제 해결을 위하여 하나의 스택을 가정할.. 2024. 7. 12.
스택의 응용: 후위 표기 수식 계산 중위(infix): 연산자가 피연산자 사이에후위(postfix): 연산자가 피연산자 뒤에전위(prefix): 연산자가 피연산자 앞에인간은 주로 중위표기법을 사용하지만 컴파일러는 후위표기법을 사용한다. 프로그래머가 수식을 중위표기법으로 작성하면 컴파일러는 이를 후위표기법으로 변환한 뒤 스택을 사용해 계산한다.중위 표기법전위 표기법후위 표기법2+3*4+2*34234*+a*b+5+*ab5ab*5+(1+2)*7*+12712+7* 중위표기법에서는 먼저 계산할 부분을 나타내기 위해 괄호를 사용해야 하는 데 비해, 후위표기법에서는 괄호가 필요 없다. 또, 이미 식 자체에 우선순위가 표현되어 있어 연산자의 우선순위도 고려할 필요가 없으므로 수식을 읽으면서 바로 계산이 가능하다. 후위 표기 수식을 계산하려면, 수식을 왼.. 2024. 7. 11.
스택의 응용: 괄호 검사 문제 괄호가 올바르게 사용되었는지 스택을 사용하여 검사한다. 괄호의 검사 조건은 아래와 같다.조건 1: 왼쪽 괄호의 개수와 오른쪽 괄호의 개수가 동일조건 2: 같은 종류의 괄호에서 왼쪽 괄호는 오른쪽 괄호보다 먼저 나와야 함조건 3: 서로 다른 종류의 왼쪽 괄호와 오른쪽 괄호 쌍은 서로를 교차할 수 없음{A[(i + 1) = 0]} ->오류 없음if ((i == 0) && (j == 0) ->오류: 조건 1A[(i + 1]) = 0 ->오류: 조건 3 이러한 괄호 사용 오류 검사에 스택을 사용할 수 있다. 가장 가까운 거리에 있는 괄호들끼리 서로 쌍을 이루어야 하므로, 스택을 사용하여 왼쪽 괄호들('(', '{', '[')을 만나면 계속 삽입하다가 오른쪽 괄호들(')', '}', ']')이 나오면 스택에.. 2024. 7. 11.
백준 1676: 팩토리얼 0의 개수(java) 문제 풀이N을 입력받고 N의 팩토리얼을 구한 뒤 각 숫자를 0과 비교하여 0이 아닌 숫자가 나오기 전까지 0의 개수를 세면 되는 비교적 간단한 문제이다. 라고 아무 생각 없이 풀면 저처럼 됩니다import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class Main { private static int getFactorial(int n) { if(n==1) return 1; else return(n*getFactorial(n-1)); } public static void main(String[] args) throws IOException{ BufferedReader in=.. 2024. 7. 9.
백준 11650: 좌표 정렬하기(java) 문제문제를 보자마자 2차원 배열을 생성해 Arrays.sort()를 사용하려 했는데, Arrays.sort()로는 1차원 배열밖에 정렬할 수 없다.(Arrays.sort() 사용하여 오름차순 정렬하기 참고)0; i--){ for(j=0; jintArray[j+1]){ //앞 원소가 뒤 원소보다 크면 앞 원소를 뒤" data-og-host="sysouthelloworld.tistory.com" data-og-source-url="https://sysouthelloworld.tistory.com/15" data-og-url="https://sysouthelloworld.tistory.com/15" data-og-image="https://scrap.kakaocdn.net/dn/bZ9aXW/hyWzvOFh6B.. 2024. 7. 9.