1. 문제 25416번: 빠른 숫자 탐색 5 x 5 크기의 보드가 주어진다. 보드는 1 x 1 크기의 정사각형 격자로 이루어져 있다. 보드의 격자에는 -1, 0, 1중 하나의 숫자가 적혀 있다. 격자의 위치는 (r, c)로 표시한다. r은 행 번호, c는 열 번호 www.acmicpc.net 2. 풀이 전형적인 미로 탐색 문제이다. BFS의 개념을 이해하고 있다면 Standard와 같은 문제이므로 큰 어려움 없이 풀이가 가능하다. 네 방위(동, 서, 남, 북)로 움직일 수 있는 학생이 움직일 수 없는 조건에 대해서만 적절하게 체크해주면 풀이가 가능하다. 까다로운 조건 없이 좌표계에서 이동만 하는 것이며, `1`이 적힌 어딘가에 있는 지점으로 도달해야하므로 BFS가 가장 적합한 수단이라고 볼 수 있다. 학..

1. 문제: https://www.acmicpc.net/problem/2842 2842번: 집배원 한상덕 문제 상덕이는 언덕 위에 있는 마을의 우체국에 직업을 얻었다. 마을은 N×N 행렬로 나타낼 수 있다. 행렬로 나뉘어진 각 지역은 우체국은 'P', 집은 'K', 목초지는 '.' 중 하나로 나타낼 수 있다. 또, www.acmicpc.net 2. 풀이 문제의 핵심 조건은 아래와 같다. 1) 상하좌우 뿐만 아니라 대각선으로도 움직일 수 있다. 2) 방문하는 장소들 중 고도의 최고점과 최저점의 차이를 '피로도'라고 하며 이를 최소화 해야한다. 대각선을 추가하는 것이야 방향을 설정해주는 dy, dx 배열만 추가로 설정해주면 되는데 피로도를 최소화하기 위해서는 어떤 방법을 써야할 것 인가? 지도에서 주어진 모..

1. 문제: https://www.acmicpc.net/problem/2504 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 www.acmicpc.net 2. 풀이 Stack을 응용한 대표적인 문제를 꼽으라면 단연 괄호와 관련된 문제라고 할 수 있다. 괄호의 쌍이 올바르게 되어 있는가를 판단할 때 스택의 특성을 가장 적극적으로 활용할 수 있는데, 여는 괄호는 스택에 넣고 닫는 괄호는 스택에서 pop을 해 쌍을 확인함으로써 풀이할 수 있다. 문제 해석에 앞서 잠시 올바른 괄호의 쌍인가를 확인하는 코드를 정리하고 간다. // '()' 소..

1. 문제: https://www.acmicpc.net/problem/9328 9328번: 열쇠 문제 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열 www.acmicpc.net 2. 풀이 지도 상에서 돌아다니면서 문을 만났을 때 열쇠가 있다면 열고 들어가고 없으면 열지 못하는 본 문제와 비슷한 유형의 문제를 백준에서 풀었던 기억이 있다. 그 문제가 뭐였는지 기억한다면 첨부하도록 하겠다.... 아무튼 문제의 상근이가 문서를 훔치기 위해서 빌딩 내부를 돌아다녀야 하는데 문제의 중요한 몇 가지만 인지하고 있다면 크게 어려울 것은 없다. 1) 상근이의 출발점이 정해지지 않았으..

1. 문제: https://www.acmicpc.net/problem/6426 6426번: Psuedo-Random Numbers Each input line will contain four integer values, in order, for Z, I, M, and L. The last line will contain four zeroes, and marks the end of the input data. L will be less than M. www.acmicpc.net 2. 풀이 문제를 간단하게 해석하면 다음과 같다. 컴퓨터는 실제로 난수를 발생시킬 수 없지만, 유사난수 생성기(pseudo-random numbers generator)를 통해 난수를 만들어내는 것 처럼 할 수 있다. 널리 알려진 ..

1. 문제: https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 2. 풀이 소수를 판별하는 방법에는 다양한 방법들이 존재하고, 이를 최적으로 판별하기 위한 방법에도 여러가지가 있다. 기본적으로 소수를 판별하기 위해서는 소수의 조건에 위배되지 않는지 일일이 확인해 보는 가장 원시적인 방법이 있겠다. //원시시대 방법 boolean isPrime = true; for(int i = 2; i < a; i++) { if(a % i == 0) { isPrime = false; break; } } String ret = isP..

1. 문제: https://www.acmicpc.net/problem/18808 18808번: 스티커 붙이기 혜윤이는 최근에 다양한 대회를 참여하면서 노트북에 붙일 수 있는 스티커들을 많이 받았다. 스티커는 아래와 같이 사각 모눈종이 위에 인쇄되어 있으며, 스티커의 각 칸은 상하좌우로 모두 연결되어 있다. 또한 모눈종이의 크기는 스티커의 크기에 꼭 맞아서, 상하좌우에 스티커가 포함되지 않는 불필요한 행이나 열이 존재하지 않는다. 아래는 올바른 모눈종이의 예시이다. 주황색 칸은 스티커가 붙은 칸을, 하얀색 칸은 스티커가 붙지 않은 칸을 나타낸다. 반면 아래는 올바 www.acmicpc.net 2. 풀이 현재 문제에서 요구하고 있는 것은 노트북의 왼쪽 상단부터 오른쪽 하단으로 진행하며 순차적으로 먼저 주어진..