매일 조금씩

문제 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 ..

문제 https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 풀이 아래와 같이 짜면 시간/메모리 초과가 발생한다. public static long recur(long a, long b, long c){ if(a==1 || b==1) return a; return a * recur(a, b-1, c) % c; } recur(a*a, b/2, c)로 호출하여 함수 호출 횟수를 줄이는게 핵심이다. overflow가 발생하지 않도록 여러 곳에 c로 mod연산을 해야한다. b가 1인 조건일 때 mod연산을 누락해서 한참 헤..

문제 https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 풀이 아래 문제와 달리 해당 문제는 분할을 9개로 한다. (내부에서 좌표를 갱신하여 재귀함수를 9번 호출) 이 외에 풀이는 아래 문제와 유사하다. 2021.11.16 - [Problem Solving/BOJ] - [BOJ 2630] 색종이 만들기 (Java) [BOJ 2630] 색종이 만들기 (Java) 문제 https://www.acmicpc.net/problem/2630 263..

문제 https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 풀이 분할정복으로 푼다. 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 사분면 순으로 재귀함수를 호출하면서 모든 숫자가 1이면 1 출력, 0이면 0 출력. 이외의 케이스는 좌표와 크기를 갱신하여 다시 재귀를 돌려주면 된다. 2021.11.16 - [Problem Solving/BOJ] - [BOJ 2630] 색종이 만들기 (Java) [BOJ 2630] 색종이 만들기 (Java..

문제 https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 풀이 분할 정복 문제, 재귀용법을 이용하여 푼다. 소스코드 package dp; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class BOJ2630 { public static int oneCnt, zeroCnt; pub..

문제 https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 풀이 Deque 문제로 R명령어가 들어왔을 때 값이 들어가는 입구를 바꿔주면 된다. (First, Last) First를 입구로 사용한다면 나중에 값을 뽑을 땐 Last로 뽑아야 생각한 순서대로 값이 출력된다. (반대도 마찬가지) 이 부분이 처음에 헷갈려서 LinkedList 메소드를 테스트하면서 정리해보았다. 2021.11.15 - [Java] - [Java] Deque 자료 구조 (LinkedList 메소드) [Java] Deque 자료 구조 ..

문제 https://www.acmicpc.net/problem/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net 풀이 어렵지 않은 문제이다. deque를 이용해서 풀면 된다. 중간 값을 찾아서 현재 수가 왼쪽에 있는지 오른쪽에 있는지 판단하는 부분에서 많이 헷갈렸다. index 경계값 처리 하는게 머릿속으로 바로바로 안된다. 소스코드는 아래와 같다. 소스코드 package queue; import java.io.BufferedReader; import java.io.InputStreamReader;..

문제 https://www.acmicpc.net/problem/18258 18258번: 큐 2 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 풀이 Deque 구현체로 풀었다. 소스코드 package queue; import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.ArrayDeque; import ..

문제 https://www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 입력의 종료조건으로 맨 마 www.acmicpc.net So when I die (the [first] I will see in (heaven) is a score list). [ first in ] ( first out ). Half Moon tonight (At least it is better than no Moon at all]. A rope may form )( a trail in a maze. Help( I[m being..

문제 https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 풀이 Stack의 대표문제 '(' 는 Stack에 넣고, ')' 가 나오면 Stack top이 '(' 일 경우 top을 pop한다. 모든 순회가 끝난 후 Stack이 비어있다면 올바른 괄호이다. 아래 문제와 유사하다. 2021.10.18 - [Problem Solving/Programmers] - [프로그래머스] 올바른 괄호 (Java) [프로그래머스] 올바른 ..