본문 바로가기

전체 글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.
스택(2)-동적 배열 스택 - 이전까지는 컴파일 시 크기가 결정되는 정적 할당 사용- 필요한 스택의 크기를 미리 알아야 함 → 곤란- C언어에서는 malloc()을 호출하여 실행 시간에 메모리를 할당받을 수 있음- 필요할 때마다 스택 크기를 늘릴 수 있음typedef int element;typedef struct{ element* data; int capacity; //현재 크기 int top;}StackType;- 동적 메모리 할당을 이용하는 스택 코드//스택 생성 함수void init_stack(StackType* s) { s->top = -1; s->capacity = 1; s->data = (element*)malloc(s->capacity * sizeof(element));}//스택 삭제 함수void dele.. 2024. 7. 8.
스택(1) 스택- 후입선출(LIFO: Last In First Out)의 입출력 구조- 스택에서의 입출력은 맨 위에서만 일어나고 스택의 중간에서는 데이터를 삭제할 수 없음- 자료의 출력 순서가 입력 순서의 역순으로 이루어져야 할 때 사용(ex: undo 기능)스택 상단(stack top): 입출력이 이루어지는 부분스택 하단(stack bottom): 반대쪽인 바닥 부분요소(element): 스택에 저장되는 값공백 스택(empty stack): 요소가 하나도 없는 스택추상 자료형 스택- push 연산: 스택에 요소 삽입- pop 연산: 스택에서 요소 삭제 - is_empty 연산: 스택이 공백 상태에 있는지 검사- is_full 연산: 스택이 포화 상태에 있는지 검사- create 연산: 스택 생성- peek 연산:.. 2024. 7. 8.
백준 2798: 블랙잭(java/C) 문제 풀이3중 for문을 사용하여(카드 3장을 고르므로 3중, n장 뽑으려면 n중첩) N개의 카드에서 가능한 모든 경우의 수를 탐색하면 된다. 전체 탐색을 하려니 N이 커질수록 너무 비효율적일 것 같았지만... 고민해 봐도 다른 방법은 잘 모르겠다ㅜ 1. 전체 경우의 수를 탐색하고2. 이들 중 합이 M에 가장 가까운 것을 출력 하는 간단한 알고리즘이다. [JAVA]import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { public static void main(String[] args) throws IOEx.. 2024. 7. 6.
백준 30802: 웰컴 키트(java/C) 문제참가자: NS, M, L, XL, XXL, XXXL: 사이즈 별 신청자 수(한 명이 한 사이즈만 주문 가능)T: 셔츠 한 묶음에 몇 벌 들어가는지P: 펜 한 묶음에 몇 자루 들어가는지설명이 개인적으로 뭔가? 이해가 안 돼서 다시 적었다.티셔츠와 펜의 묶음 수 T와 P라고 하면 보통 n개짜리 T묶음, m개짜리 P묶음이라고 생각했는데내가 멍청한 걸지도... 풀이 한 묶음에 T벌씩 총 셔츠 n벌을 구매하려면1. n÷T묶음을 구매하고2. n÷T의 나머지에 대해서도 한 묶음을 더 구매해야 한다(한 묶음에 10벌씩 31벌을 구매한다 치면 총 4묶음을 구매하고 마지막 한 묶음에서 한 벌을 꺼내서 따로 줘야 하니까)int shirt = 0; //셔츠 묶음 개수for (int i = 0; i  펜은 인원수랑 똑같이 .. 2024. 7. 6.

티스토리툴바