본문 바로가기

Problem Solving1213

[백준] 10845 큐 - Data Structure / Java • 문제 링크 10845번: 큐 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net • 풀이 과정 Queue(FIFO) 자료구조에 관련된 기본적인 동작들을 구현하는 문제. 이전에 풀이한 10828 문제와 전체적인 구현 방식은 동일하다. 추가로 큐의 가장 뒤에 있는 정수를 출력하는 back 명령어를 구현 시 큐의 가장 뒤에 있는 정수는 가장 마지막에 offer, 또는 add 한 값으로, 이를 back 변수에 갱신해주고 back 명령이 주어질 때 그대로 back 변수에 저장된 값을 출력한다. • 풀이 코드 import .. 2022. 6. 12.
[백준] 10828 스택 - Data Structure / Java • 문제 링크 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net • 풀이 과정 Stack(LIFO) 자료구조에 관련된 기본적인 동작들을 구현하는 문제. 입력받은 명령어를 sprit 함수로 comm 배열의 0번째 인덱스에 저장시키고 push 할 값은 1번째 인덱스로써 스택에 삽입하며, 각각의 입력받은 명령어를 스택 자료구조의 명령어에 대입시켜 구현하여 정답을 출력한다. • 풀이 코드 import java.io.BufferedReader; import java.io.BufferedWriter; im.. 2022. 6. 12.
[백준] 1697 숨바꼭질 - Graph Theory / Java • 문제 링크 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net • 풀이 과정 너비 우선 탐색을 수행할 함수를 정의, 현재 위치(n) 와 도착 위치(k) 를 매개변수로 받고 큐에 현재 위치를 저장한다. 그리고 방문 여부를 확인할 chk 배열을 문제에 제시된 조건에 의해 100,001의 크기로 생성, 현재 위치를 1로 표시한다. 현재 위치는 loc 변수에, 다음으로 이동할 위치를 move 변수에 설정하며 3가지 이동 방법 (n + 1, n - 1, n * 2) 으로 이동한 모든 경우를 .. 2022. 6. 11.
[백준] 16953 A → B - Graph Theory / Java • 문제 링크 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net • 풀이 과정 • 풀이 코드 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class Main { public static void main(String[] args) thr.. 2022. 6. 10.
[백준] 1541 잃어버린 괄호 - Greedy / Java • 문제 링크 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net • 풀이 과정 덧셈과 뺄셈이 혼재되어 있는 식에서 문제에 제시되어 있는 조건 상 최소 값을 구해내기 위해선 덧셈으로 이루어진 식을 괄호를 쳐서 먼저 계산한 후 뺄셈을 계산해야한다. 우선 전체식을 "-" 를 기준으로 분리하고 각각의 분리된 식에 포함된 수를 모두 더하는데 분리된 식을 문자열 파싱할 때 "+" 는 메타문자이므로 "\\+" 을 기준으로 파싱하며, 이때 생성된 모든 수를 더한 값을 result 변수에 뺄셈한다. 이때 result 변수.. 2022. 6. 9.
[백준] 13305 주유소 - Greedy / Java • 문제 링크 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net • 풀이 과정 우선 맨 처음 주유소는 다음 주유소로 이동하기 위해 필연적으로 이용해야 하며 마지막 주유소는 도착 지점이므로 계산에 포함되지 않는다. 각 주유소에 도달했을 때 해당 주유소의 가격이 다음 주유소의 가격보다 저렴하다면 다음 주유소에서 주유할 분량을 미리 주유하여 비용을 최소화하며 이는 현재 상황에서 최선의 수를 선택하는 그리디 알고리즘의 기본 원리에 부합한다. 첫번째 입력에서 이와 같은 규칙을 적용 시 5 2 4 1 -> 5.. 2022. 6. 8.

티스토리툴바