동동매니저의 생활

★ solved.ac 난이도 : S4 (2021년 12월 29일 기준) [문제 링크] 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net [문제 분석] 스택을 활용한 괄호 검사 문제 [풀이] 이 문제는, 괄호의 모양이 올바른지를 검사하는 문제입니다. 자료구조를 예습하면서 접하게 된 문제인데요, 여기에서 LIFO(후입 선출)의 스택을 사용했습니다. 그 이유는, 가장 가까운 거리에 있는 괄호끼리 서로 쌍을 이루어야 하기 때문입니다. 괄호 검사의 조건을 알려드리자면, 조건 1. 여는 괄호..

★ solved.ac 난이도 : G5 (2021년 12월 29일 기준) [문제 링크] 1405번: 미친 로봇 첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고, 모든 확률은 100보다 작거나 같은 자 www.acmicpc.net [문제 분석] DFS와 가지 치기를 활용한 문제 (탑코더 빨간 책에도 있는 문제!!) [풀이] 이 문제는, 탑코더 빨간 책에도 나와있는 문제입니다. (심지어 입력 값의 범위도 같다는 점...) 여기에서는, DFS 탐색 도중 이미 움직인 지점으로 가는 경우에 가지 치기를 사용했습니다. (가지 치기는, 불필요한 탐색을 줄이는 방법입니다.) DFS는 재귀 함수로 구현하였고, 탐색..

★ solved.ac 난이도 : S3 (2021년 12월 29일 기준) [문제 링크] 1004번: 어린 왕자 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 첫째 줄에 출발점 (x1, y1)과 도착점 (x2, y2)이 주어진다. 두 번째 줄에는 행성계의 개수 n이 주 www.acmicpc.net [문제 분석] 원의 성질을 이용한 최적 경로(?) 문제 [풀이] 두 점과 여러 개의 원의 정보가 주어질 때, 교차하는 원의 개수가 가장 적게 되도록 두 점을 잇는 문제라고 생각하시면 됩니다. (문제에서는 원이 맞닿거나 서로 교차하는 경우는 없고, 시작 및 끝점이 원에 맞닿는 경우는 없습니다.) 먼저, 두 점을 입력 받고, 원의 정보(x 좌표, y 좌표, 반지름)를..

★ solved.ac 난이도 : S3 (2021년 12월 29일 기준) [문제 링크] 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net [문제 분석] 스택의 push 연산과 pop 연산을 응용한 깊이 있는(?) 문제 [풀이] 이 문제는, 스택의 push 연산과 pop 연산을 활용한 심화 문제라고 볼 수 있습니다. 1부터 n까지의 수들이 오름차 순으로 push가 된다고 합니다. push 연산을 이어가면서, 수열의 데이터와 비교하고,..

★ solved.ac 난이도 : S4 (2021년 12월 29일 기준) [문제 링크] 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net [문제 분석] Map 자료구조를 활용한 문제 [풀이] 이 문제는 Java에서 기본적으로 제공하는 자료구조 중 하나인 HashMap을 이용했습니다. Map은 키와 값이 쌍으로 이루어진 자료구조인데요, 이를 배열처럼 활용할 수도 있습니다. 이 문제에서는 키의 형식을 'String', 값의 형식을 'Integer'로 두었습니다. (키, 값)의 쌍을 put..